C语言穷举法经典例题ppt课件.ppt

枚举法 穷举法 笨人之法 把所有可能的情况一一测试 筛选出符合条件的各种结果进行输出 分析 这是个不定方程 三元一次方程组问题 三个变量 两个方程 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次运算 课堂讨论 谁做的好事 有四位同学中的一位做了好事 不留名 表扬信来了之后 校长问这四位是谁做的好事 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 利用穷举法求解趣味智力题 韩信点兵 韩信有一队兵 他想知道有多少人 便让士兵排队报数 按从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 穷举法求解韩信点兵