13 递归与动态规划二

1、计第十三讲递归与动态规划(二)八皇后问题1、链接地址/problem?id=27542、问题描述会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8* 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法，定义一个皇后串a 与之对应，即a=b1b2.b8，其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解（即92个不同的皇后串）。给出一个数b，要求输出第b个串。串的比较是这样的：皇后串x置于皇后串y之前，当且仅当将x视为整数时比y小。2/34输

2、入数据第 1 行是测试数据的组数n，后面跟着n 行输入。每组测试数据占1 行，包括一个正整数b(1 = b = 92)输出要求n 行，每行输出对应一个输入。输出应是一个正整数，是对应于b 的皇后串输入样例2192输出样例15863724841362753/34问题描述3、解题思路(一)因为要求出 92 种不同摆放方法中的任意一种，所以我们不妨把92 种不同的摆放方法一次性求出来，存放在一个数组里。为求解这道题我们需要有一个矩阵仿真棋盘，每次试放一个棋子时只能放在尚未被控制的格子上，一旦放置了一个新棋子， 就在它所能控制的所有位置上设置标记，如此下去把八个棋子放好。当完成一种摆放时，就要尝试下一

3、种。若要按照字典序将可行的摆放方法记录下来，就要按照一定的顺序进行尝试。也就是将第一个棋子按照从小到大的顺序尝试； 对于第一个棋子的每一个位置，将第二个棋子从可行的位置从 小到大的顺序尝试；在第一第二个棋子固定的情况下，将第三个棋子从可行的位置从小到大的顺序尝试；依次类推。4/343、解题思路(一)首先，我们有一个8*8 的矩阵仿真棋盘标识当前已经摆放好的棋子所控制的区域。用一个有92 行每行8 个元素的二维数组记录可行的摆放方法。用一个递归程序来实现尝试摆放的过程。基本思想是假设我们将第一个棋子摆好，并设置了它所控制的区域，则这个问题变成了一个7 皇后问题，用与8 皇后同样的方法可以获得问题

4、的解。那我们就把重心放在如何摆放一个皇后棋子上，摆放的基本步骤是：从第1 到第8 个位置，顺序地尝试将棋子放置在每一个未被控制的位置上，设置该棋子所控制的格子，将问题变为更小规模的问题向下递归，需要注意的是每次尝试一个新的未被控制的位置前，要将上一次尝试的位置所控制的格子复原。5/34#include #include 4、参(一)考程序int queenPlaces928; /存放92种皇后棋子的摆放方法int count = 0;int board88; /仿真棋盘void putQueen(int ithQueen); /递归函数，每次摆好一个棋子int main(void)int n,

5、 i, j;for(i = 0; i 8; i+) / 初始化for(j = 0; j 8; j+) for(j = 0; j 92; j+)boardij = -1;queenPlacesji = 0;putQueen(0); /开始摆放，运行的结果是将queenPlaces 生成好scanf(%d, &n);for(i = 0; i n; i+)int ith; scanf(%d, &ith);for(j = 0; j 8; j+) printf(n);printf(%d, queenPlacesith - 1j);return 0;6/34void putQueen(int ithQue

6、en)int i,4k, 、r;参考程序(一)if(ithQueen = 8)count +;return;for(i = 0; i 8; i+)if(boardithQueeni = -1)boardithQueeni = ithQueen; /摆放皇后for(k = count; k 92; k+)queenPlaceskithQueen = i + 1; for(r = 0; r 8; r+) /设置控制范围for(k = 0; k 8; k+)if(boardrk = -1 &(r = ithQueen | k = i| abs(r - ithQueen) = abs(k - i)bo

7、ardrk = ithQueen; putQueen(ithQueen + 1); /向下级递归for(r = 0; r 8; r+) /回溯，撤销控制范围for(k = 0; k 8; k+)if(boardrk = ithQueen) boardrk = -1;7/345、解题思路(二)n 上面的方法用一个二维数组来记录棋盘被已经放置的棋子的控制情况，每次有新的棋子放置时用了枚举法来判断它控制的 范围。n 还可以用三个一维数组来分别记录每一列，每个45度的斜线和每个135 度的斜线上是否已经被已放置的棋子控制，这样每次有新的棋子放置时，不必再搜索它的控制范围，可以直接通 过三个一维数组判断

8、它是否与已经放置的棋子冲突，在不冲突 的情况下，也可以通过分别设置三个一维数组的相应的值，来记录新棋子的控制范围。8/34#include int record939, mark9, count = 1; /record 记录全部解，mark 记录当6、参考程序(二)解前；bool range9, line117, line217; /分别记录列方向，45度，135度方向上控被制的情况void tryToPut(int ); /求全部解的过程int main(void)int i, testtimes, num; scanf(%d, &testtimes); for(i = 0; i =8;

9、i+)rangei = true; for(i = 0; i 17; i +)line1i = line2i = true; tryToPut(1); /从第一个皇后开始放置while(testtimes -)scanf(%d, &num); for(i = 1; i 8)n /如果最后一个皇后被放置完毕，将当前解复制到全部解中n for(int k = 1; k = 8; k +)n recordcountk = markk;n count +;n n for(int j=1; j=8; j+)n /逐一尝试将当前皇后放置在不同列上n if(rangej & line1 i + j & li

10、ne2i - j + 9) /如果与前面不冲突n n marki = j;n rangej = line1i + j = line2i - j + 9 = false;n tryToPut(i + 1);n rangej = line1i + j = line2i - j + 9 = true;/回溯，撤销控制n n 10/347、解题思路(三)这个题目也可以不用仿真棋盘来模拟已放置棋子的控制区域，而只用一个有8个元素的数组记录已经摆放的棋子摆在什么位置，当要放置一个新的棋子时，只需要判断它与已经放置的棋子之间是否冲突就行了。11/34#include int ans928, num=0, h

11、uang8;void qu8een、(int参i)考程序(三)int j, k;if(i = 8) /一组新的解产生了for(j = 0; j 8; j+) num+;return;ansnumj = huangj + 1;for (j=0; j8; j+) /将当前皇后i 逐一尝试放置在不同的列for(k=0; ki; k+) /逐一判定i 与前面的皇后是否冲突if( huangk = j | (k - i) = (huangk - j)| (i - k) = (huangk - j )break;if (k = i) /放置i，尝试第i+1 个皇后huangi = j; queen(i +

12、 1);12/3413/348、参考程序(三)int main(void)n int i, j, b, n;n queen(0);n scanf(%d, &n);n for(i = 0; i n; i+)n n scanf(%d, &b);n for(j = 0; j 8; j+)n printf(%d, ansb - 1j);n printf(n);n n return 0;数字三角形1、问题描述上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。注意：路径上的每一

13、步只能从一个数走到下一层上和它最近的左边的数或者右边的数。14/34问题描述输入数据输入的第一行是一个整数N (1 N = 100)，给出三角形的行数。下面的N 行给出数字三角形。数字三角形上的数的范围都在0 和100 之间。输出要求输出最大的和。15/34问题描述输入样例573 88 1 02 7 4 44 5 2 6 5输出样例3016/342、解题思路这道题目可以用递归的方法解决。基本思路是：以D( r, j)表示第r 行第 j 个数字(r，j 都从1 开始算)，以MaxSum(r, j) 代表从第 r 行的第 j 个数字到底边的最佳路径的数字之和，则本题是要求 MaxSum(1, 1)

14、 。从某个D(r, j)出发，显然下一步只能走D(r+1, j)或者D(r+1, j+1)。如果走D(r+1, j)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j) + D(r, j)；如果走D(r+1, j+1)，那么得到的MaxSum(r, j)就是MaxSum(r+1, j+1) + D(r, j)。所以，选择往哪里走，就看MaxSum(r+1, j)和MaxSum(r+1, j+1)哪个更大了。17/343、参考程序 I#clude #define MAX_NUM 100int DMAX_NUM + 10MAX_NUM + 10;int N;int MaxSum(

15、int r, int j)if( r = N )return Drj;int nSum1 = MaxSum(r+1, j); int nSum2 = MaxSum(r+1, j+1); if( nSum1 nSum2 )return nSum1+Drj; return nSum2+Drj;18/34in3、参考程序 Iint main(void)int m; scanf(%d, &N);for( int i = 1; i = N; i + )for( int j = 1; j = i; j + ) scanf(%d, &Dij);printf(%d, MaxSum(1, 1);return 0

16、;19/34提交结果：Time Limit Exceed程序I分析73 88 1 02 7 4 44 5 2 6 5上面的程序，效率非常低，在N值并不大，比如N=100 的时候，就慢得几乎永远算不出结果了。为什么会这样呢？是因为过多的重复计算。我们不妨将对MaxSum函数的一次调用称为一次计算。那么，每次计算MaxSum(r,j)的时候，都要计算一次MaxSum(r+1,j+1)，而每次计算MaxSum(r, j+1)的时候，也要计算一次MaxSum(r+1, j+1)。重复计算因此产生。在 题 目 中 给 出 的 例 子 里 ， 如 果 我 们 将MaxSum(r,j)被计算的次数都写在位置

17、（r,j），那么就能得到右面的三角形：20/3411 11 2 11 3 3 11 4 6 4 121/34从程上图序可以分看出析，最后一行的计算次数总和是16，倒数第二行计算次数总和是8。不难总结出规律，对于N 行的三角形，总次数是20 +21+22+2(N-1)=2N-1。当的的N= 100 时，总的计算次数是一个让人无法接受的大数字。n 既然问题出在重复计算，那么解决的办法，当然就是，一个值一旦算出来，就要记住，以后不必重新计算。即第一次算出MaxSum(r, j)的值时，就将该值存放起来，下次再需要计算MaxSum(r, j)时，直接取用存好的值即可，不必再次调用MaxSum 进行函数

18、递归计算了。这样，每个MaxSum(r, j)都只需要计算1 次即可，那么总的计算次数（即调用MaxSum 函数的次数）就是三角形中的数字总数，即1+2+3+N = N(N+1)/2。n 如何存放计算出来的MaxSum（r, j）值呢？显然，用一个二维数组aMaxSumNN就能解决。aMaxSumrj就存放MaxSum(r, j)的计算结果。下次再需要MaxSum(r, j)的值时， 不必再调用MaxSum 函数，只需直接取aMaxSumrj的值即可。计算4、参考程序 II#include #include #define MAX_NUM 100int DMAX_NUM + 10MAX_NUM

19、 + 10;int N;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int MaxSum( int r, int j)if( r = N )return Drj;if( aMaxSumr+1j = -1 ) /如果MaxSum(r+1, j)没有计算过aMaxSumr+1j = MaxSum(r+1, j);if( aMaxSumr+1j+1 = -1) aMaxSumr+1j+1 = MaxSum(r+1, j+1);if( aMaxSumr+1j aMaxSumr+1j+1 )return aMaxSumr+1j +Drj; return aMaxSumr+1j

20、+1 + Drj;22/3423/344、参考程序 IIint main(void)int m; scanf(%d, & N);/将 aMaxSum 全部置成-1, 开始时所有的 MaxSum(r, j)都没有算过memset(aMaxSum, -1, sizeof(aMaxSum);for( int i = 1; i = N; i + ) for( int j = 1; j = i; j + )scanf(%d, & Dij);printf(%d, MaxSum(1, 1);return 0;程序II分析这种将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的办法，就叫做“动态

21、规划”。动态规划通常用来求最优解，能用动态规划解决的求最优解问题，必须满足，最优解的每个局部解也都是最优的。以上题为例，最佳路径上面的每个数字到底部的那一段路径，都是从该数字出发到达到底部的最佳路径。实际上，递归的思想在编程时未必要实现为递归函数。在上面的例子里，有递推公式：Drjr = NaMaxSumrj = Max(aMaxSumr + 1j,aMaxSumr + 1j + 1) + Drj其他因此，不需要写递归函数，从aMaxSumN-1这一行元素 开始向上逐行递推，就能求得aMaxSum11的值了。24/34int5、DMAX_NUM + 10MAX_NUM + 10;III参考程序

22、intN;int aMaxSumMAX_NUM + 10MAX_NUM + 10;int main(void)int i, j; scanf(%d, & N);for( i = 1; i = N; i + ) for( j = 1; j = i; j + )scanf(%d, &Dij); for( j = 1; j 1 ; i - )思考题：上面的几个程序只算出了最佳路径的数字之和。如果要求输出最佳路径上的每个数字，该怎么办？for( j = 1; j aMaxSumij+1 )aMaxSumi-1j = aMaxSumij + Di-1j;elseaMaxSumi-1j = aMaxSum

23、ij+1 + Di-1j;printf(%d, aMaxSum11); return 0;25/34n 许多求最优解的问题可以用动态规划来解决。n 首先要把原问题分解为若干个子问题。注意单纯的递归往往会导致子问题被重复计算，用动态规划的方法，子问题的解一旦求出就要被保存，所以每个子问题只需求解一次。n 子问题经常和原问题形式相似，有时甚至完全一样，只不过规模从原来的n 变成了n-1，或从原来的nm 变成了n(m-1) 等等。n 找到子问题，就意味着找到了将整个问题逐渐分解的办法。n 分解下去，直到最底层规模最小的的子问题可以一目了然地看出解。n 每一层子问题的解决，会导致上一层子问题的解决，逐

24、层向上， 就会导致最终整个问题的解决。n 如果从最底层的子问题开始，自底向上地推导出一个个子问题的解，那么编程的时候就不需要写递归函数。26/34动态规划解题的一般思路n 用动态规划解题时，将和子问题相关的各个变量的一组取值，称之为一个“状态”。一个“状态”对应于一个或多个子问题， 所谓某个“状态”下的“值”，就是这个“状态”所对应的子 问题的解。n 比如数字三角形，子问题就是“从位于(r，j)数字开始，到底边路径的最大和”。这个子问题和两个变量r 和j 相关，那么一个“状态”，就是r, j 的一组取值，即每个数字的位置就是一个“状态”。该“状态”所对应的“值”，就是从该位置的数字开始，到底边

25、的最佳路径上的数字之和。n 定义出什么是“状态”，以及在该 “状态”下的“值”后， 就要找出不同的状态之间如何迁移即如何从一个或多个 “值”已知的 “状态”，求出另一个“状态”的“值”。状态的迁移可以用递推公式表示，此递推公式也可被称作“状态转移方程”。27/34动态规划解题的一般思路r = NDrjaMaxSumrj = Max(aMaxSumr + 1j,aMaxSumr + 1j + 1) + Drj其他用动态规划解题，如何寻找“子问题”，定义“状态”，“状态转移方程”是什么样的，并没有一定之规，需要具体问 题具体分析，题目做多了就会有感觉。甚至，对于同一个问题，分解成子问题的办法可能不

26、止一种，因而“状态”也可以有不同的定义方法。不同的“状态”定义 方法可能会导致时间、空间效率上的区别。28/34动态规划解题的一般思路最长上升子序列1、问题描述一个数的序列bi，当b1 b2 . bS 的时候， 我们称这个序列是上升的。对于给定的一个序列(a1, a2, ., aN)，我们可以得到一些上升的子序列(ai1, ai2, ., aiK)，这里1 = i1 i2 . iK = N。比如，对于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8).你的任务，就是对于给定的序列，求出最长上升子序 列的长度。29/34输入数据输入的第一行是序列的长度N (1 = N = 1000)。第二行给出序列中的N 个整数，这些整数的取值范围都在0 到10000。输出要求最长上升子序列的长度。输入样例71 7 3 5 9 4 8输出样例430/34问题描述2、解题思路n 如何把这个问题分解成子问题呢？经过分析，发现 “求以ak（k=1, 2, 3N）为终点的最长上升子序列的长度”是个好的子问题这里把一个上升子序列中最右边的那个数，称为该子序列的“终点”。虽然这个子问题和原问题形式上并不完全一样，但是只要