錯(cuò)解剖析得真知

錯(cuò)解剖析得真知（四十）§13．3算法案例一、知識(shí)導(dǎo)學(xué)1．算法設(shè)計(jì)思想：（1）“韓信點(diǎn)兵—孫子問(wèn)題”對(duì)正整數(shù)m從2開(kāi)始逐一檢驗(yàn)條件，若三個(gè)條件中有任何一個(gè)不滿(mǎn)足，則m遞增1，一直到m同時(shí)滿(mǎn)足三個(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è)操作，直到所得的數(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ù)的區(qū)別較明顯.（2）從結(jié)果體現(xiàn)形式來(lái)看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù)則以減數(shù)與差相等而得到.4．用二分法求方程近似解，必須先判斷方程在給定區(qū)間[]上是否有解,即連續(xù)且滿(mǎn)足.并在二分搜索過(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=.A．16，-1，4，3B.15，0，4，3C.15,-1,3,4D.15,-1,4,3錯(cuò)解：根據(jù)表示不超過(guò)的整數(shù)部分,表示除以所得的余數(shù),選擇B.錯(cuò)因:對(duì)表示的含義理解不透徹,將不超過(guò)-0.05的整數(shù)錯(cuò)認(rèn)為是0,將負(fù)數(shù)的大小比較與正數(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ù).ReadxIfororThenPrintxEndifEnd錯(cuò)因：在表示個(gè)位或最后兩位或最后三位出現(xiàn)錯(cuò)誤，“/”僅表示除，y/10,y/100,y/1000都僅僅表示商.正解：可用來(lái)表示個(gè)位，最后兩位以及最后三位.Readx圖13-3-2流程圖為圖13-3-3偽代碼為10Read20304050IfThenGoto12060IfThen70100Endif80Else90100Endif110IfThenGoto20120Print130End點(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)式的變形.把一個(gè)次多項(xiàng)式改寫(xiě)成，求多項(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ū)，其引申出的“大衍求一術(shù)”稱(chēng)為“中國(guó)剩余原理”：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？”答曰（）.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ì)隨機(jī)產(chǎn)生的十個(gè)兩位正整數(shù)中偶數(shù)和奇數(shù)的個(gè)數(shù)，并求出偶數(shù)與奇數(shù)各自的總和.ForIfrom1to10Printx;IfThenElseEndIfEndforPrintPrint“奇數(shù)個(gè)數(shù)=”；，“偶數(shù)個(gè)數(shù)=”；4．若一個(gè)數(shù)的各因子之和正好等于該數(shù)本身，則該數(shù)成為完數(shù).請(qǐng)補(bǔ)充完整下列找出1～100之間的所有完數(shù)的偽代碼.Forfrom2to100Forbfrom2toIfmod(a,b)=0Then