枚舉法 窮舉法 笨人之法 把所有可能的情況一一測試 篩選出符合條件的各種結果進行輸出 分析 這是個不定方程 三元一次方程組問題 三個變量 兩個方程 x y z 1005x 3y z 3 100設公雞為x只 母雞為y只 小雞為z只 百元買百雞問題分析 x y z 1005x 3y z 3 100 三重循環 voidmain intx y z for x 0 x 100 x for y 0 y 100 y for z 0 z 100 z if x y z 100 結果 x 0 y 25 z 75x 4 y 18 z 78x 8 y 11 z 81x 12 y 4 z 84 討論 為什么多了幾組解 百元買百雞問題分析 voidmain intx y z for x 0 x 100 x for y 0 y 100 y for z 0 z 100 z if z 3 0 結果 x 0 y 25 z 75x 4 y 18 z 78x 8 y 11 z 81x 12 y 4 z 84 討論 此為 最笨 之法 要進行101 101 101 1030301次 100多萬次 運算 優化 voidmain intx y z for x 0 x 100 x for y 0 y 100 y z 100 x y if z 3 0 討論 令z 100 x y只進行101 101 10201次運算 前者的1 取x 20 y 33只進行21 34 714次運算 第1種運算的6 9e 4 繼續優化 voidmain intx y z for x 0 x 14 x for y 0 y 25 y if 7 x 4 y 100 z 100 x y printf cocks d hens d chickens d n x y z 取x 14 y 25只進行15 26 390次運算 利用窮舉法求解趣味智力題 韓信點兵 韓信有一隊兵 他想知道有多少人 便讓士兵排隊報數 按從1至5報數 最末一個士兵報的數為1 按從1至6報數 最末一個士兵報的數為5 按從1至7報數 最末一個士兵報的數為4 最后再按從1至11報數 最末一個士兵報的數為10 你知道韓信至少有多少兵嗎 設兵數為x 則x應滿足 x 5 1 x 6 5 x 7 4 x 11 10窮舉法對x從1開始試驗 includevoidmain intx for x 1 x 5000 x if x 5 1 屬于 瞎貓碰死耗子 的做法 窮舉法求解韓信點兵 includevoidmain intx for x 1 x if x 5 1 死循環 永遠不會退出的循環 窮舉法求解韓信點兵 窮舉法求解韓信點兵 方案1 goto includevoidmain intx for x 1 x if x 5 1 窮舉法求解韓信點兵 方案2 break includevoidmain intx for x 1 x if x 5 1 窮舉法求解韓信點兵 方案3 標志變量 includevoidmain intx intfind 0 設置找到標志為假 for x 1 find x if x 5 1 課堂討論 誰做的好事 有四位同學中的一位做了好事 不留名 表揚信來了之后 校長問這四位是誰做的好事 A說 不是我 B說 是C C說 是D D說 C胡說 已知三個人說的是真話 一個人說的是假話 現在要根據這些信息 找出做了好事的人 編程思路 如何找到該人 一定是 先假設該人是做好事者 然后到每句話中去測試看有幾句是真話 有三句是真話就確定是該人 否則換下一人再試 比如 先假定是A同學 讓thisman A 代入到四句話中A說 thisman A A A 假 值為0 B說 thisman C A C 假 值為0 C說 thisman D A D 假 值為0 D說 thisman D A D 真 值為1 顯然 不是 A 做的好事 四個關系表達式值的和為1 再試B同學 讓thisman B 代入到四句話中A說 thisman A B A 真 值為1 B說 thisman C B C 假 值為0 C說 thisman D B D 假 值為0 D說 thisman D B D 真 值為1 顯然 不是 B 所為 四個關系表達式值的和為2 再試C同學 讓thisman C 代入到四句話中A說 thisman A C A 真 值為1 B說 thisman C C C 真 值為1 C說 thisman D C D 假 值為0 D說 thisman D C D 真 值為1 顯然 就是 C 做了好事 四個關系表達式值之和為3 這時 我們可以理出頭緒 要用枚舉法 一個人一個人地去試 四句話中有三句為真 該人即所求 includevoidmain charthisman intsa sb sc sd cond for thisman A thisman D thisman sa thisman A sb thisman C sc thisman D sd thisman D cond sa sb sc sd if cond 3 printf 做好事的人是 c n thisman
展開閱讀全文
)
)
