《算法设计与分析》蛮力法.ppt

算法分析与设计 1 蛮力法 算法分析与设计 2 蛮力法BruteForce 蛮力法 枚举法 穷举法 暴力法 要求设计者找出所有可能的方法 然后选择其中的一种方法 若该方法不可行则试探下一种可能的方法 蛮力法是一种直接解决问题的方法 常常直接基于问题的描述和所设计的概念定义 力 指计算机的能力 而不是人的智力 蛮力法常常是最容易应用的方法 求an n为非负整数 用连续整数检测算法计算GCD m n 算法分析与设计 3 蛮力法BruteForce 蛮力法不是一个最好的算法 巧妙和高效的算法很少出自蛮力 但当我们想不出更好的办法时 它也是一种有效的解决问题的方法 它可能是惟一一种几乎什么问题都能解决的一般性方法 常用于一些非常基本 但又十分重要的算法 比如计算n个数字的和 求一个列表的最大元素等等 算法分析与设计 4 蛮力法的优点 逻辑清晰 编写程序简洁对于一些重要的问题 比如 排序 查找 矩阵乘法和字符串匹配 可以产生一些合理的算法解决问题的实例很少时 可以花费较少的代价可以解决一些小规模的问题 使用优化的算法没有必要 而且某些优化算法本身较复杂 可以作为其他高效算法的衡量标准 算法分析与设计 5 使用蛮力法的几种情况 搜索所有的解空间搜索所有的路径直接计算模拟和仿真 算法分析与设计 6 比较熟悉的蛮力法应用 选择排序和起泡排序选择排序 每趟排序在当前待排序序列中选出关键码最小的记录 添加到有序序列中 起泡排序 两两比较相邻记录关键码 如果反序则交换 直到没有反序的记录为止 顺序查找和蛮力字符串匹配顺序查找 从线性表的一端向另一端逐个将关键码与给定值进行比较 若相等 则查找成功 给出该记录在表中的位置 若整个表检测完仍未找到与给定值相等的关键码 则查找失败 给出失败信息 蛮力字符串匹配 即朴素模式串匹配 算法分析与设计 7 根据问题中的条件将可能的情况一一列举出来 逐一尝试从中找出满足问题条件的解 但有时一一列举出的情况数目很大 如果超过了我们所能忍受的范围 则需要进一步考虑 排除一些明显不合理的情况 尽可能减少问题可能解的列举数目 用蛮力法解决问题 通常可以从两个方面进行算法设计 1 找出枚举范围 分析问题所涉及的各种情况 2 找出约束条件 分析问题的解需要满足的条件 并用逻辑表达式表示 蛮力法解题步骤 例1 百钱百鸡问题 中国古代数学家张丘建在他的 算经 中提出了著名的 百钱百鸡问题 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 算法设计1 通过对问题的理解 可能会想到列出两个三元一次方程 去解这个不定解方程 就能找出问题的解 这确实是一种办法 但这里我们要用 懒惰 的枚举策略进行算法设计 设x y z分别为公鸡 母鸡 小鸡的数量 尝试范围 由题意给定共100钱要买百鸡 若全买公鸡最多买100 5 20只 显然x的取值范围1 20之间 同理 y的取值范围在1 33之间 z的取值范围在1 100之间 约束条件 x y z 100且5 x 3 y z 3 100 算法分析与设计 9 算法1如下 main intx y z for x 1 x 20 x x 1 for y 1 y 34 y y 1 for z 1 z 100 z z 1 if 100 x y z 枚举尝试20 34 100 68000次 算法分析与设计 10 算法设计2 在公鸡 x 母鸡 y 的数量确定后 小鸡的数量z就固定为100 x y 无需再进行枚举了此时约束条件只有一个 5 x 3 y z 3 100算法2如下 算法分析与设计 11 main intx y z for x 1 x 20 x x 1 for y 1 y 33 y y 1 z 100 x y if z 3 0 枚举尝试20 33 660次 Z能被3整除时 才会判断 5 x 3 y z 3 100 算法分析与设计 12 例2 求所有的三位数 它除以11所得的余数等于它的三个数字的平方和 解题思路 三位数只有900个 可用枚举法解决 枚举时可先估计有关量的范围 以缩小讨论范围 减少计算量 解 设这个三位数的百位 十位 个位的数字分别为x y z 由于任何数除以11所得余数都不大于10 所以x2 y2 z2 10 从而1 x 3 0 y 3 0 z 3 所求三位数必在以下数中 100 101 102 103 110 111 112 120 121 122 130 200 201 202 211 212 220 221 300 301 310 不难验证只有100 101两个数符合要求 例3狱吏问题某国王对囚犯进行大赦 让一狱吏n次通过一排锁着的n间牢房 每通过一次 按所定规则转动n间牢房中的某些门锁 每转动一次 原来锁着的被打开 原来打开的被锁上 通过n次后 门锁开着的 牢房中的犯人放出 否则犯人不得获释 转动门锁的规则是这样的 第一次通过牢房 要转动每一把门锁 即把全部锁打开 第二次通过牢房时 从第二间开始转动 每隔一间转动一次 第k次通过牢房 从第k间开始转动 每隔k 1间转动一次 问通过n次后 哪些牢房的锁仍然是打开的 算法分析与设计 15 算法设计1 1 一维数组a n 记录n个锁的状态1 被锁上0 被打开2 对i号锁的一次开关锁可以转化为算术运算 a i 1 a i 3 第一次转动的是1 2 3 n号牢房 第二次转动的是2 4 6 号牢房 第i次转动的是i 2i 3i 4i 号牢房 是起点为i 公差为i的等差数列 4 不做其它的优化 用蛮力法通过循环模拟狱吏的开关锁过程 最后当第i号牢房对应的数组元素a i 为0时 该牢房的囚犯得到大赦 算法分析与设计 16 算法1如下 input n 输入na newint n 1 for i 1 i n i a i 1 for i 1 i n i for j i j n j j i a i 1 a i for i 1 i n i if a i 0 print i isfree 算法分析 以一次开关锁计算 算法的时间复杂度为n 1 1 2 1 3 1 n O nlogn 问题分析 转动门锁的规则可以有另一种理解 第一次转动的是编号为1的倍数的牢房 第二次转动的是编号为2的倍数的牢房 第三次转动的是编号为3的倍数的牢房 则狱吏问题是一个关于因子个数的问题 令d n 为自然数n的因子个数 这里不计重复的因子 如4的因子为1 2 4共三个因子 而非1 2 2 4 则d n 有的为奇数 有的为偶数 见下表 表1编号与因数个数的关系 算法分析与设计 18 数学模型1 上表中的d n 有的为奇数 有的为偶数 由于牢房的门开始是关着的 这样编号为i的牢房 所含1 i之间的不重复因子个数为奇数时 牢房最后是打开的 反之 牢房最后是关闭的 算法分析与设计 19 算法设计2 1 算法应该是求出每个牢房编号的不重复的因子个数 当它为奇数时 这里边的囚犯得到大赦 2 一个数的因子是没有规律的 只能从1 n枚举尝试 算法2如下 input n for i 1 i n i s 1 for j 2 j i j j if i j 0 s s 1 if s 2 1 print i isfree 算法分析与设计 20 算法分析 算法1中狱吏开关锁的主要操作是a i 1 a i 共执行了n 1 1 2 1 3 1 n 次 时间近似为复杂度为O nlogn 使用了n个空间的一维数组 算法2没有使用辅助空间 但由于求一个编号的因子个数也很复杂 其主要操作是判断imodj是否为0 共执行了n 1 2 3 n 次 时间复杂度为O n2 仔细观察表1 算法分析与设计 21 数学模型2 观察表1 发现当且仅当n为完全平方数时 d n 为奇数 这是因为n的因子是成对出现的 也即当n a b且a b时 必有两个因子a b 只有n为完全平方数 也即当n a2时 才会出现d n 为奇数的情形 算法设计3 这时只需要找出小于n的平方数即可 算法分析与设计 22 算法3如下 input n for i 1 i n i if i i n print i isfree elsebreak 注意 在对运行效率要求较高的大规模的数据处理问题时 必须多动脑筋找出效率较高的数学模型及其对应的算法 算法分析与设计 23 例4假金币 N个金币 编号为1 N 中有一枚重量不同的假金币 真金币重量相同 利用唯一的一台天平将金币分组称量可以找出假金币 输入 第一行输入2个空格隔开的整数N和K N是金币的总数 2 1000 K是称重的次数 1 100 随后2K行记录称量的情况和结果 连续2行记录一次称量 第1行首先是Pi 1 N 2 表示两边托盘放置的金币数目 随后是左边托盘中Pi个金币编号和右边托盘中Pi个金币编号 所有数之间都由空格隔开 第2行用和 记录称量结果 算法分析与设计 24 输出输出假金币的编号 如果称量记录无法确定假金币 输出0输入样例 5321234 114 125 输出样例 3 算法分析与设计 25 搜索过程 依次假设i号金币是假的对称量的记录进行比较 如果假设与所有的记录都不矛盾 则有可能是假的如果可能的假金币只有1个 输出他的编号 否则 输出0 算法分析与设计 26 Intjd intj int s charc 函数判断假设j金币是假的与称量结果是否矛盾 s是称量结果 其第一个元素是左托盘中金币的个数 c是称量结果m 2 s 0 for i f 1 i m 算法分析与设计 27 intmain intnum 100 1000 chars 1000 输入内容for i 1 count 0 i1 break 不止一枚假金币no i if count 1 printf 0 elseprintf d no 算法分析与设计 28 例5 用蛮力法解决凸包问题 凸包问题 S是平面上的一个点集 封闭S中所有顶点的最小凸多边形 称为S的凸包 凸包问题就是为一个n个点的集合构造凸包的问题 对于一个n个点集合中的两个点pi和pj 当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时 它们的连线是该集合凸包边界的一部分 例6最近对问题找出一个包含n个点的集合中距离最近的两个点 算法分析与设计 29 1 某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析 A B至少有一人作案 A E F三人中至少有两人参与作案 A D不可能是同案犯 B C或同时作案 或与本