1、算法部分章質量檢測本章知識結構一、知識點剖析1算法的定義和特點掌握要點：算法定義：在數學中指按照一定規則解決某一類問題的明確和有限的步驟。算法特點：有窮性：一個算法的步驟是有限的，它應在有限步操作之后停止。確定性，算法的每一步操作必須是明確的，不能有歧義或模糊且算法執行后一定產生確定的結果，不能模棱兩可。可行性：算法從初始步驟開始，分為若干明確的步驟，每一個步驟只能有一個明確的后繼步驟，前一步是后一步的前提,只有執行完前一步才能進行下一步，并且每一步都要準確無誤才能解決問題。不惟一性：求解某一類問題的算法是不惟一的，對于一個問題可以有不同的算法。普遍性，很多具體的問題都可以設計合理的算法解決。

2、易混易錯：（1）算法一般是機械的，有時要進行大量重復的運算，只要按部就班的做總能算出結果，通常把算法過程稱為“數學機械化”，“數學機械化”的最大優點是它可以讓計算機來完成。（2）實際上，處理任何問題都需要算法。如，郵購物品有其相應的手續。購買飛機票也有一定的手續等。（3）求解某個問題的算法不惟一。2（1）程序框圖表示算法步驟的一些常用的圖形和符號圖形符號名稱功能終端框（起止框）程序的開始和結束，輸入、輸出框表示數據的輸入或結果的輸出處理框賦值,計算判斷框判斷某一條件是否成立，成立時在出口處標明：“是”或“YES”；不成立時在出口處標明“否”或”NO”流程線連接程序框連接點連接程序框圖的兩部分易

3、混易錯：在所給的上述符號之中只有判斷框有一個入口和兩個出口，它是唯一有兩個退出點的符號。（2）三種基本邏輯結構順序結構 條件結構循環結構順序結構：順序結構是最簡單的算法結構，語句與語句之間，框與框之間是按從上到下的順序進行的。這是任何一個算法都離不開的基本結構。條件結構：在一個算法中，經常會遇到一些條件的判斷，算法的流程根據條件是否成立會有不同的流向，條件結構就是處理這種過程的結構。易混易錯：在條件結構中無論條件是否成立，都只能執行兩框之一，兩框不可能同時執行，也不可能兩框都不執行。循環結構：算法結構中經常會遇到從某處開始，按照一定條件反復執行某些步驟的情況，這就是循環結構，反復執行的步驟成為

4、循環體。循環結構分為兩種：當性循環結構和直到性循環結構。當性循環結構：在每次執行循環體前，對條件進行判斷，當條件滿足時，執行循環體，否則終止循環。“先判斷”直到性循環結構：在執行了一次循環體后，對條件進行判斷，如果條件不滿足就繼續執行循環體，直到條件滿足時終止循環。“先循環”注意：循環結構中一定包含著條件結構。3基本算法語句（1）輸入語句輸入語句的一般形式是：INPUT “提示內容”；變量輸入語句的作用是實現算法的輸入信息功能“提示內容”提示用戶輸入什么樣的信息輸入語句可以給變量提供初值提示內容與變量之間用分號隔開，若輸入多個變量，變量之間用逗號隔開。例如：INPUT “提示內容1，提示內容2

5、，提示內容3，”；變量1，變量2，變量（2）輸出語句 輸出語句的一般形式是：PRINT “提示內容”；表達式 輸出語句的作用是實現算法的輸出結果功能。 “提示內容”提示用戶輸入什么樣的信息，如PRINT “S=；S 是提示輸出的結果是S的值PRINT語句可以在屏幕上出現常量、變量以及系統信息。注意：任何求解問題的算法，都要把求解問題的結果輸出。（3）賦值語句賦值語句是最基本的語句賦值語句的一般格式為：變量=表達式“=”叫做賦值號。易混易錯: 賦值號做變只能是變量而不能使表達式。賦值號的左右兩邊不能調換。不能利用賦值語句進行代數式的演算（如化簡、因式分解、解方程等）。賦值號與數學中的符號意義不同

6、。注意:輸入語句、輸出語句、賦值語句基本上對應程序框圖中的順序結構；一個算法有0個或者多個輸入，有一個或多個輸出；輸出語句和賦值語句具有運算功能而輸入語句不具有運算功能。（4）條件語句共分為兩種形式 IF-THEN-ELSE格式滿足條件？語句1語句2是否IF 條件 THEN語句1ELSE語句2END IF(1)當計算機執行上述語句時，首先對IF后的條件進行判斷，如果條件符合，就執行THEN后的語句1，否則執行ELSE后的語句2。其對應的程序框圖為：（如上右圖）滿足條件？語句是否 IF-THEN格式IF 條件 THEN語句END IF計算機執行這種形式的條件語句時，也是首先對IF后的條件進行判斷

7、，如果條件符合，就執行THEN后的語句，如果條件不符合，則直接結束該條件語句，轉而執行其他語句。其對應的程序框圖為：（如上右圖）條件語句的作用：在程序執行過程中，根據判斷是否滿足約定的條件而決定是否需要轉換到何處去。需要計算機按條件進行分析、比較、判斷，并按判斷后的不同情況進行不同的處理。（5）循環語句算法中的循環結構是由循環語句來實現的。對應于程序框圖中的兩種循環結構。一般程序設計語言中也有當型（WHILE型）和直到型（UNTIL型）兩種語句結構。即WHILE語句和UNTIL語句。滿足條件？循環體是否WHILE語句的一般格式是：WHILE 條件循環體WEND其中循環體是由計算機反復執行的一組

8、語句構成的。WHLIE后面的“條件”是用于控制計算機執行循環體或跳出循環體的。當計算機遇到WHILE語句時，先判斷條件的真假，如果條件符合，就執行WHILE與WEND之間的循環體；然后再檢查上述條件，如果條件仍符合，再次執行循環體，這個過程反復進行，直到某一次條件不符合為止。這時，計算機將不執行循環體，直接跳到WEND語句后，接著執行WEND之后的語句。因此，當型循環有時也稱為“前測試型”循環。其對應的程序結構框圖為：（如上右圖）滿足條件？循環體是否UNTIL語句的一般格式是：DO循環體LOOP UNTIL 條件其對應的程序結構框圖為：（如上右圖）從UNTIL型循環結構分析，計算機執行該語句時

9、，先執行一次循環體，然后進行條件的判斷，如果條件不滿足，繼續返回執行循環體，然后再進行條件的判斷，這個過程反復進行，直到某一次條件滿足時，不再執行循環體，跳到LOOP UNTIL語句后執行其他語句，是先執行循環體后進行條件判斷的循環語句。區別：在WHILE語句中，是當條件滿足時執行循環體，而在UNTIL語句中，是當條件不滿足時執行循環體。4算法案例輾轉相除法算法：第一步：用較大的數m除以較小的數n得到一個商q0和一個余數r0；第二步：若r00，則n為m，n的最大公約數；若r00，則用除數n除以余數r0得到一個商q1和一個余數r1；第三步：若r10，則r1為m，n的最大公約數；若r10，則用除數

10、r0除以余數r1得到一個商q2和一個余數r2；依次計算直至rn0，此時所得到的rn1即為所求的最大公約數。程序框圖程序：INPUT “m=”;mINPUT “n=”;nIF m<n THEN x=mm=nn=xEND IFr=m MOD nWHILE r<>0 r=m MOD nm=nn=rWENDPRINT mEND更相減損術更相減損術求最大公約數的步驟如下：可半者半之，不可半者，副置分母·子之數，以少減多，更相減損，求其等也，以等數約之。翻譯出來為：第一步：任意給出兩個正數；判斷它們是否都是偶數。若是，用2約簡；若不是，執行第二步。第二步：以較大的數減去較小的數

11、，接著把較小的數與所得的差比較，并以大數減小數。繼續這個操作，直到所得的數相等為止，則這個數（等數）就是所求的最大公約數。（1） 輾轉相除法與更相減損術區別聯系都是求最大公約數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。從結果體現形式來看，輾轉相除法體現結果是以相除余數為0則得到，而更相減損術則以減數與差相等而得到(2)秦九韶算法與排序掌握秦九韶算法的原理=anvk=vk-1+an-k (k=1,2,3,n)(3)進位制進位制是一種記數方式，用有限的數字在不同的位置表示不同的數值。可使用數字符

12、號的個數稱為基數，基數為n，即可稱n進位制，簡稱n進制。現在最常用的是十進制，通常使用10個阿拉伯數字0-9進行記數。易混易錯：表示各種進位制數一般在數字右下腳加注來表示, 如111001(2)表示二進制數,34(5)表示5進制數.二、典型例題剖析1判斷某一事情是否為算法方法歸納：（1） 判斷某一問題是否為算法要把握算法的五個特征：有窮性確定性可行性不惟一性普遍性例1下列關于算法的說法中正確的個數有( )求解某一類問題的算法是唯一的 算法必須在有限步操作之后停止算法的每一步操作必須是明確的，不能有歧義或模糊算法執行后一定產生確定的結果A. 1 B. 2 C. 3 D. 4主要過程：由算法的五個

13、特征可以解得只有是錯誤的，解答某一類問題的算法時不惟一的。強調內容：把握好算法的五個特征。2就某一問題畫出程序框圖并寫出算法方法歸納：（1）畫程序框圖時一定要明確圖中各個符號的作用并能正確使用三種基本邏輯結構。（2）用程序設計語言描述算法時一定要注意有些符號與框圖之中書寫的不同。例2設計算法求的值.要求畫出程序框圖，寫出用基本語句編寫的程序.主要過程： i=1 s=0 DO s=s+1/(i*(i+1) i=i+1 LOOP UNTIL i>99 PRINT s END 開始i=1s=0s=s+1/(i*(i+1)i=i+1i>99?？輸出s結束強調內容：解答此題目是一定要注意循環

14、終止的條件是i>99而不是i>100,因為這個數列共有99項3討論法畫程序框圖寫程序方法歸納：先通過解決數學題的思想進行討論，再畫圖寫程序。例3、畫出解關于x的不等式ax+b<0 (a，bR)的流程圖及程序。INPUT a,bIF a= 0 THEN IF b0 THEN PRINT 無解 ELSE PRINT x為全體實數ELSE IF a0 THEN PRINT ELSE PRINT END IFEND 主要過程：如上強調內容：注意討論時要全面，不但要討論a還要討論b.4實際應用：方法歸納：先通過解決數學題的思想進行討論，再畫圖寫程序例4、某城市現有人口總數為100萬人，

15、如果年自然增長率為1.2%，試解答下列問題：（1）寫出該城市人口數y（萬人）與年份x（年）的函數關系式；（2）用程序表示計算10年以后該城市人口總數的算法；（3）用流程圖表示計算大約多少年以后該城市人口將達到120萬人的算法。開始結束S=100I=1.2X=0S=S*IX= X +1S<120?輸出XNY主要過程：（1） （2)程序如下： S=100I=1.2X=0WHILE S<120 S=S*IX=X+1WEND PRINT XEND 5 求高次多項式的值 方法歸納：能夠熟練利用秦九韶算法原理求高次多項式的值v=av=v+a (k=1,2,3,n)用秦九韶算法計算主要過程：a

16、=5, a=4,a=3,a=2,a =1,a =1 v= a=5 v= v*2+ a=5*2+4=14 v= v*2+ a=14*2+3=31 v= v*2+ a=31*2+2=64 v= v*2+ a=64*2+1=129 v= v*2+ a=129*2+1=259 所以 f(2)=259強調內容：注意在運算過程之中v=v+a (k=1,2,3,n)的正確應用三、高考鏈接（2008廣東 ）1閱讀右上的程序框圖。若輸入m = 4，n = 3，則輸出a = _12_，i =_3_ 。（注：框圖中的賦值符號“=”也可以寫成“”或“：=”）開始輸入結束輸出否是（2007山東）2閱讀如上右邊的程序框圖

17、，若輸入的是100，則輸出的變量和的 （ D ）A2500，2500B2550，2550 C2500，2550D2550，2500鞏固練習輸入a,b,ca>ba>ca=b輸出aa=cYYNN第1題1、給出一個算法的流程圖（如圖），若，則輸出結果為 （ ）A、sin B、 C、tan D、不確定2x=5y=6PRINT  x+y=11END上面程序運行時輸出的結果是( )A.xy=11        B.11        C.x+y=

18、11      D.出錯信息3.如果下邊程序執行后輸出的結果是990，那么在程序中UNTIL后面的“條件”應為( )i=11s=1DO s=s*i i=i1LOOP UNTIL “條件”（第3題圖）PRINT SEND （第10題） A. i>10 B. i<8 C. i<=9 D. i<9 程序：S=1I=1WHILE I<=10 S=3*SI=I+1WENDPRINT SEND （第4題）4.如右圖所示的程序是用來( )A計算3×10的值 B計算的值C計算的值 D計算1×2×3&#

19、215;×10的值5.計算機中常用十六進制，采用數字09和字母AF共16個計數符號與十進制得對應關系如下表：16進制0123456789ABCDEF10進制0123456789101112131415 例如用十六進制表示有D+E1B，則A×B=( )A 6E B 7C C 5F D B0二、填空題6. 若六進數化為十進數為，則= 7. 二進制數轉換成十進制數是_.8. 右邊程序輸出的n的值是_.j=1 n=0WHILE j<=11 j=j+1 IF j MOD 4=0 THEN n=n+1 END IF j=j+1WENDPRINT nEND 9下圖給出的是計算的值的

20、一個程序框圖，其中判斷框內應填入的條件是 .第9題10計算時多項式的值，需要 次加法運算，（ ） 次乘法運算,此多項式寫成算法INPUT“m=”;mINPUT“n=”;nDO r=m MOD n m=n n=rLOOP UNTIL r=0PRINT mEND第11題圖語句為（ ）。三解答題。11.執行右圖中程序，回答下面問題。（1）若輸入：m=888,n=1147，則輸出的結果為：_（2）畫出該程序的程序框圖。12已知請設計程序框圖，要求從鍵盤輸入x，輸出y。并寫出計算機程序。13 已知S=12223242(n1)2n2，請設計程序框圖，算法要求從鍵盤輸入n，輸出S。并寫出計算機程序。14.

21、按如圖所示的流程圖操作開始寫下1對前一個數加2寫下結果你已寫下了10個數嗎？NY結束AB（）操作結果得到的數集是什么？如果把依次產生的數看成是數列的項，試寫出其通項公式 （）如何變更A框，能使操作流程圖產生的數分別是數列的前10項？15.到銀行辦理個人異地匯款（不超過100萬元）時， 銀行要收取一定的手續費。匯款額不超過100元，收取1元手續費；超過100元但不超過5000元，按匯款額的1%收取；超過5000元，一律收取50元手續費。設計算法求匯款額為x元時，銀行收取的手續費y元。畫出流程圖并寫出程序。16求成立的的最大整數值，畫出程序框圖，并寫程序17.某城市現有人口總數為100萬人，如果年自然增長率為1.2%，試解答下列問題： （1）寫出該城市人口數y（萬人）與年份x（年）的函數關系式 （2）用程序表示計算10年以后該城市人口總數的算法； （3）用流程圖表示計算大約多少年以后該城市人口將達到120萬人的算法。參考答