高中數(shù)學(xué)必修三算法知識點總結(jié)

1、高中數(shù)學(xué)必修3 知識點總結(jié)第一章算法初步1.1.1算法的概念1、算法概念：在數(shù)學(xué)上，現(xiàn)代意義上的“算法”通常是指可以用計算機來解決的某一類問題是程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之內(nèi)完成.2. 算法的特點 :(1)有限性：一個算法的步驟序列是有限的，必須在有限操作之后停止，不能是無限的.(2)確定性：算法中的每一步應(yīng)該是確定的并且能有效地執(zhí)行且得到確定的結(jié)果，而不應(yīng)當(dāng)是模棱兩可.(3)順序性與正確性：算法從初始步驟開始，分為若干明確的步驟，每一個步驟只能有一個確定的后繼步驟，前一步是后一步的前提，只有執(zhí)行完前一步才能進行下一步，并且每一步都準(zhǔn)確無誤，才能完成問題.(

2、4)不唯一性：求解某一個問題的解法不一定是唯一的，對于一個問題可以有不同的算法.(5)普遍性：很多具體的問題，都可以設(shè)計合理的算法去解決，如心算、計算器計算都要經(jīng)過有限、事先設(shè)計好的步驟加以解決 .1.1.2程序框圖1、程序框圖基本概念：（一）程序構(gòu)圖的概念：程序框圖又稱流程圖，是一種用規(guī)定的圖形、指向線及文字說明來準(zhǔn)確、直觀地表示算法的圖形。一個程序框圖包括以下幾部分：表示相應(yīng)操作的程序框；帶箭頭的流程線；程序框外必要文字說明。（二）構(gòu)成程序框的圖形符號及其作用程序框名稱功能表示一個算法的起始和結(jié)束，是任何流程圖不可少的。起止框表示一個算法輸入和輸出的信息，可用在算法中任何需輸入、輸出框要輸

3、入、輸出的位置。賦值、計算，算法中處理數(shù)據(jù)需要的算式、公式等分別處理框?qū)懺诓煌挠靡蕴幚頂?shù)據(jù)的處理框內(nèi)。判斷某一條件是否成立，成立時在出口處標(biāo)明“是”或判斷框“Y”；不成立時標(biāo)明“否”或“N”。名可道教育科技有限公司學(xué)習(xí)這部分知識的時候，要掌握各個圖形的形狀、作用及使用規(guī)則，畫程序框圖的規(guī)則如下：1 、使用標(biāo)準(zhǔn)的圖形符號。2 、框圖一般按從上到下、從左到右的方向畫。3 、除判斷框外，大多數(shù)流程圖符號只有一個進入點和一個退出點。判斷框具有超過一個退出點的唯一符號。4 、判斷框分兩大類，一類判斷框“是”與“否”兩分支的判斷，而且有且僅有兩個結(jié)果；另一類是多分支判斷，有幾種不同的結(jié)果。5、在圖形符號

4、內(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í)行的處理步驟組成的，它是任何一個算法都離不開的一種基本算法結(jié)構(gòu)。順序結(jié)構(gòu)在程序框圖中的體現(xiàn)就是用流程線將程序框自上而下地連接起來，按順序執(zhí)行算法步驟。如在示意圖中，A 框和 B框是依次執(zhí)行的，只有在執(zhí)行完A 框指定的操作后，才能接著執(zhí)行 B 框所指定的操作。AB2、條件結(jié)構(gòu)：條件結(jié)構(gòu)是指在算法中通過對條件的判斷根據(jù)條件是否成立而選擇不同流向的算法結(jié)構(gòu)。條件 P 是否成立而選擇執(zhí)行A 框或 B

5、框。無論P 條件是否成立，只能執(zhí)行A 框或 B 框之一，不可能同時執(zhí)行A 框和B 框，也不可能A 框、 B 框都不執(zhí)行。一個判斷結(jié)構(gòu)可以有多個判斷框。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)可細分為兩類：（1 ）、一類是當(dāng)型循環(huán)結(jié)構(gòu)，如下左圖所示，它的功能是當(dāng)給定的條件P 成立時，執(zhí)行A 框， A 框執(zhí)行完畢后，再判斷條件P 是否成立，如果仍然成立，再執(zhí)行A 框，如此反復(fù)執(zhí)行A 框，直到某一次條件P 不成立為止，此時不再執(zhí)行A 框，離

6、開循環(huán)結(jié)構(gòu)。（2 ）、另一類是直到型循環(huán)結(jié)構(gòu)，如下右圖所示， 它的功能是先執(zhí)行，然后判斷給定的條件P 是否成立， 如果 P 仍然不成立，則繼續(xù)執(zhí)行A 框，直到某一次給定的條件P 成立為止，此時不再執(zhí)行A 框，離開循環(huán)結(jié)構(gòu)。當(dāng)型 循環(huán) 結(jié)構(gòu)直到型循環(huán)結(jié)構(gòu)AA構(gòu) 要在某個 條件P注意：1 循環(huán)結(jié)成立P下終止循環(huán)，這就需要條件結(jié)構(gòu)來判斷。因此，循環(huán)結(jié)構(gòu)中一定包含條件結(jié)構(gòu)，但不不成立2 在循環(huán)結(jié)構(gòu)中都有一個計數(shù)變量和累加變量。成立不成立計數(shù)變量允許“死循環(huán)”。用于記錄循環(huán)次數(shù)， 累加變量用于輸出結(jié)名可道教育科技有限公司果。計數(shù)變量和累加變量一般是同步執(zhí)行的，累加一次，計數(shù)一次。1.2.1輸入、輸出語句

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

8、戶輸入什么樣的信息，表達式是指程序要輸出的數(shù)據(jù)；（4）輸出語句可以輸出常量、變量或表達式的值以及字符。3、賦值語句（1）賦值語句的一般格式圖形計算器變量表達式格式表達式變量（ 2）賦值語句的作用是將表達式所代表的值賦給變量；（3）賦值語句中的“”稱作賦值號，與數(shù)學(xué)中的等號的意義是不同的。賦值號的左右兩邊不能對換， 它將賦值號右邊的表達式的值賦給賦值號左邊的變量；（4）賦值語句左邊只能是變量名字，而不是表達式，右邊表達式可以是一個數(shù)據(jù)、常量或算式；（5）對于一個變量可以多次賦值。注意： 賦值號左邊只能是變量名字，而不能是表達式。如：2=X是錯誤的。賦值號左右不能對換。如“A=B ”“B=A ”的

9、含義運行結(jié)果是不同的。不能利用賦值語句進行代數(shù)式的演算。（如化簡、因式分解、解方程等）賦值號“= ”與數(shù)學(xué)中的等號意義不同。1 22 條件語句1、條件語句的一般格式有兩種：（1）IFTHENELSE語句；（2）IF THEN語句。 2、IF THEN ELSE語句IF THENELSE語句的一般格式為圖1，對應(yīng)的程序框圖為圖2。IF 條件 THEN否語句 1滿足條件？ELSE是語句 2語句 1語句 2END IF名可道教育科技有限公司圖 1圖 2分析：在 IF THEN ELSE語句中，“條件”表示判斷的條件， “語句 1”表示滿足條件時執(zhí)行的操作內(nèi)容；“語句 2”表示不滿足條件時執(zhí)行的操作內(nèi)

10、容；END IF 表示條件語句的結(jié)束。計算機在執(zhí)行時，首先對IF 后的條件進行判斷，如果條件符合，則執(zhí)行 THEN后面的語句1；若條件不符合，則執(zhí)行ELSE后面的語句 2。3、 IFTHEN語句IF THEN語句的一般格式為圖3，對應(yīng)的程序框圖為圖4。IF 條件 THEN是語句滿足條件？END IF（圖 3）否語句（圖 4）注意：“條件”表示判斷的條件； “語句”表示滿足條件時執(zhí)行的操作內(nèi)容，條件不滿足時，結(jié)束程序； END IF 表示條件語句的結(jié)束。計算機在執(zhí)行時首先對IF 后的條件進行判斷，如果條件符合就執(zhí)行THEN 后邊的語句，若條件不符合則直接結(jié)束該條件語句，轉(zhuǎn)而執(zhí)行其它語句。1 2

11、3 循環(huán)語句循環(huán)結(jié)構(gòu)是由循環(huán)語句來實現(xiàn)的。對應(yīng)于程序框圖中的兩種循環(huán)結(jié)構(gòu)，一般程序設(shè)計語言中也有當(dāng)型（WHILE 型）和直到型（ UNTIL 型）兩種語句結(jié)構(gòu)。即WHILE語句和 UNTIL 語句。1、 WHILE 語句（1）WHILE語句的一般格式是對應(yīng)的程序框圖是循環(huán)體WHILE條件循環(huán)體是WEND滿足條件？否（2）當(dāng)計算機遇到WHILE語句時，先判斷條件的真假，如果條件符合，就執(zhí)行WHILE與 WEND之間的循環(huán)體；然后再檢查上述條件，如果條件仍符合，再次執(zhí)行循環(huán)體，這個過程反復(fù)進行，直到某一次條件不符合為止。這時，計算機將不執(zhí)行循環(huán)體，直接跳到WEND語句后，接著執(zhí)行WEND 之后的語

12、句。因此，當(dāng)型循環(huán)有時也稱為“前測試型”循環(huán)。2、 UNTIL 語句（1）UNTIL 語句的一般格式是對應(yīng)的程序框圖是DO循環(huán)體循環(huán)體LOOP UNTIL條件否滿足條件？是（2）直到型循環(huán)又稱為“后測試型”循環(huán)，從UNTIL 型循環(huán)結(jié)構(gòu)分析，計算機執(zhí)行該語句時，先執(zhí)行一次循環(huán)體，然后進行名可道教育科技有限公司條件的判斷， 如果條件不滿足，繼續(xù)返回執(zhí)行循環(huán)體，然后再進行條件的判斷，這個過程反復(fù)進行，直到某一次條件滿足時，不再執(zhí)行循環(huán)體，跳到LOOP UNTIL語句后執(zhí)行其他語句，是先執(zhí)行循環(huán)體后進行條件判斷的循環(huán)語句。分析： 當(dāng)型循環(huán)與直到型循環(huán)的區(qū)別：（先由學(xué)生討論再歸納）（1）當(dāng)型循環(huán)先判斷

13、后執(zhí)行，直到型循環(huán)先執(zhí)行后判斷；在 WHILE語句中，是當(dāng)條件滿足時執(zhí)行循環(huán)體，在UNTIL 語句中，是當(dāng)條件不滿足時執(zhí)行循環(huán)1.3.1 輾轉(zhuǎn)相除法與更相減損術(shù)1、輾轉(zhuǎn)相除法。也叫歐幾里德算法，用輾轉(zhuǎn)相除法求最大公約數(shù)的步驟如下：（ 1）：用較大的數(shù) m除以較小的數(shù) n 得到一個商 S0 和一個余數(shù) R0 ；（2）：若 R0 0，則 n 為 m，n 的最大公約數(shù)； 若 R0 0，則用除數(shù) n 除以余數(shù) R0 得到一個商 S1 和一個余數(shù) R1 ；（3）：若 R1 0，則 R1為 m，n 的最大公約數(shù)； 若 R1 0，則用除數(shù) R0除以余數(shù) R1 得到一個商 S2 和一個余數(shù) R2 ；依次計算直

14、至Rn 0，此時所得到的 Rn 1 即為所求的最大公約數(shù)。2、更相減損術(shù)我國早期也有求最大公約數(shù)問題的算法，就是更相減損術(shù)。在九章算術(shù)中有更相減損術(shù)求最大公約數(shù)的步驟：可半者半之，不可半者，副置分母?子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之。翻譯為：（1）：任意給出兩個正數(shù)；判斷它們是否都是偶數(shù)。若是，用2 約簡；若不是，執(zhí)行第二步。（2）：以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù)。例 2 用更相減損術(shù)求98 與 63 的最大公約數(shù) .分析：（略）3、輾轉(zhuǎn)相除法與更相減損術(shù)的區(qū)別：（

15、1）都是求最大公約數(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.3.2 秦九韶算法與排序1、秦九韶算法概念：f(x)=anxn +an-1 xn- 1+ .+a1x+a0 求值問題f(x)=anxn +an-1 xn- 1+ .+a1x+a0=( anxn-1+an-1xn-2 + .+a1)x+a0 =( an xn- 2+an-1 xn- 3+ .+a2)x+a1 )x+a0=.=

16、(.( an x+an-1)x+an-2)x+.+a1)x+a0求多項式的值時，首先計算最內(nèi)層括號內(nèi)依次多項式的值，即v 1=anx+an-1然后由內(nèi)向外逐層計算一次多項式的值，即v2=v1x+an-2v3=v2x+an-3.vn=vn-1x+a0名可道教育科技有限公司這樣，把n 次多項式的求值問題轉(zhuǎn)化成求n 個一次多項式的值的問題。2、兩種排序方法：直接插入排序和冒泡排序1、直接插入排序基本思想：插入排序的思想就是讀一個，排一個。將第個數(shù)放入數(shù)組的第個元素中，以后讀入的數(shù)與已存入數(shù)組的數(shù)進行比較，確定它在從大到小的排列中應(yīng)處的位置將該位置以及以后的元素向后推移一個位置，將讀入的新數(shù)填入空出的位置中（由于算法簡單，可以舉例說明）2、冒泡排序基本思想：依次比較相鄰的兩個數(shù), 把大的放前面 , 小的放后面 . 即首先比較第1 個數(shù)和第2 個數(shù) , 大數(shù)放前 , 小數(shù)放后 . 然后比較第 2 個數(shù)和第 3 個數(shù) .直到比較最后兩個數(shù). 第一趟結(jié)束 , 最小的一定沉到最后. 重復(fù)上過程 , 仍從第 1 個數(shù)開始 , 到最后第 2 個數(shù) .由于在排序過程中總是大數(shù)往前, 小數(shù)往后 , 相當(dāng)氣泡上升 , 所以叫冒泡排序.1.3.3 進位制1、概念：進位制 是一種記數(shù)方式， 用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為 n，即可稱 n 進位制，簡稱n 進制?，F(xiàn)