1、算法案例 備課資料例題解析【例1】輸入兩個(gè)正整數(shù)a和b（ab），求它們的最大公約數(shù).解析：求兩個(gè)正整數(shù)a、b（ab）的最大公約數(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（ab）；S2求a/b的余數(shù)r；S3如果r0，則將ba，rb，再次求a/b的余數(shù)r，轉(zhuǎn)至S2；S4輸出最大公約數(shù)b.偽代碼如下：10Read a，b20rmod（a，b）30Ifr=0thenGoto 8040El

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

3、個(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=8162+102；816=1028；所以1734與816的最大公約數(shù)為102.再求102與1343的最大公約數(shù)，1343=10213+17；102=176.所以1343與102的最大公約數(shù)為17，即1734，816，1343的最大公約數(shù)為17.【例3】猴子吃桃問題：有一堆桃子不知數(shù)目，猴子第一天吃掉一半，覺得不過(guò)癮，又多吃了一只，第二天照此辦法，吃掉剩下桃子的一半另加一個(gè)，天天如

4、此，到第十天早上，猴子發(fā)現(xià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，1.這就是此題的數(shù)學(xué)模型.再考察上面從a9，a8直至a1的計(jì)算過(guò)程，這其實(shí)是一個(gè)遞推過(guò)程，這種遞推的方法在計(jì)算機(jī)解題中經(jīng)常用到.另一方面，這九步運(yùn)算從形式上完全一樣

5、，不同的只是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.50ii160Ifi1 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)解決.思考過(guò)程算法是在有限步驟內(nèi)求解某一問題所使用的一組定義明確的規(guī)則.通俗點(diǎn)說(shuō)，就是計(jì)算機(jī)解題的過(guò)程.1.本節(jié)通過(guò)對(duì)解決具體問題過(guò)程與步驟的分析（如求兩個(gè)數(shù)的最大公約數(shù)），體會(huì)算法的思想，進(jìn)一步了解算法的含義.2.本節(jié)通過(guò)閱讀中國(guó)古代數(shù)學(xué)中的算法案例，如約分術(shù)，體會(huì)中國(guó)古代數(shù)學(xué)對(duì)世界數(shù)