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