算法案例(完整版)

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

知識回顧舊方法：先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù).有沒有什么新方法？對8251與6105這兩個(gè)數(shù)：進(jìn)行以下步驟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的最大公因數(shù)！上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？

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

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

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

可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之.

例1分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168與93的最大公約數(shù).輾轉(zhuǎn)相除法：168=93×1+75， 93=75×1+18， 75=18×4+3， 18=3×6.更相減損術(shù):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三數(shù)的最大公約數(shù)

因?yàn)?25=130×2+65，130=65×2，所以325與130的最大公約數(shù)是65.

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

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

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

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

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

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

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

思考1:用秦九韶算法求多項(xiàng)式的值，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？第一步，輸入多項(xiàng)式的次數(shù)n，最高次

項(xiàng)的系數(shù)an和x的值.

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

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

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

練習(xí)：用秦九韶算法求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進(jìn)位制知識探究(一):進(jìn)位制的概念

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

思考:十進(jìn)制使用0～9十個(gè)數(shù)字，那么二進(jìn)制、五進(jìn)制、七進(jìn)制分別需要使用哪些數(shù)字？

思考:在十進(jìn)制中10表示十，

在二進(jìn)制中10表示2.一般地，若k是一個(gè)大于1的整數(shù)，則以k為基數(shù)的k進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫在一起的形式：

anan-1…a1a0(k).其中各個(gè)數(shù)位上的數(shù)字an，an-1，…，a1，a0的取值范圍如何？意義是什么？思考:十進(jìn)制數(shù)4528表示的數(shù)可以寫成4×103+5×102+2×101+8×100，依此類比，二進(jìn)制數(shù)110011（2）,八進(jìn)制數(shù)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.結(jié)論:一般地，如何將k進(jìn)制數(shù)anan-1…a1a0(k)寫成各數(shù)位上的數(shù)字與基數(shù)k的冪的乘積之和的形式？（十進(jìn)制）思考:在二進(jìn)制中，0+0，0+1，1+0，1+1值分別是多少？知識探究(二):k進(jìn)制化十進(jìn)制的算法

思考:二進(jìn)制數(shù)110011（2）化為十進(jìn)制數(shù)是什么數(shù)？

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

結(jié)論：二進(jìn)制數(shù)右數(shù)第i位數(shù)字ai化為十進(jìn)制數(shù)是

問題：運(yùn)用以下循環(huán)結(jié)構(gòu)，設(shè)計(jì)算法把二進(jìn)制數(shù)

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

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

，i=i+1.同樣地，把k進(jìn)制數(shù)

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

若是，則輸出b的值；

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

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

例1將下列各進(jìn)制數(shù)化為十進(jìn)制數(shù).（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）,求數(shù)字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進(jìn)制數(shù)使用0～（k-1）共k個(gè)數(shù)字，但左側(cè)第一個(gè)數(shù)位上的數(shù)字（首位數(shù)字）不為0.

小

結(jié)2.用

表示k進(jìn)制數(shù)，其中k稱為基數(shù)，十進(jìn)制數(shù)不標(biāo)注基數(shù).3.把k進(jìn)制數(shù)化為十進(jìn)制數(shù)的一般算式是：1.3算法案例4十進(jìn)制數(shù)化為k進(jìn)制數(shù)

問題提出1.“滿幾進(jìn)一”就是幾進(jìn)制，k進(jìn)制使用哪幾個(gè)數(shù)字，k進(jìn)制數(shù)化為十進(jìn)制數(shù)的一般算式是什么？2.k進(jìn)制數(shù)化十進(jìn)制數(shù)的一般算式，可以構(gòu)造算法，設(shè)計(jì)程序，通過計(jì)算機(jī)就能把任何一個(gè)k進(jìn)制數(shù)化為十進(jìn)制數(shù).在實(shí)際應(yīng)用中，我們還需要把任意一個(gè)十進(jìn)制數(shù)化為k進(jìn)制數(shù)的算法。知識探究(一):除k取余法二進(jìn)制數(shù)101101（2）化為十進(jìn)制數(shù)是什么數(shù)？十進(jìn)制數(shù)89化為二進(jìn)制數(shù)是什么數(shù)？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）.思考：上述化十進(jìn)制數(shù)為二進(jìn)制數(shù)的算法叫做除2取余法，轉(zhuǎn)化過程有些復(fù)雜，觀察下面的算式你有什么發(fā)現(xiàn)嗎？

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

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

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

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

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

否則，輸出全部余數(shù)r排列得到

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