算法设计习题课

1、1 枚举法枚举法 枚举法适合于解的候选者是有限、可枚举枚举法适合于解的候选者是有限、可枚举 的场合。的场合。 枚举法就是对可能是解的众多候选者按某枚举法就是对可能是解的众多候选者按某 种顺序进行逐一枚举和检验，从中找出符种顺序进行逐一枚举和检验，从中找出符 合要求的候选解作为问题的解。合要求的候选解作为问题的解。 基于枚举法的算法一般都比较直观，容易基于枚举法的算法一般都比较直观，容易 理解。但由于要检查所有的候选解，因此理解。但由于要检查所有的候选解，因此 时间性能较差时间性能较差 2 枚举法实例枚举法实例 用用5050元钱买了三种水果：西瓜、苹果和桔元钱买了三种水果：西瓜、苹果和桔 子。各

2、种水果加起来一共子。各种水果加起来一共100100个。假如，西个。假如，西 瓜瓜5 5元一个，苹果元一个，苹果1 1元一个，桔子元一个，桔子1 1元元3 3个，个， 设计一算法输出每种水果各买了几个。设计一算法输出每种水果各买了几个。 3 约束条件约束条件 三种水果一共三种水果一共100100个；个； 买三种水果一共花了买三种水果一共花了5050元。元。 如果西瓜有如果西瓜有mellonmellon个，苹果有个，苹果有appleapple个，桔个，桔 子有子有orangeorange个，那么：个，那么： mellon + apple + orange 等于等于100 5 * mellon +

3、1 * apple + orange /3等于等于50。 4 直观的枚举直观的枚举 For (mellon = 1, mellon 99; + mellon) For (apple = 1, apple 99; +apple) For (orange = 1; orange 99; orange) If （mellon + apple + orange 等于等于100 并并 且且 5 * mellon + 1 * apple + orange /3等于等于 50） 输出此方案；输出此方案； 列出所有的情况，检查是否满足两个约束条件列出所有的情况，检查是否满足两个约束条件 5 改进的方案改进的方

4、案 int main() int mellon, apple, orange; for (mellon=1; mellon10; +mellon) for ( apple=1; apple 50 - 5 * mellon; +apple) orange = 3*(50-5*mellon-apple); if (mellon+apple+orange = 100) cout mellon: mellon ; cout apple: apple ; cout orange: orange endl; return 0; 按一个约束条件列出所有可行的情况，然后对每个可按一个约束条件列出所有可行的情况

5、，然后对每个可 能解检查它是否满足第二个约束条件。能解检查它是否满足第二个约束条件。 6 执行结果执行结果 Mellon：1 apple：18 orange：81 Mellon：2 apple：11 orange：87 Mellon：3 apple：4 orange：93 7 贪婪法贪婪法 贪婪法适合于分阶段完成的工作。在每贪婪法适合于分阶段完成的工作。在每 一阶段都选择当前最好的答案，而不管一阶段都选择当前最好的答案，而不管 将来如何。将来如何。 DijkstraDijkstra算法，算法，primprim算法和算法和KruskalKruskal算法算法 都是贪婪算法都是贪婪算法 贪婪法不一

6、定能得到最优解，但是一个贪婪法不一定能得到最优解，但是一个 可行的、较好的解。可行的、较好的解。 8 最少背包问题最少背包问题 假设有许多盒子，每个盒子能保存的总重量为假设有许多盒子，每个盒子能保存的总重量为 1.01.0。有。有N N个项个项i i1 1,i,i2 2, ,i,iN N，它们的重量分别是，它们的重量分别是 w w1 1,w,w2 2, ,w,wN N。目的是用尽可能少的盒子放入所。目的是用尽可能少的盒子放入所 有的项，任何盒子的重量不能超过他的容量。有的项，任何盒子的重量不能超过他的容量。 例如，如果项的重量为例如，如果项的重量为0.4, 0.4, 0.60.4, 0.4,

7、0.6和和0.60.6， 最佳的方案是用两个盒子。最佳的方案是用两个盒子。 但要得到最佳方案，必须尝试所有种组合情况。但要得到最佳方案，必须尝试所有种组合情况。 当当n n很大时，这是不可能的。很大时，这是不可能的。 一种解决方案使用贪婪法一种解决方案使用贪婪法 9 解决策略解决策略 按给定的次序扫描每一个项，把每一个按给定的次序扫描每一个项，把每一个 项放入能够容纳他而不至于溢出的最满项放入能够容纳他而不至于溢出的最满 的盒子。的盒子。 如果项的重量为如果项的重量为0.4, 0.4, 0.60.4, 0.4, 0.6和和0.60.6， 贪婪法的方案是用三个盒子。其装载的贪婪法的方案是用三个盒

8、子。其装载的 重量分别为重量分别为0.8,0.6,0.60.8,0.6,0.6 10 分治法分治法 分而治之法的思想分而治之法的思想 分：递归解决若干个较小的问题分：递归解决若干个较小的问题 治：从子问题的答案中形成原始问题的解治：从子问题的答案中形成原始问题的解 分治法的的算法至少有两个递归调用分治法的的算法至少有两个递归调用 已见过的分治法算法：快速排序，树的已见过的分治法算法：快速排序，树的 遍历遍历 11 最近点问题最近点问题 在二维平面上有在二维平面上有N N个点，试找出距离最短的个点，试找出距离最短的 两个点。两个点。 蛮力算法：计算两两之间的距离，从中找蛮力算法：计算两两之间的距

9、离，从中找 出最小的一个。出最小的一个。N N个点有个点有N N（N-1N-1）/2/2对距离，对距离， 因此时间复杂度为因此时间复杂度为O(NO(N2 2) ) 12 分治法解法分治法解法 将所有的点按将所有的点按x x值排序。取一个合适的值排序。取一个合适的x x值，值， 把所有点分成两半把所有点分成两半P PL L和和P PR R。距离最近的两个。距离最近的两个 点可能出现在点可能出现在P PL L中中(d(dL L) )，也可能出现在，也可能出现在P PR R(d(dR R) ) 中，也可能一个点在中，也可能一个点在P PL L，一个点在，一个点在P PR R(d(dC C) ) d

10、dL L和和d dR R可用递归得到可用递归得到 d dC C的计算：的计算： 设设=min(=min(d dL L,d,dR R) ) 如果如果d dC C比比大，则没必要计算。因此用于计算大，则没必要计算。因此用于计算 d dC C的点必须落在分界线的点必须落在分界线 的范围内，计算此的范围内，计算此 范围中点对的距离中的最小值范围中点对的距离中的最小值 13 dL dR dC 14 优化优化 在最坏的情况下，所有的点都落在分界线在最坏的情况下，所有的点都落在分界线 以内。但此时不一定要计算所有点对的以内。但此时不一定要计算所有点对的 距离。只要两点的距离。只要两点的y y坐标大于坐标大于

11、，这两点之，这两点之 间的距离也不用算了。间的距离也不用算了。 假设该区间中的点按假设该区间中的点按y y坐标排序，则可得下坐标排序，则可得下 列算法列算法 15 for( i= 0; i= ) break; else if( dist(pj, pj+1) ) = dist(pj, pj+1); 16 数学计算问题数学计算问题 设设X X和和Y Y是两个是两个N N位的整数，假如一位乘法花位的整数，假如一位乘法花 费一个单位时间，那么计算费一个单位时间，那么计算 X X* *Y Y 的时间复的时间复 杂性为杂性为O(NO(N2 2) ) 分治法计算分治法计算 将将X X和和Y Y均分成两半，分

12、别称为均分成两半，分别称为X XL L，X XR R，Y YL L，Y YR R。 则则 X = XX = XL L1010N/2 N/2+X +XR R， Y = YY = YL L1010N/2 N/2+Y +YR R。那么，。那么， XY=XXY=XL LY YL L1010N N+(X+(XL LY YR R+X+XR RY YL L) 10) 10N/2 N/2+X +XR RY YR R 时间复杂度：时间复杂度：T(N) = 4T(N/2) + O(N) =O(NT(N) = 4T(N/2) + O(N) =O(N2 2) ) 17 进一步改进进一步改进 上述算法的问题是需要太多次

13、（上述算法的问题是需要太多次（4 4次）的递归调用。如果次）的递归调用。如果 能减少递归调用，则能提高时间性能能减少递归调用，则能提高时间性能 注意：注意：X XL LY YR R+X+XR RY YL L = (X = (XL L X XR R)(Y)(YR R Y YL L) + X) + XL LY YL L + X + XR RY YR R 代入前式，代入前式，XY=XXY=XL LY YL L1010N N+(X+(XL LY YR R+X+XR RY YL L) 10) 10N/2 N/2+X +XR RY YR R= = X XL LY YL L1010N N+(X+(XL L

14、X XR R)(Y)(YR R Y YL L) + X) + XL LY YL L + X + XR RY YR R ) ) 1010N/2 N/2+X +XR RY YR R 可见只需可见只需3 3次递归调用次递归调用 时间复杂性：时间复杂性： )()()()2/(3)( 59. 13log2 NONONONTNT 18 动态规划动态规划 用表代替递归用表代替递归 例：斐波那契函数例：斐波那契函数f(nf(n)=f(n-1)+f(n-2)=f(n-1)+f(n-2)。 计算计算f(nf(n) )需要计算需要计算f(n-1)f(n-1)和和f(n-2)f(n-2)。当计。当计 算算f(n-1)

15、f(n-1)时要计算时要计算f(n-2)f(n-2)和和f(n-3)f(n-3)。因此。因此 在计算在计算f(nf(n) )中中f(n-2)f(n-2)被计算了两次。被计算了两次。 为了减少重复的递归调用，我们可以反过为了减少重复的递归调用，我们可以反过 来计算。先计算来计算。先计算f(2)f(2)，有了，有了f(2)f(2)再计算再计算 f(3)f(3)，以此类推，计算到，以此类推，计算到f(nf(n) )。在此过程。在此过程 中不需要任何递归中不需要任何递归 19 动态规划动态规划 硬币找零问题硬币找零问题 最优二叉查找树最优二叉查找树 20 找零问题找零问题 对于一种货币，有面值为对于一

16、种货币，有面值为C1, C2, C1, C2, , , CN(CN(分分) )的硬币，最少需要多少个硬币来找的硬币，最少需要多少个硬币来找 出出K K分钱的零钱。分钱的零钱。 21 贪婪法解法贪婪法解法 我们不断使用可能的最大面值的硬币我们不断使用可能的最大面值的硬币 如：美元的硬币有如：美元的硬币有1 1、5 5、1010和和2525分的面值分的面值( (忽略流忽略流 通频率很低的通频率很低的5050分硬币分硬币) )。我们可以通过使用。我们可以通过使用2 2个个 2525分、一个分、一个1010分的硬币以及三个分的硬币以及三个1 1分来找出分来找出6363分钱，分钱， 一共是一共是6 6个

17、硬币。个硬币。 如果美元中包含一个如果美元中包含一个2121分硬币时，贪心算法仍然分硬币时，贪心算法仍然 给出一个用六个硬币的解，但是最佳的解是用三给出一个用六个硬币的解，但是最佳的解是用三 个硬币个硬币( (三个都是三个都是2121分的硬币。分的硬币。) ) 22 解法解法1分治法分治法 如果我们可以用一个硬币找零，这就是如果我们可以用一个硬币找零，这就是 最小的。最小的。 否则，对于每个可能的值否则，对于每个可能的值i i，我们可以独，我们可以独 立计算找立计算找i i分钱零钱和分钱零钱和K-iK-i分钱需要的最分钱需要的最 小硬币数。然后选择这个和最小的小硬币数。然后选择这个和最小的i

18、i。 23 怎样找出怎样找出63分钱零钱分钱零钱 找出找出1 1分钱零钱和分钱零钱和6262分钱零钱分别需要的硬币数是分钱零钱分别需要的硬币数是 1 1和和4 4。因此，。因此，6363分钱需要使用五个硬币。分钱需要使用五个硬币。 找出找出2 2分钱和分钱和6161分钱分别需要分钱分别需要2 2和和4 4个硬币，一共是个硬币，一共是 六个硬币。六个硬币。 我们继续尝试所有的可能性。我们看到一个我们继续尝试所有的可能性。我们看到一个2121分分 和和4242分的分解，它可以分别用一个和两个硬币来分的分解，它可以分别用一个和两个硬币来 找开，因此，这个找零问题就可以用三个硬币解找开，因此，这个找零

19、问题就可以用三个硬币解 决。决。 我们需要尝试的最后一种分解是我们需要尝试的最后一种分解是3131分和分和3232分。我分。我 们可以用两个硬币找出们可以用两个硬币找出3131分零钱，用三个硬币找分零钱，用三个硬币找 出出3232分零钱，一共是五个硬币。分零钱，一共是五个硬币。 因此最小值是三个硬币。因此最小值是三个硬币。 24 int coin(int k) int i, tmp, int coinNum = k; if （能用一个硬币找零）（能用一个硬币找零） return 1; for (i=1; i coinNum) coinNum = tmp; return coinNum; 25

20、上述解法分析上述解法分析 此算法的效率很低此算法的效率很低 事实上事实上6363分钱找零的问题是不会在一个合分钱找零的问题是不会在一个合 理的时间内解决的。就如理的时间内解决的。就如FinbonacciFinbonacci 函数函数 一样一样 26 解法解法2 通过指定其中的一个硬币来递归地简化问题。通过指定其中的一个硬币来递归地简化问题。 例如，对于例如，对于6363分钱，我们可以给出以下找零的办法。分钱，我们可以给出以下找零的办法。 一个一个1 1分的硬币加上递归地分派分的硬币加上递归地分派6262分钱分钱 一个一个5 5分的硬币加上递归地分派分的硬币加上递归地分派5858分钱分钱 一个一

21、个1010分的硬币加上递归地分派分的硬币加上递归地分派5353分钱分钱 一个一个2121分的硬币加上递归地分派分的硬币加上递归地分派4242分钱分钱 一个一个2525分的硬币加上递归地分派分的硬币加上递归地分派3838分钱分钱 该算法的问题仍然是效率问题该算法的问题仍然是效率问题 27 动态规划解动态规划解 效率低下主要是由于重复计算造成的。效率低下主要是由于重复计算造成的。 因此，可把已有子问题的答案存放起来，因此，可把已有子问题的答案存放起来， 当再次遇到此子问题时就不用重复计算当再次遇到此子问题时就不用重复计算 了。了。 在本例中，我们用在本例中，我们用coinsUsedicoinsUs

22、edi 代表了代表了 找找i i分零钱所需的最小硬币数。分零钱所需的最小硬币数。 28 算法思想算法思想 先找出一分钱的找零方法，把最小硬币数先找出一分钱的找零方法，把最小硬币数 存入存入coinUsed1 coinUsed1 依次找出依次找出2 2分钱、分钱、3 3分钱分钱的找零方法，知的找零方法，知 道到达要找零的钱为止：道到达要找零的钱为止： 对每个要找的零钱对每个要找的零钱i i，可以把，可以把i i分解成某个分解成某个 coinsjcoinsj 和和 i - coinsji - coinsj ， 所需硬币数为所需硬币数为coinUsedi-coinsj+1coinUsedi-coin

23、sj+1。对所。对所 有的有的j j，取最小的，取最小的coinUsedi-coinsj+1coinUsedi-coinsj+1作作 为为i i元钱找零的的答案。元钱找零的的答案。 29 函数原型函数原型 Void makechange( int coins, int differentCoins, int maxChange, int coinUsed ) Coins存放所有不同的硬币值，不同的硬币存放所有不同的硬币值，不同的硬币 个数为个数为differentCoins。 maxChange为要找的零钱数为要找的零钱数 30 void makechange( int coins , int

24、 differentCoins, int maxChange, int coinUsed ) coinUsed0 = 0; for (int cents = 1; cents = maxChange; cents+) int minCoins = cents; for (int j = 1; j cents) continue; if (coinUsed cents - coinsj + 1 minCoins) minCoins = coinUsed cents - coinsj + 1; coinUsedcents = minCoins; 31 动态规划动态规划 硬币找零问题硬币找零问题 最

25、优二叉查找树最优二叉查找树 32 最优二叉查找树最优二叉查找树 有一组词有一组词 w1,w2,w1,w2,wN,wN，他们的出现概率分别，他们的出现概率分别 为为p1,p2,p1,p2,pNpN。构建一棵二叉排序树使得访问。构建一棵二叉排序树使得访问 时间的期望值最小。即如果时间的期望值最小。即如果wiwi所在的层次是所在的层次是didi， 那么那么 该问题类似于哈夫曼树，概率大的靠近根，概该问题类似于哈夫曼树，概率大的靠近根，概 率小的远离根。但它比哈夫曼树更复杂。因为率小的远离根。但它比哈夫曼树更复杂。因为 它还要满足二叉排序树的特性它还要满足二叉排序树的特性 N i ii dp 1 )1

26、 ( 33 贪婪法的解法贪婪法的解法 选择出现概率最大的词作为树根，把剩余的词选择出现概率最大的词作为树根，把剩余的词 分成两组：小于根的和大于根的。递归构建左分成两组：小于根的和大于根的。递归构建左 子树和右子树。子树和右子树。 A0.22 Am0.18 And0.20 Egg0.05 If0.25 The0.02 two0.08 if two the a and amegg 显然不是最优的，代价为：显然不是最优的，代价为： 2.43 34 最优解法最优解法 假如要对假如要对w wleft left到 到w wright right构建一棵最优二叉排序树，那么 构建一棵最优二叉排序树，那么

27、这棵树的形式一定是根为这棵树的形式一定是根为w wi i，左子树的节点为，左子树的节点为leftleft到到 i-1i-1，右子树的节点为，右子树的节点为i+1i+1到到rightright，左子树和右子树，左子树和右子树 也是最优的也是最优的 设设C Cleft left，rightright是树的代价，那么 是树的代价，那么 )(min )(min , 11, 1 1 , 11, right leftj jrightiileft rightileft right ij j i leftj jrightiilefti rightileft rightleft pCC ppCCpC 35 最优

28、解法最优解法 对对 a,am.and,egg,if,the,twoa,am.and,egg,if,the,two对所有的可能的情况计算它对所有的可能的情况计算它 的代价，从中找出最小的：的代价，从中找出最小的： 根为根为a a，左子树为空，右子树为，左子树为空，右子树为amam，twotwo。 根为根为amam，左子树为，左子树为a a，右子树为，右子树为and,and,，twotwo。 根为根为andand，左子树为，左子树为a a，am,am,右子树为右子树为egg,egg,，twotwo。 根为根为eggegg，左子树为，左子树为a,am,anda,am,and, ,右子树为右子树为if

29、,if,，twotwo。 在上述每一种情况中，我们需要继续递归。如：在尝试根在上述每一种情况中，我们需要继续递归。如：在尝试根 为为eggegg，左子树为，左子树为a,am,anda,am,and, ,右子树为右子树为if,if,，twotwo的情况时，的情况时， 要找出最优的左子树，我们又要尝试要找出最优的左子树，我们又要尝试 根节点为根节点为a a，左子树为空，右子树为，左子树为空，右子树为amam和和andand 根节点为根节点为amam，左子树为，左子树为a a，右子树为，右子树为andand 根节点为根节点为andand，左子树为，左子树为a a和和amam，右子树为空。，右子树为空

30、。 36 动态规划解法动态规划解法 从上述分析可以看出，在找出由从上述分析可以看出，在找出由a a到到twotwo组成组成 的最优树时，由的最优树时，由a a组成的树，由组成的树，由a a和和amam组成的组成的 树，由树，由amam和和andand组成的树，组成的树，会分别被计算，会分别被计算 很多次。很多次。 解决方法：从小到大计算由解决方法：从小到大计算由n n个节点组成的最个节点组成的最 优树，并把它保存在一个表中。当所有的节优树，并把它保存在一个表中。当所有的节 点形成了一棵树时，任务就完成了。点形成了一棵树时，任务就完成了。 每棵树的保存用两个信息：根和代价。每棵树的保存用两个信息

31、：根和代价。 37 生成过程生成过程 先生成由一个节点组成的树。树的代价就是节点先生成由一个节点组成的树。树的代价就是节点 的权值。保存这些树和相应的代价。的权值。保存这些树和相应的代价。 生成所有由两个节点组成的树：生成所有由两个节点组成的树： 将第一个节点作为根，第二个节点作为右子树。计算将第一个节点作为根，第二个节点作为右子树。计算 代价。代价。 将第二个节点作为根，第一个节点作为右子树。计算将第二个节点作为根，第一个节点作为右子树。计算 代价。代价。 取代价小的树作为最终的树保存下来。取代价小的树作为最终的树保存下来。 生成由三个节点组成的树，四个节点组成的树生成由三个节点组成的树，四

32、个节点组成的树 38 two0.08the0.02if0.25egg0.05and0.20am0.18a0.22 Two.twoThe.theIf.ifEgg.eggAnd.andAm.ama.a Left=7Left=6Left=5Left=4Left=3Left=2Left=1 a0.58 a.am and0.56 Am.and and0.30 And.egg if0.35 Egg.if if0.29 If.the two0.12 The.two and0.66 Am.egg and0.80 And.if if0.39 Egg.the if0.47 If.two Am1.02 a.and

33、and1.21 Am.if if0.84 And.the if0.57 Egg.two Am1.17 a.egg and1.27 Am.the if1.02 And.two And1.83 a.if and1.53 Am.two And1.89 a.the And2.15 a.two i=1 i=2 i=3 i=4 i=5 i=6 i=7 and a am if eggtwo the 39 回溯法回溯法 八皇后问题八皇后问题 分书问题分书问题 首先暂时放弃问题规模大小的限制，并将问题的候首先暂时放弃问题规模大小的限制，并将问题的候 选解按某种顺序逐一枚举和检验。当发现候选解不选解按某种顺序逐一

34、枚举和检验。当发现候选解不 可能是解时，就选择下一候选解。如果当前候选解可能是解时，就选择下一候选解。如果当前候选解 除了不满足规模要求外，满足其他所有要求时，继除了不满足规模要求外，满足其他所有要求时，继 续扩大当前候选解的规模，并继续试探。如果当前续扩大当前候选解的规模，并继续试探。如果当前 的候选解满足包括问题规模在内的所有要求时，该的候选解满足包括问题规模在内的所有要求时，该 候选解就是问题的一个解。候选解就是问题的一个解。 40 八皇后问题八皇后问题 在一个在一个8 8* *8 8的棋盘上放的棋盘上放8 8个皇后，使个皇后，使8 8个皇后个皇后 中没有两个以上的皇后会在同一行、同一中

35、没有两个以上的皇后会在同一行、同一 列或同一对角线上列或同一对角线上 41 八皇后问题的求解过程八皇后问题的求解过程 求解过程从空配置开始，在第一列到第求解过程从空配置开始，在第一列到第m m 列为合理配置的基础上再配置列为合理配置的基础上再配置m+1m+1列，直列，直 到第到第n n列的配置也时合理时，就找到了一列的配置也时合理时，就找到了一 个解。另外在一列上也有个解。另外在一列上也有n n种配置。开始种配置。开始 时配置在第一行，以后改变时，顺序选择时配置在第一行，以后改变时，顺序选择 第二行、第三行、。、第第二行、第三行、。、第n n行。当配置行。当配置 到第到第n n行时还找不到一个

36、合理的配置时，行时还找不到一个合理的配置时， 就要回朔，去改变前一列的配置。就要回朔，去改变前一列的配置。 42 算法 m = 0; /*从空配置开始从空配置开始*/ good = true; /*配置中的皇后不冲突配置中的皇后不冲突*/ do if (good) if (m = 8) 输出解；输出解； 重新寻找下一可行的解；重新寻找下一可行的解； else 向前试探，扩展至下一列；向前试探，扩展至下一列； else 回朔，形成下一候选解；回朔，形成下一候选解； good = 检查当前候选解的合理性；检查当前候选解的合理性； while (m != 0); 43 棋盘的棋盘的数据结构的设计数据

37、结构的设计 比较直观的方法是采用一个二维数组，但仔细考察，就会发比较直观的方法是采用一个二维数组，但仔细考察，就会发 现，这种表示方法给调整候选解及检查其合理性会带来困难。现，这种表示方法给调整候选解及检查其合理性会带来困难。 对于本题来说，我们关心的并不是皇后的具体位置，而是对于本题来说，我们关心的并不是皇后的具体位置，而是 “一个皇后是否已经在某行和某条斜线合理地安置好了一个皇后是否已经在某行和某条斜线合理地安置好了”。 因为在每一列上恰好放一个皇后，所以引入一个一维数组因为在每一列上恰好放一个皇后，所以引入一个一维数组 ( (设为设为colcol（9 9）) )，值，值coljcolj

38、表示在棋盘第表示在棋盘第j j列上的皇后位置。列上的皇后位置。 如如col3col3的值为的值为4 4，就表示第三列的皇后在第四行。另外，就表示第三列的皇后在第四行。另外， 为了使程序在找完了全部解后回溯到最初位置，设定为了使程序在找完了全部解后回溯到最初位置，设定col0col0 的初值为的初值为0 0。当回溯到第。当回溯到第0 0列时，说明程序已求得全部解列时，说明程序已求得全部解( (或或 无解无解) )，结束程序执行。，结束程序执行。 44 候选解的合理性检查候选解的合理性检查 引入以下三个工作数组引入以下三个工作数组 数组数组a9a9，aA=trueaA=true表示第表示第A A行

39、上还没有皇后；行上还没有皇后； 数组数组b16b16，bA=truebA=true表示第表示第A A条右高左低斜线条右高左低斜线 上没有皇后；从左上角依次编到右下角上没有皇后；从左上角依次编到右下角(1-15)(1-15)。 数组数组c16c16，cA=truecA=true表示第表示第A A条左高右低斜线条左高右低斜线 上没有皇后。从左下角依次编到右上角上没有皇后。从左下角依次编到右上角(1-15)(1-15)。 45 void queen_a11(int k) /在在8x8棋盘的第棋盘的第k列上找合理的配置列上找合理的配置 int i, j; char awn; for(i = 1; i

40、= 9; i+) / 依次在依次在l至至8行上配置行上配置k列的皇后列的皇后 if ( ai ai = bk+i-1 = c8+k-i = false; /置对应位置有皇后置对应位置有皇后 if (k = 8) / 找到一个可行解找到一个可行解 for (j = 1; j = 8; j+) cout j colj t ; cout awn; if (awn=Q | awn=q) exit(0); else queen_a11(k+1);/递归至第递归至第k十十1列列 ai = bk+i-1 = c8+k-i = true; /恢复对应位置无皇后恢复对应位置无皇后 46 主程序主程序 int c

41、ol9; bool a9, b17,c17; int main() int j; for(j = 0; j =8; j+) aj = true; for(j = 0; j = 16; j+) bj = cj = true; queen_a11(1); return 0; 47 回溯法回溯法 八皇后问题八皇后问题 分书问题分书问题 首先暂时放弃问题规模大小的限制，并将问题的候首先暂时放弃问题规模大小的限制，并将问题的候 选解按某种顺序逐一枚举和检验。当发现候选解不选解按某种顺序逐一枚举和检验。当发现候选解不 可能是解时，就选择下一候选解。如果当前候选解可能是解时，就选择下一候选解。如果当前候选解

42、 除了不满足规模要求外，满足其他所有要求时，继除了不满足规模要求外，满足其他所有要求时，继 续扩大当前候选解的规模，并继续试探。如果当前续扩大当前候选解的规模，并继续试探。如果当前 的候选解满足包括问题规模在内的所有要求时，该的候选解满足包括问题规模在内的所有要求时，该 候选解就是问题的一个解。候选解就是问题的一个解。 48 分书问题分书问题 有编号为有编号为0，1，2，3，4的的5 本书，准备分给本书，准备分给5个人个人A，B， C，D，E，每个人的阅读兴，每个人的阅读兴 趣用一个二维数组描述：趣用一个二维数组描述： Likeij = true i喜欢书喜欢书j Likeij = false

43、 i不喜欢书不喜欢书 j 写一个程序，输出所有皆大写一个程序，输出所有皆大 欢喜的分书方案欢喜的分书方案 00110 11001 01101 00010 01001 49 存储设计存储设计 用一个二维数组用一个二维数组likelike存储用户的兴趣存储用户的兴趣 用一个一维的整型数组用一个一维的整型数组taketake表示某本书分表示某本书分 给了某人。给了某人。TakejTakej = i = i表示第表示第j j本书给了本书给了 第第i i个人。个人。 50 解题思路解题思路 依次尝试把书依次尝试把书j j分给人分给人i i。 如果第如果第i i个人不喜欢第个人不喜欢第j j本书，则尝试下

44、一本书，如果喜本书，则尝试下一本书，如果喜 欢，并且第欢，并且第j j本书尚未分配，则把书本书尚未分配，则把书j j分配给分配给i i。 如果如果i i是最后一个人，则方案数加是最后一个人，则方案数加1 1，输出该方案。否则，输出该方案。否则 调用调用trytry（i+1)i+1)为第为第i+1i+1个人分书。个人分书。 回溯。让第回溯。让第i i个人退回书个人退回书j j，尝试下一个，尝试下一个j j，即寻找下一，即寻找下一 个可行的方案个可行的方案 由于在每次由于在每次trytry中都要用到中都要用到likelike，taketake以及目前找以及目前找 到的方案数到的方案数n n，因此可

45、将它们作为全局变量，以免，因此可将它们作为全局变量，以免 每次函数调用时都要带一大串参数。每次函数调用时都要带一大串参数。 设计一个函数设计一个函数try(i)给第给第i个人分书。个人分书。 51 void trynext(int i) int j, k; for (j=0; j5; +j) if (likeij if (i = 4) n+; cout n第第 n 种方案种方案: endl; cout 书书t人人 endl; for (k=0; k5; k+) cout k t char(takek+A) endl; else trynext(i+1); takej = -1; 52 true

46、falsefalsetruefalse falsetruefalsefalsefalse truefalsetruetruefalse truefalsefalsetruetrue falsetruetruefalsefalse 当当likelike矩阵的值为矩阵的值为 调用调用trynext(0);trynext(0);的结果为：的结果为： 第1种方案： 书 人 0 B 1 C 2 A 3 D 4 E 第2种方案： 书 人 0 B 1 E 2 A 3 D 4 C 53 素数检测素数检测 方法一：依次检测方法一：依次检测1 1到到N N能否被能否被N N整除，如果能被整除整除，如果能被整除 的

47、数的个数等于的数的个数等于2 2，则，则N N是素数。时间复杂度为是素数。时间复杂度为O O（N N） 方法二：依次检测方法二：依次检测2 2、3 3、5 5、7 7到到sqrt(Nsqrt(N) )，只要有一，只要有一 个能整除个能整除N N，则，则N N为非素数。最坏情况的时间复杂度为非素数。最坏情况的时间复杂度 O(NO(N1/2 1/2) ) 上述两方法对小素数适合，大素数不适合上述两方法对小素数适合，大素数不适合 方法三：随机算法。该算法能保证：当声称是非素数方法三：随机算法。该算法能保证：当声称是非素数 时，时，100%100%为非素数；当声称是素数时，有一个可以忽为非素数；当声称是素数时，有一个可以忽 略不计的很小的误差。略不计的很小的误差。 54 理论基础理论基础 定理一：如果定理一：如果p p是素数，并且是素数，并且0 a p0 a p，那么，那么 A Ap-1 p-1 1(mod p) 1(mod p) 定理二：如果定理二：如果p p是素数，并且是素数，并且0 xp0 xp，那么方程，那么方程 x x2 21 (mod