[語文]算法案例彭飛

《[語文]算法案例彭飛》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、算法案例知識探究（一）:輾轉(zhuǎn)相除法思考1:18與30的最大公約數(shù)是多少？你是怎樣得到的？先用兩個數(shù)公有的質(zhì)因數(shù)連續(xù)去除，一直除到所得的商是互質(zhì)數(shù)為止，然后把所有的除數(shù)連乘起來即為最大公約數(shù).思考2:對于8251與6105這兩個數(shù)，由于其公有的質(zhì)因數(shù)較大，利用上述方法求最大公約數(shù)就比較困難.注意到8251=6105×1+2146，那么8251與6105這兩個數(shù)的公約數(shù)和6105與2146的公約數(shù)有什么關(guān)系？思考3:又6105=2146×2+1813，同理，6105與2146的公約數(shù)和2146與1813的公約數(shù)相等.重復(fù)上述操作，你能得到8251與6105這兩個數(shù)的最大公約數(shù)

2、嗎？2146=1813×1+333，148=37×4+0.333=148×2+37，1813=333×5+148，8251=6105×1+2146，6105=2146×2+1813，大數(shù)除以小數(shù)，直到余數(shù)為0，最后的除數(shù)為最大公約數(shù)思考4:上述求兩個正整數(shù)的最大公約數(shù)的方法稱為輾轉(zhuǎn)相除法或歐幾里得算法.一般地，用輾轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)，可以用什么邏輯結(jié)構(gòu)來構(gòu)造算法？其算法步驟如何設(shè)計？第一步，給定兩個正整數(shù)m，n(m>n).第二步，計算m除以n所得的余數(shù)r.第三步，m=n，n=r.第四步，若r=0，則m，n的最大公約數(shù)等于m；否則，返回第二步.思考5:該

3、算法的程序框圖如何表示？開始輸入m，nm=nn=rr=0？是輸出m結(jié)束否求m除以n的余數(shù)r思考6:該程序框圖對應(yīng)的程序如何表述？INPUTm，nDOr=mMODnm=nn=rLOOPUNTILr=0PRINTmEND開始輸入m，nm=nn=rr=0？是輸出m結(jié)束否求m除以n的余數(shù)r思考7:如果用當(dāng)型循環(huán)結(jié)構(gòu)構(gòu)造算法，則用輾轉(zhuǎn)相除法求兩個正整數(shù)m，n的最大公約數(shù)的程序框圖和程序分別如何表示？開始輸入m，n求m除以n的余數(shù)rm=nn>0？否輸出m結(jié)束是n=rINPUTm，nWHILEn>0r=mMODnm=nn=rWENDPRINTmEND知識探究（二）:更相減損術(shù)思考1:求

4、得98與63的最大公約數(shù)為多少？98-63=35，14-7=7.21-7=14，28-7=21，35-28=7，63-35=28，大數(shù)減小數(shù)，直到所得的減數(shù)與差相等，最后相等的減數(shù)或差作為最大公約數(shù)?！案鄿p損術(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

5、-18=21，21-18=3，18-3=15，15-3=12，12-3=9，9-3=6，6-3=3.1、求兩個數(shù)的最大公約數(shù)的兩種方法分別是（）和（）。2、兩個數(shù)21672，8127的最大公約數(shù)是（）A、2709B、2606C、2703D、2706練習(xí):3.求325，130，270三個數(shù)的最大公約數(shù).因為325=130×2+65，130=65×2，所以325與130的最大公約數(shù)是65.因為270=65×4+10，65=10×6+5，10=5×2，所以65與270最大公約數(shù)是5.故325，130，270三個數(shù)的最大公約數(shù)是5.思考怎樣求多項式f(x)=x5+x4+x3+x2

6、+x+1當(dāng)x=5時的值呢？計算多項式ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１當(dāng)x=5的值的算法：算法1：因為ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906計算多項式ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１當(dāng)x=5的值的算法：算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１分析：兩種算法各用了幾次乘法運

7、算？和幾次加法運算？算法1：因為ｆ(ｘ)=ｘ５＋ｘ４＋ｘ３＋ｘ２＋ｘ＋１所以ｆ(5)=5５＋5４＋5３＋5２＋5＋１=3125＋625＋125＋25＋5＋１=3906算法2：ｆ(5)=5５＋5４＋5３＋5２＋5＋１=5×(5４＋5３＋5２＋5＋１)＋１=5×(5×(5３＋5２＋5＋１)＋１)＋１=5×(5×(5×(5２+5+１)+１)+１)+１=5×(5×(5×(5×(5+１)+１)+１)+１)+１共做了1+2+3+4=10次乘法運算，5次加法運算。共做了4次乘法運算，5次加法運算。《數(shù)書九章》——秦九韶算法設(shè)是一個n次的多項