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次运算 课堂讨论 谁做的好事 有四位同学中的一位做了好事 不留名 表扬信来了之后 校长问这四位是谁做的好事 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 穷举法求解韩信点兵 方案3 标志变量 includevoidmain intx intfind 0 设置找到标志为假 for x 1 find x if x 5 1 练习题1 试编程求出100000 200000之间间隔最大的两个素数并输出 同时输出最大间隔 2 试编程求出八位数中所有的水仙花数 三位水仙花为abc a 3 b 3 c 3 八位数水仙花为该数字等于所有位数的八次方之和 3 年龄几何 张三 李四 王五 刘六的年龄成一等差数列 他们四人的年龄相加是26 相乘是880 求以他们的年龄为前4项的等差数列的前20项 4 委派任务 某侦察队接到一项紧急任务 要求在A B C D E F六个队员中尽可能多地挑若干人 但有以下限制条件 A和B两人中至少去一人 A和D不能一起去 A E和F三人中要派两人去 B和C都去或都不去 C和D两人中去一个 若D不去 则E也不去 问应当让哪几个人去 5 在下面的加法算式中 不同的符号代表不同的数字 相同的符号代表相同的数字 请设计程序求出 都 要 学 C 4个符号分别代表的数字 提示 让计算机解奥数题 穷举 都 要 学 C 4个符号分别代表的数字 从0到9 然后进行组合 如果组合起来符合规则 不同的符号代表不同的数字