高中數(shù)學(xué)必修三算法初步復(fù)習(xí)要點2

1、算法的概念1、算法的概念：在數(shù)學(xué)中，算法通常是指按照一定規(guī)則解決某一類問題的明確和有限的步驟。2. 算法的特點(1)有限性：一個算法的步驟應(yīng)是有限的，必須在有限操作之后停止，不能是無限的。(2)確定性：算法中的每一步應(yīng)該是確定的并且能有效地執(zhí)行且得到確定的結(jié)果，而不應(yīng)當(dāng)模棱兩可。(3)順序性與正確性：算法從初始步驟開始，分為若干明確的步驟，每一個步驟只能有一個確定的后繼步驟，前一步是后一步的前提，只有執(zhí)行完前一步才能進行下一步，并且每一步都準(zhǔn)確無誤，才能完成問題。(4)不唯一性：求解某一個問題的解法不一定是唯一的，對于一個問題可以有不同的算法.(5)普遍性：很多具體的問題，都可以設(shè)計合理的算法

2、去解決.1.1.1 程序框圖1、程序框圖的基本概念：（一）程序框圖的概念：程序框圖又稱流程圖，是一種用規(guī)定的圖形、流程線及文字說明來準(zhǔn)確、直觀地表示算法的圖形.一個程序框圖包括以下幾部分：表示相應(yīng)操作的程序框；帶箭頭的流程線；程序框外必要文字說明.（二）構(gòu)成程序框的圖形符號及其作用圖形符號名 稱功 能終端框（起止框）表示一個算法的起始和結(jié)束，是任何流程圖不可少的。輸入、輸出框表示一個算法輸入和輸出的信息，可用在算法中任何需要輸入、輸出的位置。處理框（執(zhí)行框）賦值、計算，算法中處理數(shù)據(jù)需要的算式、公式等分別寫在不同的用以處理數(shù)據(jù)的處理框內(nèi)。判斷框判斷某一條件是否成立，成立時在出口處標(biāo)明“是”或“

3、Y”；不成立時標(biāo)明“否”或“N”。流程線連接程序框連接點連接程序框圖的兩部分（三）學(xué)習(xí)這部分知識的時候，要掌握各個圖形的形狀、作用及使用規(guī)則，畫程序框圖的規(guī)則如下：（1）使用標(biāo)準(zhǔn)的圖形符號。（2）框圖一般按從上到下、從左到右的方向畫。（3）除判斷框外，大多數(shù)流程圖符號只有一個進入點和一個出口點。（4）判斷框是具有超過一個出口點的唯一圖形。（5）在圖形符號內(nèi)描述的語言要非常簡練清楚。（四）、算法的三種基本邏輯結(jié)構(gòu)：順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。（1）、順序結(jié)構(gòu)：順序結(jié)構(gòu)是最簡單的算法結(jié)構(gòu)，語句與語句之間，框與框之間是按從上到下的順序進行的，它是由若干個依次執(zhí)行的處理步驟組成的，它是任何一個算法都

4、離不開的一種基本算法結(jié)構(gòu)，如右圖。（2）、條件結(jié)構(gòu)：條件結(jié)構(gòu)是指在算法中通過對條件的判斷，根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu)。在學(xué)習(xí)時要掌握兩種不同的條件結(jié)構(gòu)。第一種是先判斷條件，條件滿足時執(zhí)行步驟A，條件不滿足時直接跳過，框圖和對應(yīng)的程序語句如右圖。另一種是先判斷條件，條件滿足時執(zhí)行步驟A，條件不滿足時執(zhí)行步驟B，框圖和對應(yīng)的程序語句如圖（3）、循環(huán)結(jié)構(gòu)：在一些算法中，經(jīng)常會出現(xiàn)從某處開始，按照一定條件，反復(fù)執(zhí)行某一處理步驟的情況，這就是循環(huán)結(jié)構(gòu)，反復(fù)執(zhí)行的處理步驟為循環(huán)體，顯然，循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)。循環(huán)結(jié)構(gòu)又稱重復(fù)結(jié)構(gòu)，循環(huán)結(jié)構(gòu)可細(xì)分為兩類：一類是當(dāng)型循環(huán)結(jié)構(gòu)，這類結(jié)構(gòu)首先是

5、去判斷條件，根據(jù)條件再決定執(zhí)不執(zhí)行循環(huán)體。當(dāng)條件滿足時進行循環(huán)，執(zhí)行循環(huán)體，然后再回到條件判斷處，繼續(xù)判斷條件；當(dāng)條件不滿足時跳出循環(huán)。對應(yīng)的框圖結(jié)構(gòu)和循環(huán)語句如圖。另一類是直到型循環(huán)結(jié)構(gòu)，它的功能是先執(zhí)行循環(huán)，然后判斷給定的條件是否成立，如果仍然不成立，則繼續(xù)執(zhí)行循環(huán)，直到某一次給定的條件成立為止，此時不再執(zhí)行循環(huán)，離開循環(huán)結(jié)構(gòu)，對應(yīng)的框圖結(jié)構(gòu)和循環(huán)語句如圖。注意：循環(huán)結(jié)構(gòu)要在某個條件下終止循環(huán)，這就需要條件結(jié)構(gòu)來判斷。因此，循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)，但不允許“死循環(huán)”。1.2.1 輸入、輸出語句和賦值語句1、輸入語句（1）輸入語句的一般格式： INPUT“提示內(nèi)容”；變量（2）輸入語句的

6、作用是實現(xiàn)算法的輸入信息功能；（3）“提示內(nèi)容”提示用戶輸入什么樣的信息，變量是指程序在運行時其值是可以變化的量；（4）輸入語句要求輸入的值只能是具體的常數(shù)，不能是函數(shù)、變量或表達(dá)式；（5）提示內(nèi)容與變量之間用分號“；”隔開，若輸入多個變量，變量與變量之間用逗號“，”隔開。2、輸出語句（1）輸出語句的一般格式：PRINT“提示內(nèi)容”；表達(dá)式（2）輸出語句的作用是實現(xiàn)算法的輸出結(jié)果功能；（3）“提示內(nèi)容”提示用戶輸出什么樣的信息，可以省略，“表達(dá)式”是指程序要輸出的數(shù)據(jù)；（4）輸出語句可以輸出常量、變量或表達(dá)式的值以及字符。3、賦值語句（1）賦值語句的一般格式：變量表達(dá)式（2）賦值語句的作用是將

7、表達(dá)式所代表的值賦給變量；（3）賦值語句中的“”稱作賦值號，與數(shù)學(xué)中的等號的意義是不同的。它將賦值號右邊的表達(dá)式的值賦給賦值號左邊的變量；（4）賦值語句左邊只能是變量名字，而不是表達(dá)式，右邊表達(dá)式可以是一個數(shù)據(jù)、常量或算式；（5）對于一個變量可以多次賦值。注意：賦值號左邊只能是變量名字，而不能是表達(dá)式。如：2=X是錯誤的。賦值號左右不能對換。如“A=B”“B=A”的含義運行結(jié)果是不同的。賦值號“=”與數(shù)學(xué)中的等號意義不同。122條件語句1、條件語句的一般格式有兩種：（1）IFTHENELSE語句；（2）IFTHEN語句。2、IFTHENELSE語句。IFTHENELSE語句中，“條件”表示判斷

8、的條件，“語句體A”表示滿足條件時執(zhí)行的操作內(nèi)容；“語句體B”表示不滿足條件時執(zhí)行的操作內(nèi)容；END IF表示條件語句的結(jié)束。計算機在執(zhí)行時，首先對IF后的條件進行判斷，如果條件符合，則執(zhí)行THEN后面的語句體A；若條件不符合，則執(zhí)行ELSE后面的語句體B。3、IFTHEN語句IFTHEN語句的一般格式如圖。計算機在執(zhí)行時，首先對IF后的條件進行判斷，如果條件符合，則執(zhí)行THEN后面的語句體A；若條件不符合，則直接跳過語句體A，執(zhí)行END IF后面的操作內(nèi)容。 123循環(huán)語句循環(huán)結(jié)構(gòu)是由循環(huán)語句來實現(xiàn)的。對應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般程序設(shè)計語言中也有當(dāng)型（WHILEWEND型）和直到型

9、（DOLOOP UNTIL型）兩種語句結(jié)構(gòu)，即WHILE語句和UNTIL語句。1、WHILEWEND語句（1）WHILEWEND語句的一般格式和對應(yīng)的邏輯結(jié)構(gòu)如圖。（2）當(dāng)計算機遇到WHILE語句時，先判斷條件的真假，如果條件符合，就執(zhí)行WHILE與WEND之間的循環(huán)體；然后再檢查上述條件，如果條件仍符合，再次執(zhí)行循環(huán)體，這個過程反復(fù)進行，直到某一次條件不符合為止。這時，計算機將不執(zhí)行循環(huán)體，直接跳到WEND語句后，接著執(zhí)行WEND之后的語句。2、DOLOOP UNTIL語句（1）語句的一般格式和對應(yīng)的邏輯結(jié)構(gòu)如圖。（2）計算機執(zhí)行該語句時，先執(zhí)行一次循環(huán)體，然后進行條件的判斷，如果條件不滿足

10、，繼續(xù)返回執(zhí)行循環(huán)體，然后再進行條件的判斷，這個過程反復(fù)進行，直到某一次條件滿足時，不再執(zhí)行循環(huán)體，跳到LOOP UNTIL語句后執(zhí)行其他語句，是先執(zhí)行循環(huán)體后進行條件判斷的循環(huán)語句。分析：當(dāng)型循環(huán)與直到型循環(huán)的區(qū)別：當(dāng)型循環(huán)先判斷后執(zhí)行，直到型循環(huán)先執(zhí)行后判斷；WHILEWEND語句中，是當(dāng)條件滿足時執(zhí)行循環(huán)體，在DOLOOP UNTIL語句中，是當(dāng)條件不滿足時繼續(xù)執(zhí)行循環(huán)。輾轉(zhuǎn)相除法與更相減損術(shù)1、輾轉(zhuǎn)相除法。也叫歐幾里德算法，用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：（1）：比較兩數(shù)大小，用較大的數(shù)m除以較小的數(shù)n得到一個商S0和一個余數(shù)R0；（2）：若R00，則n為m，n的最大公約數(shù)；若R0

11、0，則用除數(shù)n除以余數(shù)R0得到一個商S1和一個余數(shù)R1；（3）：若R10，則R0為m，n的最大公約數(shù)；若R10，則用除數(shù)R0除以余數(shù)R1得到一個商S2和一個余數(shù)R2 ； 依次計算直至Rn0，此時所得到的Rn-1即為所求的最大公約數(shù)。2、更相減損術(shù), 用更相減損術(shù)求最大公約數(shù)的步驟如下：（1）、比較兩數(shù)大小，以較大的數(shù)減去較小的數(shù)，得到它們的差；（2）、比較減數(shù)與所得的差的大小，若兩數(shù)相等，則差就是所求的兩數(shù)最大公約數(shù)；（3）、如果減數(shù)與差不相等，則繼續(xù)拿減數(shù)與差中的大數(shù)減去小數(shù)，繼續(xù)這個操作，直到所得的差與減數(shù)相等為止，則這個數(shù)（差）就是所求的最大公約數(shù)。3、輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：（1

12、）都是求最大公約數(shù)的方法，計算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少，特別是當(dāng)兩個數(shù)字的大小區(qū)別較大時計算次數(shù)的區(qū)別較明顯。（2）從結(jié)果體現(xiàn)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到秦九韶算法1、秦九韶算法概念：f(x)=anxn+an-1xn-1+.+a1x+a0求值問題f(x)=anxn+an-1xn-1+.+a1x+a0=( anxn-1+an-1xn-2+.+a1)x+a0 =( anxn-2+an-1xn-3+.+a2)x+a1)x+a0 =.=(.( anx+an-1)x+an-2)x+.+a1

13、)x+a0求多項式的值時，首先計算最內(nèi)層括號里一次式的值，即v1=anx+an-1然后由內(nèi)向外逐層計算一次多項式的值，即v2=v1x+an-2 ，v3=v2x+an-3 .vn=vn-1x+a0 ,這樣，把n次多項式的求值問題轉(zhuǎn)化成求n個一次多項式的值的問題。進位制題型1、其他進制數(shù)轉(zhuǎn)化為十進制數(shù)。在做這一種題時，先把其他進制數(shù)表示成不同數(shù)位上的數(shù)字與基數(shù)的冪的乘積之和的形式，然后再按照十進制的運算法則求出結(jié)果即可。不同數(shù)位上的數(shù)字與基數(shù)的冪的乘積中，要從非十進制數(shù)最右邊的數(shù)字?jǐn)?shù)起，若該數(shù)是從右邊數(shù)起的第m個數(shù)字，則它與基數(shù)的冪的乘積中，冪的次數(shù)就是m-1.題型2、十進制數(shù)轉(zhuǎn)化為K進制數(shù)。用“

14、除K取余法”?！俺齥取余法”是將十進制數(shù)除以k，然后將商繼續(xù)除以k，直到商為0，然后將依次所得的余數(shù)倒序排列即可得到答案例如：用“除k取余法”將十進制數(shù)2009轉(zhuǎn)化為八進制數(shù). 余數(shù)解： 2009÷8=2511251÷8=31.331÷8=3.73÷8=03故2009（10）=3731（8）題型3、非十進制數(shù)轉(zhuǎn)化為K進制數(shù)。計算時要分兩步，第一步，先轉(zhuǎn)化為十進制數(shù)。第二步，再把所得的十進制數(shù)用“除K取余法”轉(zhuǎn)化為非十進制數(shù)。課堂練習(xí)題1將兩個數(shù)交換,使,下面語句正確一組是 ( )a=bb=ab=aa=bc=bb=aa=ca=cc=bb=a A. B. C

15、. D. 2計算機執(zhí)行下面的程序段后，輸出的結(jié)果是（ ）PRINT ，A B C D3將化成四進制數(shù)后，它的末位是 4把“五進制”數(shù)轉(zhuǎn)化為 “八進制”數(shù)為 5用“輾轉(zhuǎn)相除法”求得和的最大公約數(shù)是 n=5s=0WHILE s<15 s=s + n n=n1WENDPRINT nEND(第9題)6下列各數(shù) 、 、 、 中最小的數(shù)是 7用輾轉(zhuǎn)相除法或者更相減損術(shù)求三個數(shù)的最大公約數(shù).8.下列給出的賦值語句中正確的是（ ）A B C D9右邊程序執(zhí)行后輸出的結(jié)果是（ ）A. B C D10. 下左程序運行后輸出的結(jié)果為 IF THEN ELSE END IFPRINT xy ；yxEND 第10

16、題11.已知函數(shù) ,畫出一個求函數(shù)值的程序框圖12.下邊程序執(zhí)行后輸出的結(jié)果是 13.如果下邊程序執(zhí)行后輸出的結(jié)果是132,那么在程序UNTIL后面的“條件”應(yīng)為 IFTHENELSEPRINT y第14題 “條件” A. B. C. D.14.當(dāng)時，下面的程序段輸出的結(jié)果是（ ）A B C Di=1s=0WHILE i<=4s=s*x+1i=i+1WENDPRINT sEND（16題）15. 右圖給出的是計算的值的一個流程圖，其中判斷i=1WHILE i<8 i=i+2 s=2*i+3 i=i-3WENDPRINT s, iEND （18題）框內(nèi)應(yīng)填入的條件是 16.當(dāng)時，下面的

17、程序段結(jié)果是 ( )A. B. C. D. 17、若六進數(shù)化為十進數(shù)為，則= 18、以下程序運行后輸出的結(jié)果為（ ）A、 17，8 B、 21，7C、 21，8 D、 19，8 19.以下給出的各數(shù)中不可能是八進制數(shù)的是 ( ) （15題） A.312 B.10110 C.82 D.74571、用“輾轉(zhuǎn)相除法”求得459和357的最大公約數(shù)是A、3 B、9 C、17 D、512、將數(shù)轉(zhuǎn)化為十進制數(shù)為A、524 B、774 C、256 D、2603、執(zhí)行語句A=15,A=-A+5后, A的值為 A、-10 B、20 C、15 D、無意義4、把88化為五進制數(shù)是 A、324(5) B、323(5)

18、 C、233(5) D、332(5) 5、下列圖形中表示處理框的是 A、菱形框 B、平行四邊形框 C、矩形框 D、圓角矩形框6、下列語句不具備計算功能的是 A、輸入語句 B、輸出語句 C、賦值語句 D、以上三種語句都具備7、下列關(guān)于條件語句的敘述，正確的是 A、條件語句中必須有IF、ELSE和END B、條件語句中可以沒有ELSE，但必須有ENDC、條件語句中可以沒有END D、條件語句中可以沒有ELSE，也可以沒有END8、用二分法求方程x32=0的近似根的算法中要用哪種算法結(jié)構(gòu) A、順序結(jié)構(gòu) B、條件分支結(jié)構(gòu) C、循環(huán)結(jié)構(gòu) D、三種結(jié)構(gòu)都要用到9、給出以下四個問題： 輸入一個數(shù)x，輸出它的相反數(shù)； 求面積為6的正方形周長； 求三個數(shù)a、b、c中的最大數(shù)；求函數(shù)f(x)=的函數(shù)值。其中不需要條件語句來描述其算法的有 A、1個 B、2個 C、3個 D、4個10、算法：第一步： 輸入整數(shù)n；第二步： 判斷n是否為2；第三步：若n為2，則n滿足條件；若n>2，則執(zhí)行第四步；第四步：依次