算法设计习题课

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 + 1 * apple +

3、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改进的方案改进的方案int main() int mel

4、lon, 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：81Mellon：2 apple：11 orange：87Mellon：3 apple：4 orange：937贪婪法贪婪法 贪婪法适合于分阶段完成的工作。在每贪婪法适合于分阶段完成的工作。在每一阶段都选择当前最好的答案，而不管一阶段都选择当前最好的答案，而不管将来如何。将来如何。 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, 0.6和和0.60.6，最佳的方案是用两个盒子。最佳的方案是用两个盒子

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

8、法分治法 分而治之法的思想分而治之法的思想 分：递归解决若干个较小的问题分：递归解决若干个较小的问题 治：从子问题的答案中形成原始问题的解治：从子问题的答案中形成原始问题的解 分治法的的算法至少有两个递归调用分治法的的算法至少有两个递归调用 已见过的分治法算法：快速排序，树的已见过的分治法算法：快速排序，树的遍历遍历11最近点问题最近点问题 在二维平面上有在二维平面上有N N个点，试找出距离最短的个点，试找出距离最短的两个点。两个点。 蛮力算法：计算两两之间的距离，从中找蛮力算法：计算两两之间的距离，从中找出最小的一个。出最小的一个。N N个点有个点有N N（N-1N-1）/2/2对距离，对距

9、离，因此时间复杂度为因此时间复杂度为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 dL L和和d dR R可用递归得到可用递归得到 d dC C的计算：的计算： 设设=min(=min(d dL

10、 L,d,dR R) ) 如果如果d dC C比比大，则没必要计算。因此用于计算大，则没必要计算。因此用于计算d dC C的点必须落在分界线的点必须落在分界线 的范围内，计算此的范围内，计算此范围中点对的距离中的最小值范围中点对的距离中的最小值13dLdRdC14优化优化 在最坏的情况下，所有的点都落在分界线在最坏的情况下，所有的点都落在分界线以内。但此时不一定要计算所有点对的以内。但此时不一定要计算所有点对的距离。只要两点的距离。只要两点的y y坐标大于坐标大于，这两点之，这两点之间的距离也不用算了。间的距离也不用算了。 假设该区间中的点按假设该区间中的点按y y坐标排序，则可得下坐标排序，

11、则可得下列算法列算法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均分成两半，分别称为均分成两半，分别称为X XL L，X XR R，Y YL L，Y YR R。则则 X = XX = XL L1010N/2N/2+X+XR

12、R， Y = YY = YL L1010N/2N/2+Y+YR R。那么，。那么，XY=XXY=XL LY YL L1010N N+(X+(XL LY YR R+X+XR RY YL L) 10) 10N/2N/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进一步改进进一步改进 上述算法的问题是需要太多次（上述算法的问题是需要太多次（4 4次）的递归调用。如果次）的递归调用。如果能减少递归调用，则能提高时间性能能减少递归调用，则能提高时间性能 注意：注意：X XL L

13、Y 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/2N/2+X+XR RY YR R= = X XL LY YL L1010N N+(X+(XL L X XR R)(Y)(YR R Y YL L) + X) + XL LY YL L + X+ XR RY YR R ) 10 ) 10N/2N/2+X+XR RY YR R

14、可见只需可见只需3 3次递归调用次递归调用 时间复杂性：时间复杂性：)()()()2/(3)(59. 13log2NONONONTNT18动态规划动态规划 用表代替递归用表代替递归 例：斐波那契函数例：斐波那契函数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)f(n-1)时要计算时要计算f(n-2)f(n-2)和和f(n-3)f(n-3)。因此。因此在计算在计算f(nf(n) )中中f(n-2)f(n-2)被计算了两次。被计算了两次。 为了减少重复

15、的递归调用，我们可以反过为了减少重复的递归调用，我们可以反过来计算。先计算来计算。先计算f(2)f(2)，有了，有了f(2)f(2)再计算再计算f(3)f(3)，以此类推，计算到，以此类推，计算到f(nf(n) )。在此过程。在此过程中不需要任何递归中不需要任何递归19动态规划动态规划 硬币找零问题硬币找零问题 最优二叉查找树最优二叉查找树20找零问题找零问题 对于一种货币，有面值为对于一种货币，有面值为C1, C2, C1, C2, , , CN(CN(分分) )的硬币，最少需要多少个硬币来找的硬币，最少需要多少个硬币来找出出K K分钱的零钱。分钱的零钱。21贪婪法解法贪婪法解法 我们不断使

16、用可能的最大面值的硬币我们不断使用可能的最大面值的硬币 如：美元的硬币有如：美元的硬币有1 1、5 5、1010和和2525分的面值分的面值( (忽略流忽略流通频率很低的通频率很低的5050分硬币分硬币) )。我们可以通过使用。我们可以通过使用2 2个个2525分、一个分、一个1010分的硬币以及三个分的硬币以及三个1 1分来找出分来找出6363分钱，分钱，一共是一共是6 6个硬币。个硬币。 如果美元中包含一个如果美元中包含一个2121分硬币时，贪心算法仍然分硬币时，贪心算法仍然给出一个用六个硬币的解，但是最佳的解是用三给出一个用六个硬币的解，但是最佳的解是用三个硬币个硬币( (三个都是三个都

17、是2121分的硬币。分的硬币。) ) 22解法解法1分治法分治法如果我们可以用一个硬币找零，这就是如果我们可以用一个硬币找零，这就是最小的。最小的。否则，对于每个可能的值否则，对于每个可能的值i i，我们可以独，我们可以独立计算找立计算找i i分钱零钱和分钱零钱和K-iK-i分钱需要的最分钱需要的最小硬币数。然后选择这个和最小的小硬币数。然后选择这个和最小的i i。 23怎样找出怎样找出63分钱零钱分钱零钱 找出找出1 1分钱零钱和分钱零钱和6262分钱零钱分别需要的硬币数是分钱零钱分别需要的硬币数是1 1和和4 4。因此，。因此，6363分钱需要使用五个硬币。分钱需要使用五个硬币。 找出找出

18、2 2分钱和分钱和6161分钱分别需要分钱分别需要2 2和和4 4个硬币，一共是个硬币，一共是六个硬币。六个硬币。 我们继续尝试所有的可能性。我们看到一个我们继续尝试所有的可能性。我们看到一个2121分分和和4242分的分解，它可以分别用一个和两个硬币来分的分解，它可以分别用一个和两个硬币来找开，因此，这个找零问题就可以用三个硬币解找开，因此，这个找零问题就可以用三个硬币解决。决。 我们需要尝试的最后一种分解是我们需要尝试的最后一种分解是3131分和分和3232分。我分。我们可以用两个硬币找出们可以用两个硬币找出3131分零钱，用三个硬币找分零钱，用三个硬币找出出3232分零钱，一共是五个硬币

19、。分零钱，一共是五个硬币。 因此最小值是三个硬币。因此最小值是三个硬币。24int coin(int k) int i, tmp, int coinNum = k; if （能用一个硬币找零）（能用一个硬币找零） return 1; for (i=1; i coinNum) coinNum = tmp; return coinNum;25上述解法分析上述解法分析 此算法的效率很低此算法的效率很低 事实上事实上6363分钱找零的问题是不会在一个合分钱找零的问题是不会在一个合理的时间内解决的。就如理的时间内解决的。就如FinbonacciFinbonacci 函数函数一样一样26解法解法2 通过指

20、定其中的一个硬币来递归地简化问题。通过指定其中的一个硬币来递归地简化问题。 例如，对于例如，对于6363分钱，我们可以给出以下找零的办法。分钱，我们可以给出以下找零的办法。 一个一个1 1分的硬币加上递归地分派分的硬币加上递归地分派6262分钱分钱 一个一个5 5分的硬币加上递归地分派分的硬币加上递归地分派5858分钱分钱 一个一个1010分的硬币加上递归地分派分的硬币加上递归地分派5353分钱分钱 一个一个2121分的硬币加上递归地分派分的硬币加上递归地分派4242分钱分钱 一个一个2525分的硬币加上递归地分派分的硬币加上递归地分派3838分钱分钱 该算法的问题仍然是效率问题该算法的问题仍

21、然是效率问题27动态规划解动态规划解 效率低下主要是由于重复计算造成的。效率低下主要是由于重复计算造成的。因此，可把已有子问题的答案存放起来，因此，可把已有子问题的答案存放起来，当再次遇到此子问题时就不用重复计算当再次遇到此子问题时就不用重复计算了。了。 在本例中，我们用在本例中，我们用coinsUsedicoinsUsedi 代表了代表了找找i i分零钱所需的最小硬币数。分零钱所需的最小硬币数。28算法思想算法思想 先找出一分钱的找零方法，把最小硬币数先找出一分钱的找零方法，把最小硬币数存入存入coinUsed1 coinUsed1 依次找出依次找出2 2分钱、分钱、3 3分钱分钱的找零方法

22、，知的找零方法，知道到达要找零的钱为止：道到达要找零的钱为止： 对每个要找的零钱对每个要找的零钱i i，可以把，可以把i i分解成某个分解成某个coinsjcoinsj 和和 i - coinsji - coinsj ， 所需硬币数为所需硬币数为coinUsedi-coinsj+1coinUsedi-coinsj+1。对所。对所有的有的j j，取最小的，取最小的coinUsedi-coinsj+1coinUsedi-coinsj+1作作为为i i元钱找零的的答案。元钱找零的的答案。 29函数原型函数原型 Void makechange( int coins, int differentCoin

23、s, int maxChange, int coinUsed ) Coins存放所有不同的硬币值，不同的硬币存放所有不同的硬币值，不同的硬币个数为个数为differentCoins。 maxChange为要找的零钱数为要找的零钱数30void makechange( int coins , int differentCoins, int maxChange, int coinUsed ) coinUsed0 = 0; for (int cents = 1; cents = maxChange; cents+) int minCoins = cents; for (int j = 1; j ce

24、nts) continue; if (coinUsed cents - coinsj + 1 minCoins) minCoins = coinUsed cents - coinsj + 1; coinUsedcents = minCoins; 31动态规划动态规划 硬币找零问题硬币找零问题 最优二叉查找树最优二叉查找树32最优二叉查找树最优二叉查找树 有一组词有一组词 w1,w2,w1,w2,wN,wN，他们的出现概率分别，他们的出现概率分别为为p1,p2,p1,p2,pNpN。构建一棵二叉排序树使得访问。构建一棵二叉排序树使得访问时间的期望值最小。即如果时间的期望值最小。即如果wiwi所在

25、的层次是所在的层次是didi，那么那么 该问题类似于哈夫曼树，概率大的靠近根，概该问题类似于哈夫曼树，概率大的靠近根，概率小的远离根。但它比哈夫曼树更复杂。因为率小的远离根。但它比哈夫曼树更复杂。因为它还要满足二叉排序树的特性它还要满足二叉排序树的特性Niiidp1)1 (33贪婪法的解法贪婪法的解法 选择出现概率最大的词作为树根，把剩余的词选择出现概率最大的词作为树根，把剩余的词分成两组：小于根的和大于根的。递归构建左分成两组：小于根的和大于根的。递归构建左子树和右子树。子树和右子树。A0.22Am0.18And0.20Egg0.05If0.25The0.02two0.08iftwothea

26、andamegg显然不是最优的，代价为：显然不是最优的，代价为：2.4334最优解法最优解法 假如要对假如要对w wleftleft到到w wrightright构建一棵最优二叉排序树，那么构建一棵最优二叉排序树，那么这棵树的形式一定是根为这棵树的形式一定是根为w wi i，左子树的节点为，左子树的节点为leftleft到到i-1i-1，右子树的节点为，右子树的节点为i+1i+1到到rightright，左子树和右子树，左子树和右子树也是最优的也是最优的 设设C Cleftleft，rightright是树的代价，那么是树的代价，那么)(min)(min, 11,11, 11,rightlef

27、tjjrightiileftrightileftrightijjileftjjrightiileftirightileftrightleftpCCppCCpC35最优解法最优解法 对对 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

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

29、amam，左子树为，左子树为a a，右子树为，右子树为andand 根节点为根节点为andand，左子树为，左子树为a a和和amam，右子树为空。，右子树为空。36动态规划解法动态规划解法 从上述分析可以看出，在找出由从上述分析可以看出，在找出由a a到到twotwo组成组成的最优树时，由的最优树时，由a a组成的树，由组成的树，由a a和和amam组成的组成的树，由树，由amam和和andand组成的树，组成的树，会分别被计算，会分别被计算很多次。很多次。 解决方法：从小到大计算由解决方法：从小到大计算由n n个节点组成的最个节点组成的最优树，并把它保存在一个表中。当所有的节优树，并把它保

30、存在一个表中。当所有的节点形成了一棵树时，任务就完成了。点形成了一棵树时，任务就完成了。 每棵树的保存用两个信息：根和代价。每棵树的保存用两个信息：根和代价。37生成过程生成过程 先生成由一个节点组成的树。树的代价就是节点先生成由一个节点组成的树。树的代价就是节点的权值。保存这些树和相应的代价。的权值。保存这些树和相应的代价。 生成所有由两个节点组成的树：生成所有由两个节点组成的树： 将第一个节点作为根，第二个节点作为右子树。计算将第一个节点作为根，第二个节点作为右子树。计算代价。代价。 将第二个节点作为根，第一个节点作为右子树。计算将第二个节点作为根，第一个节点作为右子树。计算代价。代价。

31、取代价小的树作为最终的树保存下来。取代价小的树作为最终的树保存下来。 生成由三个节点组成的树，四个节点组成的树生成由三个节点组成的树，四个节点组成的树38two0.08the0.02if0.25egg0.05and0.20am0.18a0.22Two.twoThe.theIf.ifEgg.eggAnd.andAm.ama.aLeft=7Left=6Left=5Left=4Left=3Left=2Left=1a0.58a.amand0.56Am.andand0.30And.eggif0.35Egg.ifif0.29If.thetwo0.12The.twoand0.66Am.eggand0.80A

32、nd.ifif0.39Egg.theif0.47If.twoAm1.02a.andand1.21Am.ifif0.84And.theif0.57Egg.twoAm1.17a.eggand1.27Am.theif1.02And.twoAnd1.83a.ifand1.53Am.twoAnd1.89a.theAnd2.15a.twoi=1i=2i=3i=4i=5i=6i=7andaamifeggtwothe39回溯法回溯法 八皇后问题八皇后问题 分书问题分书问题首先暂时放弃问题规模大小的限制，并将问题的候首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不选解按某

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

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

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

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

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

38、6，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 = 9; i+) / 依次在依次在l至至8行上配置行上配置

39、k列的皇后列的皇后 if ( ai & bk+i-1 & c8+k-i) /可行位置可行位置 colk = i; 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主程序

40、主程序int col9;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回溯法回溯法 八皇后问题八皇后问题 分书问题分书问题首先暂时放弃问题规模大小的限制，并将问题的候首先暂时放弃问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现候选解不选解按某种顺序逐一枚举和检验。当发现候选解不可能是解时，就选择下一候选解。如果当前候选解可能是解时，就选择下一候选解。如果当前候

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

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

43、喜欢，并且第欢，并且第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，因此可将它们作为全局变量，以免，因此可将它们作为全局变量，以

44、免每次函数调用时都要带一大串参数。每次函数调用时都要带一大串参数。设计一个函数设计一个函数try(i)给第给第i个人分书。个人分书。51void trynext(int i) int j, k; for (j=0; j5; +j) if (likeij & takej = -1) takej = i; 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; 52truefalsefa

45、lsetruefalsefalsetruefalsefalsefalsetruefalsetruetruefalsetruefalsefalsetruetruefalsetruetruefalsefalse当当likelike矩阵的值为矩阵的值为调用调用trynext(0);trynext(0);的结果为：的结果为：第1种方案：书 人0 B1 C2 A3 D4 E第2种方案：书 人0 B1 E2 A3 D4 C53素数检测素数检测 方法一：依次检测方法一：依次检测1 1到到N N能否被能否被N N整除，如果能被整除整除，如果能被整除的数的个数等于的数的个数等于2 2，则，则N N是素数。时间复

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