高二數(shù)學(xué)下學(xué)期

1、1.3 1.3 算法案例算法案例1.3.4 1.3.4 十進(jìn)制化十進(jìn)制化K K進(jìn)制進(jìn)制1.3.1 1.3.1 輾轉(zhuǎn)相除法和更相減損術(shù)輾轉(zhuǎn)相除法和更相減損術(shù)1.3.2 1.3.2 秦九韶算法秦九韶算法1.3.3 K1.3.3 K進(jìn)制化十進(jìn)制進(jìn)制化十進(jìn)制1.3 1.3 算法案例算法案例1.3.1 1.3.1 輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法和更相減損術(shù)和更相減損術(shù)復(fù)習(xí)復(fù)習(xí)1.1.研究一個(gè)實(shí)際問(wèn)題的算法，主要從哪幾方面展開(kāi)？研究一個(gè)實(shí)際問(wèn)題的算法，主要從哪幾方面展開(kāi)？2.2.在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？3.3.在程序設(shè)計(jì)中基本的算法語(yǔ)句有哪幾種？在程序設(shè)計(jì)中基

2、本的算法語(yǔ)句有哪幾種？算法步驟、程序框圖和編寫(xiě)程序算法步驟、程序框圖和編寫(xiě)程序三方面展開(kāi)三方面展開(kāi). .順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)順序結(jié)構(gòu)、條件結(jié)構(gòu)、循環(huán)結(jié)構(gòu)輸入語(yǔ)句、輸出語(yǔ)句、賦值語(yǔ)句、條件語(yǔ)句、循環(huán)語(yǔ)句輸入語(yǔ)句、輸出語(yǔ)句、賦值語(yǔ)句、條件語(yǔ)句、循環(huán)語(yǔ)句情境創(chuàng)設(shè) 韓信是秦末漢初的著名軍事家.據(jù)說(shuō)有一次漢高祖劉邦在衛(wèi)士的簇?fù)硐聛?lái)到練兵場(chǎng),劉邦問(wèn)韓信有什么方法,不要逐個(gè)報(bào)數(shù),就能知道場(chǎng)上的士兵的人數(shù),韓信先令士兵排成3列縱隊(duì),結(jié)果有2人多余,接著下令排成5列縱隊(duì),結(jié)果又多出3人,隨后他又下令改為7列縱隊(duì),這次又剩下2人無(wú)法成整行.在場(chǎng)的人都哈哈大笑,以為韓信不能清點(diǎn)出準(zhǔn)確的人數(shù),不料笑聲剛落,韓

3、信高聲報(bào)告共有士兵2333人.眾人聽(tīng)了一楞,不知道韓信用什么方法這么快就能得到正確的結(jié)果的.今天,我們將以這些古典案例的思想,設(shè)計(jì)出適宜計(jì)算機(jī)的運(yùn)行程序,提高我們對(duì)基本算法結(jié)構(gòu)和算法語(yǔ)句在實(shí)際中的運(yùn)用能力.探究一,輾轉(zhuǎn)相除法思考思考1:在小學(xué)中我們是如何求出兩個(gè)正整數(shù)在小學(xué)中我們是如何求出兩個(gè)正整數(shù)的最大公約數(shù)的呢的最大公約數(shù)的呢?算法案例算法案例之求最大公約數(shù)之求最大公約數(shù)求以下幾組正整數(shù)的最大公約數(shù)。(注：若整數(shù)m和n滿足n整除m，則（m,n）=n。用（m,n）來(lái)表示m和n的最大公約數(shù)。)（1）（18，30） （2）（24，16）（3）（63，63） （4）（72，8） （5）（301，1

4、33 ）解：2 1 8 2 4 用公有質(zhì)因數(shù)2除， 3 9 1 2 用公有質(zhì)因數(shù)3除， 3 4 3和4互質(zhì)不除了。 得：18和24最大公約數(shù)是：236 例、求18與24的最大公約數(shù)：6；8；63；8；7；短除法短除法想一想，如何求8251與6105的最大公約數(shù)？ 思考思考2:2:對(duì)于對(duì)于82518251與與61056105這兩個(gè)數(shù)，它們這兩個(gè)數(shù)，它們的最大的最大公約數(shù)是多少？你是怎樣得到的？公約數(shù)是多少？你是怎樣得到的？ 由于它們公有的質(zhì)因數(shù)較大，利用上述方法求由于它們公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難最大公約數(shù)就比較困難. .有沒(méi)有其它的方法可以較簡(jiǎn)有沒(méi)有其它的方法可以較簡(jiǎn)

5、單的找出它們的最大公約數(shù)呢？單的找出它們的最大公約數(shù)呢？ 思考思考3 3：注意到：注意到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩個(gè)數(shù)的公約數(shù)和這兩個(gè)數(shù)的公約數(shù)和61056105與與21462146的公約數(shù)有的公約數(shù)有什么關(guān)系？什么關(guān)系？ 我們發(fā)現(xiàn)我們發(fā)現(xiàn)6105=21466105=21462+18132+1813，同理，同理，61056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公約數(shù)相等的公約數(shù)相等. . 思考思考4 4：重復(fù)上述操作，你能得到：重復(fù)上述操作，你能得到8251825

6、1與與61056105這這兩個(gè)數(shù)的最大公約數(shù)嗎？?jī)蓚€(gè)數(shù)的最大公約數(shù)嗎？2146=18132146=18131+3331+333，148=37148=374+0.4+0.333=148333=1482+372+37，1813=3331813=3335+1485+148，8251=61058251=61051+21461+2146，6105=21466105=21462+18132+1813，定義定義:所謂的輾轉(zhuǎn)相除法,就是對(duì)于給定的兩個(gè)數(shù),用較大的數(shù)除以較小的數(shù),若余數(shù)不為零,則將余數(shù)和較小的數(shù)構(gòu)成新的數(shù)對(duì),繼續(xù)上面的除法, 直到大數(shù)被小數(shù)除盡,則這是較小的數(shù)就是原來(lái)兩個(gè)數(shù)的最大公約數(shù)輾轉(zhuǎn)相除法

7、求兩個(gè)數(shù)的最大公約數(shù)，其算法可以描述如下：輾轉(zhuǎn)相除法是一個(gè)反復(fù)執(zhí)行直到余數(shù)等于0停止的步驟，這實(shí)際上是一個(gè)循環(huán)結(jié)構(gòu) 思考思考4 4：輾轉(zhuǎn)相除直到何時(shí)結(jié)束？：輾轉(zhuǎn)相除直到何時(shí)結(jié)束？主要運(yùn)用的是哪種算法結(jié)構(gòu)？主要運(yùn)用的是哪種算法結(jié)構(gòu)？如此循環(huán)，直到得到結(jié)果。 輸入兩個(gè)正整數(shù)m和n； 求余數(shù)r：計(jì)算m除以n，將所得余數(shù)存放到變量r中；更新被除數(shù)和余數(shù)：m=n，n=r。判斷余數(shù)r r是否為0：若余數(shù)為0則輸出結(jié)果，否則轉(zhuǎn)向第步繼續(xù)循環(huán)執(zhí)行。第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn).n(mn).第二步，計(jì)算第二步，計(jì)算m m除以除以n n所得的余數(shù)所得的余數(shù)r. r. 第三步，第三

8、步，m=nm=n，n=r.n=r. 第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于m m；否則，返回第二步否則，返回第二步. . 思考思考5:5:你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？你能把輾轉(zhuǎn)相除法編成一個(gè)計(jì)算機(jī)程序嗎？程序框圖程序框圖開(kāi)始開(kāi)始輸入輸入m m，n n求求m m除以除以n n的余數(shù)的余數(shù)r rm=nm=nn=rn=rr=0r=0？是是輸出輸出m m結(jié)束結(jié)束否否INPUT mINPUT m，n nDODOr=m MOD nr=m MOD nm=nm=nn=rn=rLOOP UNTIL r=0LOOP UNTIL r=0PRINT mPRIN

9、T mENDEND 思考思考6:6:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)轉(zhuǎn)相除法求兩個(gè)正整數(shù)m m、n n的最大公約數(shù)的程序框的最大公約數(shù)的程序框圖和程序分別如何表示？圖和程序分別如何表示？開(kāi)始開(kāi)始輸入輸入m m，n n求求m m除以除以n n的余數(shù)的余數(shù)r rm=nm=nr0r0？否否輸出輸出m m結(jié)束結(jié)束是是n=rn=rINPUT mINPUT m，n nWHILE r0WHILE r0r=m MOD nr=m MOD nm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND練習(xí)：用輾轉(zhuǎn)相除法求下列兩數(shù)的最大公約

10、數(shù)：（1）（225，135） （2）（98，196）（3）（72，168） （4）（153，119）45982417二、更相減損術(shù)二、更相減損術(shù) 九章算術(shù)九章算術(shù)是中國(guó)古代的數(shù)學(xué)專著，其中的是中國(guó)古代的數(shù)學(xué)專著，其中的“更相減損術(shù)更相減損術(shù)”也可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)，也可以用來(lái)求兩個(gè)數(shù)的最大公約數(shù)，即即“可半者半之，不可半者，副置分母、子之?dāng)?shù)，可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也以少減多，更相減損，求其等也.以等數(shù)約之以等數(shù)約之.”意思是：意思是： 第一步：任意給定兩個(gè)正整數(shù)，判斷它們是否第一步：任意給定兩個(gè)正整數(shù)，判斷它們是否都是偶數(shù)都是偶數(shù). 若是，用

11、若是，用2約簡(jiǎn)；若不是，執(zhí)行第二步約簡(jiǎn)；若不是，執(zhí)行第二步. 第二步：以較大的數(shù)減去較小的數(shù)，接著把差第二步：以較大的數(shù)減去較小的數(shù)，接著把差與較小的數(shù)比較，并以大數(shù)減小數(shù)與較小的數(shù)比較，并以大數(shù)減小數(shù).繼續(xù)這個(gè)操作，繼續(xù)這個(gè)操作，直到所得的數(shù)相等為止，則這個(gè)等數(shù)或這個(gè)數(shù)與約直到所得的數(shù)相等為止，則這個(gè)等數(shù)或這個(gè)數(shù)與約簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù)簡(jiǎn)的數(shù)的乘積就是所求的最大公約數(shù).例例1 1：用更相減損術(shù)求：用更相減損術(shù)求9898與與6363的最大公約數(shù)的最大公約數(shù). .98-63=3598-63=35，14-7=7.14-7=7.21-7=1421-7=14，28-7=2128-7=21，

12、35-28=735-28=7，63-35=2863-35=28，因?yàn)橐驗(yàn)?3不是偶數(shù)，所以不是偶數(shù)，所以所以最大公約數(shù)是所以最大公約數(shù)是7. 例例2 2 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：更相減損術(shù)更相減損術(shù): : 168-93=75 168-93=75， 93-75=1893-75=18， 75-18=5775-18=57， 57-18=3957

13、-18=39， 39-18=2139-18=21， 21-18=321-18=3， 18-3=1518-3=15， 15-3=1215-3=12， 12-3=912-3=9， 9-3=69-3=6， 6-3=3.6-3=3.例例3 3 用更相減損術(shù)求用更相減損術(shù)求8080與與3636的最大公的最大公約數(shù)約數(shù). . 例例4 4 求求325325，130130，270270三個(gè)數(shù)的最大公約數(shù)三個(gè)數(shù)的最大公約數(shù). . 因?yàn)橐驗(yàn)?25=130325=1302+652+65，130=65130=652 2，所以，所以325325與與130130的最大公約數(shù)是的最大公約數(shù)是65.65. 因?yàn)橐驗(yàn)?70=6

14、5270=654+104+10，65=1065=106+56+5，10=510=52 2，所以所以6565與與270270最大公約數(shù)是最大公約數(shù)是5. 5. 故故325325，130130，270270三個(gè)數(shù)的最大公約數(shù)是三個(gè)數(shù)的最大公約數(shù)是5.5. 練習(xí)練習(xí): :用更相減損術(shù)求兩個(gè)正整數(shù)用更相減損術(shù)求兩個(gè)正整數(shù)m m，n n的最大公的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟約數(shù)，可以用什么邏輯結(jié)構(gòu)來(lái)構(gòu)造算法？其算法步驟如何設(shè)計(jì)？如何設(shè)計(jì)？ 第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn).n(mn). 第二步，計(jì)算第二步，計(jì)算m-nm-n所得的差所得的差k. k.

15、第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表示，表示，小者用小者用n n表示表示. . 第四步，若第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于m m；否則，返回第二步否則，返回第二步. . 討論討論: :該算法的程序框圖如何表示？該算法的程序框圖如何表示？開(kāi)始開(kāi)始輸入輸入m m，n nnknk？m=nm=n是是輸出輸出m m結(jié)束結(jié)束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否 討論討論: :該程該程序框圖對(duì)應(yīng)的程序框圖對(duì)應(yīng)的程序如何表述？序如何表述？INPUT mINPUT m，n nWHILE mW

16、HILE mn nk=m-nk=m-nIF nk THENIF nk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND開(kāi)始開(kāi)始輸入輸入m m，n nnknk？m=nm=n是是輸出輸出m m結(jié)束結(jié)束mnmn？k=m-nk=m-n是是否否n=kn=km=km=k否否 1 1、輾轉(zhuǎn)相除法、輾轉(zhuǎn)相除法. . 小結(jié)小結(jié) 2 2、更相減損術(shù)、更相減損術(shù). .布置作業(yè)：布置作業(yè)：P45P45練習(xí)：練習(xí)：1.1.P48P48習(xí)題習(xí)題1.3A1.3A組：組：1.1.1.3.2 1.3.2 秦九韶算法秦九韶算法 1 1、什

17、么是輾轉(zhuǎn)相除法和更相減損術(shù)？、什么是輾轉(zhuǎn)相除法和更相減損術(shù)？ 2 2、輾轉(zhuǎn)相除法和更相減損術(shù)，是求兩個(gè)正整、輾轉(zhuǎn)相除法和更相減損術(shù)，是求兩個(gè)正整數(shù)的最大公約數(shù)的優(yōu)秀算法，我們將算法轉(zhuǎn)化為數(shù)的最大公約數(shù)的優(yōu)秀算法，我們將算法轉(zhuǎn)化為程序后，就可以由計(jì)算機(jī)來(lái)執(zhí)行運(yùn)算，實(shí)現(xiàn)了古程序后，就可以由計(jì)算機(jī)來(lái)執(zhí)行運(yùn)算，實(shí)現(xiàn)了古代數(shù)學(xué)與現(xiàn)代信息技術(shù)的完美結(jié)合代數(shù)學(xué)與現(xiàn)代信息技術(shù)的完美結(jié)合. .復(fù)習(xí)復(fù)習(xí)探究三、秦九昭算法 思考思考1,在初中在初中,我們是如何求一個(gè)多項(xiàng)式的我們是如何求一個(gè)多項(xiàng)式的值的值的? 思考思考2,已知一個(gè)已知一個(gè)n 次多項(xiàng)式次多項(xiàng)式f(x)=anxn+an-1xn-1+a1x+a0當(dāng)當(dāng)x=x

18、0時(shí)，除時(shí)，除了用代入法求解外是否還有更好的方法呢？了用代入法求解外是否還有更好的方法呢？秦九韶算法秦九韶算法的基本思想的基本思想 思考思考1:1:對(duì)于多項(xiàng)式對(duì)于多項(xiàng)式f(x)=xf(x)=x5 5+x+x4 4+x+x3 3+x+x2 2+x+1+x+1，求，求f(5)f(5)的值的值. . 4+3+2+1=104+3+2+1=10次乘法運(yùn)算，次乘法運(yùn)算，5 5次加法運(yùn)算次加法運(yùn)算. . 分析：把分析：把5 5代入多項(xiàng)式，若先計(jì)算各項(xiàng)的值，代入多項(xiàng)式，若先計(jì)算各項(xiàng)的值，然后再相加，那么一共要做：然后再相加，那么一共要做： 思考思考2:2:另一種做法是先計(jì)算另一種做法是先計(jì)算x x2 2的值，

19、然后依的值，然后依次計(jì)算次計(jì)算x x2 2x x，(x(x2 2x)x)x x，(x(x2 2x)x)x)x)x x的的值，這樣每次都可以利用上一次計(jì)算的結(jié)果，這值，這樣每次都可以利用上一次計(jì)算的結(jié)果，這時(shí)一共做了：時(shí)一共做了： 4 4次乘法運(yùn)算，次乘法運(yùn)算，5 5次加法運(yùn)算次加法運(yùn)算. . 思考思考3:3:有沒(méi)有更有效的算法呢？利用后一種算有沒(méi)有更有效的算法呢？利用后一種算法求多項(xiàng)式法求多項(xiàng)式f(x)=af(x)=an nx xn n+a+an-1n-1x xn-1n-1+ +a+a1 1x+ax+a0 0的值，這的值，這個(gè)多項(xiàng)式應(yīng)寫(xiě)成哪種形式？個(gè)多項(xiàng)式應(yīng)寫(xiě)成哪種形式？f(x)=af(x)=

20、an nx xn n+a+an-1n-1x xn-1n-1+ +a+a1 1x+ax+a0 0 =(a=(an nx xn-1n-1+a+an-1n-1x xn-2n-2+ +a+a2 2x+ax+a1 1)x+a)x+a0 0=(a=(an nx xn-2n-2+a+an-1n-1x xn-3n-3+ +a+a2 2)x+a)x+a1 1)x+a)x+a0 0 = = =(=(a(an nx+ax+an-1n-1)x+a)x+an-2n-2)x+)x+a+a1 1)x+a)x+a0 0. . 這就是我國(guó)南宋時(shí)期數(shù)學(xué)家秦九韶在他的著作這就是我國(guó)南宋時(shí)期數(shù)學(xué)家秦九韶在他的著作數(shù)書(shū)九章數(shù)書(shū)九章中提

21、出的算法中提出的算法. .思考思考4:4:對(duì)于對(duì)于f(x)=(f(x)=(a(an nx+ax+an-1n-1)x+ a)x+ an-2n-2)x+)x+a+a1 1)x+a)x+a0 0，由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟如何？由內(nèi)向外逐層計(jì)算一次多項(xiàng)式的值，其算法步驟如何？ 第一步，計(jì)算第一步，計(jì)算v v1 1=a=an nx+ax+an-1n-1. . 第二步，計(jì)算第二步，計(jì)算v v2 2=v=v1 1x+ax+an-2n-2. .第三步，計(jì)算第三步，計(jì)算v v3 3=v=v2 2x+ax+an-3n-3. . 第第n n步，計(jì)算步，計(jì)算v vn n=v=vn-1n-1x+ax+

22、a0 0. .上述方法稱為秦九韶算法上述方法稱為秦九韶算法. . 思考思考5:5:在秦九韶算法中，記在秦九韶算法中，記v v0 0=a=an n，那么第，那么第k k步的步的算式是什么？算式是什么？ v vk k=v=vk-1k-1x+ax+an-kn-k (k=1 (k=1，2 2，n)n)解：解：f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.f(x)=(4x+2)x+3.5)x-2.6)x+1.7)x-0.8.v v1 1=4=45+2=225+2=22；v v2 2=22=225+3.5=113.55+3.5=113.5；v v3 3=113.5=113.55-2

23、.6=564.95-2.6=564.9；v v4 4=564.9=564.95+1.7=2826.25+1.7=2826.2；v v5 5=2826.2=2826.25-0.8=14130.2.5-0.8=14130.2.所以所以f(5)= =14130.2.f(5)= =14130.2. 例例1 1 已知一個(gè)已知一個(gè)5 5次多項(xiàng)式為次多項(xiàng)式為 用秦九韶算法求用秦九韶算法求f(5)f(5)的值的值. . 8 . 07 . 16 . 25 . 3242345xxxxxxf練習(xí)：閱讀下列程序，說(shuō)明它解決的實(shí)際問(wèn)題是什么？練習(xí)：閱讀下列程序，說(shuō)明它解決的實(shí)際問(wèn)題是什么？INPUT INPUT “x=

24、x=”；a an=0n=0y=0y=0WHLE n5WHLE n=0WHILE i=0INPUT INPUT “ai=ai=”；a a v=v v=v* *x+ax+ai=i-1i=i-1 WEND WENDPRINT vPRINT vENDENDPRINT PRINT “i=i=”；i i小結(jié)小結(jié) 2. 2.計(jì)算機(jī)的一個(gè)很重要的特點(diǎn)就是運(yùn)算速度快，計(jì)算機(jī)的一個(gè)很重要的特點(diǎn)就是運(yùn)算速度快，但評(píng)價(jià)算法好壞的一個(gè)重要標(biāo)志是運(yùn)算的次數(shù)，如但評(píng)價(jià)算法好壞的一個(gè)重要標(biāo)志是運(yùn)算的次數(shù)，如果一個(gè)算法從理論上需要超出計(jì)算機(jī)允許范圍內(nèi)的果一個(gè)算法從理論上需要超出計(jì)算機(jī)允許范圍內(nèi)的運(yùn)算次數(shù)，那么這樣的算法就只能是

25、一個(gè)理論算法運(yùn)算次數(shù)，那么這樣的算法就只能是一個(gè)理論算法. .在多項(xiàng)式求值的各種算法中，秦九韶算法是一個(gè)優(yōu)在多項(xiàng)式求值的各種算法中，秦九韶算法是一個(gè)優(yōu)秀算法秀算法. . 1.1.秦九韶算法計(jì)算多項(xiàng)式的值及程序設(shè)計(jì)秦九韶算法計(jì)算多項(xiàng)式的值及程序設(shè)計(jì). . 布置作業(yè)：布置作業(yè)：P45P45練習(xí)：練習(xí)：2.2.P48P48習(xí)題習(xí)題1.3A1.3A組：組：2.2.1.3.3 K1.3.3 K進(jìn)制化十進(jìn)制進(jìn)制化十進(jìn)制 1. 1.簡(jiǎn)述輾轉(zhuǎn)相除法和更相減損術(shù)的用途及內(nèi)容簡(jiǎn)述輾轉(zhuǎn)相除法和更相減損術(shù)的用途及內(nèi)容. .2、秦九韶算法的用途及內(nèi)容、秦九韶算法的用途及內(nèi)容. 將這些算法轉(zhuǎn)化為程序，就可以由計(jì)算機(jī)來(lái)完將

26、這些算法轉(zhuǎn)化為程序，就可以由計(jì)算機(jī)來(lái)完成相關(guān)運(yùn)算成相關(guān)運(yùn)算. . 復(fù)習(xí)復(fù)習(xí)進(jìn)位制的概念進(jìn)位制的概念 進(jìn)位制是為了計(jì)數(shù)和運(yùn)算方便而約定的記數(shù)系進(jìn)位制是為了計(jì)數(shù)和運(yùn)算方便而約定的記數(shù)系統(tǒng)統(tǒng). .約定滿二進(jìn)一，就是二進(jìn)制；約定滿二進(jìn)一，就是二進(jìn)制；滿十進(jìn)一，就是十進(jìn)制；滿十進(jìn)一，就是十進(jìn)制；七天為一周，就是七進(jìn)制；七天為一周，就是七進(jìn)制；十二個(gè)月為一年，就是十二進(jìn)制；十二個(gè)月為一年，就是十二進(jìn)制； 六十秒為一分鐘，六十分鐘為一個(gè)小時(shí)，就是六十秒為一分鐘，六十分鐘為一個(gè)小時(shí)，就是六十進(jìn)制；等等六十進(jìn)制；等等. . 一般地，一般地，“滿幾進(jìn)一滿幾進(jìn)一”就是就是幾進(jìn)制幾進(jìn)制. . 思考思考1:1:十進(jìn)制使

27、用十進(jìn)制使用0 09 9十個(gè)數(shù)字，那么二進(jìn)制、十個(gè)數(shù)字，那么二進(jìn)制、五進(jìn)制、七進(jìn)制分別使用哪些數(shù)字？五進(jìn)制、七進(jìn)制分別使用哪些數(shù)字？ 在十進(jìn)制中在十進(jìn)制中1010表示十，在二進(jìn)制中表示十，在二進(jìn)制中1010表示表示2.2.一一般地，若般地，若k k是一個(gè)大于是一個(gè)大于1 1的整數(shù)，則以的整數(shù)，則以k k為基數(shù)的為基數(shù)的k k進(jìn)進(jìn)制數(shù)可以表示為一串?dāng)?shù)字連寫(xiě)在一起的形式：制數(shù)可以表示為一串?dāng)?shù)字連寫(xiě)在一起的形式： a an na an-1n-1a a1 1a a0(k)0(k). . “滿滿K K進(jìn)一進(jìn)一”就是就是K K進(jìn)制進(jìn)制，其中，其中k k稱為稱為k k進(jìn)制的進(jìn)制的基數(shù)基數(shù). .那么那么k k

28、是一個(gè)什么范圍內(nèi)的數(shù)？是一個(gè)什么范圍內(nèi)的數(shù)？ 與十進(jìn)制類似，其它的進(jìn)位制也可以按照位置原與十進(jìn)制類似，其它的進(jìn)位制也可以按照位置原則計(jì)數(shù)則計(jì)數(shù). . 思考思考2 2：其中各個(gè)數(shù)位上的數(shù)字：其中各個(gè)數(shù)位上的數(shù)字a an n，a an-1n-1，a a1 1，a a0 0的取值范圍如何？的取值范圍如何？ 例如例如: :十進(jìn)制數(shù)十進(jìn)制數(shù)37213721表示的數(shù)可以寫(xiě)成：表示的數(shù)可以寫(xiě)成： 110011110011（2 2）=1=12 25 5+1+12 24 4+0+02 23 3+0+02 22 2+1+12 21 1+1+12 20 0 =51=51 56715671（8 8）=5=58 83

29、3+6+68 82 2+7+78 81 1+1+18 80 0=3001.=3001. 例例1 1：把二進(jìn)制數(shù)：把二進(jìn)制數(shù)110011110011（2 2）化為十進(jìn)制數(shù)化為十進(jìn)制數(shù). . 練習(xí)：把八進(jìn)制數(shù)練習(xí)：把八進(jìn)制數(shù) 56715671（8 8）化為十進(jìn)制數(shù)化為十進(jìn)制數(shù). .3 310103 3+7+710102 2+2+210101 1+1+110100 0. . 探究探究: :如何將如何將k k進(jìn)制數(shù)進(jìn)制數(shù)a an na an-1n-1a a1 1a a0(k)0(k)寫(xiě)成各數(shù)位寫(xiě)成各數(shù)位上的數(shù)字與基數(shù)上的數(shù)字與基數(shù)k k的冪的乘積之和的形式？的冪的乘積之和的形式？ 討論討論: :在二進(jìn)

30、制中，在二進(jìn)制中，0+00+0，0+10+1，1+01+0，1+11+1的值分的值分別是多少？別是多少？a an n a an-1n-1a a1 1a a0(k) 0(k) = a= an nk kn n+ a+ an-1n-1k kn-1n-1+ + + a+ a1 1k k1 1+ a+ a0 0k k0 0 例例2:2:二進(jìn)制數(shù)二進(jìn)制數(shù)110011110011（3 3）化為十進(jìn)制數(shù)是什么數(shù)？化為十進(jìn)制數(shù)是什么數(shù)？ 110011110011（3 3）討論討論: : an an-1a1a0(2) 中a ai i化為十進(jìn)制數(shù)是什么數(shù)？化為十進(jìn)制數(shù)是什么數(shù)？=1=13 35 5+1+13 34

31、4+0+03 33 3+0+03 32 2+1+13 31 1+1+13 30 0 =243+81+3+1=243+81+3+1=328. =328. a ai i2 2i-1i-1 練習(xí)：將下列各進(jìn)制數(shù)化為十進(jìn)制數(shù)練習(xí)：將下列各進(jìn)制數(shù)化為十進(jìn)制數(shù). .（1 1）1030410304（4 4） ； （2 2）43214321（5 5）. .1030410304（4 4）=1=14 44 4+3+34 42 2+4+44 40 0=308.=308.43214321（5 5）=4=45 53 3+3+35 52 2+2+25 51 1+1+15 50 0=586. =586. 探究：如何改進(jìn)上述

32、算法，把其他進(jìn)位制化為十探究：如何改進(jìn)上述算法，把其他進(jìn)位制化為十進(jìn)制數(shù)？請(qǐng)舉例說(shuō)明進(jìn)制數(shù)？請(qǐng)舉例說(shuō)明. . 例例3:3:設(shè)計(jì)一個(gè)算法，把設(shè)計(jì)一個(gè)算法，把2 2進(jìn)制數(shù)進(jìn)制數(shù)a a（共有（共有n n位）化位）化為十進(jìn)制數(shù)為十進(jìn)制數(shù)b b，并轉(zhuǎn)化成程序框圖，寫(xiě)出程序，并轉(zhuǎn)化成程序框圖，寫(xiě)出程序. . 第二步，令第二步，令b=0b=0，i=1.i=1. 第四步，判斷第四步，判斷in in 是否成立是否成立. .若是，則執(zhí)行第五若是，則執(zhí)行第五步；否則，返回第三步步；否則，返回第三步. .第一步，輸入第一步，輸入a a，2 2和和n n的值的值. . 第三步，第三步，b=b+ab=b+ai i2 2i

33、-1i-1，i=i+1.i=i+1.第五步，輸出第五步，輸出b b的值的值. . 練習(xí)練習(xí): :設(shè)計(jì)一個(gè)算法，把設(shè)計(jì)一個(gè)算法，把k k進(jìn)制數(shù)進(jìn)制數(shù)a a（共有（共有n n位）位）化為十進(jìn)制數(shù)化為十進(jìn)制數(shù)b.b.第二步，令第二步，令b=0b=0，i=1.i=1.第四步，判斷第四步，判斷in in 是否成立是否成立. .若是，則執(zhí)行第五步；若是，則執(zhí)行第五步；否則，返回第三步否則，返回第三步. .第一步，輸入第一步，輸入a a，k k和和n n的值的值. .第三步，第三步，b=b+ab=b+ai ik ki-1i-1，i=i+1.i=i+1.第五步，輸出第五步，輸出b b的值的值. .開(kāi)始開(kāi)始輸入

34、輸入a a，k k，n nb=0b=0i=1i=1把把a(bǔ) a的右數(shù)第的右數(shù)第i i位數(shù)字賦給位數(shù)字賦給t tb=b+tb=b+tk ki-1i-1i=i+1i=i+1in?in?結(jié)束結(jié)束是是輸出輸出b b否否程序框圖程序框圖INPUT INPUT “a a，k k，n=n=”;a,k,n;a,k,nb=0b=0i=1i=1t=a MOD 10t=a MOD 10DODOb=b+tb=b+t* *k k（i-1i-1）a=a10a=a10t=a MOD 10t=a MOD 10i=i+1i=i+1LOOP UNTIL inLOOP UNTIL inPRINT bPRINT bENDEND開(kāi)始開(kāi)始

35、輸入輸入a a，k k，n nb=0b=0i=1i=1把把a(bǔ) a的右數(shù)第的右數(shù)第i i位數(shù)字賦給位數(shù)字賦給t tb=b+tb=b+tk ki-1i-1i=i+1i=i+1in?in?結(jié)束結(jié)束是是輸出輸出b b否否 例例4 4：已知：已知20a120a1（2 2）=b10=b10（3 3）, ,求數(shù)字求數(shù)字a a，b b的值的值. .所以所以2a+17=9b+32a+17=9b+3，即，即9b-2a=14. 9b-2a=14. 20a120a1（2 2）=2=22 23 3+a+a2+1=2a+17.2+1=2a+17.b10b10（3 3）=b=b3 32 2+1+13=9b+3.3=9b+3

36、.故故a=2a=2，b=2. b=2. 1 1、k k進(jìn)制數(shù)使用進(jìn)制數(shù)使用0 0（k-1k-1）共）共k k個(gè)數(shù)字，但左個(gè)數(shù)字，但左側(cè)第一個(gè)數(shù)位上的數(shù)字（首位數(shù)字）不為側(cè)第一個(gè)數(shù)位上的數(shù)字（首位數(shù)字）不為0.0.小結(jié)小結(jié) 2 2、用、用 表示表示k k進(jìn)制數(shù)，其中進(jìn)制數(shù)，其中k k稱為基數(shù)，十進(jìn)制數(shù)一般不標(biāo)注基數(shù)稱為基數(shù)，十進(jìn)制數(shù)一般不標(biāo)注基數(shù). .a an n a an-1n-1a a1 1a a0(k) 0(k) 3 3、把、把k k進(jìn)制數(shù)化為十進(jìn)制數(shù)的一般算式是：進(jìn)制數(shù)化為十進(jìn)制數(shù)的一般算式是：a an n a an-1n-1a a1 1a a0(k) 0(k) = a= an nk k

37、n n+ a+ an-1n-1k kn-1n-1+ + + a+ a1 1k k1 1+ a+ a0 0k k0 0布置作業(yè)：布置作業(yè)：P48P48習(xí)題習(xí)題1.3B1.3B組：組：1.1.1.3.4 1.3.4 十進(jìn)制化十進(jìn)制化K K進(jìn)制進(jìn)制1 1、“滿幾進(jìn)一滿幾進(jìn)一”就是幾進(jìn)制就是幾進(jìn)制. .2 2、k k進(jìn)制使用進(jìn)制使用0 0，1 1，k-1k-1這這k k個(gè)數(shù)字個(gè)數(shù)字. .3 3、k k進(jìn)制數(shù)化為十進(jìn)制數(shù)的一般算式進(jìn)制數(shù)化為十進(jìn)制數(shù)的一般算式: :a an n a an-1n-1a a1 1a a0(k) 0(k) = a= an nk kn n+ a+ an-1n-1k kn-1n-1

38、+ + + a+ a1 1k k1 1+ a+ a0 0k k0 0 復(fù)習(xí)復(fù)習(xí)4 4、利用、利用k k進(jìn)制數(shù)化十進(jìn)制數(shù)的一般算式，可以進(jìn)制數(shù)化十進(jìn)制數(shù)的一般算式，可以構(gòu)造算法，設(shè)計(jì)程序，通過(guò)計(jì)算機(jī)就能把任何構(gòu)造算法，設(shè)計(jì)程序，通過(guò)計(jì)算機(jī)就能把任何一個(gè)一個(gè)k k進(jìn)制數(shù)化為十進(jìn)制數(shù)進(jìn)制數(shù)化為十進(jìn)制數(shù). .練習(xí)練習(xí): :把二進(jìn)制數(shù)把二進(jìn)制數(shù)100101100101（2 2）化為十進(jìn)制數(shù)化為十進(jìn)制數(shù). .100101100101（2 2）=2=25 5+2+22 2+1=37. +1=37. 討論討論: :怎樣把十進(jìn)制數(shù)怎樣把十進(jìn)制數(shù)8989化為二進(jìn)制數(shù)？化為二進(jìn)制數(shù)？例例1:1:把十進(jìn)制數(shù)把十進(jìn)制數(shù)

39、8989化為二進(jìn)制數(shù)化為二進(jìn)制數(shù). .觀察下面的算式你有什么發(fā)現(xiàn)嗎？觀察下面的算式你有什么發(fā)現(xiàn)嗎？ 89=289=2（2 2（2 2（2 2（2 22+12+1）+1+1）+0+0）+0+0）+1+1=1=12 26 6+0+02 25 5+1+12 24 4+1+12 23 3+0+02 22 2+0+02 21 1+1+12 20 0=1011001=1011001（2 2）. .根據(jù)二進(jìn)制根據(jù)二進(jìn)制“滿二進(jìn)一滿二進(jìn)一”的原則，可以用的原則，可以用2 2連續(xù)去連續(xù)去除除8989或所得商，然后取余數(shù)或所得商，然后取余數(shù). . 2 21 12 22 22 25 50 02 211112 222

40、222 244442 289891 10 00 01 11 10 01 1余數(shù)余數(shù)例例1:1:把十進(jìn)制數(shù)把十進(jìn)制數(shù)8989化為二進(jìn)制數(shù)化為二進(jìn)制數(shù). . 上述化十進(jìn)上述化十進(jìn)制數(shù)為二進(jìn)制數(shù)制數(shù)為二進(jìn)制數(shù)的算法叫做的算法叫做除除2 2取余法取余法. . 練習(xí)練習(xí): :把十進(jìn)制數(shù)把十進(jìn)制數(shù)196196化為五進(jìn)制數(shù)化為五進(jìn)制數(shù). . 除二取余法也可以推廣為把十進(jìn)制數(shù)化為除二取余法也可以推廣為把十進(jìn)制數(shù)化為k k進(jìn)進(jìn)制數(shù)的算法，稱為制數(shù)的算法，稱為除除k k取余法取余法. .0 05 51 15 57 75 539395 51961961 14 42 21 1余數(shù)余數(shù)196=1241196=1241（

41、5 5）若十進(jìn)制數(shù)若十進(jìn)制數(shù)a a除以除以k k所得的商是所得的商是q q0 0，余數(shù)是，余數(shù)是r r0 0， 即即a=ka=kq q0 0+ r+ r0 0； q q0 0除以除以k k所得的商是所得的商是q q1 1，余數(shù)是，余數(shù)是r r1 1， 即即q q0 0=k=kq q1 1+ r+ r1 1； q qn-1n-1除以除以k k所得的商是所得的商是0 0，余數(shù)是，余數(shù)是r rn n， 即即q qn-1n-1= r= rn n，那么十進(jìn)制數(shù)那么十進(jìn)制數(shù)a a化為化為k k進(jìn)制數(shù)是：進(jìn)制數(shù)是：a=ra=rn nr rn-1n-1r r1 1r r0(2)0(2)推廣：怎樣把十進(jìn)制數(shù)轉(zhuǎn)化為推廣：怎樣把十進(jìn)制數(shù)轉(zhuǎn)化為k k進(jìn)制數(shù)？進(jìn)制數(shù)？ 例例2:2:根據(jù)上面的分析，將十進(jìn)制數(shù)根據(jù)上面的分析，將十進(jìn)制數(shù)a a化為二進(jìn)化為二進(jìn)制數(shù)的算法步驟如何設(shè)計(jì)？制數(shù)的算法步驟如何設(shè)計(jì)？ 第四步，若第四步，若q0q0，則，