算法案例PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1問題提出問題提出t57301p2 1. 1.研究一個(gè)實(shí)際問題的算法，主要從算法步驟、程序框圖和編寫程序三方面展開研究一個(gè)實(shí)際問題的算法，主要從算法步驟、程序框圖和編寫程序三方面展開. .在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序設(shè)計(jì)中基本的算法語句有哪幾種？在程序框圖中算法的基本邏輯結(jié)構(gòu)有哪幾種？在程序設(shè)計(jì)中基本的算法語句有哪幾種？ 2.“ 2.“求兩個(gè)正整數(shù)的最大公約數(shù)求兩個(gè)正整數(shù)的最大公約數(shù)”是數(shù)學(xué)中的一個(gè)基礎(chǔ)性問題，它有各種解決辦法，我們以此為案例，對(duì)該問題的算法作一些探究是數(shù)學(xué)中的一個(gè)基礎(chǔ)性問題，它有各種解決辦法，我們以此為案例，對(duì)該問題的算法作一些探究. .第1頁(yè)/共21

2、頁(yè)第2頁(yè)/共21頁(yè)知識(shí)探究（一）知識(shí)探究（一）: :輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法思考思考1:1:1818與與3030的最大公約數(shù)是多少？你是怎樣得到的？的最大公約數(shù)是多少？你是怎樣得到的？ 先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù)先用兩個(gè)數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù). . 第3頁(yè)/共21頁(yè)思考思考2:2:對(duì)于對(duì)于82518251與與61056105這兩個(gè)數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難這兩個(gè)數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困

3、難. .注意到注意到8251=61058251=61051+21461+2146，那么，那么82518251與與61056105這兩個(gè)數(shù)的公約數(shù)和這兩個(gè)數(shù)的公約數(shù)和61056105與與21462146的公約數(shù)有什么關(guān)系？的公約數(shù)有什么關(guān)系？ 第4頁(yè)/共21頁(yè)思考思考3:3:又又6105=21466105=21462+18132+1813，同理，同理，61056105與與21462146的公約數(shù)和的公約數(shù)和21462146與與18131813的公約數(shù)相等的公約數(shù)相等. .重復(fù)上述操作，你能得到重復(fù)上述操作，你能得到82518251與與61056105這兩個(gè)數(shù)的最大公約數(shù)嗎？這兩個(gè)數(shù)的最大公約數(shù)嗎

4、？21462146= =181318131+1+333333，148148= =37374+0.4+0.333333= =1481482+2+3737，18131813= =3333335+5+148148，8251=8251=610561051+1+21462146，61056105= =214621462+2+18131813，第5頁(yè)/共21頁(yè)思考思考4:4:上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法輾轉(zhuǎn)相除法或或歐幾里得算法歐幾里得算法. .一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)一般地，用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，可以用什么邏

5、輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？ 第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn(mn).n).第二步，計(jì)算第二步，計(jì)算m m除以除以n n所得的余數(shù)所得的余數(shù)r. r. 第三步，第三步，m=nm=n，n=r.n=r.第四步，若第四步，若r=0r=0，則，則m m，n n的最大公約數(shù)等的最大公約數(shù)等 于于m m；否則，返回第二步；否則，返回第二步. . 第6頁(yè)/共21頁(yè)思考思考5:5:該算法的程序框圖如何表示？該算法的程序框圖如何表示？開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是

6、輸出輸出m結(jié)束結(jié)束否否第7頁(yè)/共21頁(yè)思考思考6:6:該程序框圖對(duì)應(yīng)的程序如何表述？該程序框圖對(duì)應(yīng)的程序如何表述？INPUT mINPUT m，n nDODOr=m MODnr=m MODnm=nm=nn=rn=rLOOP UNTILLOOP UNTIL r=0r=0PRINT mPRINT mENDEND開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm=nn=rr=0？是是輸出輸出m結(jié)束結(jié)束否否第8頁(yè)/共21頁(yè)思考思考7:7:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)的程序框圖和程序分別如何表示

7、？的最大公約數(shù)的程序框圖和程序分別如何表示？第9頁(yè)/共21頁(yè)開始開始輸入輸入m，n求求m除以除以n的余數(shù)的余數(shù)rm =nn 0？否否輸出輸出m結(jié)束結(jié)束是是n=rINPUT mINPUT m，n nWHILEWHILE n n0 0r=m MODnr=m MODnm=nm=nn=rn=rWENDWENDPRINT mPRINT mENDEND第10頁(yè)/共21頁(yè)知識(shí)探究（二）知識(shí)探究（二）: :更相減損術(shù)更相減損術(shù) 思考思考1:1:設(shè)兩個(gè)正整數(shù)設(shè)兩個(gè)正整數(shù)m mn n，若，若m-n=km-n=k，則，則m m與與n n的最大公約數(shù)和的最大公約數(shù)和n n與與k k的最大公約數(shù)相等的最大公約數(shù)相等.

8、.反復(fù)利用這個(gè)原理，可求得反復(fù)利用這個(gè)原理，可求得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，35-28=735-28=7，63-35=2863-35=28，第11頁(yè)/共21頁(yè)思考思考2:2:上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為上述求兩個(gè)正整數(shù)的最大公約數(shù)的方法稱為更相減損術(shù)更相減損術(shù). .一般地，用更相減損術(shù)求兩個(gè)正整數(shù)一般地，用更相減損術(shù)求兩個(gè)正整數(shù)m m，n n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？的最大公約數(shù)，可以用什么邏

9、輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計(jì)？第一步，給定兩個(gè)正整數(shù)第一步，給定兩個(gè)正整數(shù)m m，n(mn).n(mn). 第二步，計(jì)算第二步，計(jì)算m-nm-n所得的差所得的差k. k. 第三步，比較第三步，比較n n與與k k的大小，其中大者用的大小，其中大者用m m表表 示，小者用示，小者用n n表示表示. . 第四步，若第四步，若m=nm=n，則，則m m，n n的最大公約數(shù)等于的最大公約數(shù)等于 m m；否則，返回第二步；否則，返回第二步. . 第12頁(yè)/共21頁(yè)思考思考3:3:該算法的程序框圖如何表示？該算法的程序框圖如何表示？開始開始輸入輸入m，nnk？m=n是是輸出輸出m結(jié)束結(jié)束mn？k=

10、m- -n是是否否n=km=k否否第13頁(yè)/共21頁(yè)思考思考4:4:該程序框圖對(duì)應(yīng)的程序如何表述？該程序框圖對(duì)應(yīng)的程序如何表述？INPUT mINPUT m，n nWHILE WHILE m mn nk=m-nk=m-nIF nIF nk THENk THENm=nm=nn=kn=kELSEELSEm=km=kEND IFEND IFWENDWENDPRINT mPRINT mENDEND開始開始輸入輸入m，nnk？m=n是是輸 出輸 出m結(jié)束結(jié)束mn？k=m- -n是是否否n=km=k否否第14頁(yè)/共21頁(yè)“更相減損術(shù)更相減損術(shù)”在中國(guó)古代數(shù)學(xué)專著在中國(guó)古代數(shù)學(xué)專著九章算術(shù)九章算術(shù)中記述為：

11、中記述為： 可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也，以等數(shù)約之. . 第15頁(yè)/共21頁(yè)理論遷移理論遷移 例例1 1 分別用輾轉(zhuǎn)相除法和更相減損術(shù)求分別用輾轉(zhuǎn)相除法和更相減損術(shù)求168168與與9393的最大公約數(shù)的最大公約數(shù). . 輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法：168=93168=931+751+75， 93=7593=751+181+18， 75=1875=184+34+3， 18=318=36.6.第16頁(yè)/共21頁(yè)更相減損術(shù)更相減損術(shù):168-93=75:168-93=75， 93-

12、75=1893-75=18， 75-18=5775-18=57， 57-18=3957-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.第17頁(yè)/共21頁(yè) 例例2 2 求求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)橐?/p>

13、為270=65270=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.第18頁(yè)/共21頁(yè) 1. 1.輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正輾轉(zhuǎn)相除法，就是對(duì)于給定的兩個(gè)正整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不整數(shù)，用較大的數(shù)除以較小的數(shù)，若余數(shù)不為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)為零，則將余數(shù)和較小的數(shù)構(gòu)成新的一對(duì)數(shù)，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為，繼續(xù)上面的除法，直到大數(shù)被小數(shù)除盡為止，這時(shí)的較小的數(shù)即為原來兩個(gè)數(shù)的最大止，這時(shí)的較小的數(shù)即為原來兩個(gè)數(shù)的最大公約數(shù)公約數(shù). . 小結(jié)作業(yè)小結(jié)作業(yè) 2. 2. 更相減損術(shù)，就是對(duì)于給定的兩個(gè)正更相減損術(shù)，就是對(duì)于