13.3《算法案例》錯(cuò)誤解題分析

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

2、的數(shù)與所得的差比較，并以大數(shù)減小數(shù)。繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)數(shù)（等數(shù)）就是所求的最 大公約數(shù)。（3） 二分法求方程 f（x） 0在區(qū)間a,b內(nèi)的一個(gè)近似解 x*的解題步驟可表示為1S1取a,b的中點(diǎn)x0a b，將區(qū)間一分為二；2S2若f X。0，則Xo就是方程的根；否則判別根 x在Xo的左側(cè)還是右側(cè)：若 fa f Xo0， x* Xo,b，以 Xo 代替 a ；若 fa f X00，則 x* a, X0，以 x° 代替 b ；S3若a b c，計(jì)算終止，此時(shí) xX0，否則轉(zhuǎn)S1。二、疑難知識(shí)導(dǎo)析1、 int（ x）表示不超過(guò)x的整數(shù)部分，如int（5.86） 5,i

3、nt（0.32） 0，但當(dāng)x是負(fù)數(shù)時(shí)極易出錯(cuò)，如int（ 1.14）1就是錯(cuò)誤的，應(yīng)為-2。2、mod（a,b）表示a除以b所得的余數(shù)，也可用 a mod b表示。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ū)間a,b上是否有解，即f x連續(xù)且滿足f a f b0。并在二分

4、搜索過(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 int(5 ) ，int( 0.05) ，mod(67,9)，45 mod 7=。A 16，-1，4，3 B 、15，0，4，3 C 、15,-1,3,4 D 、15,-1,4,3【錯(cuò)解】根據(jù)int(x)表示不超過(guò)x的整數(shù)部分，mod(a,b)表示a除以b所得的余數(shù),選擇B?！惧e(cuò)因】對(duì)int( x)表示的含義理解不透徹，將不超過(guò)-0。05的整數(shù)錯(cuò)認(rèn)為是 0,將負(fù)數(shù)的大小 比較與正數(shù)的大小比較相混淆?！菊狻坎怀^(guò)-0。05的整數(shù)是-1,所以答案為Db例2所謂

5、同構(gòu)數(shù)是指此數(shù)的平方數(shù)的最后幾位與該數(shù)相等。請(qǐng)?jiān)O(shè)計(jì)一算法判斷一個(gè)大于0且小于1000的整數(shù)是否為同構(gòu)數(shù)?！惧e(cuò)解】算法思想：求出輸入數(shù)的平方， 考慮其個(gè)位或最后兩位或最后三位與輸入數(shù)是否相 等，若相等，則為同構(gòu)數(shù)。Read xy x xIf (x y 10) or (x y 100) or (x y 1000) ThenPrint xEnd ifEnd【錯(cuò)因】在表示個(gè)位或最后兩位或最后三位出現(xiàn)錯(cuò)誤，“/”僅表示除，y/10,y/100,y/1000都僅僅表示商?！菊狻靠捎胢od( y,10), mod( y,100), mod( y,1000)來(lái)表示個(gè)位，最后兩位以及最后三位。Read xy

6、x xIf (x mod(y,10) or (x mod(y,100) or (x mod(y,1000) ThenPrint xEnd ifEnd例3孫子算經(jīng)中的“物不知數(shù)”問(wèn)題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問(wèn)物幾何？ ”可以用下面的算法解決：先在紙上寫(xiě)上2，每次加3，加成5除余3的時(shí)候停下來(lái)，再在這個(gè)數(shù)上每次加15,至懦出7除2的時(shí)候，就是答數(shù)。試用流程圖和偽代碼表示這一算法。解：流程圖為：偽代碼為:10 m220 mm 330 If mod m,53 Then Goto 20 40 If mod(m,7) 2 ThenPrintmGoto 80 50 En

7、d if60 m m 1570 Goto 4080 End【點(diǎn)評(píng)】這是孫子思想的體現(xiàn)，主要是依次滿足三個(gè)整除條件。例 4分別用輾轉(zhuǎn)相除法、更相減損法求192與 81的最大公約數(shù)。解：輾轉(zhuǎn)相除法：S1192 81 230S28130221S3302119S421923S5 9 3 3 0 故 3 是 192 與 81 的最大公約數(shù)。 更相減損法：S119281111S21118130S3813051S4513021S530219S621912S71293S8936S9633故 3 是 192 與 81 的最大公約數(shù)。【點(diǎn)評(píng)】 輾轉(zhuǎn)相除法以除法為主， 更相減損術(shù)以減法為主， 計(jì)算次數(shù)上輾轉(zhuǎn)相除法計(jì)

8、算次數(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ū)間二分法求方程 x3 x2 1 0 在0 ，1 上的一個(gè)近似解（誤差不超過(guò) 0。001）的算法 , 流程圖的各個(gè)框圖如下所示 , 請(qǐng)重新排列各框圖 , 并用帶箭頭的流線和判斷符號(hào)“丫”、 “N'組成正確的算法流程圖，并寫(xiě)出其偽代碼。（其中a,b分別表示區(qū)間的左右端點(diǎn)）流程圖為/軸人耳鳥(niǎo)/心l （十占）/2/輸出 /圖 13-3-3偽代碼為10 Read a, b20 xo(a b). 230

9、f (a) a3 a2140f(x)X。3X。2150Iff(x0)0 ThenGoto 12060If f(a)f(X0)0The n70bXo100End if80Else90aXo100End if110Ifa b 0.001The n Goto 20120PrintX0130End【點(diǎn)評(píng)】二分法的基本思想在必修一中已滲透，這里運(yùn)用算法將二分法求方程近似解的步驟更清晰的表述出來(lái)。例6用秦九韶算法計(jì)算多項(xiàng)式 f(x) 12 35x 8x2 79x3 6x4 5x5 3x6在x4時(shí)的值時(shí)， V3的值為。解：根據(jù)秦九韶算法，此多項(xiàng)式可變形為f Xx x x x x 3x 567983512按照

10、從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)x 4時(shí)的值:V04V13 ( 4)57V2(4) ( 7)634V3(4) 347957故當(dāng)X4時(shí)多項(xiàng)式的值為57?！军c(diǎn)評(píng)】秦九韶算法的關(guān)鍵是 n 次多項(xiàng)式的變形。把一個(gè) n 次多項(xiàng)式f (x) anxn an 1xn 1a1x a0 改寫(xiě)成f(x) ( (anx an 1)x an 2)x a1)x a0 ，求多項(xiàng)式的值，首先計(jì)算最內(nèi)層括號(hào) 內(nèi)一次多項(xiàng)式的值， 然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值， 這樣把求 n 次多項(xiàng)式的值問(wèn)題 轉(zhuǎn)化為求 n 個(gè)一次多項(xiàng)式的值的問(wèn)題， 這種方法成為秦九韶算法。 這種算法中有反復(fù)執(zhí)行的 步驟，因此，可考慮用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。僅供個(gè)人用于學(xué)習(xí)、研究；不得用于商業(yè)用途。For personal use only in study and research; not for commercial use.Nur f u r den pers?nlichen f u r Studien, Forschung, zu kommerziellen Zweckerwerdet werden.Pour l ' e tude et