算法案例教案4蘇教版必修3

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

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

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

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

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

6、之差人數(shù)，每人所得數(shù)×人數(shù)盈物品總數(shù)，求得強盜有（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ù)列的前100項的值的算法，畫出流程圖并用偽代碼表示.我的思路：數(shù)列Fn有個特點，前兩個數(shù)都是1，從第3個數(shù)開始，每個數(shù)都是前兩個數(shù)的和，例如：3是1和2的和；13是5和8的和等等.此問題的算法用流程圖和偽代碼表示：a1；b1；n1；輸出n，；while n<100；nn

7、+1；ca+b；輸出n，；ab；bc；End while流程圖：例4：輸入兩個正整數(shù)a和b（a>b），求它們的最大公約數(shù).解析：求兩個正整數(shù)a、b（a>b）的最大公約數(shù)，可以歸結為求一數(shù)列：a，b，r1，r2，rn1，rn，rn+1，0此數(shù)列的首項與第二項是a和b，從第三項開始的各項，分別是前兩項相除所得的余數(shù)，如果余數(shù)為0，它的前項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流程圖如下：點評：算法的多樣性：對于同一個問題，可以有不同的算法.例如求1+2+3+100的和，可以采用如下方法：先求1+2，再加3，再加4，一直加到100，最后得到結果5050.也可以采用這樣的方法：1+2+3+100=（1+100）+（2+99）+（3+98）+（50+51）=50×101=5050.顯然，對于算法來說，后一種方法更簡便，而循環(huán)累加更適用于計算機解題.因此，為了有效地進行解題，不僅要保證算法正確，還要選擇好的算法，即方法簡單、運算步驟少，能迅速得出正

9、確結果的算法.例5：求1734，816，1343的最大公約數(shù).分析：三個數(shù)的最大公約數(shù)分別是每個數(shù)的約數(shù)，因此也是任意兩個數(shù)的最大公約數(shù)的約數(shù)，也就是說三個數(shù)的最大公約數(shù)是其中任意兩個數(shù)的最大公約數(shù)與第三個數(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：猴子吃桃問題：

10、有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮，又多吃了一只，第二天照此辦法，吃掉剩下桃子的一半另加一個，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問這堆桃子原來有多少個？解析：此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設第一天開始時有a1只桃子，第二天有a2只第9天有a9只，第10天有a10只.在a1，a2，a10中，只有a10=1是知道的，現(xiàn)要求a1，而我們可以看出a1，a2，a10之間存在一個簡單的關系：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ù)學模型.再考察上面從a9，a8直至a1的計算過程，這其實是一個遞推過程，這種遞推的方法在計算機解題中經(jīng)常用到.另一方面，這九步運算從形式上完全一樣，不同的只是ai的下標而已.由此，我們引入循環(huán)的處理方法，并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)，將算法改寫如下：S1a11；第10天的桃子數(shù)，a1的初值S2i9；計數(shù)器初值為9S3a02×（a1+1）；計算當天的桃子數(shù)S4a1a0；將當天的桃子數(shù)作為下一次計算的初值S5ii1；S6若i1，轉(zhuǎn)S3；S7輸出a0的值；偽代碼如下：10a1120i930a02×（a1+1）40a1a0.50ii160

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

13、界數(shù)學發(fā)展的貢獻.通過學生自己的親身實踐，親自去解決幾個算法設計的問題，才能體會到算法的基本思想.數(shù)學的其他內(nèi)容與算法密切相關，如函數(shù)、數(shù)列等.我們在學習這些內(nèi)容時要和算法聯(lián)系起來.課后作業(yè)課本P31 1，3.變式練習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兩個值中較大的一個值4.下面的偽代碼的算法目的是.Reada，b，c，If a>b thentaabbtElse if a>c thentaacctElse if b>c thentbbccbEnd ifPrint a，b，c答案：輸入三個數(shù)，要求由小到大的順序輸出5.流程圖填空：輸入x的值，通過函數(shù)y=求出y的值.其算法流程圖如下：答案：x1x<103x116.根據(jù)下面的流

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

16、0SS+2×HHH/2End forPrint S，H流程圖：9.用秦九韶算法求多項式f(x)=3x6+12x5+8x43.5x3+7.2x2+5x13當x=6時的值.答案：243168.2.10.區(qū)間二分法是求方程近似解的常用算法，其解法步驟為S1取a，b的中點x0=（a+b）/2；S2若f(x0)=0，則x0就是方程的根，否則若f(a)f(x0)>0，則ax0；否則bx0；S3若|ab|<c，計算終止，x0就是方程的根，否則轉(zhuǎn)S1.寫出用區(qū)間二分法求方程2x34x2+3x6=0在區(qū)間（10，10）之間的一個近似解（誤差不超過0.001）的一個算法.答案：解：偽代碼：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.求三個數(shù)390，455，546的最大公約數(shù).答案：13.12.迭代法是用于求方程或方程組近似根的一種常用的算法設計方法.設方程為f(x)=0，用某種數(shù)學方法導出等價的形式x=g(x)，然后按以下步驟執(zhí)行：（1）選一個方程的近似根，賦給變量x0；（2）將x0的

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