算法設計與分析第三章3算法優(yōu)化

1、3 33 3 算法優(yōu)化基本技巧算法優(yōu)化基本技巧3 33 31 1 算術運算的妙用算術運算的妙用3 33 32 2 標志量的妙用標志量的妙用333 信息數(shù)字化信息數(shù)字化3.3.1 3.3.1 算術運算的妙用算術運算的妙用 有關算術運算的妙用，在前面的許多例題中已有體現(xiàn)。有關算術運算的妙用，在前面的許多例題中已有體現(xiàn)。如：上一節(jié)如：上一節(jié)321“原始信息與處理結果的巧妙對應原始信息與處理結果的巧妙對應”中的例中的例2 2，通過算術運算把數(shù)據(jù)信息歸類后與下標對應。，通過算術運算把數(shù)據(jù)信息歸類后與下標對應。 總之，通過恰當?shù)乃阈g運算可以很好地提高編程效率，總之，通過恰當?shù)乃阈g運算可以很好地提高編程效率

2、，以及相關算法的運行效率。值得認真總結學習。以及相關算法的運行效率。值得認真總結學習?！纠纠? 1】一次考試，共考了五門課。統(tǒng)計五十個學生中至】一次考試，共考了五門課。統(tǒng)計五十個學生中至 少有三門課成績高于少有三門課成績高于9090分的人數(shù)。分的人數(shù)。 問題分析：若一個學生五門課的成績分別記為：問題分析：若一個學生五門課的成績分別記為：a1,a2,a3,a4,a5a1,a2,a3,a4,a5，則要表示有三門課成績高于，則要表示有三門課成績高于9090分，有分，有C C3 35 5=10=10組關系邏輯表達式，每組三個關系表達式。無論書寫還是運組關系邏輯表達式，每組三個關系表達式。無論書寫還是

3、運行效率都極低。但通過算法運算就能很簡便地解決這類問題。行效率都極低。但通過算法運算就能很簡便地解決這類問題。 算法設計：算法設計：1 1）對每個同學，先計算其成績高于）對每個同學，先計算其成績高于9090分的課程數(shù)目，若超過分的課程數(shù)目，若超過3 3，則累加滿足條件的人數(shù)中。則累加滿足條件的人數(shù)中。2 2）用二重循環(huán)實現(xiàn)以上過程，外層循環(huán)模擬）用二重循環(huán)實現(xiàn)以上過程，外層循環(huán)模擬5050個同學，內層循個同學，內層循環(huán)模擬五門課程。環(huán)模擬五門課程?！纠纠? 2】開燈問題：有從】開燈問題：有從1 1到到n n依次編號的依次編號的n n個同學和個同學和n n 盞燈。盞燈。1 1號號同學將所有的燈

4、都關掉；同學將所有的燈都關掉；2 2號同學將編號為號同學將編號為2 2的倍數(shù)的燈都打開；的倍數(shù)的燈都打開；3 3號同學則將編號為號同學則將編號為3 3的倍數(shù)的燈作相反處理（該號燈如打開的，的倍數(shù)的燈作相反處理（該號燈如打開的，則關掉；如關閉的，則打開）；以后的同學都將自己編號的倍則關掉；如關閉的，則打開）；以后的同學都將自己編號的倍數(shù)的燈，作相反處理。問經(jīng)數(shù)的燈，作相反處理。問經(jīng)n n個同學操作后，哪些燈是打開的？個同學操作后，哪些燈是打開的？問題分析：問題分析：1 1）用數(shù)組表示某種狀態(tài)，這里定義有）用數(shù)組表示某種狀態(tài)，這里定義有n n個元素的個元素的a a數(shù)組，它數(shù)組，它 的每個下標變量的

5、每個下標變量aiai視為一燈，視為一燈，i i表示其編號。表示其編號。ai=1ai=1 表示燈處于打開狀態(tài)，表示燈處于打開狀態(tài)，ai=0ai=0表示燈處于關閉狀態(tài)。表示燈處于關閉狀態(tài)。2 2）實現(xiàn)將第）實現(xiàn)將第i i 燈作相反處理的操作，可以用條件語句燈作相反處理的操作，可以用條件語句ifif表表 示：當示：當aiai為為1 1時，時，aiai被重新賦為被重新賦為0 0；當；當aiai為為0 0時，時， aiai被重新賦為被重新賦為1 1。但通過以下算術運算：。但通過以下算術運算： ai=1-aiai=1-ai 就很好地模擬就很好地模擬“開關開關”燈的操作。燈的操作。main( )main(

6、) int n,a1000,i,k; int n,a1000,i,k; print(“input a number”); print(“input a number”); input(“%d”,&n); input(“%d”,&n); for( i=1;i=n;i+) for( i=1;i=n;i+) ai=0; ai=0; for( i=2;i=n;i+) for( i=2;i=n;i+) k=1; k=1; while ( i while ( i* *k=n)k=n) ai ai* *k=1-aik=1-ai* *k;k; k=k+1; k=k+1; for( i=1;i=

7、n;i+) for( i=1;i=b+c or b=a+c or c=a+b) if(a=b+c or b=a+c or c=a+b) print(“dont form a triangle”); print(“dont form a triangle”); else else flag=0; flag=0; if (a if (a* *a=ba=b* *b+cb+c* *c or bc or b* *b=ab=a* *a+ca+c* *c or cc or c* *c=ac=a* *a+ba+b* *b)b) print(“form a right-angle triangle”); fla

8、g=1; print(“form a right-angle triangle”); flag=1; if(a=b and b=c) if(a=b and b=c) print(“form a equilateral triangle”);flag=1; print(“form a equilateral triangle”);flag=1; else if(a=b or b=c or c=a) else if(a=b or b=c or c=a) print(“form a equal haunch triangle”);flag=1; print(“form a equal haunch

9、triangle”);flag=1; if(flag=0) if(flag=0) print(“form a triangle”); print(“form a triangle”); 【例【例4 4】編寫算法，求任意三個數(shù)的最小公倍數(shù)?！烤帉懰惴?，求任意三個數(shù)的最小公倍數(shù)。算法設計：算法設計：1 1）用短除法求三個已知數(shù)的最小公倍數(shù)的過程就是求它們的因）用短除法求三個已知數(shù)的最小公倍數(shù)的過程就是求它們的因數(shù)之積，這個因數(shù)可能是三個數(shù)共有的、兩個數(shù)共有或一個數(shù)數(shù)之積，這個因數(shù)可能是三個數(shù)共有的、兩個數(shù)共有或一個數(shù)獨有的三種情況。獨有的三種情況。2 2）在手工完成這個問題時，我們的大腦可以判斷三

10、個數(shù)含有哪）在手工完成這個問題時，我們的大腦可以判斷三個數(shù)含有哪些因數(shù)，及屬于哪種情況。用算法實現(xiàn)就只能利用嘗試法了。些因數(shù)，及屬于哪種情況。用算法實現(xiàn)就只能利用嘗試法了。嘗試的范圍應該是嘗試的范圍應該是22三個數(shù)中最大數(shù)之間的因數(shù)。三個數(shù)中最大數(shù)之間的因數(shù)。 無論因數(shù)屬于以下三種情況之一，都只算作一個因數(shù)，累乘無論因數(shù)屬于以下三種情況之一，都只算作一個因數(shù)，累乘一次。一次。若某個數(shù)是三個數(shù)的共有的因數(shù)，如：若某個數(shù)是三個數(shù)的共有的因數(shù)，如：2 2是是2 2，1414，6 6的因數(shù)；的因數(shù)； 若某個數(shù)是其中兩個數(shù)的因數(shù)，如：若某個數(shù)是其中兩個數(shù)的因數(shù)，如：2 2 是是2 2，5 5，6 6的因

11、數(shù)；的因數(shù)； 若某個數(shù)是其中某一個數(shù)的因數(shù)，如：若某個數(shù)是其中某一個數(shù)的因數(shù)，如：2 2 是是2 2，5 5，9 9的因數(shù)。的因數(shù)。以上三種情況例子中，因數(shù)以上三種情況例子中，因數(shù)2 2都只累乘一次都只累乘一次3 3）再看例子）再看例子2 2，4 4，8 8中中2 2是的因數(shù)，為避免因數(shù)重復計算，一定要用是的因數(shù)，為避免因數(shù)重復計算，一定要用2 2整除整除這三個數(shù)得到這三個數(shù)得到1 1，2 2，4 4。注意到。注意到2 2仍是（仍是（1 1，2 2，4 4）的因數(shù)，所以在嘗試某）的因數(shù)，所以在嘗試某數(shù)是否是三個數(shù)的因數(shù)時，不是用條件語句數(shù)是否是三個數(shù)的因數(shù)時，不是用條件語句ifif，而是要用循

12、環(huán)語句，而是要用循環(huán)語句whilewhile，以保證將三個數(shù)中所含的某個因數(shù)能全部被找出，直到三個數(shù)都不含這個以保證將三個數(shù)中所含的某個因數(shù)能全部被找出，直到三個數(shù)都不含這個數(shù)做因數(shù)時循環(huán)結束。數(shù)做因數(shù)時循環(huán)結束。 main( ) main( ) int x1,x2,x3,t=1,i,flag,x0; int x1,x2,x3,t=1,i,flag,x0; print(“Input 3 number:”); input(x1,x2,x3); print(“Input 3 number:”); input(x1,x2,x3); x0=max(x1,x2,x3); x0=max(x1,x2,x3)

13、; for (i=2;i=x0;i=i+1) for (i=2;i=x0;i=i+1) flag=1; flag=1; while(flag=1) while(flag=1) flag=0; flag=0; if (x1 mod i=0) x1=x1/i; flag=1; if (x1 mod i=0) x1=x1/i; flag=1; if(x2 mod i=0) x2=x2/i; flag=1; if(x2 mod i=0) x2=x2/i; flag=1; if(x3 mod i=0) x3=x3/i; flag=1; if(x3 mod i=0) x3=x3/i; flag=1; if

14、 (flag=1) t=t if (flag=1) t=t* *i; /whilei; /while結束符結束符 x0=max(x1,x2,x3) /forx0=max(x1,x2,x3) /for結束符結束符 print(“The result is ”,t);print(“The result is ”,t); 3.3.3 3.3.3 信息數(shù)字化信息數(shù)字化 學到這里，我們已經(jīng)會處理許多數(shù)值計算方面的問題了。學到這里，我們已經(jīng)會處理許多數(shù)值計算方面的問題了。計算機算法還能幫助我們做什么？從我們學到的計算機基礎知計算機算法還能幫助我們做什么？從我們學到的計算機基礎知識知道，計算機能存儲和處理各

15、種多媒體信息，如：圖形、圖識知道，計算機能存儲和處理各種多媒體信息，如：圖形、圖象、聲音等，當然前提條件是將這些信息進行的數(shù)字化。本書象、聲音等，當然前提條件是將這些信息進行的數(shù)字化。本書已聲明不研究專業(yè)性強的算法，所以對多媒體信息的數(shù)字化及已聲明不研究專業(yè)性強的算法，所以對多媒體信息的數(shù)字化及其壓縮存儲、處理等相關的算法，請讀者閱讀別的參考資料。其壓縮存儲、處理等相關的算法，請讀者閱讀別的參考資料。下面就一些表面上看是非數(shù)值的問題，但經(jīng)過進行數(shù)字化后，下面就一些表面上看是非數(shù)值的問題，但經(jīng)過進行數(shù)字化后，就可方便進行算法設計的問題做簡單介紹。就可方便進行算法設計的問題做簡單介紹?！纠纠?

16、1】警察局抓了】警察局抓了a a，b b，c c，d d四名偷竊嫌疑犯，其中只有一人是小四名偷竊嫌疑犯，其中只有一人是小偷。審問中偷。審問中 a a說：說：“我不是小偷。我不是小偷?！?b b說：說：“c c是小偷。是小偷?！?c c說：說：“小偷肯定是小偷肯定是d d?！?d d說：說：“c c在冤枉人。在冤枉人?！爆F(xiàn)在已經(jīng)知道四個人中三人說的是真話，一人說的是假話，現(xiàn)在已經(jīng)知道四個人中三人說的是真話，一人說的是假話，問到底誰是小偷？問到底誰是小偷？問題分析：將問題分析：將a,b,c,da,b,c,d將四個人進行編號，號碼分別將四個人進行編號，號碼分別為為1 1，2 2，3 3，4 4。則問

17、題可用枚舉嘗試法來解決。則問題可用枚舉嘗試法來解決。算法設計：算法設計：用變量用變量x x存放小偷的編號，則存放小偷的編號，則x x的取值范圍從的取值范圍從1 1取到取到4 4，就假設了他們中的某人是小偷的所有情況。四個人所說的話就可就假設了他們中的某人是小偷的所有情況。四個人所說的話就可以分別寫成：以分別寫成： a a說的話：說的話：x1x1 b b說的話：說的話：x=3x=3 c c說的話：說的話：x=4x=4 d d說的話：說的話：x4x4或或not(x=4)not(x=4) 注意注意: :在在x x的枚舉過程中，當這四個邏輯式的值相加等于的枚舉過程中，當這四個邏輯式的值相加等于3 3時

18、，即表時，即表示示“四個人中三人說的是真話，一人說的是假話四個人中三人說的是真話，一人說的是假話”。 算法如下：算法如下：main( )main( ) int x; int x; for(x=1;x=4;x+) for(x=1;x=4;x+) if(x1)+(x=3)+(x=4)+(x4)=3) if(x1)+(x=3)+(x=4)+(x4)=3) print(chr(64+x),“is a thief .”); print(chr(64+x),“is a thief .”); 運行結果：運行結果： c is a thief .c is a thief .【例【例2 2】三位老師對某次數(shù)學競賽

19、進行了預測。他們的預測如下：】三位老師對某次數(shù)學競賽進行了預測。他們的預測如下： 甲說：學生甲說：學生A A得第一名，學生得第一名，學生B B得第三名。得第三名。 乙說：學生乙說：學生C C得第一名，學生得第一名，學生D D得第四名。得第四名。 丙說：學生丙說：學生D D得第二名，學生得第二名，學生A A得第三名。得第三名。競賽結果表明，他們都說對了一半，說錯了一半，并且無并列名次，競賽結果表明，他們都說對了一半，說錯了一半，并且無并列名次，試編程輸出試編程輸出A A、B B、C C、D D各自的名次。各自的名次。問題分析：用數(shù)問題分析：用數(shù)1 1，2 2，3 3，4 4分別代表學生分別代表學

20、生a a，b b，c c，d d獲得的名次。獲得的名次。問題就可以利用三重循環(huán)把所有的情況枚舉出來。問題就可以利用三重循環(huán)把所有的情況枚舉出來。 算法設計：算法設計： 1 1）用）用a a，b b，c c，d d 代表四個同學，其存儲的值代表他們的名代表四個同學，其存儲的值代表他們的名 次。次。 設置第一層計數(shù)循環(huán)設置第一層計數(shù)循環(huán)a a的范圍從的范圍從1 1到到4 4； 設置第二層計數(shù)循環(huán)設置第二層計數(shù)循環(huán)b b的范圍從的范圍從1 1到到4 4； 設置內計數(shù)循環(huán)設置內計數(shù)循環(huán)c c的范圍從的范圍從1 1到來到來4 4； 由于無并列名次，名次的和為由于無并列名次，名次的和為1+2+3+4=10

21、1+2+3+4=10，由此可計算，由此可計算 出出d d的名次值為的名次值為10-a-b-c10-a-b-c。 2 2）問題的已知內容，可以表示成以下幾個條件式：）問題的已知內容，可以表示成以下幾個條件式： (1) (a=1)+(b=3)=1(1) (a=1)+(b=3)=1 (2) (c=1)+(d=4)=1 (2) (c=1)+(d=4)=1 (3) (d=2)+(a=3)=1 (3) (d=2)+(a=3)=1 若三個條件均滿足，則輸出結果，若不滿足，繼續(xù)循環(huán)若三個條件均滿足，則輸出結果，若不滿足，繼續(xù)循環(huán) 搜索，直至循環(huán)正常結束。搜索，直至循環(huán)正常結束。 算法如下：算法如下：main(

22、 )main( )int a,b,c,d;int a,b,c,d;for( a=1;a=4;a=a+1)for( a=1;a=4;a=a+1) for( b=1;b=4;b=b+1) for( b=1;b=4;b=b+1) if (ab) if (ab) for( c=1;c=4;c=c+1) for( c=1;c=4;c=c+1) if (ca and cb) if (ca and cb) d=10-a-b-c; d=10-a-b-c; if (da and db and dc ) if (da and db and dc ) if(a=1)+(b=3)=1 and (c=1)+(d=4)=

23、1 and if(a=1)+(b=3)=1 and (c=1)+(d=4)=1 and (d=2)+(a=3)=1) (d=2)+(a=3)=1) print( “a,b,c,d=”,a,b,c,d); print( “a,b,c,d=”,a,b,c,d); 輸入任意輸入任意5 5個數(shù)個數(shù)x1,x2,x3,x4,x5x1,x2,x3,x4,x5每相鄰兩個數(shù)之間填上一每相鄰兩個數(shù)之間填上一個運算符。在填入四個運算符后，使得表達式值為一個指個運算符。在填入四個運算符后，使得表達式值為一個指定值定值y(yy(y由鍵盤輸入由鍵盤輸入) )。求出所有滿足條件的表達式。求出所有滿足條件的表達式。 算法設計

24、：算法設計：1 1）枚舉法解題：先填四個）枚舉法解題：先填四個+。檢驗條件表達式。檢驗條件表達式 x1+x2+x3+x4+x5=yx1+x2+x3+x4+x5=y，如果不成立，則將第四個運算符，如果不成立，則將第四個運算符 改為改為-，以后改，以后改* *、改、改/。輪完一遍，把第三個運算。輪完一遍，把第三個運算 符改為符改為-，第四個運算符按，第四個運算符按+ +、- -、* *、/順序再輪一順序再輪一 遍，遍，如此下去，直至第一個運算符，由如此下去，直至第一個運算符，由+至至/輪輪 完為止。完為止?！纠纠? 3】填寫運算符】填寫運算符2 2）若當前運算符輪到）若當前運算符輪到/則運算符右

25、端的數(shù)必須非零，因為則運算符右端的數(shù)必須非零，因為 零不能當除數(shù)。零不能當除數(shù)。3 3）為了便于循環(huán)我們在算法中，把）為了便于循環(huán)我們在算法中，把+ +、- -、* *、/數(shù)字化作數(shù)字化作1 1、 2 2、3 3、4 4。五個數(shù)據(jù)間需四個運算符，用一個有四個元。五個數(shù)據(jù)間需四個運算符，用一個有四個元 素數(shù)組素數(shù)組i1i4 i1i4 來代表它們。來代表它們。 4 4）為了解決運算的優(yōu)先級問題，我們設置如下變量：）為了解決運算的優(yōu)先級問題，我們設置如下變量： f-f-減去標志。減法運算時，置減去標志。減法運算時，置f=-1,f=-1,否則否則f=1f=1； q-q-若當前運算符為若當前運算符為+

26、+（- -）時）時,q,q存貯運算符的左項值；存貯運算符的左項值； 若當前運算符為若當前運算符為* *（/ /）時，）時，q q存貯兩數(shù)乘（除）后存貯兩數(shù)乘（除）后 結果；結果； p-p-累加器。每填一個算符累加器。每填一個算符p=p+fp=p+f* *q q。 for(j=1;j=5;j+) for(j=1;j=5;j+) input(nj); input(nj);print(“ input result:”); print(“ input result:”); input(n0); input(n0); total=0;total=0;for (i1=1 ;i1=4 ;i1+) for (

27、i1=1 ;i1=4 ;i1+) if (i14) | (n2!=0) ) if (i14) | (n2!=0) ) for (i2=1 ;i2=4 ;i2+) for (i2=1 ;i2=4 ;i2+) if( (i24) | (n3!=0) ) if( (i24) | (n3!=0) ) for (i3=1 ;i3=4 ;i3+) for (i3=1 ;i3=4 ;i3+) if (i34) |(n4!=0) ) if (i34) |(n4!=0) ) for (i4=1 ;i4=4 ;i4+) for (i4=1 ;i4=4 ;i4+) if(i44) | (n5!=0) ) if(i4

28、4) | (n5!=0) ) p=0; q=n1; f=1; p=0; q=n1; f=1; for (k=1;k=4;k+)for (k=1;k=4;k+) switch (ik) switch (ik) case 1: p=p+f case 1: p=p+f* *q; f=1; q=nk+1; break;q; f=1; q=nk+1; break; case 2: p=p+f case 2: p=p+f* *q; f=-1; q=nk+1; break;q; f=-1; q=nk+1; break; case 3: q=q case 3: q=q* *nk+1; break;nk+1;

29、break; case 4: q=q/nk+1; case 4: q=q/nk+1; if ( p+fif ( p+f* *q=n0)q=n0) total+; print (“total: ” ,total); total+; print (“total: ” ,total); for (k=1;k=4;k+) for (k=1;k2k k取最大時記為取最大時記為k1，k1+1號箱為的次品號箱為的次品箱；箱； 繼續(xù)討論繼續(xù)討論w/10-2 k1 2 k k取最大時記為取最大時記為k2， k2+1號箱為號箱為的次品箱；的次品箱； 直到取等號直到取等號w/10-2 ki-1 =2 ki ，ki+

30、1號箱為的次品箱；結束。號箱為的次品箱；結束。 算法如下：算法如下：main( )main( ) int i,k,n,w1=0,w2=0,t; int i,k,n,w1=0,w2=0,t; print(“Input the number of boxes:”) print(“Input the number of boxes:”)； input(n);input(n); t=1; t=1; for (i=1;i=n;i+) for (i=1;i=0) while( w1-t=0) t=t t=t* *2; k=k+1; 2; k=k+1; print(k,“is bad”); print(k,

31、“is bad”); w1=w1-t/2; w1=w1-t/2; 算法說明：算法中的最后一個內層算法說明：算法中的最后一個內層while while 循環(huán)及其后語句，是用于計循環(huán)及其后語句，是用于計算最接近當前重量算最接近當前重量w1w1的的2 k，則，則k k號箱為次品箱。這個過程也可以通號箱為次品箱。這個過程也可以通過使用函數(shù)來完成。過使用函數(shù)來完成。 main( )main( ) int i,k,n,w1=0,w2=0,t; int i,k,n,w1=0,w2=0,t; print(“Input the number of boxes:”) print(“Input the number

32、 of boxes:”)；input(n);input(n);t=1;t=1;for (i=1;i=n;i=i+1)for (i=1;i=n;i=i+1) print(i, “box take”,t,”letter.”); print(i, “box take”,t,”letter.”); w1=w1+t; t=t w1=w1+t; t=t* *2; 2; w1=w1w1=w1* *100;100;print(“n normal weight ”,w1);print(“n normal weight ”,w1);print(“Input reality weight”);input(w2);p

33、rint(“Input reality weight”);input(w2);w1=(w1-w2)/10; w1=(w1-w2)/10; while( w10)while( w10) k=log(w1)/log(2); / k=log(w1)/log(2); /以以2 2為底取對數(shù)為底取對數(shù) print(k+1 ,“is bad”);print(k+1 ,“is bad”); w1=w1-pow(2,k); / pow(2,k) w1=w1-pow(2,k); / pow(2,k)的功能是求的功能是求2k 【例【例5 5】編寫算法對輸入的一個整數(shù)，判斷它能否被】編寫算法對輸入的一個整數(shù)，判斷它

34、能否被3 3，5 5， 7 7整除，并輸出以下信息之一：整除，并輸出以下信息之一： （1 1） 能同時被能同時被3 3，5 5，7 7整除；整除； （2 2） 能被其中兩數(shù)（要指出哪兩個）整除；能被其中兩數(shù)（要指出哪兩個）整除； （3 3） 能被其中一個數(shù)（要指出哪一個）整除；能被其中一個數(shù)（要指出哪一個）整除； （4 4） 不能被不能被3 3，5 5，7 7任一個整除。任一個整除。34 優(yōu)化算法的數(shù)學模型優(yōu)化算法的數(shù)學模型341 楊輝三角形的應用楊輝三角形的應用342 最大公約數(shù)的應用最大公約數(shù)的應用343 公倍數(shù)的應用公倍數(shù)的應用344 裴波那契數(shù)列應用裴波那契數(shù)列應用345 遞推關系求解

35、方程遞推關系求解方程 說到數(shù)學建模，有好多人感到不知所云，下說到數(shù)學建模，有好多人感到不知所云，下面我們看一個很簡單的例子：面我們看一個很簡單的例子： 已知有五個數(shù)，求前四個數(shù)與第五個數(shù)分已知有五個數(shù)，求前四個數(shù)與第五個數(shù)分 別相乘后的最大當數(shù)。給出兩個算法分別如下：別相乘后的最大當數(shù)。給出兩個算法分別如下：1認識數(shù)學模型和數(shù)學建模認識數(shù)學模型和數(shù)學建模max1(int a,b,c,d,e) max2(int a,b,c,d,e) int x ; int x a=a*e; if (ab) b=b*e; x=a; c=c*e; else d=d*e; x=b; if( ab) if (cx) x

36、=a; x=c; else if (dx) x=b; x=d; if (cx) x=x*e; x=c; print(x); if (dx) x=d; print(x); 操作算法 乘法賦值條件判斷 Max1 4 7 3 Max2 1 4 3 以上兩個算法以上兩個算法 數(shù)學建模數(shù)學建模就是把現(xiàn)實世界中的實際問題加以提就是把現(xiàn)實世界中的實際問題加以提煉，抽象為數(shù)學模型，求出模型的解，驗證模型煉，抽象為數(shù)學模型，求出模型的解，驗證模型的合理性，并用該數(shù)學模型所提供的解答來解釋的合理性，并用該數(shù)學模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學知識的這一應用過程稱為現(xiàn)實問題，我們把數(shù)學知識的這一應用過程稱為

37、數(shù)學建模。數(shù)學建模。n2數(shù)學建模的基本方法數(shù)學建模的基本方法從分析問題的幾種簡單的、特殊的情況中，從分析問題的幾種簡單的、特殊的情況中，發(fā)現(xiàn)一般規(guī)律或做出某種猜想，從而找到解決發(fā)現(xiàn)一般規(guī)律或做出某種猜想，從而找到解決問題的途徑。這種研究問題方法叫做歸納法。問題的途徑。這種研究問題方法叫做歸納法。即歸納法是從簡單到復雜，由個別到一般的一即歸納法是從簡單到復雜，由個別到一般的一種研究方法。種研究方法。3 34 41 1 楊輝三角形的應用楊輝三角形的應用【例】求【例】求n次二項式各項的系數(shù)：已知二項式的展次二項式各項的系數(shù)：已知二項式的展 開式為：開式為：問題分析：若只用的數(shù)學組合數(shù)學的知識，直接建

38、模問題分析：若只用的數(shù)學組合數(shù)學的知識，直接建模 k=0，1，2，3n。用這個公式去計算，用這個公式去計算，n+1個系數(shù)，即使你考慮到了個系數(shù)，即使你考慮到了前后系數(shù)之間的數(shù)值關系：算法中也要有大量的乘前后系數(shù)之間的數(shù)值關系：算法中也要有大量的乘法和除法運算，效率是很低的。法和除法運算，效率是很低的。數(shù)學知識是各階多項式的系數(shù)呈楊輝三角形的規(guī)律數(shù)學知識是各階多項式的系數(shù)呈楊輝三角形的規(guī)律(a+b)0 1 (a+b)1 1 1(a+b)2 1 2 1(a+b)3 1 3 3 1(a+b)4 1 4 6 4 1(a+b)5 則求則求n次二項式的系數(shù)的數(shù)學模型就是求次二項式的系數(shù)的數(shù)學模型就是求n階

39、楊輝三角階楊輝三角形。形。算法設計要點：算法設計要點： 除了首尾兩項系數(shù)為除了首尾兩項系數(shù)為1外，當外，當n1時，時，(a+b)n的中間各項系數(shù)是的中間各項系數(shù)是(a+b)n-1的相應兩項系數(shù)之和，的相應兩項系數(shù)之和，如果把如果把(a+b)n的的n+1的系數(shù)列為數(shù)組的系數(shù)列為數(shù)組c，則除了，則除了c(1)、c(n+1)恒為恒為1外，設外，設(a+b)n的系數(shù)為的系數(shù)為c(i)，(a+b)n-1 的系數(shù)的系數(shù)設為設為c(i)。則有：。則有： c(i)=c(i)+c(i-1) 而當而當n=1時，只有兩個系數(shù)時，只有兩個系數(shù) c(1) 和和 c(2) (值都為值都為1)。不難。不難看出，對任何看出，

40、對任何n, (a+b)n的二項式系數(shù)可由的二項式系數(shù)可由(a+b)n-1的系數(shù)的系數(shù)求得，直到求得，直到n=1時，兩個系數(shù)有確定值，故可寫成遞歸子時，兩個系數(shù)有確定值，故可寫成遞歸子算法。算法。 coeff(int a ,int n) if (n=1) a1=1; a2=1; else coeff(a,n-1); an+1=1; for (i=n;i=2;i- -) ai=ai+ai-1; a1=1; 342 最大公約數(shù)的應用最大公約數(shù)的應用【例】數(shù)組中有【例】數(shù)組中有n個數(shù)據(jù)，要將它們順序循環(huán)向后移個數(shù)據(jù)，要將它們順序循環(huán)向后移k位，位，即前面的元素向后移即前面的元素向后移k位，后面的元素則

41、循環(huán)向前移位，后面的元素則循環(huán)向前移k位，例：位，例：1、2、3、4、5循環(huán)移循環(huán)移3位后為：位后為：3、4、5、1、2。考慮到?？紤]到n會很大，不允許用會很大，不允許用2*n以上個空間來以上個空間來完成此題。完成此題。 問題分析問題分析1：若題目中沒有關于存儲空間的限制，我：若題目中沒有關于存儲空間的限制，我們可以方便地開辟兩個一維數(shù)組，一個存儲原始數(shù)據(jù)，們可以方便地開辟兩個一維數(shù)組，一個存儲原始數(shù)據(jù)，另一個存儲移動后的數(shù)據(jù)。另一個存儲移動后的數(shù)據(jù)。main( )main( )int a100,b100,i,n,k;int a100,b100,i,n,k; input(n,k ); inpu

42、t(n,k ); for(i=0;in;i=i+1) for(i=0;in;i=i+1) input(ai); input(ai); for(i=0;in;i=i+1) for(i=0;in;i=i+1) b(k+i) mod n=ai; b(k+i) mod n=ai;for(i=0;in;i=i+1)for(i=0;in，這樣移動會出，這樣移動會出現(xiàn)重復操作現(xiàn)重復操作,可以在輸入數(shù)據(jù)可以在輸入數(shù)據(jù)后，執(zhí)行后，執(zhí)行k = k mod n; 以保以保證不出現(xiàn)重復移動的問題。證不出現(xiàn)重復移動的問題。這個算法的移動（賦值）次這個算法的移動（賦值）次數(shù)為數(shù)為k*n。當。當n較大時不是一較大時不是一個

43、好的算法。個好的算法。問題分析問題分析2： 將最后一個存儲空間的數(shù)據(jù)將最后一個存儲空間的數(shù)據(jù),存儲在臨時存儲空間中；存儲在臨時存儲空間中； 其余數(shù)據(jù)逐個向后移動一位。其余數(shù)據(jù)逐個向后移動一位。這樣操作共這樣操作共k次就能完成問題的要求。算法次就能完成問題的要求。算法2如下：如下：main( )main( )int a100, i,j,n,k,temp;int a100, i,j,n,k,temp; input(n,k); input(n,k); for(i=0;in;i=i+1) for(i=0;in;i=i+1) input(ai); input(ai); for(i=0;ik;i=i+1)

44、 for(i=0;i0;j=j-1)for(j=n-1;j0;j=j-1) aj=aj-1; aj=aj-1; a0= temp ; a0= temp ; for(i=0;in;i=i+1)for(i=0;in;i=i+1) print(ai); print(ai); 問題分析問題分析3 利用一個臨時存儲空間，把每一個數(shù)據(jù)一次移動到利用一個臨時存儲空間，把每一個數(shù)據(jù)一次移動到位：位：1） 一組循環(huán)移動的情況：一組循環(huán)移動的情況： 通過計算我們可以確定某個元素移動后的具體位置，如通過計算我們可以確定某個元素移動后的具體位置，如n=5, k=3時：時： 0、1、2、3、4循環(huán)移循環(huán)移3位后為位后為

45、2、3、4、0、1。可通過計算得出可通過計算得出0移到移到3的位置，的位置，3移到移到1的位置，的位置，1移到移到4的位置，的位置，4移到移到2的位置，的位置，2移到移到0的位置；一組移動（的位置；一組移動（0-3-1-4-2-0）正好將）正好將全部數(shù)據(jù)按要求進行了移動。這樣只需要一個輔助變量，每個數(shù)全部數(shù)據(jù)按要求進行了移動。這樣只需要一個輔助變量，每個數(shù)據(jù)只需一次移動就可完成整個移動過程。據(jù)只需一次移動就可完成整個移動過程。如果算法就這樣按一組移動去解決問題，就錯了。因為還有其它如果算法就這樣按一組移動去解決問題，就錯了。因為還有其它情況。情況。2）多組循環(huán)移動的情況：算法不能按一組移動去解

46、決問題。）多組循環(huán)移動的情況：算法不能按一組移動去解決問題。 看下一個例子，當看下一個例子，當n=6，k=3時時,1、2、3、4、5、6經(jīng)移動經(jīng)移動 的的結果是結果是4、5、6、1、2、3. 并不象上一個例子并不象上一個例子,一組循環(huán)一組循環(huán) 移動沒移動沒有將全部數(shù)據(jù)移動到位。還需要（有將全部數(shù)據(jù)移動到位。還需要（2-5-2）（）（3-6-3）兩組移動，）兩組移動，共要進行三組循環(huán)移動（共要進行三組循環(huán)移動（1-4，2-5，3-6）才能將全部數(shù)據(jù)操作）才能將全部數(shù)據(jù)操作完畢。完畢。 循環(huán)移動的組數(shù)，與循環(huán)移動的組數(shù)，與k、n的是怎么樣的關系呢？的是怎么樣的關系呢？ 我們再看一個例子，當我們再看

47、一個例子，當N=6，K=2時時, 1、2、3、4、5、6經(jīng)移動的結果是經(jīng)移動的結果是5、6、1、2、3、4. 1移到移到3的位置，的位置，3移到移到5的位置，的位置，5移到移到1的位置，一組移動完成了的位置，一組移動完成了3個數(shù)據(jù)的移動，接個數(shù)據(jù)的移動，接下來，還有一組下來，還有一組2-4-6-2。共進行二組循環(huán)移動，就能將全部數(shù)。共進行二組循環(huán)移動，就能將全部數(shù)據(jù)移動完畢。據(jù)移動完畢。數(shù)學模型：循環(huán)移動的組數(shù)等于數(shù)學模型：循環(huán)移動的組數(shù)等于N與與K的最大公約數(shù)。的最大公約數(shù)。算法設計：算法設計：1）編寫函數(shù)，完成求）編寫函數(shù)，完成求n , k最大公約數(shù)最大公約數(shù)m的功能的功能2）進行）進行m

48、組循環(huán)移動。組循環(huán)移動。3）每組移動，和算法）每組移動，和算法2一樣，通過計算可以確定某個一樣，通過計算可以確定某個 元素移動后的具體位置。在移動之前，用臨時變量元素移動后的具體位置。在移動之前，用臨時變量 存儲需要被覆蓋的數(shù)據(jù)。存儲需要被覆蓋的數(shù)據(jù)。算法算法3如下：如下：ff ( int a ，int b) t = 1; for ( i = 2；i=a and ib0a0=b0，a2=b1, b0a2=b1, b0（a0a0）=a2=a2，b1= b0b1= b0；a4=b1, b0a4=b1, b0（a2a2）= a4= a4，b1= b0b1= b0；a0=b1, b0a0=b1, b0

49、（a4a4）= a0 = a0 ，b1= b0b1= b0；改進后（和算法改進后（和算法2 2類似）：類似）： a4=b a4=b ；a2=a4,a0=a2, b=a0a2=a4,a0=a2, b=a0。 將每組最后一個數(shù)據(jù)元素存儲在輔助存儲空間，以后就可將每組最后一個數(shù)據(jù)元素存儲在輔助存儲空間，以后就可以安全地覆蓋后面的數(shù)組元素了（注意覆蓋順序）。這樣，一以安全地覆蓋后面的數(shù)組元素了（注意覆蓋順序）。這樣，一組循環(huán)移動只需一次將數(shù)據(jù)存入輔助存儲空間，其后一次移動組循環(huán)移動只需一次將數(shù)據(jù)存入輔助存儲空間，其后一次移動只需一次賦值，全部工作大約需要賦值只需一次賦值，全部工作大約需要賦值n n次就

50、可完成。請讀者嘗次就可完成。請讀者嘗試完成。試完成。 343 公倍數(shù)的應用公倍數(shù)的應用【例】編程完成下面給【例】編程完成下面給“余余”猜數(shù)的游戲：猜數(shù)的游戲：你心里先想好一個你心里先想好一個1100之間的整數(shù)之間的整數(shù)x，將它分別除以，將它分別除以3、5和和7并得到三個余數(shù)。你把這三個余數(shù)告訴計算機，計算機并得到三個余數(shù)。你把這三個余數(shù)告訴計算機，計算機能馬上猜出你心中的這個數(shù)。游戲過程如下：能馬上猜出你心中的這個數(shù)。游戲過程如下：please think of a number between 1 and 100your number divided by 3 has a remainder

51、 of? 1your number divided by 5 has a remainder of? 0your number divided by 7 has a remainder of? 5let me think a momentyour number was 40問題分析：算法的關鍵是：找出余數(shù)與求解數(shù)之間的關系，問題分析：算法的關鍵是：找出余數(shù)與求解數(shù)之間的關系，也就是建立問題的數(shù)學模型。也就是建立問題的數(shù)學模型。數(shù)學模型：數(shù)學模型： 1）不難理解當）不難理解當s=u+3*v+3*w時，時，s除以除以3的余數(shù)與的余數(shù)與u除以除以3的的余數(shù)是一樣的。余數(shù)是一樣的。 2）對）對s=cu

52、+3*v+3*w，當，當c除以除以3余數(shù)為余數(shù)為1的數(shù)時的數(shù)時, s除以除以3的的余數(shù)與余數(shù)與u除以除以3的余數(shù)也是一樣的。證明如下：的余數(shù)也是一樣的。證明如下： c 除以除以 3余數(shù)為余數(shù)為1，記，記c=3*k+1，則，則s=u+3*k*u+3*v+3*w，由，由1)的結的結論，上述結論正確。論，上述結論正確。 記記a，b，c分別為所猜數(shù)據(jù)分別為所猜數(shù)據(jù)d除以除以3，5，7后的余數(shù)，則后的余數(shù)，則 d=70*a+21*b+15*c。 為問題的數(shù)學模型，其中為問題的數(shù)學模型，其中70稱作稱作a的系數(shù)，的系數(shù)，21稱作稱作b的系數(shù)的系數(shù),15稱作稱作c的系數(shù)。的系數(shù)。由以上數(shù)學常識，由以上數(shù)學常識，a、b、c的系數(shù)必須滿足：的系數(shù)必須滿足：1） b、c的系數(shù)能被的系數(shù)能被3整除，且整除，且a的系數(shù)被的系數(shù)被3整除余整除余1；這樣；這樣d除以除以3的余數(shù)與的余數(shù)與a相同。相同。2） a、c的系數(shù)能被的系數(shù)能被5整除，且整除，且b的系數(shù)被的系數(shù)被5整除余整除余1；這樣；這樣d除以除以5的余數(shù)與的余數(shù)與b相同。相同。3) a、b的系數(shù)能被的系數(shù)能被7整除，且整除，且c的系數(shù)被的系數(shù)被7整除余整除余1；這樣；這樣d除以除以