《算法設(shè)計：第九講》ppt課件

1、3.3 3.3 優(yōu)化算法的根本技巧優(yōu)化算法的根本技巧【例題【例題2424】有】有1010箱產(chǎn)品每箱有箱產(chǎn)品每箱有10001000件，正品每件件，正品每件100100克。其中克。其中的幾箱是次品，次品每件比正品輕的幾箱是次品，次品每件比正品輕1010克，問能否用秤只稱一次克，問能否用秤只稱一次，就找出哪幾箱是次品。，就找出哪幾箱是次品。問題分析：問題分析：1 1假設(shè)只需一箱是次品：假設(shè)只需一箱是次品：2 2假設(shè)有幾箱是次品：假設(shè)有幾箱是次品：3.3 3.3 優(yōu)化算法的根本技巧優(yōu)化算法的根本技巧【例題【例題2525】編寫算法對輸入的一個整數(shù)，判別它能否被】編寫算法對輸入的一個整數(shù)，判別它能否被3

2、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任一個整除。任一個整除。3.3 3.3 優(yōu)化算法的根本技巧優(yōu)化算法的根本技巧【算法分析】【算法分析】1 1運用運用ifif語句實現(xiàn)，但需求進(jìn)展多次條件判別，而且嵌套語句實現(xiàn)，但需求進(jìn)展多次條件判別，而且嵌套的的ifif語句降低了程序的可讀性。語句降低了程序的可讀性。2 2運用表達(dá)

3、式運用表達(dá)式 k=(x%3=0)+(x%5=0)+(x%7=0) k=(x%3=0)+(x%5=0)+(x%7=0) k k為為0 0：不能被：不能被3 3，5 5，7 7整除整除 k k為為1 1：能被：能被3 3、5 5、7 7中的一個整除，但不能指出是哪一個中的一個整除，但不能指出是哪一個 k k為為2 2：能被：能被3 3、5 5、7 7中的兩個整除中的兩個整除 k k為為3 3：能同時被：能同時被3 3、5 5、7 7整除整除3.3 3.3 優(yōu)化算法的根本技巧優(yōu)化算法的根本技巧3 3K%3=0K%5=0K%7=0全部1117其中2個110610150113其中1個1004010200

4、110個00003.3 3.3 優(yōu)化算法的根本技巧優(yōu)化算法的根本技巧 構(gòu)造表達(dá)式構(gòu)造表達(dá)式 k=(k%3=0) k=(k%3=0)* *4+(k%5=0)4+(k%5=0)* *2+(k%7=02+(k%7=0* *1 1 switch(k) switch(k) case 7: print( case 7: print(“allall);break;);break; case 6: print( case 6: print(“3,53,5);break;);break; case 5: print( case 5: print(“3,73,7);break;);break; case 4: p

5、rint case 4: print3 3；break;break; case 3: print( case 3: print(“5,75,7);break;);break; case 2: print( case 2: print(“5 5);break;);break; case 1: print( case 1: print(“7 7);break;);break; case 0: print( case 0: print(“NoneNone);break;);break; 3.4 3.4 優(yōu)化算法的數(shù)學(xué)模型優(yōu)化算法的數(shù)學(xué)模型l選擇恰當(dāng)?shù)臄?shù)學(xué)模型，可以使算法的效率更高、占用空間更選擇恰當(dāng)

6、的數(shù)學(xué)模型，可以使算法的效率更高、占用空間更合理或使算法更簡約。合理或使算法更簡約。l認(rèn)識數(shù)學(xué)模型和數(shù)學(xué)建模認(rèn)識數(shù)學(xué)模型和數(shù)學(xué)建模l一個關(guān)于數(shù)學(xué)模型的簡單實例：知有一個關(guān)于數(shù)學(xué)模型的簡單實例：知有5 5個數(shù)，求前四個數(shù)與第個數(shù)，求前四個數(shù)與第五個數(shù)分別相乘后的最大數(shù)。五個數(shù)分別相乘后的最大數(shù)。 p106 p106l算法算法1 1：l算法算法2 2：3.4 3.4 優(yōu)化算法的數(shù)學(xué)模型優(yōu)化算法的數(shù)學(xué)模型操作操作算法算法 乘法乘法賦值賦值條件判別條件判別 Max1 4 7 3 Max2 1 4 33.4 3.4 優(yōu)化算法的數(shù)學(xué)模型優(yōu)化算法的數(shù)學(xué)模型w數(shù)學(xué)模型：是利用數(shù)學(xué)言語符號、式子與圖像模擬現(xiàn)數(shù)學(xué)

7、模型：是利用數(shù)學(xué)言語符號、式子與圖像模擬現(xiàn)實的模型。實的模型。w根本特征：把現(xiàn)實模型籠統(tǒng)、簡化為某種數(shù)據(jù)構(gòu)造。根本特征：把現(xiàn)實模型籠統(tǒng)、簡化為某種數(shù)據(jù)構(gòu)造。w作用：作用：w解釋特定景象的現(xiàn)實形狀解釋特定景象的現(xiàn)實形狀w預(yù)測到對象的未來情況預(yù)測到對象的未來情況w提供處置對象的最優(yōu)決策或控制提供處置對象的最優(yōu)決策或控制3.4 3.4 優(yōu)化算法的數(shù)學(xué)模型優(yōu)化算法的數(shù)學(xué)模型w數(shù)學(xué)建模：數(shù)學(xué)建模就是把現(xiàn)實世界中的實踐問題加以提數(shù)學(xué)建模：數(shù)學(xué)建模就是把現(xiàn)實世界中的實踐問題加以提煉，籠統(tǒng)為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性煉，籠統(tǒng)為數(shù)學(xué)模型，求出模型的解，驗證模型的合理性，并用該數(shù)學(xué)模型所提供的解答來

8、解釋現(xiàn)實問題，我們把，并用該數(shù)學(xué)模型所提供的解答來解釋現(xiàn)實問題，我們把數(shù)學(xué)知識的這一運用過程稱為數(shù)學(xué)建模。數(shù)學(xué)知識的這一運用過程稱為數(shù)學(xué)建模。w歸納法：歸納法：w是通用而簡單的數(shù)學(xué)建模方法。是通用而簡單的數(shù)學(xué)建模方法。w從分析問題的幾種簡單的、特殊的情況中，發(fā)現(xiàn)普通規(guī)律從分析問題的幾種簡單的、特殊的情況中，發(fā)現(xiàn)普通規(guī)律或作出某種猜測，從而找到處理問題的途徑。或作出某種猜測，從而找到處理問題的途徑。w歸納法是從簡單到復(fù)雜，由個別到普通的一種研討方法。歸納法是從簡單到復(fù)雜，由個別到普通的一種研討方法。3.4.1 3.4.1 楊輝三角形的運用楊輝三角形的運用【例題】求【例題】求n n次二項式各項的系

9、數(shù)。次二項式各項的系數(shù)。知二項式的展開式為：知二項式的展開式為：分析：假設(shè)只用的組合數(shù)學(xué)的知識，直接建模分析：假設(shè)只用的組合數(shù)學(xué)的知識，直接建模問題：算法中也要有大量的乘法和除法運算，效率很低。問題：算法中也要有大量的乘法和除法運算，效率很低。3.4.1 3.4.1 楊輝三角形的運用楊輝三角形的運用數(shù)學(xué)常識：各階多項式的系數(shù)呈楊輝三角形的規(guī)律：數(shù)學(xué)常識：各階多項式的系數(shù)呈楊輝三角形的規(guī)律：(a+b)0 1 (a+b)0 1 (a+b)1 1 1(a+b)1 1 1(a+b)2 1 2 (a+b)2 1 2 1 1(a+b)3 1 (a+b)3 1 3 3 13 3 1(a+b)4 1 4 6

10、4 1(a+b)4 1 4 6 4 1(a+b)5 (a+b)5 數(shù)學(xué)模型：數(shù)學(xué)模型：n n次二項式的系數(shù)就是次二項式的系數(shù)就是n n階楊輝三角形。階楊輝三角形。3.4.1 3.4.1 楊輝三角形的運用楊輝三角形的運用求求n n階楊輝三角形的遞歸算法：階楊輝三角形的遞歸算法：ff(inta,intn)if(n=1)a1=1;a2=1;elseff(a,n-1);/*遞歸求出遞歸求出n-1階階*/an+1=1;for(i=n;i=2;i-)ai=ai+ai-1; main( )int a100,i,n; input( n ); ff(a,n); for(i=1;i=n+1;i=i+1) prin

11、t(ai);3.4.2 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用【例題】數(shù)組中有【例題】數(shù)組中有n n個數(shù)據(jù)，要將它們順序循環(huán)向后移個數(shù)據(jù)，要將它們順序循環(huán)向后移k k位，即位，即前面的元素向后移前面的元素向后移k k位，后面的元素那么循環(huán)向前移位，后面的元素那么循環(huán)向前移k k位。位。例：例：1 1、2 2、3 3、4 4、5 5循環(huán)移循環(huán)移3 3位后為：位后為：3 3、4 4、5 5、1 1、2 2?！緦崿F(xiàn)【實現(xiàn)1 1】利用一個數(shù)組存放原始數(shù)據(jù)，利用另外一個數(shù)組存】利用一個數(shù)組存放原始數(shù)據(jù)，利用另外一個數(shù)組存放結(jié)果。放結(jié)果。3.4.2 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用l假設(shè)

12、標(biāo)題限定：不能運用假設(shè)標(biāo)題限定：不能運用2 2* *n n以上的空間來實現(xiàn)此題。以上的空間來實現(xiàn)此題。 l【實現(xiàn)【實現(xiàn)2 2】利用】利用k k次循環(huán)，每次挪動一位。次循環(huán)，每次挪動一位。l 1 1先把先把a(bǔ)nan保管到暫時單元保管到暫時單元temptempl 2 2將將an-1anan-1an，an-2 an-1an-2 an-1l 3 3將將temp a0temp a0中中3.4.2 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用【實現(xiàn)【實現(xiàn)3 3】利用一個暫時變量，將每一個數(shù)據(jù)一次挪動到位】利用一個暫時變量，將每一個數(shù)據(jù)一次挪動到位1 1一組循環(huán)挪動的情況：一組循環(huán)挪動的情況： 經(jīng)過計算我們

13、可以確定某個元素挪動后的詳細(xì)位置，經(jīng)過計算我們可以確定某個元素挪動后的詳細(xì)位置， 如如n=5, k=3n=5, k=3時：時： 0 0、1 1、2 2、3 3、4 4循環(huán)移循環(huán)移3 3位后為位后為2 2、3 3、4 4、0 0、1 1。 可經(jīng)過計算得出可經(jīng)過計算得出0303，3131，1 41 4，4242，2020； 一組挪動一組挪動0-3-1-4-2-00-3-1-4-2-0正好將全部數(shù)據(jù)按要求進(jìn)展了正好將全部數(shù)據(jù)按要求進(jìn)展了挪動。這樣只需求一個輔助變量，每個數(shù)據(jù)只需一次挪動就可挪動。這樣只需求一個輔助變量，每個數(shù)據(jù)只需一次挪動就可完成整個挪動過程。完成整個挪動過程。3.4.2 3.4.2

14、 最大公約數(shù)的運用最大公約數(shù)的運用2 2多組循環(huán)挪動的情況：多組循環(huán)挪動的情況： 當(dāng)當(dāng)n=6n=6，k=3k=3時時, , 1 1、2 2、3 3、4 4、5 5、6 6經(jīng)挪動的結(jié)果是經(jīng)挪動的結(jié)果是4 4、5 5、6 6、1 1、2 2、3. 3. 并不象上一個例子并不象上一個例子, ,一組循環(huán)挪動一組循環(huán)挪動1-4-11-4-1沒有將全部數(shù)沒有將全部數(shù)據(jù)挪動到位。還需求據(jù)挪動到位。還需求2-5-22-5-23-6-33-6-3兩組挪動才干將全部兩組挪動才干將全部數(shù)據(jù)操作終了。數(shù)據(jù)操作終了。 循環(huán)挪動的組數(shù)，與循環(huán)挪動的組數(shù)，與k k、n n的是怎樣樣的關(guān)系呢？的是怎樣樣的關(guān)系呢？ 3.4.2

15、 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用我們再看一個例子：我們再看一個例子：當(dāng)當(dāng)N=6N=6，K=2K=2時時, , 1 1、2 2、3 3、4 4、5 5、6 6經(jīng)挪動的結(jié)果是經(jīng)挪動的結(jié)果是5 5、6 6、1 1、2 2、3 3、4. 4. 一組挪動一組挪動1-3-5-11-3-5-1，完成了，完成了3 3個數(shù)據(jù)的挪動；接下來，還有個數(shù)據(jù)的挪動；接下來，還有一組一組2-4-6-22-4-6-2。共進(jìn)展二組循環(huán)挪動，就能將全部數(shù)據(jù)挪動終。共進(jìn)展二組循環(huán)挪動，就能將全部數(shù)據(jù)挪動終了。了。數(shù)學(xué)模型：循環(huán)挪動的組數(shù)等于數(shù)學(xué)模型：循環(huán)挪動的組數(shù)等于N N與與K K的最大公約數(shù)。的最大公約數(shù)。3.

16、4.2 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用算法設(shè)計：算法設(shè)計：1 1編寫函數(shù)，完成求編寫函數(shù)，完成求n,kn,k最大公約數(shù)最大公約數(shù)m m的功能的功能2 2進(jìn)展進(jìn)展m m組循環(huán)挪動。組循環(huán)挪動。3 3每組共每組共n/mn/m個數(shù)據(jù)：個數(shù)據(jù)：第一組：第一組：a1 a(1+k)%n a(1+2k)%na1 a(1+k)%n a(1+2k)%n第二組：第二組：a2 a(2+k)%n a(2+2k)%na2 a(2+k)%n a(2+2k)%n第第m m組：組： am a(m+k)%n a(m+2k)%n am a(m+k)%n a(m+2k)%n3.4.2 3.4.2 最大公約數(shù)的運用最大

17、公約數(shù)的運用/*求求a，b的最大公約數(shù)的最大公約數(shù)*/int ff ( int a,int b) t = 1; for ( i = 2；i=a &i=b；i+) while (a%i=0 and b%i=0 ) t=t * i ; a=a / i ; b= b / i ; return(t) ; main( )int a100,b0,b1,i,j,n,k,m,tt;input(n,k);for(i=0;in;i=i+1) input(ai);m=ff(n,k);for(j=0;jm;j=j+1) /*共挪動m組*/ b0= aj; /*將每組的第一個數(shù)保管到b0中*/ tt=j; 3.4.2

18、3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用for(i=0;in/m;i=i+1) /*每組中共有n/m個數(shù)據(jù)*/ tt=(tt+k)%n; /*計算挪動的目的位置*/ b1=att; /*先保管目的位置中的數(shù)據(jù)*/ att=b0; /*將前面的數(shù)據(jù)b0移入目的位置*/ b0=b1; /*將b1作為新的b0*/ for(i=0;in;i=i+1) print(ai);3.4.2 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用分析該算法中挪動數(shù)據(jù)時的賦值次數(shù)f=n/m;for(j=0;j0;i-) a(j+i*k)%n=a(j+(i-1)*k)%n;/*從后向前挪動*/ aj=b; /*把該組的最

19、后一個數(shù)送到aj處*/ 3.4.2 3.4.2 最大公約數(shù)的運用最大公約數(shù)的運用【例】編程完成下面給“余猜數(shù)的游戲：他心里先想好一個1100之間的整數(shù)x，將它分別除以3、5和7并得到三個余數(shù)。他把這三個余數(shù)通知計算機(jī)，計算機(jī)能馬上猜出他心中的這個數(shù)。游戲過程如下：Please think of a number between 1 and 100Your number divided by 3 has a remainder of? 1your number divided by 5 has a remainder of? 0your number divided by 7 has a rem

20、ainder of? 5your number is 403.4.3 3.4.3 公倍數(shù)的運用公倍數(shù)的運用【問題分析】算法設(shè)計的關(guān)鍵：找出余數(shù)與求解數(shù)之間的關(guān)系，建立問題的數(shù)學(xué)模型?！緮?shù)學(xué)模型】 1不難了解當(dāng)s=u+3*v+3*w時，s除以3的余數(shù)與u除以3的余數(shù)是一樣的。 2對s=cu+3*v+3*w，當(dāng)c是除以3余1的數(shù)時, s除以3的余數(shù)與u除以3的余數(shù)也是一樣的。3.4.3 3.4.3 公倍數(shù)的運用公倍數(shù)的運用【模型建立】設(shè)a,b,c分別是該數(shù)除以3，5，7后的余數(shù)，那么該數(shù)為： x=c1*a+c2*b+c3*c3.4.3 3.4.3 公倍數(shù)的運用公倍數(shù)的運用分析：1x除以3余a：那么

21、c1應(yīng)除以3余1，c2,c3為3的倍數(shù)2x除以5余b：那么c2應(yīng)除以5余1，c1,c3為5的倍數(shù)3x除以7余c：那么c3應(yīng)除以7余1，c1,c2為7的倍數(shù)計算后，滿足條件的c1=70 c2=21 c3=15 x=70*a+21*b+15*c假設(shè)求解的d比100大，需求循環(huán)減去3，5，7的最小公倍數(shù)。main( ) int a,b,c,d; input(a);/*除3后的余數(shù)*/ input(b);/*除5后的余數(shù)*/ input(c);/*除7后的余數(shù)*/ d=70*a+21*b+15*c; while (d100) d=d-105;/*105為3,5,7的最小公倍數(shù)*/ print( “yo

22、ur number is , d); 3.4.3 3.4.3 公倍數(shù)的運用公倍數(shù)的運用思索：3個除數(shù)也由用戶給出，請設(shè)計算法?！纠繕翘萆嫌小纠繕翘萆嫌衝 n階臺階，上樓可以一步上階臺階，上樓可以一步上1 1階，也可以一步階，也可以一步上上2 2階，編寫算法計算共有多少種不同的上樓梯方法。階，編寫算法計算共有多少種不同的上樓梯方法?！緮?shù)學(xué)模型】此問題假設(shè)按照習(xí)慣，從前向后思索，也就是【數(shù)學(xué)模型】此問題假設(shè)按照習(xí)慣，從前向后思索，也就是從第一階開場，思索怎樣樣走到第二階、第三階、第四階從第一階開場，思索怎樣樣走到第二階、第三階、第四階，那么很難找出問題的規(guī)律；而反過來先思索，那么很難找出問題的

23、規(guī)律；而反過來先思索“到第到第n n階階有哪幾種情況？，答案就簡單了，只需兩種情況：有哪幾種情況？，答案就簡單了，只需兩種情況： 1 1 從第從第n-1n-1階到第階到第n n階；階； 2 2 從第從第n-2n-2階到第階到第n n階。階。3.4.4 3.4.4 斐波那契數(shù)列的運用斐波那契數(shù)列的運用反向分析法反向分析法記記n n階臺階的走法數(shù)為階臺階的走法數(shù)為f(n)f(n)，那么，那么 f(n)= 1 n=1 f(n)= 1 n=1 f(n)= 2 f(n)= 2 n=2 n=2 f(n)=f(n-1)+f(n-2) n2 f(n)=f(n-1)+f(n-2) n23.4.4 3.4.4 斐

24、波那契數(shù)列的運用斐波那契數(shù)列的運用2 2倒推法：是對某些特殊問題所采用的從后向前推解問題倒推法：是對某些特殊問題所采用的從后向前推解問題的方法。的方法?！纠纠? 3】猴子吃桃問題：一只小猴子摘了假設(shè)干桃子，每天吃】猴子吃桃問題：一只小猴子摘了假設(shè)干桃子，每天吃現(xiàn)有桃的一半多一個，到第現(xiàn)有桃的一半多一個，到第1010天時就只需一個桃子了，求原有天時就只需一個桃子了，求原有多少個桃？多少個桃？數(shù)學(xué)模型：數(shù)學(xué)模型： 每天的桃子數(shù)為：每天的桃子數(shù)為：a10=1, a9=(1+a10)a10=1, a9=(1+a10)* *2, a8=(1+a9)2, a8=(1+a9)* *2 2 遞推公式為：遞推

25、公式為：ai=(1+ai+1)ai=(1+ai+1)* *2 i = 9,8,7,612 i = 9,8,7,61【例【例2 2】穿越沙漠問題】穿越沙漠問題用一輛吉普車穿越用一輛吉普車穿越10001000公里的沙漠。吉普車的總裝油量為公里的沙漠。吉普車的總裝油量為500500加侖，耗油率為加侖，耗油率為1 1加侖加侖/ /公里。由于沙漠中沒有油庫，必需先用公里。由于沙漠中沒有油庫，必需先用這輛車在沙漠中建立暫時油庫。該吉普車以最少的耗油量穿越這輛車在沙漠中建立暫時油庫。該吉普車以最少的耗油量穿越沙漠，應(yīng)在什么地方建油庫，以及各處的貯油量。沙漠，應(yīng)在什么地方建油庫，以及各處的貯油量?！痉治觥肯瓤?/p>

26、一簡單問題：【分析】先看一簡單問題： 有一位探險家用有一位探險家用5 5天的時間徒步橫穿天的時間徒步橫穿A A、B B兩村，兩村間是兩村，兩村間是荒無人煙的沙漠，假設(shè)一個人只能攜帶荒無人煙的沙漠，假設(shè)一個人只能攜帶3 3天的食物和水，那么天的食物和水，那么這個探險家至少雇幾個人才干順利經(jīng)過沙漠。這個探險家至少雇幾個人才干順利經(jīng)過沙漠。 【例】核反響堆中有【例】核反響堆中有和和兩種粒子，每秒鐘內(nèi)一個兩種粒子，每秒鐘內(nèi)一個粒子粒子可以反響產(chǎn)生可以反響產(chǎn)生3 3個個粒子，而一個粒子，而一個粒子可以反響產(chǎn)生粒子可以反響產(chǎn)生1 1個個粒子和粒子和2 2個個粒子。假設(shè)在粒子。假設(shè)在t=0t=0時辰的反響堆

27、中只需一個時辰的反響堆中只需一個粒粒子，求在子，求在t t時辰的反響堆中時辰的反響堆中粒子和粒子和粒子數(shù)。粒子數(shù)?！痉治觥俊痉治觥?.4.5 3.4.5 特征根求解遞歸方程特征根求解遞歸方程時辰010103236363*3+2*6i i-13*ai-1+2*bi-1【數(shù)學(xué)模型【數(shù)學(xué)模型1 1】此題中共涉及兩個變量，】此題中共涉及兩個變量，i i時辰時辰粒子數(shù)為粒子數(shù)為nini，粒子數(shù)為粒子數(shù)為mimi，那么有：，那么有：n0=1,m0=0,ni=mi-1n0=1,m0=0,ni=mi-1，mi=3ni-mi=3ni-1+2mi-11+2mi-13.4.5 3.4.5 特征根求解遞歸方程特征根求

28、解遞歸方程mainmain int n100,m100,t,i; int n100,m100,t,i; input(t); input(t); n0=1; / n0=1; /初始化操作初始化操作 m0=0; m0=0; for (i=1;i=t;i+) / for (i=1;i=t;i+) /進(jìn)展進(jìn)展t t次遞推次遞推 ni=mi-1; ni=mi-1; mi=3 mi=3 * * ni-1 + 2 ni-1 + 2 * * mi-1; mi-1; print(nt print(nt，mt); /mt); /輸出結(jié)果輸出結(jié)果 【數(shù)學(xué)模型【數(shù)學(xué)模型2 2】設(shè)在】設(shè)在t t時辰的時辰的粒子數(shù)為粒子

29、數(shù)為f ft t，粒子數(shù)為粒子數(shù)為g(t)g(t)，依題可知：，依題可知： g(t)=3f(t -1)+2g(t -1) g(t)=3f(t -1)+2g(t -1) 1 1 f(t)=g(t -1) f(t)=g(t -1) 2 2 g(0)=0, g(0)=0, f(0)=1 f(0)=1 整理得：整理得： g(t)=3g(t-2)+2g(t-1) g(t)=3g(t-2)+2g(t-1) t2t2 4 4 g(0)=0 g(0)=0 g(1)=3 g(1)=33.4.5 3.4.5 特征根求解遞歸方程特征根求解遞歸方程用特征根求得：用特征根求得： g(t)= g(t)= = =3.4.5

30、 3.4.5 特征根求解遞歸方程特征根求解遞歸方程tt)1(43343mainmain int t,i; int t,i; input(t); input(t); n=pow(3,t); / n=pow(3,t); /* *n n代表代表a a粒子數(shù)量粒子數(shù)量* */ / m=pow(3,t+1); / m=pow(3,t+1); /* *m m代表代表B B粒子數(shù)量粒子數(shù)量* */ / if(t%2=1) if(t%2=1) n=n-3; m=m+3; n=n-3; m=m+3; else else n=n+3; m=m-3; n=n+3; m=m-3; n=int(n/4); n=int(n/4); m=int(m/4); m=int(m/4); print(n,m); print(n,m); 3.4.5 3.4.5 特征根求解遞歸方程特征根求解遞歸方程算法分析：在數(shù)學(xué)模型算法分析：在數(shù)學(xué)模型2 2中，中，運用數(shù)學(xué)的方法建立了遞歸函運用數(shù)學(xué)的方法建立了遞歸函數(shù)并轉(zhuǎn)化為非遞歸函數(shù)。它的數(shù)并轉(zhuǎn)化為非遞歸函數(shù)。它的優(yōu)點是算法的復(fù)雜性與問題的優(yōu)點是算法的復(fù)雜性與問題的規(guī)模無關(guān)。針對某一詳細(xì)數(shù)據(jù)，規(guī)模無關(guān)。針對某一詳細(xì)數(shù)據(jù)，問題的規(guī)模對時間的影響微乎問題的規(guī)模對時間的影響微乎其微。其微?！纠纠? 1】百錢買百雞】百錢買百雞【例【例2 2】解數(shù)字迷：】解數(shù)字迷： A B C A