資源描述：
《高中數(shù)學(xué)第1章算法初步1.4算法案例知識(shí)導(dǎo)引學(xué)案》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、1．4 算法案例案例探究有一個(gè)故事是講唐代大官楊塤提拔官員的經(jīng)過(guò)．他讓兩個(gè)資格職位相同的候選人解答下面這個(gè)問(wèn)題，誰(shuí)先答出就提拔誰(shuí)．“有人在林中散步，無(wú)意中聽(tīng)到幾個(gè)強(qiáng)盜在商量怎樣分配搶來(lái)的布匹．若每人分6匹，就剩5匹；若每人分7匹，就差8匹．問(wèn)共有強(qiáng)盜幾個(gè)？布匹多少？”你能用一個(gè)簡(jiǎn)單算式求出強(qiáng)盜個(gè)數(shù)和布匹數(shù)嗎？解析：這個(gè)問(wèn)題可看作二元一次方程組問(wèn)題．問(wèn)題的特點(diǎn)是給出兩種分配方案，一種分法分不完，一種分法不夠分．中國(guó)古代的《九章算術(shù)》一書中搜集了許多這類問(wèn)題，各題都有完整的解法，后人稱這種算法為——“盈不足術(shù)”．這種算法可以概括為兩句口訣：有余加不足，大減小來(lái)除．公式：（
2、盈+不足）÷兩次所得之差=人數(shù)，每人所得數(shù)×人數(shù)+盈=物品總數(shù)，求得強(qiáng)盜有（8+5）÷(7-6)=13（人），布匹有6×13+5=83（匹）．偽代碼：Reada,b,c,dx←(a+b)/(d-c)y←cx+aPrintx,y流程圖：自學(xué)導(dǎo)引1．int(x)表示不超過(guò)x的最大整數(shù)．2．mod(a,b)表示a除以b所得的余數(shù)，稱b為模．3．輾轉(zhuǎn)相除法是用于求兩個(gè)數(shù)的最大公約數(shù)的一種方法，這種算法由歐幾里得在公元前300年左右首先提出，因而又叫歐幾里得輾轉(zhuǎn)相除法．4．歐幾里得輾轉(zhuǎn)相除法找出a,b的最大公約數(shù)的步驟是：計(jì)算出a÷b的余數(shù)r，若r=0，則b為a,b的最大公約數(shù)
3、；若r≠0，則把前面的除數(shù)b作為新的被除數(shù)，把余數(shù)r7作為新的除數(shù)，繼續(xù)運(yùn)算，直到余數(shù)為0，此時(shí)的除數(shù)即為正整數(shù)a,b的最大公約數(shù)．5．秦九韶算法是我國(guó)南宋數(shù)學(xué)家秦九韶在他的代表作《數(shù)書九章》中提出的一種用于計(jì)算一次同余式組的方法，稱作大衍求一術(shù)．疑難剖析【例1】輸入兩個(gè)正整數(shù)a和b（a>b），求它們的最大公約數(shù)．思路分析：求兩個(gè)正整數(shù)a、b(a>b)的最大公約數(shù)，可以歸結(jié)為求一數(shù)列：a,b,r1,r2,…,rn-1,rn,rn-1,0此數(shù)列的首項(xiàng)與第二項(xiàng)是a和b，從第三項(xiàng)開(kāi)始的各項(xiàng)，分別是前兩項(xiàng)相除所得的余數(shù)，如果余數(shù)為0，它的前項(xiàng)rn-1即是a和b的最大公約數(shù)，這
4、種方法叫做歐幾里得輾轉(zhuǎn)相除法，其算法如下：S1 輸入a,b(a＞b)S2 求a/b的余數(shù)r；S3 如果r≠0，則將b→a,r→b，再次求a/b的余數(shù)r，轉(zhuǎn)至S2；S4 輸出最大公約數(shù)B．解：流程圖如下：偽代碼如下：10Reada,b20r←Mod(a,b)30Ifr=0ThenGoto8040Else50a←b60b←r70Goto2080Printb90End7思維啟示：（1）每行語(yǔ)句前邊有一個(gè)數(shù)字，我們稱這個(gè)數(shù)字為行號(hào)，它的作用表示該行在偽代碼中的位置和執(zhí)行順序．（2）If語(yǔ)句和Goto語(yǔ)句兩個(gè)語(yǔ)句可結(jié)合能夠?qū)崿F(xiàn)循環(huán)．變式訓(xùn)練：用輾轉(zhuǎn)相除法、更相減損術(shù)求228，
5、1995最大公約數(shù)．分析：使用輾轉(zhuǎn)相除法，我們就根據(jù)a=nb+r這個(gè)式子，反復(fù)執(zhí)行，直到r=0為止．用更相減損術(shù)我們就根據(jù)r=a-b這個(gè)式子，反復(fù)執(zhí)行就可．解：所以有以下解法：用輾轉(zhuǎn)相除法：1995=8×228+171228=1×171+57171=3×57+0所以：57就是228和1995的最大公約數(shù)．用更相減損術(shù)：1995-228=17671767-228=15391539-228=13111311-228=10831083-228=855855-228=627627-228=399399-228=171228-171=57171-57=114114-57=575
6、7-57=0則57就是228，1995的最大公約數(shù)．思維啟示：由該題可以看出，輾轉(zhuǎn)相除法得最大公約數(shù)步驟較少，而更相減損術(shù)運(yùn)算簡(jiǎn)易，兩種方法各有所長(zhǎng)．【例2】用二分法設(shè)計(jì)一個(gè)求方程x2-2=0的近似根的算法．思路分析：回顧二分法解方程的過(guò)程，并假設(shè)所求近似根與精確解的差的絕對(duì)值不超過(guò)0．005，則不難設(shè)計(jì)出以下步驟：第一步：令f(x)=x2-2．因?yàn)閒(1)<0,f(2)>0,所以設(shè)x1=1,x2=2．第二步：令m=，判斷f(m)是否為0．若是，則m為所求；若否，則繼續(xù)判斷f(x1)·f(m)大于0還是小于0．第三步：若f(x1)·f(m)＞0，則令x1=m；否
7、則，令x2=m．第四步：判斷
8、x1-x2
9、<0．005是否成立？若是，則x1,x2之間的任意取值均為滿足條件的近似根；若否，則返回第二步．解：流程圖如圖：7偽代碼：10f(x)←x∧2-220Read“輸入誤差ε和初值x1,x2”；ε,x1,x230 m←(x1+x2)/240Iff(m)=0ThenGoto11050Iff(x1)f(m)>0Then60x1←m70Else80x2←m90EndIf100IfABS(x1-x2)>=εThenGoto30110Printm【例3】相傳在遠(yuǎn)古時(shí)代有一片森林，棲息著3種動(dòng)物，鳳凰、麒麟和九頭鳥．鳳凰有1
