示范教案13算法案例-資料下載頁
2024-11-24 20:10本頁面
【導讀】東方人喜歡直握拍打球，對于同一個問題，東、西方人處理問題方式是有所不同的.在小學，輾轉相除法與更相減損術,由此可以體會東、西方文化的差異.怎樣用短除法求最大公約數(shù)？窮舉法求兩個正整數(shù)的最大公約數(shù)的解題步驟：從兩個數(shù)中較小數(shù)開始由大到小列舉，直到找到公約數(shù)立即中斷列舉，得到的公約數(shù)便是最大公約數(shù).代的數(shù)學專著，其中的“更相減損術”也可以用來求兩個數(shù)的最大公約數(shù)，即“可半者半之，的公約數(shù)也是6105與2146的公約數(shù)，所以它們的最大公約數(shù)相等.最后的除數(shù)37是148和37的最大公約數(shù)，也就是8251與6105的最大公約數(shù).所以，98和63的最大公約數(shù)等于7.但是二者的算理卻是相似的，有異曲同工之妙．主要區(qū)別在于輾轉相除法進行的是除法運算，另法：324－243=81,243－81=162,162－81=81，則324與243的最大公約數(shù)為81.
【正文】 十進制 數(shù)轉換成非十進制數(shù) 把十進制數(shù)轉換為二進制數(shù)，教科書上提供了 “除 2取余法 ”，我們可以類比得到十進制數(shù)轉換成 k進制數(shù)的算法 “除 k取余法 ”. 2176。 非十進制之間的轉換 一個自然的想法是利用十進制作為橋梁 .教科書上提供了一個二進制數(shù)據(jù)與 16進制數(shù)據(jù)之間的互化的方法，也就是先由二進制數(shù)轉化為十進制數(shù)，再由十進制數(shù)轉化成為 16進制數(shù) . 應用示例 思路 1 例 1 把二進制數(shù) 110 011(2)化為十進制數(shù) . 解： 110 011(2)=125+124+023+022+121+120=132+116+12+1=51. 點評： 先把二進制數(shù)寫成不同位上數(shù)字與 2的冪的乘積之和的形式，再按照十進制的運算規(guī)則計算出結果 . 變式訓練 設計一個算法，把 k進制數(shù) a（共有 n位）化為十進制數(shù) b. 算法分析： 從例 1 的計算過程可以看出，計算 k 進制數(shù) a 的右數(shù)第 i位數(shù)字 ai與 ki1的乘積aik i1，再將其累加，這是一個重復操作的步驟 .所以，可以用循環(huán)結構來構造算法 . 算法步驟如下： 第一步，輸入 a， k和 n的值 . 第二步，將 b的值初始化為 0， i的值初始化為 1. 第三步， b=b+aik i1， i=i+1. 第四步，判斷 i＞ n是否成立 .若是，則執(zhí)行第五步；否則，返回第三步 . 第五步，輸出 b的值 . 程序框圖如下圖 ： 程序： INPUT “a,k， n=”； a， k， n b=0 i=1 t=a MOD 10 DO b=b+t*k^（ i1） a=a\\10 t=a MOD 10 i=i+1 LOOP UNTIL i＞ n PRINT b END 例 2 把 89化為二進制數(shù) . 解： 根據(jù)二進制數(shù) “滿二進一 ”的原則，可以用 2連續(xù)去除 89或所得商，然后取余數(shù) .具體計算方法如下： 因為 89=244+1， 44=222+0， 22=211+0， 11=25+1， 5=22+1， 2=21+0， 1=20+1， 所以 89=2（ 2（ 2（ 2（ 22+1） +1） +0） +0） +1 =2（ 2（ 2（ 2（ 22+1） +1） +0） +0） +1 =…=12 6+025+124+123+022+021+120 =1 011 001(2). 這種算法叫做除 2取余法，還可以用下面的除法算式表示： 把上式中各步所得的余數(shù)從下到上排列，得到 89=1 011 001(2). 上述方法也可以推廣為把十進制數(shù)化為 k進制數(shù)的算法 ，稱為除 k取余法 . 變式訓練 設計一個程序，實現(xiàn) “除 k取余法 ”. 算法分析： 從例 2的計算過程可以看出如下的規(guī)律： 若十制數(shù) a除以 k所得商是 q0，余數(shù)是 r0，即 a=kq0+r0，則 r0是 a 的 k進制數(shù)的右數(shù)第 1位數(shù) . 若 q0除以 k所得的商是 q1，余數(shù)是 r1，即 q0=kq1+r1，則 r1是 a的 k進制數(shù)的左數(shù)第 2位數(shù) . …… 若 qn1除以 k所得的商是 0，余數(shù)是 rn，即 qn1=rn，則 rn是 a的 k進制數(shù)的左數(shù)第 1位數(shù) . 這樣，我們可以得到算法步驟如下： 第一步，給定十進制正整數(shù) a和轉化后的數(shù)的基數(shù) k. 第二步，求出 a除以 k所得的商 q，余數(shù) r. 第三步，把得到的余數(shù)依次從右到左排列 . 第四步，若 q≠0，則 a=q，返回第二步；否則，輸出全部余數(shù) r排列得到的 k進制數(shù) . 程序框圖如下圖： 程序： INPUT “a， k=”； a， k b=0 i=0 DO q=a\\k r=a MOD k b=b+r*10^i i=i+1 a=q LOOP UNTIL q=0 PRINT b END 思路 2 例 1 將 8進制數(shù) 314 706(8)化為十進制數(shù)，并編寫出一個實現(xiàn)算法的程序 . 解： 314 706(8)=385+184+483+782+081+680=104 902. 所以，化為十進制數(shù)是 104 902. 點評： 利用把 k進制數(shù)轉化為十進制數(shù)的一般方法就可以把 8進制數(shù) 314 706(8)化為十進制數(shù) . 例 2 把十進制數(shù) 89化為三進制數(shù)，并寫出程序語句 . 解： 具體的計算方法如下： 89=329+2， 29=39+2， 9=33+0， 3=31+0， 1=30+1， 所以 :89(10)=10 022(3). 點評： 根據(jù)三進制數(shù)滿三進一的原則，可以用 3連續(xù)去除 89 及其所得的商，然后按倒序的順序取出余數(shù)組成數(shù)據(jù)即可 . 知能訓練 將十進制數(shù) 34轉化為二進制數(shù)． 分析： 把一個十進制數(shù)轉換成二進制數(shù)，用 2反復去除這個十進制數(shù)，直到商為 0，所得余數(shù)（從下往上讀）就是所求． 解： 即 34(10)=100 010(2) 拓展提升 把 1 234(5)分別轉化為十進制數(shù)和八進制數(shù)． 解： 1 234(5)=153+252+35+4＝ 194． 則 1 234(5)=302(8) 所以， 1 234(5)=194＝ 302(8) 點評： 本題主要考查進位制以及不同進位制數(shù)的互化．五進制數(shù)直接利用公式就可以轉化為 十進制數(shù)；五進制數(shù)和八進制數(shù)之間需要借助于十進制數(shù)來轉化． 課堂小結 （ 1）理解算法與進位制的關系 . （ 2）熟練掌握各種進位制之間轉化 . 作業(yè) 習題 4. 設計感想 計算機是以二進制的形式進行存儲和計算數(shù)據(jù)的，而一般我們傳輸給計算機的數(shù)據(jù)是十進制數(shù)據(jù)，因此計算機必須先將十進制數(shù)轉換為二進制數(shù)，再處理，顯然運算后首次得到的結果為二進制數(shù)，同時，計算機又把運算結果由二進制數(shù)轉換成十進制數(shù)輸出 .因此學好進位制是非常必要的，另外，進位制也是高考的重點，本節(jié)設置了多種題型供學生訓練，所以這節(jié)課非常實用 .
教學課件相關推薦
鄂ICP備17016276號-1