陜西省西安市第六十六中學(xué)高三數(shù)學(xué)總復(fù)習(xí) 13.3 算法案例教學(xué)案 新人教版必修1.doc

133 算法案例一、知識導(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ù)運算，直到余數(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)是負數(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ù)值的符號進行多次循環(huán)判定，故需要選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，即可用goto 語句和條件語句實現(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錯解：根據(jù)表示不超過的整數(shù)部分, 表示除以所得的余數(shù),選擇b.錯因:對表示的含義理解不透徹,將不超過-0.05的整數(shù)錯認為是0,將負數(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ù).試用流程圖和偽代碼表示這一算法.解：流程圖為： 偽代碼為：10 20 30 if then goto 2040 if then print goto 8050 end if60 70 goto 4080 end 點評：這是孫子思想的體現(xiàn)，主要是依次滿足三個整除條件.例4分別用輾轉(zhuǎn)相除法、更相減損法求192與81的最大公約數(shù).解：輾轉(zhuǎn)相除法： s1 s2 s3 s4 s5 故3是192 與81 的最大公約數(shù).更相減損法：s1 s2 s3 s4 s5 s6 s7 s8 s9 故3 是192與81的最大公約數(shù).點評：輾轉(zhuǎn)相除法以除法為主，更相減損術(shù)以減法為主，計算次數(shù)上輾轉(zhuǎn)相除法計算次數(shù)相對較少.輾轉(zhuǎn)相除法是當(dāng)大數(shù)被小數(shù)整除時停止除法運算，此時的小數(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 20 30 40 50 if then goto 12060 if then70 100 end if80 else90 100 end if110 if then goto 20120 print 130 end 點評：二分法的基本思想在必修一中已滲透，這里運用算法將二分法求方程近似解的步驟更清晰的表述出來.例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ù)為（ ）.a1次 b.2次 c.3次 d.5次3下面程序功能是統(tǒng)計隨機產(chǎn)生的十個兩位正整數(shù)中偶數(shù)和奇數(shù)的個數(shù)，并求出偶數(shù)與奇數(shù)各自的總和.for i from 1 to 10 print x; if then else end ifend forprintprint “奇數(shù)個數(shù)=”； ，“偶數(shù)個數(shù)=”；4若一個數(shù)的各因子之和正好等于該數(shù)本身，則該數(shù)成為完數(shù).請補充完整下列找出1100之間的所有完數(shù)的偽代碼.for from 2 to 100for b from 2 to if