必修3-1.3算法案例算法案例（一）輾轉相除法&更相減損術知識回顧思考：（1）57與120的最大公約數是多少？你是怎樣得到的？你的方法可以一般化嗎？（2）8251與6105的最大公因數呢？

知識回顧舊方法：先用兩個數公有的質因數連續去除，一直除到所得的商是互質數為止，然后把所有的除數連乘起來即為最大公約數.有沒有什么新方法？對8251與6105這兩個數：進行以下步驟2146÷1813=1…333，148÷37=4…0.333÷148=2…37，1813÷333=5…148，6105÷2146=2…1813，8251÷6105=1…214637為8251與6105的最大公因數！上述求兩個正整數的最大公約數的方法稱為輾轉相除法或歐幾里得算法.一般地，用輾轉相除法求兩個正整數m，n的最大公約數，可以用什么邏輯結構來構造算法？其算法步驟如何設計？

第一步，給定兩個正整數m，n(m>n).第二步，計算m除以n所得的余數r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數等于m；否則，返回第二步.

思考:該算法的程序框圖如何表示？開始輸入m，n求m除以n的余數rm=nn=rr=0？是輸出m結束否知識:更相減損術

思考1:求98與63的最大公約數為多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，“更相減損術”在中國古代數學專著《九章算術》中記述為：

可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也，以等數約之.

例1分別用輾轉相除法和更相減損術求168與93的最大公約數.輾轉相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.更相減損術:168-93=75，93-75=18，75-18=57，57-18=39，39-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.例2.求325，130，270三數的最大公約數

因為325=130×2+65，130=65×2，所以325與130的最大公約數是65.

因為270=65×4+10，65=10×6+5，10=5×2，所以65與270最大公約數是5.故325，130，270三個數的最大公約數是5.1.輾轉相除法，就是對于給定的兩個正整數，用較大的數除以較小的數，若余數不為零，則將余數和較小的數構成新的一對數，繼續上面的除法，直到大數被小數除盡為止，這時的較小的數即為原來兩個數的最大公約數.

小結小結2.更相減損術，就是對于給定的兩個正整數，用較大的數減去較小的數，然后將差和較小的數構成新的一對數，繼續上面的減法，直到差和較小的數相等，此時相等的兩數即為原來兩個數的最大公約數.算法案例2秦九韶算法思考:對于多項式f(x)=x5+x4+x3+x2+x+1，求f(5)的值.若先計算各項的值，然后再相加，那么一共要做多少次乘法運算和多少次加法運算？4+3+2+1=10次乘法運算，5次加法運算.思考:利用后一種算法求多項式f(x)=anxn+an-1xn-1+…+a1x+a0的值，這個多項式應寫成哪種形式？f(x)=anxn+an-1xn-1+…+a1x+a0=(anxn-1+an-1xn-2+…+a2x+a1)x+a0=((anxn-2+an-1xn-3+…+a2)x+a1)x+a0=…=(…((anx+an-1)x+an-2)x+…+a1)x+a0.思考:在上述問題中，若先計算x2的值，然后依次計算x2·x，(x2·x)·x，((x2·x)·x)·x的值，這樣每次都可以利用上一次計算的結果，再將這些數與x和1相加，那么一共做了多少次乘法運算和多少次加法運算？

4次乘法運算，5次加法運算.思考:對于f(x)=(…((anx+an-1)x+an-2)x+…+a1)x+a0，由內向外逐層計算一次多項式的值，其算法步驟如何？

第一步，計算v1=anx+an-1.第二步，計算v2=v1x+an-2.第三步，計算v3=v2x+an-3.

…第n步，計算vn=vn-1x+a0.思考:上述求多項式f(x)=anxn+an-1xn-1+…+a1x+a0的值的方法稱為秦九韶算法，利用該算法求f(x0)的值，一共需要多少次乘法運算，多少次加法運算？

思考:在秦九韶算法中，記v0=an，那么第k步的算式是什么？

vk=vk-1x+an-k(k=1，2，…，n)秦九韶算法的程序設計

思考1:用秦九韶算法求多項式的值，可以用什么邏輯結構來構造算法？其算法步驟如何設計？第一步，輸入多項式的次數n，最高次

項的系數an和x的值.

第二步，令v=an，i=n-1.

第三步，輸入i次項的系數ai.第四步，v=vx+ai，i=i-1.第五步，判斷i≥0是否成立.若是，則返回第

二步；否則，輸出多項式的值v.思考2:該算法的程序框圖如何表示？開始輸入n，an，x的值v=anv=vx+ai輸入aii≥0？i=n-1i=i-1結束是輸出v否理論遷移

練習：用秦九韶算法求f(5)的值.f(x)=((((5x+2)x+3.5)x-2.6)x+1.7)x-0.8.v1=5×5+2=27；v2=27×5+3.5=138.5；v3=138.5×5-2.6=689.9；v4=689.9×5+1.7=3451.2；v5=3451.2×5-0.8=17255.2.所以f(5)==17255.2.算法案例3K進位制知識探究(一):進位制的概念

進位制是為了計數和運算方便而約定的記數系統。你知道生活中有哪些進位制嗎？如逢十進一，就是十進制；每七天為一周，就是七進制；每十二個月為一年，就是十二進制；每六十秒為一分鐘，每六十分鐘為一個小時，就是六十進制；等等.一般地，“滿k進一”就是k進制，其中k稱為k進制的基數.問：k是一個什么范圍內的數？

思考:十進制使用0～9十個數字，那么二進制、五進制、七進制分別需要使用哪些數字？

思考:在十進制中10表示十，

在二進制中10表示2.一般地，若k是一個大于1的整數，則以k為基數的k進制數可以表示為一串數字連寫在一起的形式：

anan-1…a1a0(k).其中各個數位上的數字an，an-1，…，a1，a0的取值范圍如何？意義是什么？思考:十進制數4528表示的數可以寫成4×103+5×102+2×101+8×100，依此類比，二進制數110011（2）,八進制數7342（8）分別可以寫成什么式子？

110011（2）=1×25+1×24+0×23+0×22+1×21+1×20

7342（8）=7×83+3×82+4×81+2×80.結論:一般地，如何將k進制數anan-1…a1a0(k)寫成各數位上的數字與基數k的冪的乘積之和的形式？（十進制）思考:在二進制中，0+0，0+1，1+0，1+1值分別是多少？知識探究(二):k進制化十進制的算法

思考:二進制數110011（2）化為十進制數是什么數？

110011（2）=1×25+1×24+0×23+0×22+1×21+1×20=32+16+2+1=51.知識探究(二):k進制化十進制的算法

結論：二進制數右數第i位數字ai化為十進制數是

問題：運用以下循環結構，設計算法把二進制數

化為十進制數b？第二步，令b=0，i=1.第四步，判斷i>n是否成立.若是，則輸

出b的值；否則，返回第三步.第一步，輸入a和n的值.第三步，

，i=i+1.同樣地，把k進制數

化為十進制數b的算法和程序框圖如何設計？第四步，判斷i>n是否成立.

若是，則輸出b的值；

否則，返回第三步.第一步，輸入a，k和n的值.第二步，令b=0，i=1.第三步，

，i=i+1.程序框圖：開始輸入a，k，nb=0i=1把a的右數第i位數字賦給tb=b+t·ki-1i=i+1i>n?結束是輸出b否

例1將下列各進制數化為十進制數.（1）10303（4）

；

（2）1234（5）.理論遷移10303（4）=1×44+3×42+3×40=307.1234（5）=1×53+2×52+3×51+4×50=194.

例2已知10b1（2）=a02（3）,求數字a，b的值.所以2b+9=9a+2，即9a-2b=7.10b1（2）=1×23+b×2+1=2b+9.a02（3）=a×32+2=9a+2.故a=1，b=1.1.k進制數使用0～（k-1）共k個數字，但左側第一個數位上的數字（首位數字）不為0.

小

結2.用

表示k進制數，其中k稱為基數，十進制數不標注基數.3.把k進制數化為十進制數的一般算式是：1.3算法案例4十進制數化為k進制數

問題提出1.“滿幾進一”就是幾進制，k進制使用哪幾個數字，k進制數化為十進制數的一般算式是什么？2.k進制數化十進制數的一般算式，可以構造算法，設計程序，通過計算機就能把任何一個k進制數化為十進制數.在實際應用中，我們還需要把任意一個十進制數化為k進制數的算法。知識探究(一):除k取余法二進制數101101（2）化為十進制數是什么數？十進制數89化為二進制數是什么數？101101（2）=25+23+22+1=45.89=2×（2×（2×（2×（2×2+1）+1）+0）+0）+1=1×26+0×25+1×24+1×23+0×22+0×21+1×20=1011001（2）.思考：上述化十進制數為二進制數的算法叫做除2取余法，轉化過程有些復雜，觀察下面的算式你有什么發現嗎？

21222502112222442891001101余數思考3:上述方法也可以推廣為把十進制數化為k進制數的算法，稱為除k取余法，那么十進制數191化為五進制數是什么數？0515753851911321余數191=1231（5）若十進制數a除以2所得的商是q0，余r0，

即a=2·q0+r0；q0除以2所得的商是q1，余數是r1，

即q0=2·q1+r1；……qn-1除以2所得的商是0，余數是rn，

即qn-1=rn，那么十進制數a化為二進制數是什么數？a=rnrn-1…r1r0(2)知識探究(二):十進制化k進制的算法

思考1:根據上面的分析，將十進制數a化為二進制數的算法步驟如何設計？第四步，若q≠0，則a=q，返回第二步；

否則，輸出全部余數r排列得到

的二進制數.第一步，輸入十進制數a的值.第二步，求出a除以2所得的商q，余數r.第三步，把所得的余數依次從右到左排列.思考:利用除k取余