人教版高中數(shù)學全套教案導學案高中數(shù)學 13 算法案例教案 新人教A版必修3

1、1.3 算法案例 整體設計 教學分析 在學生學習了算法的初步知識，理解了表示算法的算法步驟、程序框圖和程序三種不同方式以后，再結合典型算法案例，讓學生經歷設計算法解決問題的全過程，體驗算法在解決問題中的重要作用，體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力. 三維目標 1理解算法案例的算法步驟和程序框圖. 2引導學生得出自己設計的算法程序. 3. 體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力. 重點難點 教學重點：引導學生得出自己設計的算法步驟、程序框圖和算法程序. 教學難點：體會算法的基本思想，提高邏輯思維能力，發(fā)展有條理地思考與數(shù)學表達能力.

2、 課時安排 3課時 教學過程 第1課時 案例1 輾轉相除法與更相減損術 導入新課 思路1（情境導入） 大家喜歡打乒乓球吧，由于東、西方文化及身體條件的不同，西方人喜歡橫握拍打球，東方人喜歡直握拍打球，對于同一個問題，東、西方人處理問題方式是有所不同的.在小學，我們學過求兩個正整數(shù)的最大公約數(shù)的方法：先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是互質數(shù)為止，然后把所有的除數(shù)連乘起來. 當兩個數(shù)公有的質因數(shù)較大時（如 與6 105），使用上述方法求最大公約數(shù)就比較困難.下面我們介紹兩種不同的算法 輾轉相除法與更相減損術,由此可以體會東、西方文化的差異. 思路2（直接導入） 前面我們學習了算法步

3、驟、程序框圖和算法語句.今天我們將通過輾轉相除法與更相減損術來進一步體會算法的思想. 推進新課 新知探究 提出問題 （1）怎樣用短除法求最大公約數(shù)？ （2）怎樣用窮舉法（也叫枚舉法）求最大公約數(shù)？ （3）怎樣用輾轉相除法求最大公約數(shù)？ （4）怎樣用更相減損術求最大公約數(shù)？ 討論結果： （1）短除法 求兩個正整數(shù)的最大公約數(shù)的步驟：先用兩個數(shù)公有的質因數(shù)連續(xù)去除，一直除到所得的商是兩個互質數(shù)為止，然后把所有的除數(shù)連乘起來. （2）窮舉法（也叫枚舉法） 窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，. 直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù)（3）輾轉相

4、除法 輾轉相除法求兩個數(shù)的最大公約數(shù)，其算法步驟可以描述如下： 第一步，給定兩個正整數(shù)m，n. 第二步，求余數(shù)r：計算m除以n，將所得余數(shù)存放到變量r中. 第三步，更新被除數(shù)和余數(shù)：m=n，n=r. 第四步，判斷余數(shù)r是否為0.若余數(shù)為0，則輸出結果；否則轉向第二步繼續(xù)循環(huán)執(zhí)行. 如此循環(huán)，直到得到結果為止. 這種算法是由歐幾里得在公元前300年左右首先提出的，因而又叫歐幾里得算法. （4）更相減損術 我國早期也有解決求最大公約數(shù)問題的算法，就是更相減損術. 九章算術是中國古代的數(shù)學專著，其中的“更相減損術”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，不可半者，副置分母、子之數(shù)，以少減多，

5、更相減損，求其等也.以等數(shù)約之.”翻譯為現(xiàn)代語言如下： 第一步，任意給定兩個正整數(shù)，判斷它們是否都是偶數(shù)，若是，用2約簡；若不是，執(zhí)行第二步. 第二步，以較大的數(shù)減去較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)，繼續(xù)這個操作，直到所得的數(shù)相等為止，則這個數(shù)（等數(shù)）或這個數(shù)與約簡的數(shù)的乘積就是所求的最大公約數(shù). 應用示例 例1 用輾轉相除法求8 251與6 105的最大公約數(shù),寫出算法分析，畫出程序框圖，寫出算法程序. 解：用兩數(shù)中較大的數(shù)除以較小的數(shù)，求得商和余數(shù)：8 251=6 105×1+2 146. 由此可得，6 105與2 146的公約數(shù)也是8 251與6 105的

6、公約數(shù)，反過來，8 251與6 105的公約數(shù)也是6 105與2 146的公約數(shù)，所以它們的最大公約數(shù)相等. 對6 105與2 146重復上述步驟：6 105=2 146×2+1 813. 同理，2 146與1 813的最大公約數(shù)也是6 105與2 146的最大公約數(shù).繼續(xù)重復上述步驟： 2 146=1 813×1+333， 1 813=333×5+148， 333=148×2+37， 148=37×4. 最后的除數(shù)37是148和37的最大公約數(shù)，也就是8 251與6 105的最大公約數(shù). 這就是輾轉相除法.由除法的性質可以知道，對于任意兩個正

7、整數(shù)，上述除法步驟總可以在有限步之后完成，從而總可以用輾轉相除法求出兩個正整數(shù)的最大公約數(shù). 算法分析：從上面的例子可以看出，輾轉相除法中包含重復操作的步驟，因此可以用循環(huán)結構來構造算法. 算法步驟如下： 第一步，給定兩個正整數(shù)m，n. 第二步，計算m除以n所得的余數(shù)為r. 第三步，m=n，n=r. 第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步. 程序框圖如下圖： 程序： INPUT m,n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END 點評：從教學實踐看，有些學生不能理解算法中的轉化過程，例如：求8 251與6 105的最大

8、公約數(shù),為什么可以轉化為求6 105與2 146的公約數(shù).因為8 251=6 105×1+2 146， 可以化為8 251-6 105×1=2 164，所以公約數(shù)能夠整除等式兩邊的數(shù)，即6 105與2 146的公約數(shù)也是8 251與6 105的公約數(shù). 變式訓練 你能用當型循環(huán)結構構造算法，求兩個正整數(shù)的最大公約數(shù)嗎？試畫出程序框圖和程序. 解：當型循環(huán)結構的程序框圖如下圖： 程序： INPUT m，n r=1 WHILE r0 r=m MOD n m=n n=r WEND PRINT m END 例2 用更相減損術求98與63的最大公約數(shù). 解：由于63不是偶數(shù)，把98和

9、63以大數(shù)減小數(shù)，并輾轉相減，如下圖所示. 98-63=5 63-35=28 35-28=7 28-7=21 21-7=14 14-7=7 所以，98和63的最大公約數(shù)等于7. 點評：更相減損術與輾轉相除法的比較：盡管兩種算法分別來源于東、西方古代數(shù)學名著，但是二者的算理卻是相似的，有異曲同工之妙主要區(qū)別在于輾轉相除法進行的是除法運算，即輾轉相除；而更相減損術進行的是減法運算，即輾轉相減，但是實質都是一個不斷的遞歸過程 變式訓練 用輾轉相除法或者更相減損術求三個數(shù)324,243,135的最大公約數(shù). 解：324=243×181， 243=81×30， 則324與243的最大

10、公約數(shù)為81. 又135=81×154，81=54×127， 54=27×20， 則 81 與 135的最大公約數(shù)為27. 所以,三個數(shù)324、243、135的最大公約數(shù)為27. 另法：324243=81,24381=162,16281=81，則324與243的最大公約數(shù)為81. 13581=54,8154=27,5427=27，則81與135的最大公約數(shù)為27. 所以，三個數(shù)324、243.135的最大公約數(shù)為27. 例3 （1）用輾轉相除法求123和48的最大公約數(shù). （2）用更相減損術求80和36的最大公約數(shù). 解：（1）輾轉相除法求最大公約數(shù)的過程如下：

11、1232×4827， 481×2721， 271×216， ，33×62162×3+0， 最后6能被3整除，得123和48的最大公約數(shù)為3. （2）我們將80作為大數(shù)，36作為小數(shù)，因為80和36都是偶數(shù)，要除公因數(shù)2. 80÷2=40，36÷2=18. 40和18都是偶數(shù)，要除公因數(shù)2. 40÷2=20，18÷2=9. 下面來求20與9的最大公約數(shù)， 209=11， 119=2， 92=7， 72=5， 52=3， 32=1， 21=1， 2可得80和36的最大公約數(shù)為2×1=4. 點評：對比

12、兩種方法控制好算法的結束，輾轉相除法是到達余數(shù)為0，更相減損術是到達減數(shù)和差相等. 變式訓練 分別用輾轉相除法和更相減損術求1 734，816的最大公約數(shù) 解：輾轉相除法： 1 734=816×2+102，816=102×8（余0）， 1 734與816的最大公約數(shù)是102 更相減損術：因為兩數(shù)皆為偶數(shù)，首先除以2得到867，408，再求867與408的最大公約數(shù) 867-408=459， 459-408=51， 408-51=357， 357-51=306， 306-51=255， 255-51=204， 204-51=153， 153-51=102， 102-51=51

13、. 1 734與816的最大公約數(shù)是51×2=102 利用更相減損術可另解： 1 734816918， 918816102， 816102714， 714102612， 612102510， 510102408， 408102306， 306102204， 102. 1022041 734與816的最大公約數(shù)是102 知能訓練 求319，377，116的最大公約數(shù) 解：377=319×1+58， 319=58×5+29， 58=29×2. 377與319的最大公約數(shù)為29，再求29與116的最大公約數(shù) 116=29×4. 29與116的最大公約

14、數(shù)為29. 377，319，116的最大公約數(shù)為29. 拓展提升 試寫出利用更相減損術求兩個正整數(shù)的最大公約數(shù)的程序 解：更相減損術程序： INPUT “m，n=”；m，n WHILE m<>n IF m>n THEN m-n ELSE m=n-m END IF WEND PRINT m END 課堂小結 （1）用輾轉相除法求最大公約數(shù). （2）用更相減損術求最大公約數(shù). 思想方法：遞歸思想. 作業(yè) 分別用輾轉相除法和更相減損術求261，319的最大公約數(shù). 分析：本題主要考查輾轉相除法和更相減損術及其應用使用輾轉相除法可依據m=nq+r，反復執(zhí)行，直到r=0為止；用更相減損

15、術就是根據m-n=r，反復執(zhí)行，直到n=r為止 解：輾轉相除法： 319=261×1+58, 261=58×4+29, 58=29×2. 319與261的最大公約數(shù)是29 更相減損術： 319-261=58, 261-58=203, 203-58=145, 145-58=87, 87-58=29, 58-29=29, 29的最大公約數(shù)是261與319設計感想 數(shù)學不僅是一門科學，也是一種文化，本節(jié)的引入從東、西方文化的不同開始，逐步向學生滲透數(shù)學文化.從知識方面主要學習用兩種方法求兩個正整數(shù)的最大公約數(shù)，從思想方法方面，主要學習遞歸思想.本節(jié)設置精彩例題，不僅讓學

16、生學到知識，而且讓學生進一步體會算法的思想，培養(yǎng)學生的愛國主義情操 第2課時 案例2 秦九韶算法 導入新課 思路1（情境導入） 大家都喜歡吃蘋果吧，我們吃蘋果都是從外到里一口一口的吃，而蟲子卻是先鉆到蘋果里面從里到外一口一口的吃，由此看來處理同一個問題的方法多種多樣.怎樣求多項式5432f(x)=x+x+x+x+x+1當x=5時的值呢？方法也是多種多樣的，今天我們開始學習秦九韶算法. 思路2（直接導入） 前面我們學習了輾轉相除法與更相減損術， 今天我們開始學習秦九韶算法. 推進新課 新知探究 提出問題 5432（1）求多項式f(x)=x+x+x+x+x+1當x=5時的值有哪些方法？比較它們的特

17、點. （2）什么是秦九韶算法？ （3）怎樣評價一個算法的好壞？ 討論結果： 5432（1）怎樣求多項式f(x)=x+x+x+x+x+1當x=5時的值呢？ 一個自然的做法就是把5代入多項式f(x)，計算各項的值，然后把它們加起來，這時，我們一共做了1+2+3+4=10次乘法運算，5次加法運算. 2222 另一種做法是先計算x的值，然后依次計算x·x，（x·x）·x，（x·x）·x）·x的值，這樣每次都可以利用上一次計算的結果，這時，我們一共做了4次乘法運算，5次加法運算. 第二種做法與第一種做法相比，乘法的運算次數(shù)減少了，因而能夠提高運

18、算效率，對于計算機來說，做一次乘法運算所用的時間比做一次加法運算要長得多，所以采用第二種做法，計算機能更快地得到結果. （2）上面問題有沒有更有效的算法呢？我國南宋時期的數(shù)學家秦九韶（約12021261）在他的著作數(shù)書九章中提出了下面的算法： nn-1 把一個n次多項式f(x)=ax+ax+ax+a改寫成如下形式： 01n-1nnn-1f(x)=ax+ax+ax+a 01n-1nn-1n-2=（ax+ax+a）x+ a 01n-1nn-2n-3=（ax+ax+a）x+a)x+a 02n-1n1= =（ax+a）x+a）x+a）x+a. 0n-1n-21n求多項式的值時，首先計算最內層括內一次多

19、項式的值，即 v=ax+a， n-11n然后由內向外逐層計算一次多項式的值，即 v=vx+a， n-212v=vx+a， n-323 v=vx+a， 0n-1n這樣，求n次多項式f（x）的值就轉化為求n個一次多項式的值. 上述方法稱為秦九韶算法.直到今天，這種算法仍是多項式求值比較先進的算法. （3）計算機的一個很重要的特點就是運算速度快，但即便如此，算法好壞的一個重要標志仍然是運算的次數(shù).如果一個算法從理論上需要超出計算機允許范圍內的運算次數(shù)，那么這樣的算法就只能是一個理論的算法. 應用示例 5432例1 已知一個5次多項式為f（x）=5x+2x+3.5x-2.6x+1.7x-0.8， 用秦

20、九韶算法求這個多項式當x=5時的值. 解：根據秦九韶算法，把多項式改寫成如下形式： f(x)=（(5x+2)x+3.5)x-2.6)x+1.7)x-0.8， 按照從內到外的順序，依次計算一次多項式當x=5時的值： v=5； 0v=5×5+2=27; 1v=27×5+3.5=138.5; 2v=138.5×5-2.6=689.9; 3v=689.9×5+1.7=3 451.2; 4v=3 415.2×5-0.8=17 255.2; 5所以，當x=5時，多項式的值等于17 255.2. 算法分析：觀察上述秦九韶算法中的n個一次式，可見v的計算要用到

21、v的值，若令v=a，nkk-10我們可以得到下面的公式： v?a,?n0 ?v?vx?a(k?1,2,n).?kk?k1n?這是一個在秦九韶算法中反復執(zhí)行的步驟，因此可用循環(huán)結構來實現(xiàn). 算法步驟如下： 第一步，輸入多項式次數(shù)n、最高次的系數(shù)a和x的值. n第二步，將v的值初始化為a，將i的值初始化為n-1. n第三步，輸入i次項的系數(shù)a. i第四步，v=vx+a,i=i-1. i第五步，判斷i是否大于或等于0.若是，則返回第三步；否則，輸出多項式的值v. 程序框圖如下圖： 程序： INPUT “n=”；n INPUT “an=”；a INPUT “x=”；x v=a i=n-1 WHILE

22、i=0 PRINT “i=”；i INPUT “ai=”；a v=v*x+a i=i-1 WEND PRINT v END 點評：本題是古老算法與現(xiàn)代計算機語言的完美結合，詳盡介紹了思想方法、算法步驟、程序框圖和算法語句,是一個典型的算法案例. 變式訓練 請以5次多項式函數(shù)為例說明秦九韶算法，并畫出程序框圖. 5432解：設f（x）=ax+ax+ax+ax+ax+a 032415首先，讓我們以5次多項式一步步地進行改寫： 432f（x）=（ax+ax+ax+ax+a）x+a 05234132=（ax+ax+ ax+a）x+a）x+a 0235142=（ax+ax+ a）x+a）x+a）x+a

23、051243=（ax+a）x+ a）x+a）x+a）x+a. 054132上面的分層計算,只用了小括，計算時，首先計算最內層的括，然后由里向外逐層計算，直到最外層的括，然后加上常數(shù)項即可. 程序框圖如下圖： kxn-1n，（k=2，xP(x)=ax+a+ax+a，如果在一種算法中，計算3例2 已知n次多項式nnn-10104，n）的值需要k1次乘法，計算P(x)的值共需要9次運算（6次乘法，3次加法），03那么計算P(x)的值共需要_次運算.下面給出一種減少運算次數(shù)的算法：010P(x)=a,P(x)=xP(x)+a（k0，1，2，n1）利用該算法，計算P(x)的值共需0k+1k+130k0要

24、6次運算，計算P(x)的值共需要_次運算. 010答案：65 20 nn-1點評：秦九韶算法適用一般的多項式f(x)=ax+ax+ax+a的求值問題.直接法乘法運0n-1n1(n?1)n，加法最多n次.算的次數(shù)最多可到達秦九韶算法通過轉化把乘法運算的次數(shù)減少 2到最多n次，加法最多n次. 5432例3 已知多項式函數(shù)f(x)=2x5x4x+3x6x+7，求當x=5時的函數(shù)的值. 5432解析：把多項式變形為：f(x)=2x5x4x+3x6x+7 =(2x5)x4)x+3)x6)x+7. 計算的過程可以列表表示為： 最后的系數(shù)2 677即為所求的值. 算法過程： v=2； 0v=2×5

25、5=5； 1v=5×54=21； 2v=21×5+3=108； 3v=108×56=534； 4v=534×5+7=2 677. 5點評：如果多項式函數(shù)中有缺項的話，要以系數(shù)為0的項補齊后再計算. 知能訓練 5432當x=2時，用秦九韶算法求多項式f(x)=3x+8x-3x+5x+12x-6的值 解法一：根據秦九韶算法，把多項式改寫成如下形式： f(x)=(3x+8)x-3)x+5)x+12）x-6. 按照從內到外的順序，依次計算一次多項式當x=2時的值. v=3; 0v=v×2+8=3×2+8=14; 01v=v-3=25; 3=1

26、4×2-×212v=v×2+5=25×2+5=55; 23v=v×2+12=55×2+12=122; 34v=v×2-6=122×2-6=238. 45當x=2時，多項式的值為238. 解法二：f(x)=(3x+8)x-3)x+5)x+12）x-6， 則f(2)=(3×2+8)×23)×2+5)×2+12)×26238 拓展提升 765432 用秦九韶算法求多項式f(x)=7x+6x+5x+4x+3x+2x+x當x=3時的值. 解：f(x)=(7x+6)+5)x+4

27、)x+3)x+2)x+1)x v=7； 0v=7×3+6=27； 1v=27×3+5=86； 2v=86×3+4=262； 3v=262×3+3=789； 4v=789×3+2=2 369； 5v=2 369×3+1=7 108； 6v=7 108×3+0=21 324. 7f(3)=21 324. 課堂小結 1.秦九韶算法的方法和步驟. 2.秦九韶算法的計算機程序框圖. 作業(yè) 32已知函數(shù)f(x)=x2x5x+8,求f(9)的值. 322解：f(x)=x2x5x+8=(x2x5)x+8=(x2)x5)x+8 f(9)=(9

28、2)×95)×9+8=530. 設計感想 古老的算法散發(fā)濃郁的現(xiàn)代氣息，這是一節(jié)充滿智慧的課.本節(jié)主要介紹了秦九韶算法. 通過對秦九韶算法的學習，對算法本身有哪些進一步的認識？ 教師引導學生思考、討論、概括，小結時要關注如下幾點：（1）算法具有通用的特點，可以解決一類問題；（2）解決同一類問題，可以有不同的算法，但計算的效率是不同的，應該選擇高效的算法；（3）算法的種類雖多，但三種邏輯結構可以有效地表達各種算法等等. 第3課時 案例3 進位制 導入新課 情境導入 在日常生活中，我們最熟悉、最常用的是十進制，據說這與古人曾以手指計數(shù)有關，愛好天文學的古人也曾經采用七進制、十二

29、進制、六十進制，至今我們仍然使用一周七天、一年十二個月、一小時六十分的歷法.今天我們來學習一下進位制. 推進新課 新知探究 提出問題 （1）你都了解哪些進位制？ （2）舉出常見的進位制. （3）思考非十進制數(shù)轉換為十進制數(shù)的轉化方法. . ）思考十進制數(shù)轉換成非十進制數(shù)及非十進制之間的轉換方法4（活動：先讓學生思考或討論后再回答，經教師提示、點撥，對回答正確的學生及時表揚，對回答不準確的學生提示引導考慮問題的思路 討論結果： （1）進位制是人們?yōu)榱擞嫈?shù)和運算方便而約定的計數(shù)系統(tǒng)，約定滿二進一，就是二進制；滿十進一，就是十進制；滿十二進一，就是十二進制；滿六十進一，就是六十進制等等.也就是說：“

30、滿幾進一”就是幾進制，幾進制的基數(shù)（都是大于1的整數(shù)）就是幾. （2）在日常生活中，我們最熟悉、最常用的是十進制，據說這與古人曾以手指計數(shù)有關，愛好天文學的古人也曾經采用七進制、十二進制、六十進制，至今我們仍然使用一周七天、一年十二個月、一小時六十分的歷法. （3）十進制使用09十個數(shù)字.計數(shù)時，幾個數(shù)字排成一行，從右起，第一位是個位，個位上的數(shù)字是幾，就表示幾個一；第二位是十位，十位上的數(shù)字是幾，就表示幾個十；接著依次是百位、千位、萬位 例如：十進制數(shù)3 721中的3表示3個千，7表示7個百，2表示2個十，1表示1個一.于是，我們得到下面的式子： 32103 721=3×10+7&

31、#215;10+2×10+1×10. 與十進制類似，其他的進位制也可以按照位置原則計數(shù).由于每一種進位制的基數(shù)不同，所用的數(shù)字個數(shù)也不同.如二進制用0和1兩個數(shù)字，七進制用06七個數(shù)字. 一般地，若k是一個大于1的整數(shù)，那么以k為基數(shù)的k進制數(shù)可以表示為一串數(shù)字連寫在一起的形式 aaaa（k）（0ak，0a，a，ak). 0n-1n-1101nn其他進位制的數(shù)也可以表示成不同位上數(shù)字與基數(shù)的冪的乘積之和的形式，如 543210110 011=1×2+1×2+0×2+0×2+1×2+1×2， ）（232107 342

32、=7×8+3×8+4×8+2×8. ）8（非十進制數(shù)轉換為十進制數(shù)比較簡單，只要計算下面的式子值即可： nn-1aaaa=a×k+a×k+a×k+a. 010(k)1n-1nn-1n第一步：從左到右依次取出k進制數(shù)aaaa(k)各位上的數(shù)字，乘以相應的k的冪，k0n-1n1nn-10的冪從n開始取值，每次遞減1，遞減到0，即a×k,a×k,a×k,a×k； 01n-1n第二步：把所得到的乘積加起來，所得的結果就是相應的十進制數(shù). （4）關于進位制的轉換，教科書上以十進制和二進制之間的轉

33、換為例講解，并推廣到十進制和其他進制之間的轉換.這樣做的原因是，計算機是以二進制的形式進行存儲和計算數(shù)據的，而一般我們傳輸給計算機的數(shù)據是十進制數(shù)據，因此計算機必須先將十進制數(shù)轉換為二進制數(shù)，再處理，顯然運算后首次得到的結果為二進制數(shù)，同時計算機又把運算結果由二進制數(shù)轉換成十進制數(shù)輸出. 1°十進制數(shù)轉換成非十進制數(shù) 把十進制數(shù)轉換為二進制數(shù)，教科書上提供了“除2取余法”，我們可以類比得到十進制數(shù)轉換成k進制數(shù)的算法“除k取余法”. 2°非十進制之間的轉換 一個自然的想法是利用十進制作為橋梁.教科書上提供了一個二進制數(shù)據與16進制數(shù)據之間的互化的方法，也就是先由二進制數(shù)轉化

34、為十進制數(shù)，再由十進制數(shù)轉化成為16進制數(shù). 應用示例 思路1 例1 把二進制數(shù)110 011化為十進制數(shù). (2)543210解：110 011=1×2+1×2+0×2+0×2+1×2+1×2=1×32+1×16+1×2+1=51. (2)再按照十進制的運算規(guī)的冪的乘積之和的形式，2先把二進制數(shù)寫成不同位上數(shù)字與點評：則計算出結果. 變式訓練 設計一個算法，把k進制數(shù)a（共有n位）化為十進制數(shù)b. i-1算法分析：從例1的計算過程可以看出，計算k進制數(shù)a的右數(shù)第i位數(shù)字a與k的乘積ii-1a·

35、k，再將其累加，這是一個重復操作的步驟.所以，可以用循環(huán)結構來構造算法. i 算法步驟如下： 第一步，輸入a，k和n的值. 第二步，將b的值初始化為0，i的值初始化為1. i-1第三步，b=b+a·k，i=i+1. i第四步，判斷in是否成立.若是，則執(zhí)行第五步；否則，返回第三步. 第五步，輸出b的值. 程序框圖如下圖： 程序： INPUT “a,k，n=”；a，k，n b=0 i=1 t=a MOD 10 DO b=b+t*k（i-1） a=a10 t=a MOD 10 i=i+1 LOOP UNTIL in PRINT b END 例2 把89化為二進制數(shù). 解：根據二進制數(shù)“滿

36、二進一”的原則，可以用2連續(xù)去除89或所得商，然后取余數(shù).具體計算方法如下： 因為89=2×44+1，44=2×22+0， ×11+0，22=211=2×5+1， 5=2×2+1， 2=2×1+0， 1=2×0+1， 所以 89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1 2=2×（2×（2×（2×（2+1）+1）+0）+0）+1 6543210=1×2+0×2+1×2+1×2+0×2+0×2+1×2 =1 011 001. (2)這種算法叫做除2取余法，還可以用下面的除法算式表示： 把上式中各步所得的余數(shù)從下到上排列，得到89=1 011 001. (2)上述方法也可以推廣為把十進制數(shù)化為k進制數(shù)的算法，稱為除k取余法. 變式訓練 設計一個程序，實現(xiàn)“除k取余法”. 算法分析：從例2的計算過程可以看出如下的規(guī)律： 若十制數(shù)a除以k所得商是q，余數(shù)是r，即a=k·q+r，則r是a的k進制數(shù)的右