18-19第1章14算法案例

1、1.4算法案例學(xué)習(xí)目標(biāo)：i.通過中國古代算法案例，體會中國古代數(shù)學(xué)對世界數(shù)學(xué)發(fā)展的貢獻(xiàn).2.能綜合運(yùn)用所學(xué)的算法知識解決實(shí)際問題，會用自然語言、流程圖和偽代碼表述問題的算法過程.(重點(diǎn)、難點(diǎn))3.拓展視野，進(jìn)一步感受算法的意義和價值.自主預(yù)習(xí)探新知m=3x+2,“孫子問題”是求關(guān)丁x,y,z的一次不定方程組m=5y+3,的上m=7z+2整數(shù)解.1. 輾轉(zhuǎn)相除法和更相減損術(shù)歐幾里得輾轉(zhuǎn)相除法求兩個正整數(shù)a,b的最大公約數(shù)的步驟是：計算出a韋的余數(shù)r,若M，則b.即為a,b的最大公約數(shù)；若r0,則把前面的您數(shù)b作為新的被除數(shù),把余數(shù)r作為新的除數(shù)，繼續(xù)運(yùn)算,直到余數(shù)為0,此時的除數(shù)即為a,b的最大

2、公約數(shù).“更相減損術(shù)”是我國的九章算術(shù)中提到的一種求兩個正數(shù)最大公約數(shù)的算法，它與“輾轉(zhuǎn)相除法”相似.它的基本思想是：對丁給定的兩個數(shù)，以兩個數(shù)中較大的數(shù)減去較小的數(shù)，然后將差和較小的數(shù)組成一對新數(shù)，再用兩個數(shù)中較大的數(shù)減去較小的數(shù)，反復(fù)執(zhí)行此步驟，直到產(chǎn)生一對相等的數(shù)為止，這個數(shù)就是原來兩個數(shù)的最大公約數(shù).2. Int(x)和Mod(x)函數(shù)(1) Int(x)表示不超過x的最大整數(shù).一2一一例如：Int(5)=5,Intri=0,Int(3.6)=3.3 r(2) Mod(a,b)的意義是a除以b所得的余數(shù)，因此當(dāng)Mod(a,b)=0時，表示a能被b整除，當(dāng)0<Mod(a,b)<

3、;b時，a不能被b整除，即b不是a的約數(shù).3. 利用“二分法”求方程f(x)=0在區(qū)間a,b上的近似解的步驟為：一，1S1取a,b的中點(diǎn)X0=2(a+b),將區(qū)間一分為二；、,一、一*,'，、-一，、S2若f(X0)=0，則X0就是萬程的根；否則判斷根x在X0的左側(cè)還是右側(cè)：右f(a)f(X0)>0,則x兇，b),以X0代替a；若f(a)f(Xg)<0,貝Ux(a,X0),以X0代替b;S3右|ab|<c,計算終止，此時xX0，否則轉(zhuǎn)S1.基礎(chǔ)自測1 .兩個整數(shù)490和910的最大公約數(shù)是.70.910=490X1+420,494420X1+70,420=70X6+0

4、,.490和910的最大公約數(shù)是70.2. Mod(8,3)=.2 Mod(8,3)表示8除以3所得的余數(shù).8=2X3+2,二Mod(8,3)=2.3. 若Int(x)表示不超過x的最大整數(shù)，對丁下列等式：Int(10.01)=10;Int(1)=1;Int(5.2)=5.其中正確的有個.【導(dǎo)學(xué)號：20192046】2正確，錯誤.因?yàn)镮nt(x)表示的是不超過x的最大整數(shù).所以Int(一5.2)=6.4 .用二分法求方程的近似解，誤差不超過&則循環(huán)結(jié)構(gòu)的終止條件是|X1X2|>GX1=X2=GX1<<X2；|X1X2|<£依據(jù)用二分法求方程近似解時誤差

5、限制要求判斷，對.5.試用偽代碼表示求方程組lMod(x,3)=2,JMod(x,7)=5的一個正整數(shù)解.【導(dǎo)學(xué)號：20192047解析本題用計算機(jī)解決并不困難，只要使用循環(huán)語句，從小到大搜索即可.解偽代碼為:合作探究玫重難摟型孫子剩余定理的應(yīng)用卜例。有3個連續(xù)的正整數(shù)，其中最小的能被15整除，中間的能被17整除，最大的能被19整除，畫出求滿足要求的一組三個連續(xù)正整數(shù)的流程圖，并寫出偽代碼.解析設(shè)最小的正整數(shù)m,根據(jù)題意，m應(yīng)同時滿足3個條件：(1) m被15整除即Mod(m,15)=0,(2) m+1被17整除即Mod(m+1,17)=0,(3) m+2被19整除即Mod(m+2,19)=0

6、.首先，從m=2開始檢驗(yàn)條件，若3個條件中有任何一個不滿足則m遞增1.直到m同時滿足3個條件時，輸出m,m+1,m+2.因?yàn)橐獜膍=2開始反復(fù)驗(yàn)證，故需要用循環(huán)結(jié)構(gòu).解流程圖：偽代碼：規(guī)律方法解決此類問題的方法就是從m=2開始，對每一個正整數(shù)逐一檢驗(yàn)，當(dāng)m滿足所有已知條件時，結(jié)束循環(huán)，輸出m跟蹤訓(xùn)練1.如圖1-4-1所示的流程圖，輸出的結(jié)果是.圖1-4-117m=10時，不滿足條件，WJm10+7,m=17時，Mod(m,3)=2且Mod(m,5)=2成立，故輸出17.2. m是一個正整數(shù)，對兩個正整數(shù)a,b,如果a-b是m的倍數(shù)，則稱a,b對模m同余，用符號a三b(modm)表示，則下歹U各

7、式中：12三7(mod5);21三10(mod3);34三20(mod2);47三7(mod40).【導(dǎo)學(xué)號：20192048】正確的有.(填寫正確命題的序號)逐一驗(yàn)證，由題意，對丁，12-7=5是5的倍數(shù)；對丁，2110=11不是3的倍數(shù)；對丁，34-20=14是2的倍數(shù)；對丁，47-7=40是40的倍數(shù).故正確.婁型目卜例求兩個正整數(shù)的最大公約數(shù)設(shè)計用輾轉(zhuǎn)相除法求8251與6105的最大公約數(shù)的算法，并畫出流程圖，寫出偽代碼【導(dǎo)學(xué)號：20192049解析根據(jù)用輾轉(zhuǎn)相除法求兩個正整數(shù)的算法步驟寫出解決此問題的算法，再轉(zhuǎn)換為流程圖和偽代碼.解算法如下:51 a。8251;52 b。6105;5

8、3 如果Mod(a,b)豐0,那么轉(zhuǎn)S4,否則轉(zhuǎn)S7;54 rMod(a,b);55 a。b;56 b。r,轉(zhuǎn)S3;S7輸出b.流程圖與偽代碼：規(guī)律方法輾轉(zhuǎn)相除法是用丁求兩個數(shù)的最大公約數(shù)的一種方法，這種方法由歐幾里得在公元前300年左右首先提出，因而乂叫“歐幾里得輾轉(zhuǎn)相除法”.輾轉(zhuǎn)相除法的算法步驟（以求兩個正整數(shù)a,b（a>b）的最大公約數(shù)為例）為：S1輸入兩個正整數(shù)a,b；52 如果Mod（a,b）丈。那么轉(zhuǎn)S3,否則，轉(zhuǎn)S6;53 rMod（a,b）;54 a。b;55 b。r,轉(zhuǎn)S2;S6輸出b.其流程圖如圖.偽代碼為:提醒求兩個正整數(shù)的最大公約數(shù)時，用輾轉(zhuǎn)相除法進(jìn)行設(shè)計的關(guān)鍵是

9、：將“輾轉(zhuǎn)”的過程用循環(huán)語句表示.,為了避免求循環(huán)次數(shù)對兩個具體的正整數(shù)，循環(huán)次數(shù)可以求出，但會使程序更為復(fù)雜，最好使用“While”語句.跟蹤訓(xùn)練3 .用輾轉(zhuǎn)相除法求261和319的最大公約數(shù).解析依據(jù)輾轉(zhuǎn)相除法的算法步驟求解.解319專61=1（余58）,261W8=4（余29）,58專9=2（余0）,所以319與261的最大公約數(shù)為29.4 .運(yùn)行下面?zhèn)未a，當(dāng)輸入168,72時輸出的結(jié)果是.【導(dǎo)學(xué)號：20192050】24偽代碼是求168與72的最大公約數(shù).l«®3|二分法求方程的近似解卜例E1設(shè)計用二分法求方程x32=0在區(qū)間1,2內(nèi)的近似解（誤差不超過0.005

10、）的流程圖，寫出偽代碼.【導(dǎo)學(xué)號：20192051解析依據(jù)二分法求方程的近似解的步驟設(shè)計出算法再轉(zhuǎn)換成流程圖和偽代碼，設(shè)f(x)=X32如圖所示.-、*.-、一如果估計出方程f(x)=0在某區(qū)|可a,b內(nèi)有一個根x,就能用二分法搜索求得符合誤差限制c的近似解.用自然語言表示算法如下：1S1取a,b的中點(diǎn)xo=2(a+b),將區(qū)間一分為二.、-、,一、J*、S2若f(xo)=0,則xo就是萬程的根，否則判斷根x在xo的左側(cè)還是右側(cè)；，一一一一,*一-.右f(a)f(xo)>O，則x(xo,b),以xo代替a；若f(a)f(xo)<o，則x*(a,xo),以xo代替b.S3若|a-b|

11、<c,計算終止，此時x'xo,否則轉(zhuǎn)S1.解流程圖如圖所示.偽代碼如下：規(guī)律方法1.用二分法求方程近似解，必須先判斷方程在給定區(qū)間上是否有解.2. 二分法的過程是一個多次重復(fù)的過程，故可用循環(huán)結(jié)構(gòu)處理.二分法過程中需要對中點(diǎn)端點(diǎn)處函數(shù)值的符號進(jìn)行判定，故實(shí)現(xiàn)算法需用選擇結(jié)構(gòu)，即用條件語句進(jìn)行分支選擇.跟蹤訓(xùn)練5 .流程圖1-4-2表小的算法的功能是.圖1-4-2用二分法求方程x23x+1=0在區(qū)間0,1內(nèi)的一個近似解(誤差不超過0.001)對照二分法求方程近似解的方法步驟，此流程圖表示的算法功能是用二分法求方程x23x+1=0在區(qū)間0,1內(nèi)的一個近似解(誤差不超過0.001).用

12、二分法設(shè)計一個求方程x2-2=0的近似根(誤差不超過0.005)的算法流程圖，寫出偽代碼.解析學(xué)習(xí)了二分法解方程的步驟之后，根據(jù)所求近似根與精確解的差的絕對值不超過0.005,不難設(shè)計出以下步驟.第一步令f(x)=x2-2,因?yàn)閒(1)<0,f(2)>0，所以設(shè)xi=1,X2=2,方程在X1,X2內(nèi)有一根.Xl+X2第二步令m=判斷f(m)是否為0,若是，貝Um即為所求；否則，繼續(xù)判斷f(xi)f(m)是大丁0還是小丁0.第三步若f(xi)f(m)>0，則令xi=m；否貝U,令x2=m.第四步判斷xix2|<0.005是否成立.若成立，則xi,x2之間的任意取值均為滿足

13、條件的近似根；否則，返回第二步.解流程圖如圖所示.偽代碼如下：當(dāng)堂達(dá)標(biāo)固雙基有一堆火柴棒，三根三根地數(shù)，最后余下一根；四根四根地數(shù)，最后余下兩根；五根五根地數(shù)，最后余下四根.那么這堆火柴棒最少有&.34由題意知，本題實(shí)際上是求關(guān)丁a,b,c的不定方程組的正整數(shù)解，"m=3a+i,即，m=4b+2,得m的最小值為34.Im=5c+41. 4557與5ii5的最大公約數(shù)是.93因?yàn)?115=4557X1+558,4557=558X8+93,558=93X6,所以4557與5115的最大公約數(shù)是93.2. Mod(100,17)=.15Mod(a,b)=c表示b除a所得余數(shù)為c.100=17X5+15,故余數(shù)為15.3. 根據(jù)如圖1-4-3所示的流程圖(其中x表示不大丁x的最大整數(shù))，可知輸出r=.圖1-4-36 由框圖的算法原理可知：3a=5,b="77,n=1,n(ba)=>/7->/5<1；n=2,n(b-a)