【正文】 足方程 ...... z=100時(shí)：是否滿足方程 當(dāng) x=0,y=1,z=0時(shí)：是否滿足方程 z=1時(shí)：是否滿足方程 ...... z=100時(shí)：是否滿足方程 當(dāng) x=0,y=2,z=0時(shí)：是否滿足方程 ...... 當(dāng) x=100,y=100,z=100時(shí)： ...... z=100 滿足方 程？ Y N 輸出 z++ z = 0 y=100 y++ y = 0 x=100 x++ x = 0 開始 結(jié)束 第 21 頁 典型數(shù)值問題 例 6 ? 程序 z=100 滿足方 程？ Y N 輸出 z++ z = 0 y=100 y++ y = 0 x=100 x++ x = 0 開始 結(jié)束 include void 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(..,++j,x,y,z)。 } 第 22 頁 典型數(shù)值問題 例 6 include void 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 3: cock= 4 hen=18 chicken=78 4: cock= 7 hen=13 chicken=80 5: cock= 8 hen=11 chicken=81 6: cock=11 hen= 6 chicken=83 7: cock=12 hen= 4 chicken=84 例 C3 第 23 頁 典型數(shù)值問題 例 6 ? 丟失重要條件： z 應(yīng)該能夠被 ３ 整除。 include void 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==0 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= 4 hen=18 chicken=78 3: cock= 8 hen=11 chicken=81 4: cock=12 hen= 4 chicken=84 z+=3) 第 24 頁 典型數(shù)值問題 例 6 ? 優(yōu)化程序： for (x=0。 x=20。 x++) for (z=0。 z100。 z+=3) { y = 100xz。 if ( 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 ) 。 } 第 25 頁 典型數(shù)值問題 百例 8：借書方案知多少 ? ? 問題 小明有 5本新書 ， 要借給Ａ 、 Ｂ 、 Ｃ三位小朋友 ， 若每人每次只能借一本 ， 則可有多少種不同的借法 ？ ? 問題分析與算法設(shè)計(jì) 這是一個(gè) 排列 問題 ， 即求從 ５ 中取 ３ 的排列數(shù) 。 對(duì) 5本書從 1至 5編號(hào) ， 假設(shè)三個(gè)人分別借這 5本書中的 1本 。 當(dāng) a=i 時(shí) ， 表示 a借了編號(hào)為 i的書 。 當(dāng) 3個(gè)人所借的書的編號(hào)都不相同時(shí) ， 就是滿足題意的一種借閱方法 。 假設(shè)： 三個(gè)人為 a、 b、 c， 則它們的取值范圍為： 1 = a、 b、 c = 5 且 當(dāng)： a!=b a!=c b!=c 時(shí)，即為 1 種借書的方法。 第 26 頁 典型數(shù)值問題 百例 8：借書方案知多少 ? ? 程序說明與注釋 void main( ) {int a, b, c, count=0。 for ( a=1。 a=5。 a++ ) for ( b=1。 b=5。 b++ ) for ( c=1。 a!=b c=5。 c++) /* 當(dāng)前兩個(gè)人借不同的書時(shí)， 窮舉第三個(gè)人的借本情況 */ if ( c!=a c!=b ) printf( count%8 ? %2d:%d,%d,%d : %2d:%d,%d,%d\n, ++count, a, b, c )。 }/* 60種 */ 例 C100_8 第 27 頁 趣味程序 —百例 40：三色球問題 ? 問題 若一個(gè)口袋中放有 12 個(gè)球 ， 其中有 3 個(gè) 紅 的 ， 3 個(gè) 白 的和 6 個(gè) 黑 的 ， 問從中任取 8 個(gè)共有多少種不同的顏色搭配 ？ ? 問題分析與算法設(shè)計(jì) 設(shè)：任取的紅球個(gè)數(shù)為 i， 白 球個(gè)數(shù)為 j， 則黑球個(gè)數(shù)為： 8 i j 據(jù)題意紅球 i和白球 j個(gè)數(shù)的取值范圍是 0～ 3， 在紅球和白球個(gè)數(shù)確定的條件下 ， 黑球個(gè)數(shù)取值應(yīng)為 8ij=6。 第 28 頁 趣味程序 —百例 40：三色球問題 ? 程序說明與注釋 void main( ) { int i, j, count=0。 printf( RED BALL WHITE BALL BLACK BALL\n)。 printf(\n)。 for (i=0。 i=3。 i++) /* 任取紅球的個(gè)數(shù) 0~3 */ for (j=0。 j=3。 j++) /* 任取白球的個(gè)數(shù) 0~3 */ if ( (8ij)=6 ) printf(%2d:%d %d %d\n,++count,i, j, 8ij)。 } 例 C100_40 第 29 頁 趣味程序 —百例 48：新娘和新郎 ? 問題 三對(duì)情侶參加婚禮 ， 三個(gè)新郎為Ａ 、 Ｂ 、 Ｃ ， 三個(gè)新娘為Ｘ 、 Ｙ 、 Ｚ 。 有人不知道誰和誰結(jié)婚 ， 于是詢問了六位新人中的三位 ， 但聽到的回答是這樣的：Ａ說他將和Ｘ結(jié)婚 ； Ｘ說她的未婚夫是Ｃ ； Ｃ說他將和Ｚ結(jié)婚 。 這人聽后知道他們?cè)陂_玩笑 ， 全是假話 。 請(qǐng)編程找出誰將和誰結(jié)婚 。 ? 問題分析與算法設(shè)計(jì) 設(shè)： a、 b、 c三人用 3表示 ， 將 x和 a結(jié)婚表示為 x＝ 1， 將 y不與 a結(jié)婚表示為 y!=1。 則： x!=1 Ａ不與Ｘ結(jié)婚 x!=3 Ｘ的未婚夫不是Ｃ z!=3 Ｃ不與Ｚ結(jié)婚 題意還隱含： x!=y 且 x!=z 且 y!=z 第 30 頁 趣味程序 —百例 48：新娘和新郎 ? 程序與說明 void 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)。 } } 例 C100_48 第 31 頁 典型數(shù)值問題 窮舉法的關(guān)鍵 ? 數(shù)學(xué)模型 ◆ 適宜進(jìn)行窮舉的數(shù)學(xué)模型 ◆ 決定程序是否正確 ? 窮舉的范圍 ◆ 明確的窮舉終止條件 ◆ 決定窮舉的效率，范圍過大，則效率太低。 第 32 頁 典型非數(shù)值 (圖型 )問題 例 1 ? 例 1： 在一行中輸出 m 個(gè) * 號(hào) 。 要求：從鍵盤輸入 m值，輸出 一 行 m 個(gè) *號(hào)。 例：輸入 m=4， 輸出的圖形如下： * * * * ? 基本語句： 輸出一個(gè) * 號(hào)： ptintf(”*”)。 或 putchar(’*’)。 ? 基本算法： m m 個(gè) *； \n scanf (”%d”, m)。 while (m0) { printf (”*”)。 m。 } printf (”\n”)。 第 33 頁 典型非數(shù)值 (圖型 )問題 例 1 include int main ( ) { int m。 scanf (”%d”, m)。 while ( m0 ) { printf (”*”)。 m。 } printf (”\n”)。 return 0。 } include void main ( ) { int m。 scanf (”%d”, m)。 for ( 。 m0。 m ) { printf (”*”)。 } printf (”\n”)。 return 0。 } C語言中的 一行 都是以 \n 為標(biāo)志 第 34 頁 典型非數(shù)值 (圖型 )問題 例 2 ? 例 2： 輸出邊長(zhǎng)為 m 的正方型 要求：從鍵盤輸入 m 值，輸出 m 行每行 m 個(gè) *號(hào)。 例：輸入 m=4， 輸出的圖形如下： * * * * * * * * * * * * * * * * ? 算法分析與設(shè)計(jì)： 1. 輸入 m ， 2. 重復(fù)輸出 m 行，每行 輸出 m 個(gè) *； 細(xì)化 1： 1. 輸入 m ； 2. for ( k=1。 k=m。 k++ ) 輸出 一行中的 m 個(gè) * ； 第 35 頁 典型非數(shù)值 (圖型 )問題 例 2 細(xì)化 2： 1. 輸入 m； 2. for ( k=1。 k=m。 k++ ) { 輸出 m 個(gè) * ； 換新行 。 } 細(xì)化 3： 1. 輸入 m； 2. for ( k=1。 k=m。 k++ ) { for ( j=1。 j=m。 j++ )