錯(cuò)解剖析得真知

1、錯(cuò)解剖析得真知（四十） 133 算法案例 一、知識(shí)導(dǎo)學(xué) 1算法設(shè)計(jì)思想： （1）“韓信點(diǎn)兵孫子問(wèn)題”對(duì)正整數(shù)m從2開始逐一檢驗(yàn)條件，若三個(gè)條件中有任何一個(gè)不滿足，則m遞增1，一直到m同時(shí)滿足三個(gè)條件為止(循環(huán)過(guò)程用Goto語(yǔ)句實(shí)現(xiàn))（2）用輾轉(zhuǎn)相除法找出的最大公約數(shù)的步驟是：計(jì)算出的余數(shù)，若，則為的最大公約數(shù)；若，則把前面的除數(shù)作為新的被除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為0，此時(shí)的除數(shù)即為正整數(shù)的最大公約數(shù).2.更相減損術(shù)的步驟：（1）任意給出兩個(gè)正數(shù)，判斷它們是否都是偶數(shù).若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步.（2）以較大的數(shù)減去較小的數(shù)，接著把較小的數(shù)與所得的差比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，直

2、到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最大公約數(shù).（3）二分法求方程在區(qū)間內(nèi)的一個(gè)近似解的解題步驟可表示為S1 取的中點(diǎn)，將區(qū)間一分為二；S2 若，則就是方程的根；否則判別根在的左側(cè)還是右側(cè)：若，以代替；若，則，以代替；S3 若，計(jì)算終止，此時(shí)，否則轉(zhuǎn)S1. 二、疑難知識(shí)導(dǎo)析 1表示不超過(guò)的整數(shù)部分，如，但當(dāng)是負(fù)數(shù)時(shí)極易出錯(cuò)，如就是錯(cuò)誤的，應(yīng)為-2.2表示除以所得的余數(shù)，也可用 表示.3輾轉(zhuǎn)相除法與更相減損術(shù)求最大公約數(shù)的聯(lián)系與區(qū)別：（1）都是求最大公約數(shù)的方法，計(jì)算上輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少，特別當(dāng)兩個(gè)數(shù)字大小區(qū)別較大時(shí)計(jì)算次數(shù)

3、的區(qū)別較明顯.（2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到.4用二分法求方程近似解，必須先判斷方程在給定區(qū)間上是否有解,即連續(xù)且滿足.并在二分搜索過(guò)程中需對(duì)中點(diǎn)處函數(shù)值的符號(hào)進(jìn)行多次循環(huán)判定，故需要選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，即可用Goto 語(yǔ)句和條件語(yǔ)句實(shí)現(xiàn)算法. 三、經(jīng)典例題導(dǎo)講 例1 ， ， ， 7= .A16，-1，4，3 B.15，0，4，3 C.15,-1,3,4 D.15,-1,4,3錯(cuò)解：根據(jù)表示不超過(guò)的整數(shù)部分, 表示除以所得的余數(shù),選擇B.錯(cuò)因:對(duì)表示的含義理解不透徹,將不超過(guò)-0.05的整數(shù)錯(cuò)認(rèn)為是0,將負(fù)數(shù)的大小比較與正

4、數(shù)的大小比較相混淆.正解：不超過(guò)-0.05的整數(shù)是-1,所以答案為D.例2 所謂同構(gòu)數(shù)是指此數(shù)的平方數(shù)的最后幾位與該數(shù)相等.請(qǐng)?jiān)O(shè)計(jì)一算法判斷一個(gè)大于0且小于1000的整數(shù)是否為同構(gòu)數(shù).錯(cuò)解： 算法思想：求出輸入數(shù)的平方，考慮其個(gè)位或最后兩位或最后三位與輸入數(shù)是否相等，若相等，則為同構(gòu)數(shù). Read x If or or Then Print x End if End 錯(cuò)因：在表示個(gè)位或最后兩位或最后三位出現(xiàn)錯(cuò)誤，“/”僅表示除，y/10,y/100,y/1000都僅僅表示商.正解：可用來(lái)表示個(gè)位，最后兩位以及最后三位.Read x If or or Then Print x End if En

5、d 例3孫子算經(jīng)中的“物不知數(shù)”問(wèn)題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”可以用下面的算法解決：先在紙上寫上2，每次加3，加成5除余3的時(shí)候停下來(lái)，再在這個(gè)數(shù)上每次加15，到得出7除2的時(shí)候，就是答數(shù).試用流程圖和偽代碼表示這一算法.解：流程圖為： 偽代碼為：10 20 30 If Then Goto 2040 If Then Print Goto 8050 End if60 70 Goto 4080 End 點(diǎn)評(píng)：這是孫子思想的體現(xiàn)，主要是依次滿足三個(gè)整除條件.例4分別用輾轉(zhuǎn)相除法、更相減損法求192與81的最大公約數(shù).解：輾轉(zhuǎn)相除法： S1 S2 S3

6、S4 S5 故3是192 與81 的最大公約數(shù).更相減損法：S1 S2 S3 S4 S5 S6 S7 S8 S9 故3 是192與81的最大公約數(shù).點(diǎn)評(píng)：輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)算次數(shù)相對(duì)較少.輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)整除時(shí)停止除法運(yùn)算，此時(shí)的小數(shù)就是兩者的最大公約數(shù)，更相減損術(shù)是當(dāng)大數(shù)減去小數(shù)的差等于小數(shù)時(shí)減法停止，較小的數(shù)就是最大公約數(shù). 例5為了設(shè)計(jì)用區(qū)間二分法求方程在0，1上的一個(gè)近似解（誤差不超過(guò)0.001）的算法,流程圖的各個(gè)框圖如下所示,請(qǐng)重新排列各框圖,并用帶箭頭的流線和判斷符號(hào)“Y”、“N”組成正確的算法流程圖,并寫出其偽代碼.(其中

7、分別表示區(qū)間的左右端點(diǎn)) 圖13-3-2流程圖為 圖13-3-3 偽代碼為10 Read 20 30 40 50 If Then Goto 12060 If Then70 100 End if 80 Else90 100 End if110 If Then Goto 20120 Print 130 End 點(diǎn)評(píng)：二分法的基本思想在必修一中已滲透，這里運(yùn)用算法將二分法求方程近似解的步驟更清晰的表述出來(lái).例6 用秦九韶算法計(jì)算多項(xiàng)式在時(shí)的值時(shí)， 的值為 .解： 根據(jù)秦九韶算法，此多項(xiàng)式可變形為按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)時(shí)的值： 故當(dāng)時(shí)多項(xiàng)式的值為.點(diǎn)評(píng)：秦九韶算法的關(guān)鍵是n次多項(xiàng)式的

8、變形.把一個(gè)次多項(xiàng)式改寫成，求多項(xiàng)式的值，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值，然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，這樣把求次多項(xiàng)式的值問(wèn)題轉(zhuǎn)化為求個(gè)一次多項(xiàng)式的值的問(wèn)題，這種方法成為秦九韶算法.這種算法中有反復(fù)執(zhí)行的步驟，因此，可考慮用循環(huán)結(jié)構(gòu)實(shí)現(xiàn). 四、典型習(xí)題導(dǎo)練 1以下短文摘自古代孫子算經(jīng)一書，其引申出的“大衍求一術(shù)”稱為“中國(guó)剩余原理”：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”答曰（ ）. A二十一 B.二十二 C.二十三 D.二十四2用輾轉(zhuǎn)相除法求52與39的最大公約數(shù)的循環(huán)次數(shù)為（ ）.A1次 B.2次 C.3次 D.5次3下面程序功能是統(tǒng)計(jì)隨機(jī)產(chǎn)生的十個(gè)兩位正整數(shù)中偶數(shù)和奇數(shù)的個(gè)數(shù)，并求出偶數(shù)與奇數(shù)各自的總和.For I from 1 to 10 Print x; If Then Else End IfEnd forPrintPrint “奇數(shù)個(gè)數(shù)=”； ，“偶數(shù)個(gè)數(shù)=”；4若一個(gè)數(shù)的各因子之和正好等于該數(shù)本身，則該數(shù)成為完數(shù).請(qǐng)補(bǔ)充完整下列找出1100之間的所有完數(shù)的偽代碼.For from 2 to 100For b from 2 to I