13《算法案例3》（新人教A版必修3）

1、v主講老師 潘學國第三課時第三課時 1、輾轉相除法和更相減損術，是求兩個正、輾轉相除法和更相減損術，是求兩個正整數(shù)的最大公約數(shù)的算法，秦九韶算法是求多整數(shù)的最大公約數(shù)的算法，秦九韶算法是求多項式的值的算法，將這些算法轉化為程序，就項式的值的算法，將這些算法轉化為程序，就可以由計算機來完成相關運算可以由計算機來完成相關運算. 2、人們?yōu)榱擞嫈?shù)和運算方便，約定了各種人們?yōu)榱擞嫈?shù)和運算方便，約定了各種進位制，這些進位制是什么概念，它們與十進進位制，這些進位制是什么概念，它們與十進制之間是怎樣轉化的？對此，我們從理論上作制之間是怎樣轉化的？對此，我們從理論上作些了解和研究些了解和研究. .問題提出問題

2、提出思考思考1:進位制是為了計數(shù)和運算方便而進位制是為了計數(shù)和運算方便而約定的記數(shù)系統(tǒng)，如滿十進一，就是十約定的記數(shù)系統(tǒng)，如滿十進一，就是十進制；每七天為一周，就是七進制；每進制；每七天為一周，就是七進制；每十二個月為一年，就是十二進制，每六十二個月為一年，就是十二進制，每六十秒為一分鐘，每六十分鐘為一個小時，十秒為一分鐘，每六十分鐘為一個小時，就是六十進制；等等就是六十進制；等等.一般地，一般地，“滿滿k進進一一”就是就是k進制，其中進制，其中k稱為稱為k進制的基進制的基數(shù)數(shù).那么那么k是一個什么范圍內的數(shù)？是一個什么范圍內的數(shù)？ 進位制進位制k是大于是大于1的整數(shù)。的整數(shù)。 二進制可使用的

3、數(shù)字有二進制可使用的數(shù)字有0和和1,基數(shù)是基數(shù)是2; 十六進制可使用的數(shù)字或符號有十六進制可使用的數(shù)字或符號有09等等10個數(shù)字個數(shù)字以及以及AF等等6個字母個字母(規(guī)定字母規(guī)定字母AF對應對應1015),十六進十六進制的基數(shù)是制的基數(shù)是16. 計數(shù)時，幾個數(shù)字排成一行，從右起，位數(shù)依次計數(shù)時，幾個數(shù)字排成一行，從右起，位數(shù)依次增大。增大。 注意注意: :為了區(qū)分不同的進位制為了區(qū)分不同的進位制, ,常在數(shù)字的右下常在數(shù)字的右下腳標明基數(shù)腳標明基數(shù),.,. 如如111001111001(2)(2)表示二進制數(shù)表示二進制數(shù),34,34(5)(5)表示表示5 5進制數(shù)進制數(shù). .十進制數(shù)一般不標注

4、基數(shù)十進制數(shù)一般不標注基數(shù).思考思考2:十進制使用十進制使用09十個數(shù)字，那么其它進十個數(shù)字，那么其它進制分別使用哪些數(shù)字？制分別使用哪些數(shù)字？ 思考思考3:在十進制中在十進制中10表示十，在二進制中表示十，在二進制中10表表示示2.一般地，若一般地，若k是一個大于是一個大于1的整數(shù)，則以的整數(shù)，則以k為為基數(shù)的基數(shù)的k進制數(shù)可以表示為一串數(shù)字連寫在一進制數(shù)可以表示為一串數(shù)字連寫在一起的形式：起的形式： anan-1a1a0(k). 其中各個數(shù)位上的數(shù)字其中各個數(shù)位上的數(shù)字an，an-1，a1，a0的取值范圍如何？的取值范圍如何？思考思考4:十進制數(shù)十進制數(shù)3721表示的數(shù)可以寫成表示的數(shù)可以

5、寫成3103+7102+2101+1100，依此類比，依此類比，二進制數(shù)二進制數(shù)110011（2）,八進制數(shù)八進制數(shù) 7342（8）分別可分別可以寫成什么式子？以寫成什么式子？ 110011（2）=125+124+023+022+121+120 7342（8）=783+382+481+280.思考思考5:一般地，如何將一般地，如何將k進制數(shù)進制數(shù)anan-1a1a0(k)寫成各數(shù)位上的數(shù)字與基數(shù)寫成各數(shù)位上的數(shù)字與基數(shù)k的冪的乘積之和的冪的乘積之和的形式？的形式？思考思考6:如何將其它進位制轉化為十進制數(shù)呢？如何將其它進位制轉化為十進制數(shù)呢？0 00 01 11 11 1- -n n1 1-

6、-n nn nn n0 0( (k k) )1 11 1- -n nn nk k a a+ +k k a a+ +. . . .+ +k k a a+ +k k a a= =a a. . . .a aa aa a例例1:把二進制數(shù)把二進制數(shù)110011（2）化為十進制數(shù)。化為十進制數(shù)。 110011（2）=125+124+023+022+121+120 =32+16+2+1=51. 練習：練習：把把C7A16(16)化為十進制數(shù)?；癁槭M制數(shù)。C7A16(16)=12164+7163+10162 +1161+6160.第四步，判斷第四步，判斷in 是否成立是否成立.若是，則輸出若是，則輸出b的

7、的值；否則，返回第三步；值；否則，返回第三步；第一步，輸入第一步，輸入a，k和和n的值；的值；第二步，令第二步，令b=0，i=1；思考思考7:按照上述思路，把按照上述思路，把k進制進制數(shù)數(shù)anan-1a1a0(k)化為十進制數(shù)化為十進制數(shù)b的算法步驟如何設計？的算法步驟如何設計？第三步，第三步， ，i=i+1;1- iikabb+=第五步，輸出第五步，輸出b的值。的值。開始開始輸入輸入a，k，nb=0i=1把把a的右數(shù)第的右數(shù)第i位數(shù)字賦給位數(shù)字賦給tb=b+tki-1i=i+1in?結束結束是是輸出輸出b否否思考思考8:上述把上述把k進進制制anan-1a1a0(k)化為十進制數(shù)化為十進制數(shù)

8、b的算法的程序框的算法的程序框圖如何表示？圖如何表示？思考思考9:該程序框圖對應的程序如何表述？該程序框圖對應的程序如何表述？開始開始輸入輸入a，k，nb=0i=1把把a的右數(shù)第的右數(shù)第i位數(shù)字賦給位數(shù)字賦給tb=b+tki-1i=i+1in?結束結束是是輸出輸出b否否INPUT a，k，nb=0i=1t=a MOD10DOb=b+t*k（i-1）a=a10t=a MOD10i=i+1LOOP UNTIL inPRINT bEND 例例2：將下列各進制數(shù)化為十進制數(shù)將下列各進制數(shù)化為十進制數(shù).（1）10303（4） ； （2）1234（5）.10303（4）=144+342+340=307.1234（5）=153+252+351+450=194. 例例3：已知已知10b1（2）=a02（3）,求數(shù)字求數(shù)字a，b的值的值.所以所以2b+9=9a+2，即，即9a-2b=7. 10b1（2）=123+b2+1=2b+9.a02（3）=a32+2=9a+2.故故a=1，b=1. 課時小結課時小結: : 1. k進制數(shù)使用進制數(shù)使用0（k-1）共）共k個數(shù)字，個數(shù)字，但左側第一個數(shù)位上的數(shù)字（首位數(shù)字）不但左側第一個數(shù)位上的數(shù)字（首位數(shù)字）不為為0.12 1( )n nka aaa-L 2.用用 表示表示k進制數(shù)，其中進制數(shù)，其中k稱為基數(shù)，十