數(shù)學名師導航算法案例

學必求其心得，業(yè)必貴于專精學必求其心得，業(yè)必貴于專精學必求其心得，業(yè)必貴于專精5.4算法案例名師導航三點剖析一、“韓信點兵-—孫子問題”的算法在“韓信點兵”的問題中，當士兵排成3列縱隊，結(jié)果多余2人說明士兵的總?cè)藬?shù)除以3之后余數(shù)是2,所以算法步驟就是將所有除以3之后余數(shù)是2的正整數(shù)找出來,按照從小到大的順序排成一列數(shù)；當士兵排成5列縱隊，結(jié)果多余3人說明士兵的總?cè)藬?shù)除以5之后余數(shù)是3，所以算法步驟就是將所有除以5之后余數(shù)是3的正整數(shù)找出來，按照從小到大的順序排成一列數(shù);當士兵排成7列縱隊，結(jié)果多余2人說明士兵的總?cè)藬?shù)除以7之后余數(shù)是2，所以算法步驟就是將所有除以7之后余數(shù)是2的正整數(shù)找出來，按照從小到大的順序排成一列數(shù).這樣完成上述步驟之后,就找到了“韓信點兵”問題的一個算法，從而也得出了解決“孫子問題”的算法。我國古代數(shù)學的發(fā)展有著自己的鮮明特色，走著與西方完全不同的道路,即使今天看來，這條路仍然有很大的優(yōu)越性.這條道路的一個重要特色就是“寓理于算”，即把要解決的問題“算法化"。本節(jié)中案例1直接體現(xiàn)了我國古代算法在數(shù)學和計算機程序設計中的廣泛應用。二、求兩個正整數(shù)最大公約數(shù)的算法.求兩個正整數(shù)的最大公約數(shù)的算法常見的有“歐幾里得輾轉(zhuǎn)相除法”和“更相減損術(shù)".1.“歐幾里得輾轉(zhuǎn)相除法"求兩個正整數(shù)a、b（a>b）的最大公約數(shù)，可以歸結(jié)為求一數(shù)列：a，b，r1，r2，…，rn－1，rn，rn+1，0。此數(shù)列的首項與第二項是a和b，從第三項開始的各項，分別是前兩項相除所得的余數(shù)，如果余數(shù)為0,它的前項rn+1即是a和b的最大公約數(shù).其步驟是：計算出a除以b的余數(shù)r,若r=0，則b為a、b的最大公約數(shù);若r≠0，則把b作為被除數(shù),把余數(shù)r作為除數(shù)，繼續(xù)運算,直到余數(shù)為0，此時的除數(shù)即為自然數(shù)a、b的最大公約數(shù).2?！案鄿p損術(shù)”“更相減損術(shù)”是我國的《九章算術(shù)》中提到的一種求兩個正數(shù)最大公約數(shù)的算法，它與“輾轉(zhuǎn)相除法”相似.它的基本思想是：讓兩個數(shù)中較大的數(shù)減去較小的數(shù)，以差和較小的數(shù)組成一對新數(shù)，再比較兩數(shù)的大小，然后讓兩數(shù)中較大的數(shù)減去較小的數(shù)，以同樣的操作一直做下去，直到產(chǎn)生一對相等的數(shù)為止，這個數(shù)就是兩個數(shù)的最大公約數(shù).從某種意義上說，“更相減損術(shù)"就是“歐幾里得輾轉(zhuǎn)相除法”.問題探究問題1：古今中外，許多人致力于圓周率的研究與計算.為了計算出圓周率的越來越好的近似值，一代代的數(shù)學家為這個神秘的數(shù)貢獻了無數(shù)的時間與心血。我國東漢的數(shù)學家劉徽利用“割圓術(shù)”計算圓的面積及圓周率π?！案顖A術(shù)”被稱為千古絕技，它的原理是用圓內(nèi)接正多邊形的面積去逼近圓的面積,具體計算如下：在單位圓內(nèi)作內(nèi)接正六邊形,其面積記為A1，邊長記為a1,在此基礎上作圓內(nèi)接正12邊形，面積記為A2，邊長為a2……一直作下去，記該圓的內(nèi)接正6×2n－1邊形面積為An，邊長為an.由于所考慮的是單位圓，計算出的An即為圓周率π的近似值,n越大，An與π越接近。你能設計這樣計算圓周率的一個算法嗎?圖5—31探究：應首先推導出an，an－1，An,An－1的關(guān)系。如圖531所示，設PQ為圓內(nèi)接正6×2n－1邊形的一邊，即PQ=an－1，OR為與PQ垂直的半徑,R為PQ弧的平分點,顯然PR=an.a1=1，通過上面兩式，從a1＝1開始進行迭代，可逐步計算出an與An.由于所考慮的是單位圓,計算出的An即為圓周率π的近似值,n越大，An與π越接近。算法和流程圖如下：Readn1←aForIfrom2tonA←3×2I－2×aa←Sqrt［2－2×Sqrt［1－a2/4］];PrintI，A，aEndforEnd流程圖（如圖5—32所示）：圖5-32問題2:據(jù)我國古書《唐闕史》記載，公元855年前后，有一次，青州府要從兩個辦事員中選拔一人當官，但是這兩個辦事員的職務、資歷、能力和成績、表現(xiàn)并無顯著的差異，而名額只有一個，提升誰？負責提升的官員感到十分為難，就去請教青州的地方官楊塤.楊塤考慮了很久,想出了一個主意,他說：“官員應該能寫會算，你把他們叫來，我出一道題當場考考他們,誰先算出就提升誰?！蓖瑫r，楊塤讓人把他出的題抄成兩份，負責提升的官員找來兩位辦事員，給每人一袋算籌,一聲令下兩個人開始解題，不一會兒，其中一個先算出了正確答案，楊塤當場宣布提升他。大家都認為楊塤這種辦法比較公允。在古代，像這樣用“數(shù)學競賽"來決定官員晉升是為數(shù)不少的.題目的大意如下：一天夜里，有一個人在林中散步,無意中聽到幾個強盜在商量怎樣分配搶來的布匹，只聽見他們說：“如果每人分6匹，就剩5匹；如果每人分7匹，就差8匹.”問有強盜幾個？布匹多少？能用一個簡單算法求出強盜個數(shù)和布匹數(shù)嗎？探究:中國古代的《九章算術(shù)》一書中搜集了許多這類問題，各題都有完整的解法，后人稱這種算法為-—“盈不足術(shù)”。這種算法可以概括為兩句口訣：有余加不足，大減小來除。公式:(盈＋不足)÷兩次所得之差＝人數(shù),每人所得數(shù)×人數(shù)＋盈＝物品總數(shù)，求得強盜有（8＋5）÷（7－6）＝13(人），布匹有6×13＋5＝83（匹）。偽代碼：Reada，b，c,dx←（a+b）/（d－c)y←cx+aprintx，y流程圖（如圖5—33所示）:圖5-33除此之外,這個問題可看作二元一次方程組問題.問題的特點是給出兩種分配方案,一種分法分不完，一種分法不夠分。所以,本題還有一種方法,就是利用二元一次方程組的方法來解題。首先，根據(jù)題意設有強盜x個,布匹y匹，則可列出二元一次方程如下：6x=y-5,7x=y+7。然后再根據(jù)解二元一次方程組的算法寫出該題的算法即可。精題精講例1．求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.綠色通道求兩個正整數(shù)a、b（a〉b）的最大公約數(shù)，可以歸結(jié)為求一數(shù)列:a,b，r1，r2，…，rn－1,rn，rn+1，0,此數(shù)列的首項與第二項是a和b,從第三項開始的各項，分別是前兩項相除所得的余數(shù)，如果余數(shù)為0，它的前項rn+1即是a和b的最大公約數(shù)，這種方法叫做“歐幾里得輾轉(zhuǎn)相除法”。例2．猴子吃桃問題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過癮,又多吃了一只，第二天照此辦法，吃掉剩下桃子的一半另加一個，天天如此，到第十天早上，猴子發(fā)現(xiàn)只剩一只桃子了，問這堆桃子原來有多少個?思路解析此題粗看起來有些無從著手的感覺，那么怎樣開始呢？假設第一天開始時有a1只桃子，第二天有a2只,…,第9天有a9只,第10天有a10只。在a1，a2，…,a10中,只有a10=1是知道的,現(xiàn)要求a1，而我們可以看出a1，a2，…，a10之間存在一個簡單的關(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ù)學模型。再考察上面從a9，a8直至a1的計算過程,這其實是一個遞推過程，這種遞推的方法在計算機解題中經(jīng)常用到.另一方面,這九步運算從形式上完全一樣，不同的只是ai的下標而已。由此，我們引入循環(huán)的處理方法,并統(tǒng)一用a0表示前一天的桃子數(shù)，a1表示后一天的桃子數(shù)。解：本題的算法如下:S1a1←1；{第10天的桃子數(shù),a1S2i←9；｛計數(shù)器初值為9｝S3a0←2×（a1+1S4a1←a0S5i←i－1；S6若i≥1，轉(zhuǎn)S3；S7輸出a0的值。偽代碼如下：10a1←20i←930a0←2×（a1+140a1←a50i←i－160If