【正文】 hile語句 ? 轉(zhuǎn)移語句 ? 循環(huán)應用 94 循環(huán)應用 一、遞推法 95 草原上有一對小兔子，它們剛出生后的第 1個月就會逐步長大，到了第 2個月末就生出一對小兔子。第 3個月大兔子會繼續(xù)生一對小兔子，而第 2個月出生的小兔子會逐步長大。第 4個月時，第 1月出生的兔子繼續(xù)生育，第 2月出生的小兔子也可以生育一對小兔子了，第 3月出生的小兔子則逐步長大 …… 假設(shè)這些草原的兔子非常長壽，可以認為它們不會死亡。請建立數(shù)學模型，計算 第 N個 月時，草原上將會有多少對兔子 ? 96 ? 例：數(shù)列 1 2 … 是著名的菲波那契數(shù)列，其遞推通項公式為： F1 = F2 = 1 Fn = Fn1 + Fn2 (n=3) 為求出第 N 項的值，請編寫程序。 根據(jù)遞推通項公式，可用 遞推法 編寫程序，計算第 N項的值。 97 ? 遞推法 由初始的已知條件開始，先計算出第 (N1)步的結(jié)果，再利用已知的前 (N1)項結(jié)果，按遞推公式 (或遵照遞推規(guī)則 )，推出第 N 步結(jié)果。 遞推法是程序設(shè)計中最常用的方法之一，使用遞推法必須有明確的遞推初始值和遞推規(guī)則 (遞推公式 )。 98 程序主體 f = f2 = 1。 for ( i=3。 i=n。 i++ ) { f1 = f2。 f2 = f。 f = f1 + f2。 } i = n? 向前傳遞前兩項 f1 = f2 f2 = f 成立 不成立 初始化： f=f2=1 計算 f=f1+f2 遞推項： i=3 i ++ 數(shù)列對應關(guān)系： f1， f2， f 遞推計算 f1=f2=1。 for(i=3。i=n。i++) { f=f1+f2。 f1=f2。 f2=f。 } 99 include int main( ) { long f1, f2, f。 int i。 for ( 。 。 ) { printf (Input n=?)。 scanf (%d,n)。 if ( n = 3 ) break。 /*退出 for循環(huán) */ else printf (\nInput n is error !\n)。 } /*控制輸入正確的 N值 */ f = f2 = 1。 /*設(shè)置遞推初始值 */ for ( i=3。 i=n。 i++) /*用遞推法計算第 N項的值 */ { f1 = f2。 f2 = f。 f = f1 + f2。 } printf (No. %d is %d\n, n, f)。 } 100 循環(huán)應用 二、窮舉法 101 ? 例：百錢百雞問題 中國古代數(shù)學家張丘建在他的 《 算經(jīng) 》 中提出了著名的“百錢百雞問題”：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，翁、母、雛各幾何 ? 問題分析與算法設(shè)計 設(shè)：要買 x只公雞， y只母雞， z只小雞，可得到方程 : x + y + z = 100 ① 5 x + 3 y + z / 3 = 100 ② 取值范圍： 0 = x, y, z = 100 可以采用窮舉法求解：將變量 x、 y、 z 的所有取值可能代入方程進行計算 102 int main( ) { int x,y,z,j=0。 for(x=0。x=100。x++) for(y=0。y=100。y++) for(z=0。z=100。z++) if (x+y+z==100 5*x+3*y+z/3==100) printf(%2d:cock=%2d hen=%2d chicken=%2d\n, ++j,x,y,z)。 } 運行結(jié)果： 1: cock= 0 hen=25 chicken=75 2: cock= 3 hen=20 chicken=77 … … … … … … 7: cock=12 hen= 4 chicken=84 103 丟失重要條件： z 應該能夠被 3整除。 int main( ) { int x, y, z, j=0。 for(x=0。 x=20。 x++) for(y=0。 y=33。 y++) for(z=0。 z=100。 z++) if(z%3==0x+y+z==1005*x+3*y+z/3==100) printf(%2d:cock=%2d hen=%2d chicken=%2d\n, ++j,x,y,z) 。 }運行程序，正確的結(jié)果： 1: cock= 0 hen=25 chicken=75 2: cock= 4 hen=18 chicken=78 3: cock= 8 hen=11 chicken=81 4: cock=12 hen= 4 chicken=84 z+=3) 104 優(yōu)化程序： for(x=0。 x=20。 x++) for(y=0。 y=33。 y++) for(z=0。 z=100。 z++) if(z%3==0x+y+z==100 5*x+3*y+z/3==100) printf(%2d:cock=%2d hen=%2d chicken=%2d\n, ++j,x,y,z)。 再優(yōu)化： for(x=0。 x=20。 x++) for(y=0。 y=(1005*x)/3。 y++) { z=100xy。 if( z%3==0 5*x+3*y+z/3==100) printf(%2d:cock=%2d hen=%2d chicken=%2d\n, ++j,x,y,z)。 } 105 ? 例：新娘和新郎 問題： 三對情侶參加婚禮 ， 三個新郎為 A、 B、 C， 三個新娘為 X、 Y、 Z。 有人不知道誰和誰結(jié)婚 ， 于是詢問了其中的三位 ， 聽到的回答是這樣的： Ａ說他將和Ｘ結(jié)婚；Ｘ說她的未婚夫是Ｃ；Ｃ說他將和Ｚ結(jié)婚 。 這人聽后知道他們在開玩笑 ， 全是假話 。 請編程找出誰將和誰結(jié)婚 。 問題分析與算法設(shè)計： 設(shè)： A、 B、 C三人用 3表示 ， 將 X和 A結(jié)婚表示為 x=1， 將 Y不與 A結(jié)婚表示為 y!=1。 則： x!=1 A不與 X結(jié)婚 x!=3 X的未婚夫不是 C z!=3 C不與 Z結(jié)婚 題意還隱含： x!=y 且 x!=z 且 y!=z 106 int main ( ) { int x, y, z。 for (x=1。 x=3。 x++) /*窮舉 X的全部可能配偶 */ for (y=1。 y=3。 y++) /*窮舉 Y的全部可能配偶 */ for (z=1。 z=3。 z++) /*窮舉 Z的全部可能配偶 */ if (x!=1 x!=3 z!=3 x!=y x!=z y!=z) { printf (X will marry to %c.\n, 39。A39。+x1)。 printf (Y will marry to %c.\n, 39。A39。+y1)。 printf (Z will marry to %c.\n, 39。A39。+z1)。 } } 107 循環(huán)應用 ? 窮舉法的關(guān)鍵 ? 判斷問題是否適合使用窮舉法 ? 明確窮舉的終止條件 ? 窮舉的對象 (變量 )的范圍 ? 注意效率 —— 減少嘗試次數(shù) 108 ? 求 555555的約數(shù)中最大的三位數(shù) ? 求不超過 n的最大素數(shù) ? 求首項大于 0的等差數(shù)列：前四項和為 26，前四項的積為 880 ? 從鍵盤上任意輸入一個正整數(shù)，要求判斷該正整數(shù)是否是另一個整數(shù)的平方。 ? 百錢百雞 ? 新娘和新郎 ? 其它排列組合問題 109 循環(huán)應用 三、圖形問題 110 ? 例：在一行中輸出 n 個 * 號。 例如，輸入 n=4，輸出的圖形如下： * * * * 基本語句： 輸出一個 * 號： printf(“*”)。 或 putchar(?*?)。 基本算法： 1. 輸入 n 2. 重復輸出 n 個 *； 3. 輸出一個 \n scanf (“%d”, n)。 while (n0) { printf (“*”)。 n。 } printf (“\n”)。 111 ? 例：輸出邊長為 n 的正方型 例如，輸入 n=4，輸出如下圖形： * * * * * * * * * * * * * * * * 算法分析與設(shè)計： 1. 輸入 n ； 2. 重復輸出 n行，每行 輸出 n 個 *； 加細一： 1. 輸入 n ； 2. for ( i=1。 i=n。 i++ ) 輸出 一行中的 n 個 * ； 112 加細二： 1. 輸入 n； 2. for ( i=1。 i=n。 i++ ) { 輸出 n 個 * ； 換新行 。 } 加細三： 1. 輸入 n； 2. for ( i=1。 i=n。 i++ ) { for ( j=1。 j=n。 j++ ) printf (“*”)； printf(“\n”) 。 } 113 ? 整理，得到程序如下： int main ( ) { int m, i, j； scanf( “%d”, n )； for ( i=1。 i=n。 i++ ) /* 控制輸出 n行 */ { for ( j=1。 j=n。 j++ ) /*輸出 一行中的 n個 *號 */ printf(“*”)； printf(“\n”)； } } ? 分析方法 ——逐步求精法 對于比較復雜問題，不可能一下得到程序，可以先將簡單的部分明確出來，再逐步對復雜部分進行細化，一步一步推出完整程序。 114 ? 例：輸出邊長為 n 的平行四邊形 例如，輸入 n=4，輸出如下圖形： * * * * * * * * * * * * * * * * 算法分析與設(shè)計： 在正方形每行 *號的前面先多輸出若干個空格。對于第 i 行， 1=i=n， 則應先輸出 個 空格。 ni 115 int main ( ) { int n, i, j； scanf( “%d”, n )； for ( i=1。 i=n。 i++ ) /* 控制輸出 n 行 */ { for ( j=1。 j=ni。 j++) /*控制輸出 ni個空格 */ p