高中數(shù)學(xué)必修3知識點總結(jié)：第一章-算法初步

歸海木心QQ:634102564

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

第一章算法初步

1.1.1算法的概念

1、算法概念：

在數(shù)學(xué)上，現(xiàn)代意義上的“算法”通常是指可以用計算機(jī)來解決的某一類問題是程序或步驟，這些程序或步驟必須是明確和有效的，而且能夠在有限步之程序框圖

1、程序框圖基本概念：

（一）程序構(gòu)圖的概念：程序框圖又稱流程圖，是一種用規(guī)定的圖形、指向線及文字說明來準(zhǔn)確、直觀地表示算法的圖形。一個程序框圖包括以下幾部分：表示相應(yīng)操作的程序框；帶箭頭的流程線；程序框外必要文字說明。

（二）構(gòu)成程序框的圖形符號及其作用

歸海木心QQ:634102564

歸海木心QQ:634102564

學(xué)習(xí)這部分知識的時候，要掌握各個圖形的形狀、作用及使用規(guī)則，畫程序框圖的規(guī)則如下：

1、使用標(biāo)準(zhǔn)的圖形符號。2、框圖一般按從上到下、從左到右的方向畫。3、除判斷框外，大多數(shù)流程圖符號只有一個進(jìn)入點和一個退出點。判斷框具有超過一個退出點的唯一符號。4、判斷框分兩大類，一類判斷框“是”與“否”兩分支的判斷，而且有且僅有兩個結(jié)果；另一類是多分支判斷，有幾種不同的結(jié)果。5、在圖形符號QQ:634102564

歸海木心QQ:634102564

果。計數(shù)變量和累加變量一般是同步執(zhí)行的，累加一次，計數(shù)一次。

1.2.1輸入、輸出語句和賦值語句

1、輸入語句

（1）輸入語句的一般格式

（2）輸入

語句的作

用是實現(xiàn)

算法的輸入信息功能；（3）“提示QQ:634102564

歸海木心QQ:634102564

圖1圖2

分析：在IF—THEN—ELSE語句中，“條件”表示判斷的條件，“語句1”表示滿足條件時執(zhí)行的操作IF表示條件語句的結(jié)束。計算機(jī)在執(zhí)行時，首先對IF后的條件進(jìn)行判斷，如果條件符合，則執(zhí)行THEN后面的語句1；若條件不符合，則執(zhí)行ELSE后面的語句2。3、IF—THEN語句

IF—THEN語句的一般格式為圖3，對應(yīng)的程序框圖為圖4。

注意：“條件”表示判斷的條件；“語句”表示滿足條件時執(zhí)行的操作若條件不符合則直接結(jié)束該條件語句，轉(zhuǎn)而執(zhí)行其它語句。

序；END

IF表示條件語句的結(jié)束。計算機(jī)在執(zhí)行時首先對IF后的條件進(jìn)行判斷，如果條件符合就執(zhí)行THEN后邊的語句，

1．2．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語句的一般格式是

（2）當(dāng)計算機(jī)遇到WHILE語句時，先判斷條件的真假，如果條件符合，就執(zhí)行WHILE與WEND之間的循環(huán)體；然后再檢查上述條件，如果條件仍符合，再次執(zhí)行循環(huán)體，這個過程反復(fù)進(jìn)行，直到某一次條件不符合為止。這時，計算機(jī)將不執(zhí)行循環(huán)體，直接跳到WEND語句后，接著執(zhí)行WEND之后的語句。因此，當(dāng)型循環(huán)有時也稱為“前測試型”循環(huán)。2、UNTIL語句

（1）UNTIL語句的一般格式是對應(yīng)的程序框圖是

（2）直到型循環(huán)又稱為“后測試型”循環(huán)，從UNTIL歸海木心QQ:634102564

歸海木心QQ:634102564

條件的判斷，如果條件不滿足，繼續(xù)返回執(zhí)行循環(huán)體，然后再進(jìn)行條件的判斷，這個過程反復(fù)進(jìn)行，直到某一次條件滿足時，不再執(zhí)行循環(huán)體，跳到LOOPUNTIL語句后執(zhí)行其他語句，是先執(zhí)行循環(huán)體后進(jìn)行條件判斷的循環(huán)語句。

分析：當(dāng)型循環(huán)與直到型循環(huán)的區(qū)別：（先由學(xué)生討論再歸納）

（1）當(dāng)型循環(huán)先判斷后執(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得到一個商

則用除數(shù)n除以余數(shù)

除以余數(shù)RRS0和一個余數(shù)R0；（2）：若0＝0，則n為m，n的最大公約數(shù)；若0≠0，R0得到一個商S1和一個余數(shù)R1；RRRR（3）：若1＝0，則1為m，n的最大公約數(shù)；若1≠0，則用除數(shù)0R1得到一個商S2和一個余數(shù)R2；??依次計算直至Rn＝0，此時所得到的Rn1即為所求的最大公約數(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ū)別：

（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)=anx+an-1x+….+a1x+a0求值問題

f(x)=anx+an-1x+….+a1x+a0=(anx+an-1x+….+a1)x+a0=((anx+an-1x+….+a2)x+a1)x+a0

=......=(...(anx+an-1)x+an-2)x+...+a1)x+a0nn-1n-1n-2n-2n-3nn-1

求多項式的值時，首先計算最v3=v2x+an-3......vn=vn-1x+a0

歸海木心QQ:634102564

歸海木心QQ:634102564

這樣，把n次多項式的求值問題轉(zhuǎn)化成求n個一次多項式的值的問題。

2、兩種排序方法：直接插入排序和冒泡排序

1、直接插入排序

基本思想：插入排序的思想就是讀一個，排一個。將第１個數(shù)放入數(shù)組的第１個元素中，以后讀入的數(shù)與已存入數(shù)組的數(shù)進(jìn)行比較，確定它在從大到小的排列中應(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進(jìn)位制

1、概念：進(jìn)位制是一種記數(shù)方式，用有限的數(shù)字在不同的位置表示不同的數(shù)值?？墒褂脭?shù)字符號的個數(shù)稱為基數(shù)，基數(shù)為n，即可稱n進(jìn)位制，簡稱n進(jìn)制?，F(xiàn)在最常用的是十進(jìn)制，通常使用10個阿拉伯?dāng)?shù)字0-9進(jìn)行記數(shù)。對于任何一個數(shù)，我們可以用不同的進(jìn)位制來表示。比如：十進(jìn)數(shù)57，可以用二進(jìn)制表示為111001，也可以用八進(jìn)制表示為71、用十六進(jìn)制表示為39，