锐客网

  1. 首页 > it技术 > >

动态规划&递归-危险的组合

1. 问题描述 有若干个铅盒和铀盒(足量)，要求将n(n<=30)个盒子进行排列组合，输出满足至少有三个铀盒相邻的排法的个数。例如输入5，要求输出8。
2. 问题分析

说明： 柚盒用1表示，铅盒用0表示，下同。
首先，考虑在n-1个盒子已经符合排列要求的情况下，当第n个盒子为1还是为0时，满足条件的排列数. 其情况描述图如图（1）。
对于图（1）：当n-1个时满足要求时，如果增加一个盒子n，那么无论n为1还是0，新的排列均满足。故有：2*f(n-1)个。
其次，考虑在n-1个盒子不符合排列要求的情况下，当第n个盒子为1还是为0时，满足条件的排列数. 其情况描述图如图（2）。
【动态规划&递归-危险的组合】对于图（2）：
① 首先推测第n个位置不能为0. 采用假设法。当n-1不成立时，如果n盒子为0，那么新的n个盒子的排列仍不成立，所以，第n个盒子不能为0.
② 其次推测第n个位置只能为1. n-1个盒子的排列中没有一个满足至少有三个铀盒相邻，说明，n-1个盒子的排列中，最多只能有两个1挨着，剩下的1和0轮流交替，所以，要使n-1个盒子不成立，而n个盒子的排列成立，则第n个盒子只能为1.
③ 再次，推测n-3至n-1的排列。②中提到n-1个盒子的排列中，最多只能有两个1挨着，那么如果有两个1挨着的话，这两个1的位置可以在任意位置，可以在第1和第2位，也可以在第n-2和第n-1位。为了满足成立条件，在第n个盒子能为1的情况下，且要使n个盒子的排列符合条件，那么第n-1和第n-2位上只能为1，由于n-1的排列中，最多只能有两个1相邻，所以n-3位只能为0. 由此推测出图（2）中的情况。
因此，图（2）中表示，n-1个盒子时不成立，摆放情况为110···，而n个盒子时能成立的盒子摆放示意图。因此，其成立个数应为n-4个盒子时不成立的个数。而对于n-4个盒子的摆放总数为pow(2,n-4),成立的总数为f(n-4),故图（2）成立的总数为：pow(2,n-4)-f(n-4).
最后，由于不存在其它情况，且上两种情况无重叠，所以： f(n)=2*f(n-1)+pow(n,n-4)-f(n-4) ,其中n由分析过程可知必须大于等于4。而对于0,1,2,3则分别为初值：0,0,0,1.
3. 代码实现 递归函数实现：
int calcu(int n) { if (n<3) return 0; else if (n==3) return 1; else return 2*calcu(n-1)+ ( (int)pow(2.0, n-4)-calcu(n-4)); }

4. 感悟 感悟：平时的动态规划都是在探讨边界条件，求出状态转移方程，而且一般的求法是正向求解，重点关注第n位（下一位）的增量情况。而本题另辟蹊径，使用了逆向求解，在n-1不成立时，逆向求解n-1的排列方式，这是平时思维中的一点盲点。
Reference: http://tieba.baidu.com/p/2347438416

    推荐阅读


    上一篇：数学基础及计算机理论|微积分基本公式

    下一篇：概率论基础学习