穷举法ppt课件.ppt

穷举法 在程序设计中 我们经常需要根据给定的一组条件求满足条件的解 如果问题的解可以用公式 或者按一定的规则 规律求出 那么就可以很容易地写出相应的程序 但是对于许多问题 我们都难以找到明确的公式和计算规则 在这种情况下 我们可以利用计算机高速运算的特点 用穷举法来解 穷举法的基本思想 穷举也叫枚举 它的基本思想是先依据题目的部分条件来确定答案的大致范围 可能解 然后在此范围内用其余的条件对所有可能解进行一一验证 删去那些不符合条件的解 剩下符合条件的解就是整个问题的解 1 例1 找完全数古希腊人认为因子的和等于它本身的数是一个完全数 自身因子除外 例如28的因子是1 2 4 7 14 且1 2 4 7 14 28 则28是一个完全数 编写一个程序求2 10000内的所有完全数 分析 1 本题只需一个枚举变量a即可 它的范围是2 10000 2 验证完全数的条件是 所有因子的和等于该数据本身 3 找出所有因子 并求出因子和是关键的一步 可采用循环完成分解因子和求因子和 2 main inta b s for a 2 a 10000 a s 0 for b 1 b a 2 b if a b 0 s s b if a s printf d a 运行结果 6284968128 枚举a 范围2 10000 分解因子并求出因子和 验证 如果数a满足条件 则输出 3 从上例可知 穷举法是一种比较笨拙的算法 因为它需要列举出许多个可能解来一一验证 程序往往需要运行很长时间 效率较低 但是 穷举法也有自己的优点 它思路简单 容易编写程序 只要时间足够 穷举法能够很容易地求出问题的全部正确解 针对穷举法效率较低的缺点 在设计穷举算法时 我们必须注意以下二点 考虑枚举变量一定要慎重 枚举变量应尽量少 尽量通过计算而不是枚举来确定变量 枚举前应尽可能多地将不符合条件的情况预先排除 以缩小枚举范围 4 例2 除法运算 NOIP1995初中组复赛第一题 设有下列的除法算式 请根据上述算式中的信息求出被除数和除数 分析 设除数为x 被除数为y 由算式信息可知 10 100 因此 我们可选择枚举除数 而被除数则可按公式y 809 x 1计算得出 5 main intx y for x 10 x9999 break if printf d d y x 运行结果 970912 枚举除数x 范围是10 99 计算出被除数y 验证 如果满足要求 则输出 y 1000 8 x 100 6 main intk i j x k 0 for x y j x 10 y if k k 1 printf 4d i if printf n 练习 1 求出所有满足下列条件的二位数 将此二位数的个位数字与十位数字进行交换 可得到一个新的二位数 要求新数与原数之和小于100 程序要求 每行输出6个满足条件的数 算法提要 分解每一个二位数 然后重新组成一个新数 当满足条件时 用计数器来统计个数 i 10 i 99 i i 10 i 10 i j 100 k 6 0 7 例5 方格填数如下图所示的八个格子中填入1至8八个数字 使得相邻的和对角线的数字之差不为1 编程找出所有放法 分析 由题意可知 放入b3 b6这两个格子中的数 必须和六个数不连续 仅可以和一个数是连续的 这样的数只能是1和8 因此 b1 b3 b6 b8这四个格子中数的放法可以先确定下来 2 8 1 7或7 1 8 2 接着 我们只需枚举b2 b4 b5三个变量 范围都是3至6 而b7可通过计算来得到 8 intlink 6 2 1 2 1 4 2 5 4 7 5 8 7 8 intb 9 main b 1 2 b 3 8 b 6 1 b 8 7 try b 1 7 b 2 1 b 6 8 b 8 2 try voidprint printf 4d n b 1 printf 2d 2d 2d n b 2 b 3 b 4 printf 2d 2d 2d n b 5 b 6 b 7 printf 4d n b 8 9 voidtry for b 2 2 b 2 6 b for b 4 3 b 4 6 b if b 2 b 4 for b 5 3 b 5 6 b if b 5 b 2 intchoose inti x x 0 for i 0 i 5 i if abs b link i 0 b link i 1 1 return x return 1 link 6 2 1 2 1 4 2 5 4 7 5 8 7 8 10 练习 2 将n个整数分成k组 k n 要求每组不能为空 显然这k个部分均可得到一个各自的和s1 s2 sk 定义整数P为 P S1 S2 2 S1一S3 2 S1 Sk 2 s2 s3 2 Sk 1 Sk 2问题求解 求出一种分法 使P为最小 若有多种方案仅记一种 程序说明 数组 a 1 a 2 a n 存放原数s 1 s 2 s k 存放每个部分的和b 1 b 2 b n 穷举用临时空间d 1 d 2 d n 存放最佳方案 11 main inti j n k sum a 101 b 100 s 31 scanf d d s i 0 s b i s b i a i j i 1 j k j 12 if cmin sum for i 1 i n i