高中數(shù)學(xué)第1章算法初步1.4算法案例互動(dòng)課堂學(xué)案蘇教版必修.docx

1.4 算法案例互動(dòng)課堂例1 求1 734,816,1 343的最大公約數(shù).【分析】三個(gè)數(shù)的最大公約數(shù)分別是每個(gè)數(shù)的約數(shù),因此也是任意兩個(gè)數(shù)的最大公約數(shù)的約數(shù),也就是說三個(gè)數(shù)的最大公約數(shù)是其中任意兩個(gè)數(shù)的最大公約數(shù)與第三個(gè)數(shù)的最大公約數(shù).【解】用“輾轉(zhuǎn)相除法”. 先求1 734和816的最大公約數(shù),1 734=8162+102；816=1028； 所以1 734與816的最大公約數(shù)為102. 再求102與1 343的最大公約數(shù),1 343=10213+17；102=176. 所以1 343與102的最大公約數(shù)為17,即1 734,816,1 343的最大公約數(shù)為17.【點(diǎn)評(píng)】求兩個(gè)正整數(shù)a、b（ab）的最大公約數(shù),可以歸結(jié)為求一數(shù)列：a,b,r1,r2,rn-1,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)相除法”.例2 猴子吃桃問題：有一堆桃子不知數(shù)目,猴子第一天吃掉一半,覺得不過癮,又多吃了一只,第二天照此辦法,吃掉剩下桃子的一半另加一個(gè),天天如此,到第十天早上,猴子發(fā)現(xiàn)只剩一只桃子了,問這堆桃子原來有多少個(gè)？【分析】此題粗看起來有些無從著手的感覺,那么怎樣開始呢？假設(shè)第一天開始時(shí)有a1只桃子,第二天有a2只,第9天有a9只,第10天有a10只.在a1,a2,a10中,只有a10=1是知道的,現(xiàn)要求a1,而我們可以看出a1,a2,a10之間存在一個(gè)簡單的關(guān)系：a9=2（a10+1）,a8=2（a9+1）,a1=2（a2+1）. 也就是：ai=2（ai+1+1）,i=9,8,7,6,1. 這就是此題的數(shù)學(xué)模型. 再考查上面從a9,a8直至a1的計(jì)算過程,這其實(shí)是一個(gè)遞推過程,這種遞推的方法在計(jì)算機(jī)解題中經(jīng)常用到.另一方面,這九步運(yùn)算從形式上完全一樣,不同的只是ai的下標(biāo)而已.由此,我們引入循環(huán)的處理方法,并統(tǒng)一用a0表示前一天的桃子數(shù),a1表示后一天的桃子數(shù).【解】本題的算法如下： 第一步：a11；第10天的桃子數(shù),a1的初值 第二步：i9；計(jì)數(shù)器初值為9 第三步：a02（a1+1）；計(jì)算當(dāng)天的桃子數(shù) 第四步：a1a0；將當(dāng)天的桃子數(shù)作為下一次計(jì)算的初值 第五步：ii-1； 第六步：若i1,轉(zhuǎn)第三步； 第七步：輸出a0的值. 偽代碼如下：a11i9If i1 Thena02（a1+1）a1a0ii-1End IfPrint a0 流程圖如下圖所示：【點(diǎn)評(píng)】這類題的解法是一個(gè)從具體到抽象的過程,具體方法是：（1）弄清如果由人來做,應(yīng)該采取哪些步驟；（2）對(duì)這些步驟進(jìn)行歸納整理,抽象出數(shù)學(xué)模型；（3）對(duì)其中的重復(fù)步驟,通過使用相同變量等方式求得形式的統(tǒng)一,然后簡練地用循環(huán)解決.例3 古今中外,許多人致力于圓周率的研究與計(jì)算.為了計(jì)算出圓周率的越來越好的近似值,一代代的數(shù)學(xué)家為這個(gè)神秘的數(shù)貢獻(xiàn)了無數(shù)的時(shí)間與心血.我國東漢的數(shù)學(xué)家劉徽利用“割圓術(shù)”計(jì)算圓的面積及圓周率.“割圓術(shù)”被稱為千古絕技,它的原理是用圓內(nèi)接正多邊形的面積去逼近圓的面積,具體計(jì)算如下： 在單位圓內(nèi)作內(nèi)接正六邊形,其面積記為A1,邊長記為a1,在此基礎(chǔ)上作圓內(nèi)接正12邊形,面積記為A2,邊長為a2一直作下去,記該圓的內(nèi)接正62n-1邊形面積為An,邊長為an.由于所考慮的是單位圓,計(jì)算出的An即為圓周率的近似值,n越大,An與越接近.你能設(shè)計(jì)這樣計(jì)算圓周率的一個(gè)算法嗎？【分析】應(yīng)首先推導(dǎo)出an,an-1,An,An-1的關(guān)系.如右圖所示,設(shè)PQ為圓內(nèi)接正62n-1邊形的一邊,即PQ=an-1,OR為與PQ垂直的半徑,R為PQ弧的平分點(diǎn),顯然PR=an.a1=1,an=PR=（n=2,3,4）,A1=61=,An=62n-1|OR|PT|=32n-2an-1（n=2,3,4）. 通過上面兩式,從a1=1開始進(jìn)行迭代,可逐步計(jì)算出an與An.由于所考慮的是單位圓,計(jì)算出的An即為圓周率的近似值,n越大,An與越接近.算法和流程圖如下：Read n1aFor I From 2 To n A32n-2a aSqrt2-2Sqrt1-a2/4End ForPrint I,A,a 流程圖（如下圖所示）：例4 據(jù)我國古書唐闕史記載,公元855年前后,有一次,青州府要從兩個(gè)辦事員中選拔一人當(dāng)官,但是這兩個(gè)辦事員的職務(wù)、資歷、能力和成績,表現(xiàn)并無顯著的差異,而名額只有一個(gè),提升誰？負(fù)責(zé)提升的官員感到十分為難,就去請(qǐng)教青州的地方官楊塤.楊塤考慮了很久,想出了一個(gè)主意,他說：“官員應(yīng)該能寫會(huì)算,你把他們叫來,我出一道題當(dāng)場考考他們,誰先算出就提升誰.”同時(shí),楊塤讓人把他出的題抄成兩份,負(fù)責(zé)提升的官員找來兩位辦事員,給每人一袋算籌,一聲令下兩個(gè)人開始解題,不一會(huì)兒,其中一個(gè)先算出了正確答案,楊塤當(dāng)場宣布提升他.大家都認(rèn)為楊塤這種辦法比較公允.在古代,像這樣用“數(shù)學(xué)競賽”來決定官員晉升是為數(shù)不少的.題目的大意如下: 一天夜里,有一個(gè)人在林中散步,無意中聽到幾個(gè)強(qiáng)盜在商量怎樣分配搶來的布匹,只聽見他們說：“如果每人分6匹,就剩5匹；如果每人分7匹,就差8匹.”問有強(qiáng)盜幾個(gè)？布匹多少？能用一個(gè)簡單算法求出強(qiáng)盜個(gè)數(shù)和布匹數(shù)嗎？【分析】中國古代的九章算術(shù)一書中搜集了許多這類問題,各題都有完整的解法,后人稱這種算法為“盈不足術(shù)”. 這種算法可以概括為兩句口訣：有余加不足,大減小來除. 公式：（盈不足）兩次所得之差=人數(shù), 每人所得數(shù)人數(shù)盈=物品總數(shù), 求得強(qiáng)盜有（85）（7-6）=13（人）,布匹有6135=83（匹）. 偽代碼：Read a,b,c,dx（a+b）/（d-c）ycx+aPrint x,y 流程圖（如下圖所示）： 除此之外,這個(gè)問題可看作二元一次