錯(cuò)解剖析得真知24

1、僅供個(gè)人參考For personal use only in study and research; not for commercial use錯(cuò)解剖析得真知（四十）§ 13. 3算法案例一、知識(shí)導(dǎo)學(xué)1.算法設(shè)計(jì)思想：（1） “韓信點(diǎn)兵一孫子問題”對(duì)正整數(shù)m從2開始逐一檢驗(yàn)條件，若三個(gè)條件中有任何一 個(gè)不滿足，則 m遞增1，一直到m同時(shí)滿足三個(gè)條件為止（循環(huán)過程用Goto語句實(shí)現(xiàn)）（2） 用輾轉(zhuǎn)相除法找出匸U的最大公約數(shù)的步驟是：計(jì)算出一；L：1的余數(shù)，若 I，則：為；的最大公約數(shù)；若5' I ,則把前面的除數(shù)一：作為新的被除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為0，此時(shí)的除數(shù)即為正整數(shù)

2、 -'的最大公約數(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）二分法求方程工I在區(qū)間打一內(nèi)的一個(gè)近似解丄*的解題步驟可表示為L(zhǎng) 知二丄0+占）S1取“'的中點(diǎn) 一，將區(qū)間一分為二；S2若，則就是方程的根；否則判別根在的左側(cè)還是右側(cè)：若兒】，爲(wèi)" ，以代替；若；丄1血冷1-：匚，則'一以代替；S3若l'： '''J ：，計(jì)

3、算終止，此時(shí)'匕I ,否則轉(zhuǎn)S1.二、疑難知識(shí)導(dǎo)析1. 工 門表示不超過:的整數(shù)部分，如-'：，1 -'Jr ""，但當(dāng)是負(fù)數(shù)時(shí)極易出錯(cuò)，如 二- 一、巴一 一-就是錯(cuò)誤的，應(yīng)為-2.2. 表示必除以B所得的余數(shù)，也可用l! mod力表示.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)形式來看，輾轉(zhuǎn)相除法體現(xiàn)結(jié)果是以相除余數(shù)為0則得到，而更相減損術(shù) 則以減數(shù)與

4、差相等而得到4.用二分法求方程近似解，必須先判斷方程在給定區(qū)間；'上是否有解，即連續(xù)且滿足.并在二分搜索過程中需對(duì)中點(diǎn)處函數(shù)值的符號(hào)進(jìn)行多次循環(huán)判定，故需要選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，即可用 Goto語句和條件語句實(shí)現(xiàn)算法三、經(jīng)典例題導(dǎo)講例 1血(了汀)二，血二,mod(6N9)= 45 mod 7=A. 16, -1 , 4, 3B.15, 0, 4, 3C.15,-1,3,4D.15,-1,4,3錯(cuò)解：根據(jù)工 門表示不超過:.的整數(shù)部分，豊二心川；表示“除以匚所得的余數(shù) 選擇B.錯(cuò)因：對(duì)九表示的含義理解不透徹，將不超過-0.05的整數(shù)錯(cuò)認(rèn)為是0,將負(fù)數(shù)的大小比較 與正數(shù)的大小比較相混淆正解

5、：不超過-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 xIf /or -or :ThenPrint xEnd ifEnd錯(cuò)因：在表示個(gè)位或最后兩位或最后三位出現(xiàn)錯(cuò)誤，“/”僅表示除，y/10,y/100,y/1000都僅僅表示商.正解：可用-T，- - '' ' ' 1-1- -'"來表示個(gè)位，最后兩位以及最后三位.Read xIf匕

6、or111 orThenPrint xEnd ifEnd例3孫子算經(jīng)中的“物不知數(shù)”問題：“今有物不知其數(shù)，三三數(shù)之剩二，五五數(shù)之剩三，七七數(shù)之剩二，問物幾何？ ”可以用下面的算法解決：先在紙上寫上2,每次加3,加成5除余3的時(shí)候停下來，再在這個(gè)數(shù)上每次加 15,到得出7除2的時(shí)候，就是答數(shù).試用流程圖和偽代碼表示這一算法解：流程圖為：偽代碼為：10 220 :匚30 If二，丁 - Then Goto 2040 If二二ThenPrintmGoto8050 End if60亡+、70 Goto 4080 End點(diǎn)評(píng)：這是孫子思想的體現(xiàn)，主要是依次滿足三個(gè)整除條件例4分別用輾轉(zhuǎn)相除法、更相減損

7、法求192與81的最大公約數(shù)解：輾轉(zhuǎn)相除法：S1S281- 30= 221S33021=19S4229 = 23S59 門二 3故3是192與81的最大公約數(shù).更相減損法：S1192-81 = 111S2111-81=30S381-30 = 51S451-30 = 2155 J56 ：二57 I58 -:59 .-故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ì)用

8、區(qū)間二分法求方程 .： 一 - I在0，1上的一個(gè)近似解（誤差不超過0.001）的算法，流程圖的各個(gè)框圖如下所示，請(qǐng)重新排列各框圖，并用帶箭頭的流線和判斷符號(hào)“ Y”、“ N'組成正確的算法流程圖點(diǎn)）流程圖為偽代碼為,并寫出其偽代碼.（其中分別表示區(qū)間的左右端圖 13-3-2圖 13-3-310 Read20心 (a +A)/230臺(tái) / +圧-14050If': Then Goto 12060If" Then70100End if80Else90100End if110 If -0.001 Then Goto 20120 Print '130 End點(diǎn)評(píng)：二

9、分法的基本思想在必修一中已滲透，這里運(yùn)用算法將二分法求方程近似解的步驟更清晰的表述出來例6用秦九韶算法計(jì)算多項(xiàng)式在:'- 時(shí)的值時(shí)，1的值為解：根據(jù)秦九韶算法，此多項(xiàng)式可變形為/M = x«X+5)+6)+79)-8)+35)+12按照從內(nèi)到外的順序，依次計(jì)算一次多項(xiàng)式當(dāng)，.-時(shí)的值: 故當(dāng)- T時(shí)多項(xiàng)式的值為 J 點(diǎn)評(píng)：秦九韶算法的關(guān)鍵是 n次多項(xiàng)式的變形把一個(gè)次多項(xiàng)式-' 'L ' ' 71; ' ' I改寫成_ .求多項(xiàng)式的值，首先計(jì)算最內(nèi)層括號(hào)內(nèi)一次多項(xiàng)式的值， 然后由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，這樣把求1次多項(xiàng)式的值

10、問題轉(zhuǎn)化為求1個(gè)一次多項(xiàng)式的值的問題，這種方法成為秦九韶算法這種算法中有反復(fù)執(zhí)行的步驟，因此，可考慮用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)四、典型習(xí)題導(dǎo)練1.以下短文摘自古代孫子算經(jīng)一書，其引申出的“大衍求一術(shù)”稱為“中國(guó)剩余原理”：“今有物不知其數(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ì)隨機(jī)產(chǎn)生的十個(gè)兩位正整數(shù)中偶數(shù)和奇數(shù)的個(gè)數(shù)，并求出偶數(shù)與奇 數(shù)各自的總和.For I from 1 to 10Print x;IfThenElseEnd

11、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 If mod(a,b)=0 ThenEnd ifEnd ForIf The nPrint aEnd ifEnd ForEnd5設(shè)計(jì)求被9除余4,被11除余3的最小正整數(shù)的算法，畫出流程圖，寫出偽代碼6.利用輾轉(zhuǎn)相除法或更相減損術(shù)求324,243,135的最大公約數(shù).不得用于商業(yè)用途僅供個(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 Zwecken verwendet werden.Pour l ' e tude e