c语言枚举法 穷举法 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次运算 利用穷举法求解趣味智力题 韩信点兵 韩信有一队兵 他想知道有多少人 便让士兵排队报数 按从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 thism