資源描述：
《高中數(shù)學第1章算法初步1.4算法案例知識導引學案蘇教版必修3》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、1．4 算法案例案例探究有一個故事是講唐代大官楊塤提拔官員的經(jīng)過．他讓兩個資格職位相同的候選人解答下面這個問題，誰先答出就提拔誰．“有人在林中散步，無意中聽到幾個強盜在商量怎樣分配搶來的布匹．若每人分6匹，就剩5匹；若每人分7匹，就差8匹．問共有強盜幾個？布匹多少？”你能用一個簡單算式求出強盜個數(shù)和布匹數(shù)嗎？解析：這個問題可看作二元一次方程組問題．問題的特點是給出兩種分配方案，一種分法分不完，一種分法不夠分．中國古代的《九章算術(shù)》一書中搜集了許多這類問題，各題都有完整的解法，后人稱這種算法為——“盈不足術(shù)”．這種算法可以概括為兩句口訣：有余加不足，大減小來除．公
2、式：（盈+不足）÷兩次所得之差=人數(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流程圖：自學導引1．int(x)表示不超過x的最大整數(shù)．2．mod(a,b)表示a除以b所得的余數(shù)，稱b為模．3．輾轉(zhuǎn)相除法是用于求兩個數(shù)的最大公約數(shù)的一種方法，這種算法由歐幾里得在公元前300年左右首先提出，因而又叫歐幾里得輾轉(zhuǎn)相除法．4．歐幾里得輾轉(zhuǎn)相除法找出a,b的最大公約數(shù)的步驟是：計算出a÷b的余數(shù)r，若r=0，則b為a,b
3、的最大公約數(shù)；若r≠0，則把前面的除數(shù)b作為新的被除數(shù)，把余數(shù)r作為新的除數(shù)，繼續(xù)運算，直到余數(shù)為0，此時的除數(shù)即為正整數(shù)a,b的最大公約數(shù)．5．秦九韶算法是我國南宋數(shù)學家秦九韶在他的代表作《數(shù)書九章》中提出的一種用于計算一次同余式組的方法，稱作大衍求一術(shù)．疑難剖析【例1】輸入兩個正整數(shù)a和b（a>b），求它們的最大公約數(shù)．思路分析：求兩個正整數(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
4、的最大公約數(shù)，這種方法叫做歐幾里得輾轉(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←r70Goto2080Printb90End思維啟示：（1）每行語句前邊有一個數(shù)字，我們稱這個數(shù)字為行號，它的作用表示該行在偽代碼中的位置和執(zhí)行順序．（2）If語句和Goto語句兩個語句可結(jié)合能夠?qū)崿F(xiàn)循環(huán)．變式訓練：用輾轉(zhuǎn)相除法、
5、更相減損術(shù)求228，1995最大公約數(shù)．分析：使用輾轉(zhuǎn)相除法，我們就根據(jù)a=nb+r這個式子，反復執(zhí)行，直到r=0為止．用更相減損術(shù)我們就根據(jù)r=a-b這個式子，反復執(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=
6、114114-57=5757-57=0則57就是228，1995的最大公約數(shù)．思維啟示：由該題可以看出，輾轉(zhuǎn)相除法得最大公約數(shù)步驟較少，而更相減損術(shù)運算簡易，兩種方法各有所長．【例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為所求；若否，則繼續(xù)判斷f(x1)·f(m)大于0還是小于0．第三步：若f(x1)
7、·f(m)＞0，則令x1=m；否則，令x2=m．第四步：判斷
8、x1-x2
9、<0．005是否成立？若是，則x1,x2之間的任意取值均為滿足條件的近似根；若否，則返回第二步．解：流程圖如圖：偽代碼：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】相傳在遠古時代有一片森林，棲息著3種動物，鳳凰、麒麟
10、和九頭鳥．鳳凰有1只頭2
