大学计算机 第7章：算法与 数据结构基础 7.2.1 穷举法 穷举法又称列举法、枚举法，是蛮力策略的具体体现，是一种简单而直 接地解决问题的方法 其基本思想是逐一列举问题所涉及的所有情形，并根据问题提出的条件 检验哪些是问题的解，哪些应予排除 穷举法常用于解决“是否存在”或“有多少种可能”等问题 穷举算法特点是算法简单，但运行时所花费的时间量大 例如：有一把锁和一串钥匙（共有10把钥匙），怎样找出所有开这把 锁的钥匙？ 在上，OicqPassOver这个工具穷举用户的口令，它根据机器性能 最高可以每秒测试20000个口令，如果口令简单，一分钟内，密码就 会遭到破译 7.2.1 穷举法 1、百钱百鸡问题 中国古代算书张丘建的算经中有一道著名的百鸡问题：公鸡每只值5 文钱，母鸡每只值3 文钱，而3 只小鸡值1 文钱现在用100 文钱买100 只鸡，问：这100 只鸡中，公鸡、母鸡和小鸡各有多少只？ 解法如下：设公鸡、母鸡、小鸡分别为x、y、z 只，由题意得： 用穷举法求解，对每组求得满足等式方程组的值，从而找到百钱百鸡的 解 7.2.1 穷举法 2、逻辑推断 有四位学生中的一位做了好事，不留名，表扬信来了之后，校长问这四 位是谁做的好事。
A说：不是我 B说：是C C说：是D D说：他胡说 已知三个人说的是真话，一个人说的是假话现在要根据这些信息，找 出做了好事的人 现在并不知道是谁做得好事，但知道做好事的人是A,B,C,D四个人中的某 一个因此，可以一个一个地试探这也是通过穷举法来解决问题 7.2.1 穷举法 3、韩信点兵 秦朝末年，楚汉相争一次，韩信将1500名将士与楚王大将李锋交战 他命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3 名；他又命令士兵7人一排，结果又多出2名韩信马上向将士们宣 布:“我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一 定能打败敌人汉军本来就信服自己的统帅，这一来更相信韩信是 “神仙下凡”、“神机妙算”于是士气大振一时间旌旗摇动，鼓声 喧天，汉军步步进逼，楚军乱作一团交战不久，楚军大败而逃 “韩信点兵”它形成了一类问题，这个问题计算机解决起来也是用的穷 举法，用从1开始逐个自然数的试着寻找满足上述题意要求的值，直到找 到这个数x为止 7.2.1 穷举法 用穷举算法解决问题，通常可以从两个方面进行分析： 1、问题所涉及的情况：问题所涉及的情况有哪些，情况的种数可不 可以确定。
把它描述出来 2、答案需要满足的条件：分析出来的这些情况，需要满足什么条件， 才成为问题的答案，把这些条件描述出来 穷举法穷举的数据量过大，效率较低，对于小规模的问题还是适用的 但是问题规模一旦扩大，穷举法就没有什么可取性了 一般巧妙和高效算法很少来自穷举法 7.2.2 回溯法 迷宫游戏 7.2.2 回溯法 回溯算法也叫试探法，是一种选优搜索法，按选优条件向前搜索，以达 到目标但当探索到某一步时，发现原先选择并不优或达不到目标，就 退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回 溯条件的某个状态的点称为“回溯点” 回溯法的指导思想：走不通，就掉头 回溯法在搜索过程中通过对约束条件的判定，排除错误答案，提高了搜 索效率 7.2.2 回溯法 1、 八皇后问题 八皇后问题是一个古老而著名的问题，是回溯 算法的典型例题 十九世纪著名的数学家高斯1850年提出：在 8X8格的国际象棋上摆放八个皇后，使其不能互 相攻击，即任意两个皇后都不能处于同一行、 同一列或同一斜线上，问有多少种摆法 7.2.2 回溯法 回溯法解八皇后问题思路：逐行摆放皇后 初始第1行皇后放第1列；摆放第i行皇后时，从第1列开始，逐列判定 是否与前i-1行皇后攻击，直到找到一个不攻击的位置，继续第i+1行 的摆放； 若第i行无摆放位置，则拿掉该行皇后，回溯至第i-1行，第i-1行皇后 从当前位置的下一列开始判定，继续搜索。
当第1行皇后的摆放位置超出棋盘时，全部求解过程结束，可找到92 种摆法 7.2.2 回溯法 网络爬虫是一个功能强大的自动提取网页的程 序，它为搜索引擎从万维网下载网页，是搜索 引擎的重要组成部分它可以完全不依赖用户 干预实现网络上的自动“爬行”和搜索 网络爬虫是通过网页的链接地址来寻找网页在 抓取网页的时候，网络爬虫采用了深度优先策 略 深度优先是指网络爬虫会从起始页开始，一 个链接一个链接跟踪下去，处理完这条线路 之后再转入下一个起始页，继续跟踪链接 这个方法有个优点是网络爬虫在设计的时候 比较容易这是一种典型的回溯算法 7.2.2 回溯法 回溯法的本质也是一种穷举法，但与穷举法相比，回溯法的“聪明”之 处在于能适时“回头”，若再往前走不可能得到解，就回溯，退一步另 找线路，这样可省去大量的无效操作 因此，回溯与穷举相比，回溯更适宜于量比较大，候选解比较多的问题 7.2.3 递归法 人们都熟悉一个民间故事：从前有一座山，山上有一座庙，庙里有一个 老和尚正在给小和尚讲故事，故事里说，从前有一座山，山上有一座庙， 庙里有一个老和尚正在给小和尚讲故事，故事里说 所谓递归就是一个函数或过程可以直接或间接地调用自己。
7.2.3 递归法 递归分为直接递归和间接递归两种方法 如果一个算法直接调用自己，称为直接递归调用； 如果一个算法A调用另一个算法B，而算法B又调用算法A，则此种递 归称为间接递归调用 7.2.3 递归法 1.n！问题 阶乘可以这样递归地定义成函数： 这样，所有自然数的阶乘就可以通过上面的两句话表示了2的阶乘就是 12；3的阶乘就是2的阶乘乘3，即123不仅如此，人们还可以知 道0的阶乘是多少，1的阶乘应该等于0的阶乘乘以1，显然0的阶乘必须 是1才行 7.2.3 递归法 1.n！问题 每个递归函数必须至少有一个基线条件 一般情况必须最终能简化为基线条件 7.2.3 递归法 2、汉诺塔（Hanoi）问题 相传印度有座大寺庙，它曾被认为是宇宙的中心神庙中放置了一块上 面插有三根长木钉的木板，在其中的一根木钉上，由上至下放了64片直 径由小至大的圆环形金属片古印度教的天神指示他的僧侣们将64片金 属片全部移至另一根木钉上移动规则只有两个： （1）在每次的移动中，只能移动一片金属片； （2）过程中任意时刻必须保证金属片小的在上，大的在下 7.2.3 递归法 使用递归时必须符合以下三个条件： （1）可将一个问题转化为一个新的问题，而新问题的解决方法仍与 原问题的解法相同，只不过所处理的对象有所不同而已，即它们只是 有规律的递增或递减。
（2）可以通过转化过程使问题回到对原问题的求解 （3）必须要有一个明确的结束递归的条件，否则递归会无止境地进 行下去 递归对某些问题而言存在重复调用，导致算法效率不高 7.2.4 分治法 分治法的设计思想是将一个难以直接解决的大问题，分割成一些规模较 小的相同问题，以便各个击破，分而治之 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子 结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公 共的子问题 7.2.4 分治法 1、找出伪币 一个装有1 6枚硬币的袋子，1 6枚硬币中有一个是伪造的，并且那个伪 造的硬币比真的硬币要轻一些你的任务是找出这枚伪造的硬币 为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器， 比如天平利用这台仪器，可以知道两组硬币的重量是否相同 7.2.4 分治法 1、找出伪币 方法1： 任意取1枚硬币，与其他硬币进行比较，若发现轻者，这那枚为伪币最 多可能有15次比较 7.2.4 分治法 1、找出伪币 方法2： 将硬币分为8组，每组2个，每组比较一次，若发现轻的，则为伪币。
最 多可能有8次比较 7.2.4 分治法 1、找出伪币 方法3： 7.2.4 分治法 上述三种方法,分别需要比较18次,8次,4次,那么形成比较次数差异的根据 原因在哪里? 方法1:每枚硬币都至少进行了一次比较,而有一枚硬币进行了15次比较 方法2:每一枚硬币只进行了一次比较 方法3:将硬币分为两组后一次比较可以将硬币的范围缩小到了原来的一半, 这样充分地利用了只有1枚伪币的基本性质 7.2.4 分治法 根据以上比较，第三种方法就是分治法，可以得到以下的采用分治方法 的结论： 1、参与比较的硬币数量越多，使用该方法来实现就越快，而且投机性大 大减少； 2、解决方法关键在于能将大问题分割成若干小问题； 3、小问题与原有问题是完全类似的 7.2.4 分治法 2、二分法 二分查找又称为折半查找，是一种可在有序顺序表上实现的效率比较高 的查找算法 是一个典型的分治算法 7.2.4 分治法 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子 结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公 共的子问题。
7.2.5 贪心法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看 来是最好的选择也就是说，不从整体最优上加以考虑，所做出的仅是 在某种意义上的局部最优解 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许 多问题它能产生整体最优解或者是整体最优解的近似解 只顾眼前利益，每次都选最好的 7.2.5 贪心法 1、商场找零 假设只有3种面额的币值，它们的面值分别为20元、10元、5元、和1元 现要找给某顾客37元，这时，售货员几乎不假思索地拿出1个20元、1个 l0元、1个5元和2个1元的钱币交给顾客人们不仅能很快决定要拿哪些 钱币，而且与其它找法相比这时拿出的钱币的个数肯定是最少的 在这里，收货员实际使用了这样的算法：首先选出一个面值不超过37元 的最大面额钱币（20元），然后从37元中减去20元，剩下17元中再选出 一个不超过17元的最大面额钱币（10元），如此做下去，直到找足37元 这就是所谓的贪心法 7.2.5 贪心法 2、最短路径 顶点为城市，边上的代价为两城市问的里程在图中找一条经过所有结 点一次的回路，并使里程的总和为最小 可以按这样一个想法去做： 首先在图中选一条代价最小的边。
为了选择下一条边，先要检查一下候 选边与已选入的边之间是否满足以下两点： 1)不会有三条边(候选边及已入选边)与同一顶点相关联 2)不会使入选边形成回路，除非入选边的个数已等于图中的顶点总数 在满足以上两点的候选边中，挑选最短的边作为入选边 如此做下去，直到得到一个经过所有顶点的回路最后求得的回路是1 25341，代价是14图中最小代价的回路是12543一 1，代价是10这也是典型的贪心策略 7.2.5 贪心法 2、最短路径 可以按这样一个想法去做： 首先在图中选一条代价最小的边为了选择下一条边， 先要检查一下候选边与已选入的边之间是否满足以下两 点： 1)不会有三条边(候选边及已入选边)与同一顶点相 关联 2)不会使入选边形成回路，除非入选边的个数已等 于图中的顶点总数 在满足以上两点的候选边中，挑选最短的边作为入选边 如此做下去，直到得到一个经过所有顶点的回路最后 求得的回路是125341，代价是14图中最 小代价的回路是12543一1，代价是10这也 是典型的贪心策略 7.2.5 贪心法 贪心法主要有以下两个特点： （1）贪心选择性质：算法中每一步选择都是当前看似最佳的选择，这种选 择依赖于已做出的选择，但不依赖于未作出的选择。