《算法案例》教案4(蘇教版必修3)

1、第八課時(shí) 算法案例教學(xué)目標(biāo)：本節(jié)通過(guò)算法案例的學(xué)習(xí)，進(jìn)一步理解算法的含義，掌握算法設(shè)計(jì)的常用方法.教學(xué)重點(diǎn)：如何在偽代碼中運(yùn)用條件語(yǔ)句.教學(xué)難點(diǎn)：如何在偽代碼中運(yùn)用條件語(yǔ)句.教學(xué)過(guò)程：.課題導(dǎo)入1.中國(guó)古代數(shù)學(xué)中算法的內(nèi)容是非常豐富的，比如，中國(guó)古代數(shù)學(xué)著作九章算術(shù)中介紹了下述“約分術(shù)”：“可半者半之，不可半者，副置分母、子之?dāng)?shù)，以少減多，更相減損，求其等也.以等數(shù)約之.”給出了求任意兩個(gè)數(shù)的最大公約數(shù)的一種算法，被后人稱為“更相減損術(shù)”.這種方法與歐氏的輾轉(zhuǎn)相除法異曲同工，本質(zhì)上是相同的.2.中國(guó)是研究不定方程最早的國(guó)家，公元初的五家共井問(wèn)題就是一個(gè)不定方程組問(wèn)題，公元5世紀(jì)的張丘建算經(jīng)中的

2、百雞問(wèn)題標(biāo)志著中國(guó)對(duì)不定方程理論有了系統(tǒng)研究.秦九韶的大衍求一術(shù)將不定方程與同余理論聯(lián)系起來(lái).研究不定方程要解決三個(gè)問(wèn)題：判斷何時(shí)有解；有解時(shí)決定解的個(gè)數(shù)；求出所有的解.二分法是用計(jì)算機(jī)求解多項(xiàng)式方程的一種常用方法.基本思想是：如果取a，b的中點(diǎn)x0=（a+b）/2；若f(x0)=0，則x0就是方程的根，若f(a)f(x0)>0，則解在（x0，b）上，以x0代替a，否則解在（a，x0）之間，以x0代替b，重復(fù)上述步驟，直到|ab|<c，c是一個(gè)很小的正數(shù)，計(jì)算終止，x0就是方程的根.講授新課例1：古今中外，許多人致力于圓周率的研究與計(jì)算.為了計(jì)算出圓周率的越來(lái)越好的近似值，一代代的

3、數(shù)學(xué)家為這個(gè)神秘的數(shù)貢獻(xiàn)了無(wú)數(shù)的時(shí)間與心血.我國(guó)東漢的數(shù)學(xué)家劉徽利用“割圓術(shù)”計(jì)算圓的面積及圓周率.“割圓術(shù)”被稱為千古絕技，它的原理是用圓內(nèi)接正多邊形的面積去逼近圓的面積，具體計(jì)算如下：在單位圓內(nèi)作內(nèi)接正六邊形，其面積記為A1，邊長(zhǎng)記為a1，在此基礎(chǔ)上作圓內(nèi)接正12邊形，面積記為A2，邊長(zhǎng)為a2一直做下去，記該圓的內(nèi)接正6×2n1邊形面積為An，邊長(zhǎng)為an.由于所考慮的是單位圓，計(jì)算出的An即為圓周率的近似值，n越大，An與越接近.你能設(shè)計(jì)這樣計(jì)算圓周率的一個(gè)算法嗎？我的思路：應(yīng)首先推導(dǎo)出an，an1，An，An1的關(guān)系.如圖，設(shè)PQ為圓內(nèi)接正6×2n1邊形的一邊，即PQ

4、=an1，OR為與PQ垂直的半徑，R為PQ弧的平分點(diǎn)，顯然PR=an.a1=1，an=PR=（n=2，3，4），A1=6××1×=，An=6×2n1××|OR|PT|=3×2n2an1（n=2，3，4）.通過(guò)上面兩式，從a11開始進(jìn)行迭代，可逐步計(jì)算出an與An.由于所考慮的是單位圓，計(jì)算出的An即為圓周率的近似值，n越大，An與越接近.算法和流程圖如下：BeginRead n1aFor I from 2 to nA3×2I2×aaSqrt22×Sqrt1a2/4；Print I，A，aEnd

5、forEnd流程圖：例2：有一個(gè)故事是講唐代大官楊塤提拔官員的經(jīng)過(guò).他讓兩個(gè)資格職位相同的候選人解答下面這個(gè)問(wèn)題，誰(shuí)先答出就提拔誰(shuí).“有人在林中散步，無(wú)意中聽到幾個(gè)強(qiáng)盜在商量怎樣分配搶來(lái)的布匹.若每人分6匹，就剩5匹；若每人分7匹，就差8匹.問(wèn)共有強(qiáng)盜幾個(gè)？布匹多少？”你能用一個(gè)簡(jiǎn)單算式求出強(qiáng)盜個(gè)數(shù)和布匹數(shù)嗎？我的思路：這個(gè)問(wèn)題可看作二元一次方程組問(wèn)題.問(wèn)題的特點(diǎn)是給出兩種分配方案，一種分法分不完，一種分法不夠分.中國(guó)古代的九章算術(shù)一書中搜集了許多這類問(wèn)題，各題都有完整的解法，后人稱這種算法為“盈不足術(shù)”.這種算法可以概括為兩句口訣：有余加不足，大減小來(lái)除.公式：（盈不足）÷兩次所得

6、之差人數(shù)，每人所得數(shù)×人數(shù)盈物品總數(shù)，求得強(qiáng)盜有（85）÷（76）13（人），布匹有6×13583（匹）.偽代碼：Read a，b，c，dx（a+b）/（dc）ycx+aprint x，y流程圖：例3：由F0=1，F(xiàn)1=1，F(xiàn)n=Fn2+Fn1所定義的數(shù)列Fn，稱為斐波那契數(shù)列，試設(shè)計(jì)一個(gè)求數(shù)列的前100項(xiàng)的值的算法，畫出流程圖并用偽代碼表示.我的思路：數(shù)列Fn有個(gè)特點(diǎn)，前兩個(gè)數(shù)都是1，從第3個(gè)數(shù)開始，每個(gè)數(shù)都是前兩個(gè)數(shù)的和，例如：3是1和2的和；13是5和8的和等等.此問(wèn)題的算法用流程圖和偽代碼表示：a1；b1；n1；輸出n，；while n<100；nn

7、+1；ca+b；輸出n，；ab；bc；End while流程圖：例4：輸入兩個(gè)正整數(shù)a和b（a>b），求它們的最大公約數(shù).解析：求兩個(gè)正整數(shù)a、b（a>b）的最大公約數(shù)，可以歸結(jié)為求一數(shù)列：a，b，r1，r2，rn1，rn，rn+1，0此數(shù)列的首項(xiàng)與第二項(xiàng)是a和b，從第三項(xiàng)開始的各項(xiàng)，分別是前兩項(xiàng)相除所得的余數(shù)，如果余數(shù)為0，它的前項(xiàng)rn+1即是a和b的最大公約數(shù)，這種方法叫做歐幾里得輾轉(zhuǎn)相除法，其算法如下：S1輸入a，b（a>b）；S2求a/b的余數(shù)r；S3如果r0，則將ba，rb，再次求a/b的余數(shù)r，轉(zhuǎn)至S2；S4輸出最大公約數(shù)b.偽代碼如下：10Read a，b20r

8、mod（a，b）30Ifr=0thenGoto 8040Else50ab60br70Goto 2080Print b流程圖如下：點(diǎn)評(píng)：算法的多樣性：對(duì)于同一個(gè)問(wèn)題，可以有不同的算法.例如求1+2+3+100的和，可以采用如下方法：先求1+2，再加3，再加4，一直加到100，最后得到結(jié)果5050.也可以采用這樣的方法：1+2+3+100=（1+100）+（2+99）+（3+98）+（50+51）=50×101=5050.顯然，對(duì)于算法來(lái)說(shuō)，后一種方法更簡(jiǎn)便，而循環(huán)累加更適用于計(jì)算機(jī)解題.因此，為了有效地進(jìn)行解題，不僅要保證算法正確，還要選擇好的算法，即方法簡(jiǎn)單、運(yùn)算步驟少，能迅速得出正

9、確結(jié)果的算法.例5：求1734，816，1343的最大公約數(shù).分析：三個(gè)數(shù)的最大公約數(shù)分別是每個(gè)數(shù)的約數(shù)，因此也是任意兩個(gè)數(shù)的最大公約數(shù)的約數(shù)，也就是說(shuō)三個(gè)數(shù)的最大公約數(shù)是其中任意兩個(gè)數(shù)的最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù).解：用“輾轉(zhuǎn)相除法”.先求1734和816的最大公約數(shù)，1734=816×2+102；816=102×8；所以1734與816的最大公約數(shù)為102.再求102與1343的最大公約數(shù)，1343=102×13+17；102=17×6.所以1343與102的最大公約數(shù)為17，即1734，816，1343的最大公約數(shù)為17.例6：猴子吃桃問(wèn)題：

10、有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過(guò)癮，又多吃了一只，第二天照此辦法，吃掉剩下桃子的一半另加一個(gè)，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問(wèn)這堆桃子原來(lái)有多少個(gè)？解析：此題粗看起來(lái)有些無(wú)從著手的感覺，那么怎樣開始呢？假設(shè)第一天開始時(shí)有a1只桃子，第二天有a2只第9天有a9只，第10天有a10只.在a1，a2，a10中，只有a10=1是知道的，現(xiàn)要求a1，而我們可以看出a1，a2，a10之間存在一個(gè)簡(jiǎn)單的關(guān)系：a9=2×（a10+1），a8=2×（a9+1），a1=2×（a2+1）.也就是：ai=2×（ai+1+1）i=9，8，7，6，

11、1.這就是此題的數(shù)學(xué)模型.再考察上面從a9，a8直至a1的計(jì)算過(guò)程，這其實(shí)是一個(gè)遞推過(guò)程，這種遞推的方法在計(jì)算機(jī)解題中經(jīng)常用到.另一方面，這九步運(yùn)算從形式上完全一樣，不同的只是ai的下標(biāo)而已.由此，我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)，將算法改寫如下：S1a11；第10天的桃子數(shù)，a1的初值S2i9；計(jì)數(shù)器初值為9S3a02×（a1+1）；計(jì)算當(dāng)天的桃子數(shù)S4a1a0；將當(dāng)天的桃子數(shù)作為下一次計(jì)算的初值S5ii1；S6若i1，轉(zhuǎn)S3；S7輸出a0的值；偽代碼如下：10a1120i930a02×（a1+1）40a1a0.50ii160

12、Ifi1 then Goto 3070Else80Print a0流程圖如下：點(diǎn)評(píng)：這是一個(gè)從具體到抽象的過(guò)程，具體方法：（1）弄清如果由人來(lái)做，應(yīng)該采取哪些步驟；（2）對(duì)這些步驟進(jìn)行歸納整理，抽象出數(shù)學(xué)模型；（3）對(duì)其中的重復(fù)步驟，通過(guò)使用相同變量等方式求得形式的統(tǒng)一，然后簡(jiǎn)練地用循環(huán)解決.課堂練習(xí)課本P30 1，2.課時(shí)小結(jié)算法是在有限步驟內(nèi)求解某一問(wèn)題所使用的一組定義明確的規(guī)則.通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程.1.本節(jié)通過(guò)對(duì)解決具體問(wèn)題過(guò)程與步驟的分析（如求兩個(gè)數(shù)的最大公約數(shù)），體會(huì)算法的思想，進(jìn)一步了解算法的含義.2.本節(jié)通過(guò)閱讀中國(guó)古代數(shù)學(xué)中的算法案例，如約分術(shù)，體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世

13、界數(shù)學(xué)發(fā)展的貢獻(xiàn).通過(guò)學(xué)生自己的親身實(shí)踐，親自去解決幾個(gè)算法設(shè)計(jì)的問(wèn)題，才能體會(huì)到算法的基本思想.數(shù)學(xué)的其他內(nèi)容與算法密切相關(guān)，如函數(shù)、數(shù)列等.我們?cè)趯W(xué)習(xí)這些內(nèi)容時(shí)要和算法聯(lián)系起來(lái).課后作業(yè)課本P31 1，3.變式練習(xí)1.數(shù)4557、1953、5115的最大公約數(shù)是（）A.31B.93C.217D.651答案：B2.下面的偽代碼的算法目的是（）10Read x，y20mx30ny40If m/n=int（m/n） then Goto 9050cmint（m/n）×n60mn70nc80Goto 4090a（x×y）/n100 Print aA.求x，y的最小公倍數(shù)B.求x，

14、y的最大公約數(shù)C.求x被y整除的商D.求y除以x的余數(shù)答案：B3.下面的偽代碼的算法目的是.ReadX，YIf X>Y thenPrint XElsePrint YEnd if答案：輸出x，y兩個(gè)值中較大的一個(gè)值4.下面的偽代碼的算法目的是.Reada，b，c，If a>b thentaabbtElse if a>c thentaacctElse if b>c thentbbccbEnd ifPrint a，b，c答案：輸入三個(gè)數(shù)，要求由小到大的順序輸出5.流程圖填空：輸入x的值，通過(guò)函數(shù)y=求出y的值.其算法流程圖如下：答案：x1x<103x116.根據(jù)下面的流

15、程圖寫出其算法的偽代碼.答案：解：這是計(jì)算2+4+6+200的一個(gè)算法，可以用循環(huán)語(yǔ)句表示為T0For I from 2 to 200 step 2TT+IEnd for7.輸入一個(gè)華氏溫度，要求輸出攝氏溫度.公式為C=（F32）.寫出其算法的偽代碼.答案：解：這是順序結(jié)構(gòu).其偽代碼如下：Read FC（F32）Print C8.一個(gè)小球從100 m高度自由落下，每次落地后反跳回原高度的一半，再落下.設(shè)計(jì)一個(gè)算法，求它在第10次落地時(shí)共經(jīng)過(guò)多少米？第10次反彈多高？畫出流程圖并用偽代碼表示.答案：解：這是一個(gè)循環(huán)結(jié)構(gòu)，可以用循環(huán)語(yǔ)句實(shí)現(xiàn).偽代碼：S100HS/2For n from 2 to1

16、0SS+2×HHH/2End forPrint S，H流程圖：9.用秦九韶算法求多項(xiàng)式f(x)=3x6+12x5+8x43.5x3+7.2x2+5x13當(dāng)x=6時(shí)的值.答案：243168.2.10.區(qū)間二分法是求方程近似解的常用算法，其解法步驟為S1取a，b的中點(diǎn)x0=（a+b）/2；S2若f(x0)=0，則x0就是方程的根，否則若f(a)f(x0)>0，則ax0；否則bx0；S3若|ab|<c，計(jì)算終止，x0就是方程的根，否則轉(zhuǎn)S1.寫出用區(qū)間二分法求方程2x34x2+3x6=0在區(qū)間（10，10）之間的一個(gè)近似解（誤差不超過(guò)0.001）的一個(gè)算法.答案：解：偽代碼：1

17、0Read a，b，c20x0（a+b）/230f（a）2a34a2+3a640f（x0）2x34x2+3x650If f（x0）=0 then Goto 12060If f（a）f（x0）<0 then70bx080Else90ax0100End if110If |ab|cthen Goto 20120Print x0流程圖：11.求三個(gè)數(shù)390，455，546的最大公約數(shù).答案：13.12.迭代法是用于求方程或方程組近似根的一種常用的算法設(shè)計(jì)方法.設(shè)方程為f(x)=0，用某種數(shù)學(xué)方法導(dǎo)出等價(jià)的形式x=g(x)，然后按以下步驟執(zhí)行：（1）選一個(gè)方程的近似根，賦給變量x0；（2）將x0的

18、值保存于變量x1，然后計(jì)算g(x1)，并將結(jié)果存于變量x0；（3）當(dāng)x0與x1的差的絕對(duì)值還小于指定的精度要求時(shí)，重復(fù)步驟（2）的計(jì)算.若方程有根，則按上述方法求得的x0就認(rèn)為是方程的根.試用迭代法求某個(gè)數(shù)的平方根，用流程圖和偽代碼表示問(wèn)題的算法.已知求平方根的迭代公式為x1=（x0+）.答案：解：設(shè)平方根的解為x，可假定一個(gè)初值x0=a/2（估計(jì)值），根據(jù)迭代公式得到一個(gè)新的值x1，這個(gè)新值比初值x0更接近要求的值x；再以新值作為初值，即x1x0，重新按原來(lái)的方法求x1，重復(fù)這一過(guò)程直到|x1x0|<（某一給定的精度）.此時(shí)可將x0作為問(wèn)題的解.偽代碼：Readx0，Repeatx1（x0+a/x0）/2r|x1x0|x0x1Untilr<Printx0流程圖：13.寫出計(jì)算1+2!+3!+20!的算法的偽代碼和流程圖.答案：解析：這是一個(gè)循環(huán)結(jié)構(gòu)，可以用循環(huán)語(yǔ)句實(shí)現(xiàn).偽代碼和流程圖如下：T1S0For n from 1 to 20TT×nSS+TEnd forPrint S14.未知數(shù)的個(gè)數(shù)多于方程個(gè)數(shù)的方程（組）叫做不定方程.最