算法案例

昵稱3826483 2013-12-08

展開全文

算法案例

一、知識導(dǎo)學(xué)

1．算法設(shè)計思想：

（1）“韓信點兵—孫子問題”對正整數(shù)m從2開始逐一檢驗條件，若三個條件中有任何一個不滿足，則m遞增1，一直到m同時滿足三個條件為止(循環(huán)過程用Goto語句實現(xiàn))

（2）用輾轉(zhuǎn)相除法找出的最大公約數(shù)的步驟是：計算出的余數(shù)，若，則為的最大公約數(shù)；若，則把前面的除數(shù)作為新的被除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為0，此時的除數(shù)即為正整數(shù)的最大公約數(shù).

2.更相減損術(shù)的步驟：（1）任意給出兩個正數(shù)，判斷它們是否都是偶數(shù).若是，用2約簡；若不是，執(zhí)行第二步.（2）以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù).繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）就是所求的最大公約數(shù).

（3）二分法求方程在區(qū)間內(nèi)的一個近似解的解題步驟可表示為

S1 取[]的中點，將區(qū)間一分為二；

S2 若，則就是方程的根；否則判別根在的左側(cè)還是右側(cè)：

若，，以代替；

若，則，以代替；

S3 若，計算終止，此時，否則轉(zhuǎn)S1.

二、疑難知識導(dǎo)析

1．表示不超過的整數(shù)部分，如，但當(dāng)是負(fù)數(shù)時極易出錯，如就是錯誤的，應(yīng)為-2.

2．表示除以所得的余數(shù)，也可用表示.

3．輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的聯(lián)系與區(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ù)與差相等而得到.

4．用二分法求方程近似解，必須先判斷方程在給定區(qū)間[]上是否有解,即連續(xù)且滿足.并在二分搜索過程中需對中點處函數(shù)值的符號進(jìn)行多次循環(huán)判定，故需要選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，即可用Goto 語句和條件語句實現(xiàn)算法.

三、經(jīng)典例題導(dǎo)講

[例1] ，，

， 7= .

A．16，-1，4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3

錯解：根據(jù)表示不超過的整數(shù)部分, 表示除以所得的余數(shù),選擇B.

錯因:對表示的含義理解不透徹,將不超過-0.05的整數(shù)錯認(rèn)為是0,將負(fù)數(shù)的大小比較與正數(shù)的大小比較相混淆.

正解：不超過-0.05的整數(shù)是-1,所以答案為D.

[例2] 所謂同構(gòu)數(shù)是指此數(shù)的平方數(shù)的最后幾位與該數(shù)相等.請設(shè)計一算法判斷一個大于0且小于1000的整數(shù)是否為同構(gòu)數(shù).

錯解：算法思想：求出輸入數(shù)的平方，考慮其個位或最后兩位或最后三位與輸入數(shù)是否相等，若相等，則為同構(gòu)數(shù).

Read x

If or or Then

Print x

End if

End

錯因：在表示個位或最后兩位或最后三位出現(xiàn)錯誤，“/”僅表示除，y/10,y/100,y/1000都僅僅表示商.

正解：可用來表示個位，最后兩位以及最后三位.

Read x

If or or Then

Print x

End if

End

[例3]《孫子算經(jīng)》中的“物不知數(shù)”問題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”可以用下面的算法解決：先在紙上寫上2，每次加3，加成5除余3的時候停下來，再在這個數(shù)上每次加15，到得出7除2的時候，就是答數(shù).

試用流程圖和偽代碼表示這一算法.

解：流程圖為：

偽代碼為：

30 If Then Goto 20

40 If Then

Goto 80

50 End if

70 Goto 40

80 End

點評：這是孫子思想的體現(xiàn)，主要是依次滿足三個整除條件.

[例4]分別用輾轉(zhuǎn)相除法、更相減損法求192與81的最大公約數(shù).

解：輾轉(zhuǎn)相除法：

故3是192 與81 的最大公約數(shù).

更相減損法：

故3 是192與81的最大公約數(shù).

點評：輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少.輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)整除時停止除法運(yùn)算，此時的小數(shù)就是兩者的最大公約數(shù)，更相減損術(shù)是當(dāng)大數(shù)減去小數(shù)的差等于小數(shù)時減法停止，較小的數(shù)就是最大公約數(shù).

[例5]為了設(shè)計用區(qū)間二分法求方程在[0，1]上的一個近似解（誤差不超過0.001）的算法,流程圖的各個框圖如下所示,請重新排列各框圖,并用帶箭頭的流線和判斷符號“Y”、“N”組成正確的算法流程圖,并寫出其偽代碼.(其中分別表示區(qū)間的左右端點)

圖13-3-2

流程圖為

圖13-3-3

偽代碼為

10 Read

50 If Then Goto 120

60 If Then

100 End if

80 Else

100 End if

110 If Then Goto 20

120 Print

130 End

點評：二分法的基本思想在必修一中已滲透，這里運(yùn)用算法將二分法求方程近似解的步驟更清晰的表述出來.

[例6] 用秦九韶算法計算多項式在時的值時，的值為 .

解：根據(jù)秦九韶算法，此多項式可變形為

按照從內(nèi)到外的順序，依次計算一次多項式當(dāng)時的值：

故當(dāng)時多項式的值為.

點評：秦九韶算法的關(guān)鍵是n次多項式的變形.

把一個次多項式改寫成，求多項式的值，首先計算最內(nèi)層括號內(nèi)一次多項式的值，然后由內(nèi)向外逐層計算一次多項式的值，這樣把求次多項式的值問題轉(zhuǎn)化為求個一次多項式的值的問題，這種方法成為秦九韶算法.這種算法中有反復(fù)執(zhí)行的步驟，因此，可考慮用循環(huán)結(jié)構(gòu)實現(xiàn).

四、典型習(xí)題導(dǎo)練

1．以下短文摘自古代《孫子算經(jīng)》一書，其引申出的“大衍求一術(shù)”稱為“中國剩余原理”：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？”答曰（）.

A．二十一 B.二十二 C.二十三 D.二十四

2．用輾轉(zhuǎn)相除法求52與39的最大公約數(shù)的循環(huán)次數(shù)為（）.

A．1次 B.2次 C.3次 D.5次

3．下面程序功能是統(tǒng)計隨機(jī)產(chǎn)生的十個兩位正整數(shù)中偶數(shù)和奇數(shù)的個數(shù)，并求出偶數(shù)與奇數(shù)各自的總和.

For I from 1 to 10

Print x;

If Then

Else

End If

End for