學必求其心得，業必貴于專精學必求其心得，業必貴于專精學必求其心得，業必貴于專精5．4算法案例案例探究有一個故事是講唐代大官楊塤提拔官員的經過．他讓兩個資格職位相同的候選人解答下面這個問題，誰先答出就提拔誰．“有人在林中散步，無意中聽到幾個強盜在商量怎樣分配搶來的布匹．若每人分6匹,就剩5匹；若每人分7匹,就差8匹．問共有強盜幾個？布匹多少？”你能用一個簡單算式求出強盜個數和布匹數嗎?解析:這個問題可看作二元一次方程組問題．問題的特點是給出兩種分配方案，一種分法分不完，一種分法不夠分．中國古代的《九章算術》一書中搜集了許多這類問題，各題都有完整的解法，后人稱這種算法為—-“盈不足術”．這種算法可以概括為兩句口訣：有余加不足，大減小來除．公式：(盈+不足）÷兩次所得之差=人數，每人所得數×人數+盈=物品總數，求得強盜有（8+5）÷（7—6)=13（人)，布匹有6×13+5=83（匹）．偽代碼：Reada,b,c，dx←(a+b)/(d-c)y←cx+aPrintx，y流程圖：自學導引1．int(x)表示不超過x的最大整數．2．mod(a，b)表示a除以b所得的余數,稱b為模．3．輾轉相除法是用于求兩個數的最大公約數的一種方法,這種算法由歐幾里得在公元前300年左右首先提出，因而又叫歐幾里得輾轉相除法．4．歐幾里得輾轉相除法找出a，b的最大公約數的步驟是：計算出a÷b的余數r，若r=0，則b為a,b的最大公約數；若r≠0，則把前面的除數b作為新的被除數，把余數r作為新的除數，繼續運算，直到余數為0，此時的除數即為正整數a，b的最大公約數．5．秦九韶算法是我國南宋數學家秦九韶在他的代表作《數書九章》中提出的一種用于計算一次同余式組的方法，稱作大衍求一術．疑難剖析【例1】輸入兩個正整數a和b（a>b）,求它們的最大公約數．思路分析：求兩個正整數a、b(a〉b）的最大公約數，可以歸結為求一數列：a,b,r1，r2，…，rn-1，rn,rn—1，0此數列的首項與第二項是a和b,從第三項開始的各項,分別是前兩項相除所得的余數，如果余數為0,它的前項rn-1即是a和b的最大公約數，這種方法叫做歐幾里得輾轉相除法，其算法如下：S1輸入a,b(a＞b)S2求a/b的余數r；S3如果r≠0，則將b→a,r→b,再次求a/b的余數r，轉至S2；S4輸出最大公約數B．解：流程圖如下：偽代碼如下：10Reada，b20r←Mod(a，b)30Ifr=0ThenGoto8040Else50a60b←r70Goto2080Printb90End思維啟示：（1）每行語句前邊有一個數字，我們稱這個數字為行號，它的作用表示該行在偽代碼中的位置和執行順序．(2）If語句和Goto語句兩個語句可結合能夠實現循環．變式訓練:用輾轉相除法、更相減損術求228,1995最大公約數．分析:使用輾轉相除法，我們就根據a=nb+r這個式子，反復執行，直到r=0為止．用更相減損術我們就根據r=a-b這個式子，反復執行就可．解:所以有以下解法:用輾轉相除法：1995=8×228+171228=1×171+57171=3×57+0所以：57就是228和1995的最大公約數．用更相減損術：1995-228=17671767-228=15391539-228=13111311—228=10831083-228=855855—228=627627-228=399399-228=171228-171=57171-57=114114—57=5757—57=0則57就是228,1995的最大公約數．思維啟示：由該題可以看出，輾轉相除法得最大公約數步驟較少，而更相減損術運算簡易，兩種方法各有所長．【例2】用二分法設計一個求方程x2-2=0的近似根的算法．思路分析：回顧二分法解方程的過程，并假設所求近似根與精確解的差的絕對值不超過0．005,則不難設計出以下步驟:第一步：令f（x)=x2—2．因為f(1）〈0，f（2)>0，所以設x1=1,x2=2．第二步：令m=，判斷f（m）是否為0．若是，則m為所求;若否,則繼續判斷f(x1）·f(m）大于0還是小于0．第三步：若f(x1)·f(m)＞0,則令x1=m;否則，令x2=m．第四步:判斷|x1—x2｜<0．005是否成立？若是,則x1,x2之間的任意取值均為滿足條件的近似根;若否，則返回第二步．解：流程圖如圖：偽代碼：10f（x）←x∧20Read“輸入誤差ε和初值x1,x2”；ε，x1，x30m←(x1+x2)/240Iff（m)=0ThenGoto11050Iff（x1)f（m）〉0Then60x1←m70Else80x2←m90EndIf100IfABS(x1-x2）〉=εThenGoto30110Printm【例3】相傳在遠古時代有一片森林，棲息著3種動物，鳳凰、麒麟和九頭鳥．鳳凰有1只頭2只腳,麒麟是1只頭4只腳，九頭鳥有9只頭2只腳．它們這3種動物的頭加起來一共是100只，腳加起來也正好是100只,問森林中各生活著多少只鳳凰、麒麟和九頭鳥？思路分析：假設鳳凰的只數為x，麒麟的只數為y,九頭鳥的只數為z，那么，（1)鳳凰的只數x可能的取值為1～50，如果用偽代碼表示，就應該如下：Forx=1To50Step1(2）麒麟的只數y可能的取值為1~25，如果用偽代碼表示，就應該如下：Fory=1To25Step1（3）如果知道了鳳凰和麒麟的只數后,那么九頭鳥的只數就應該如下：z=（100-x—y）/9．如何考慮x、y、z三個變量之間的關系？當鳳凰x=1時(只在開始時），變量麒麟y的取值可以從1～25，讓變量y從1開始取值（例如:y的值為1）；通過(100-x-y）/9表達式,計算出z的值；完成上述步驟后,x、y、z三個變量都取到了自己相應的值，但是這三個值是否是正確的解呢？我們必須通過以下的兩個條件來判斷：x+y+9×z=100And2×x+4×y+2×z=100．如果全部滿足，就輸出x、y、z的值,如果不滿足，就讓y值加1，然后重復步驟（2）到步驟（4)，直至y的取值超過25；然后讓x的取值加1后，重復步驟（1）到步驟（5)的操作，直至x的取值超過50為止，退出算法．解：流程圖和偽代碼如下:Forxfrom1to50Foryfrom1to25z←（100-x-y）/9If2x+4y+2z=100thenPrintx，y,zEndforEndfor拓展遷移【拓展點】意大利數學家菲波契，在1202年出版的一書里提出了這樣的一個問題：一對兔子飼養到第二個月進入成年，第三個月生一對小兔,以后每個月生一對小兔,所生小兔能全部存活并且也是第二個月成年，第三個月生一對小兔,以后每月生一對小兔，這樣下去到年底應有多少對兔子．思路分析:根據題意可知，第一個月有1對小兔,第二個月有1對成年兔子，第三個月有兩對兔子，從第三個月開始,每個月的兔子對數是前面兩個月兔子對數的和，設第N個月有F對兔子，第N—1個月有S對兔子,第N-2個月有Q對兔子，則有F=S+Q，一個月后，即第N+1個月時，式中變量S的新值應變第N個月兔子的對數（F的舊值)，變量Q的新值應變為N—1個月兔子的對數（S的舊值），這樣，用S+Q求出變量F的新值就是N+1個月兔子的數，依此類推，可以得到一個數序列，數序列的第12項就是年底應有兔子對數,我們可以先確定前兩個月的兔子對數均為1，