ACM递推归纳
ACM递推归纳
递推是我众多不擅长的项目中的比较显著的一个…题目做得太艰难了。
注意
递推中增加一个元素，在头部加和尾部加是同一种情况！！！因此考虑了尾部就不用考虑头部了！！！吃了好多亏orz。
超级楼梯
有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？
分析：
因为只能走一级或者两级，所以最后一步有两种情况：
- 走一步，剩下n-1和之前的相同
- 走两步，剩下n-2和之前的相同
于是有：
a[n] = a[n - 1] + a[n - 2]
一只小蜜蜂
有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。
分析：
a到b的可能性本质上就是爬行b-a距离的可能性。而每一步有两个选择，右边或者斜右边，剩下的就和上面的几乎一样了，于是有：
a[i] = a[i - 1] + a[i - 2]
LELE的RPG难题
有排成一行的ｎ个方格，用红(Red)、粉(Pink)、绿(Green)三色涂每个格子，每格涂一色，要求任何相邻的方格不能同色，且首尾两格也不同色．求全部的满足要求的涂法.
分析：
如果n增加一，就要根据增加前最后一个格子的颜色来判断了：
- 如果最后一个不和第一个相同，也就是满足条件，就直接是a[n - 1]了，增加的一块只有一个选择
- 如果相同，那么前面n-2个一定是满足条件的，就是a[n - 2]，增加的一块有两个选择
于是有：
a[i] = a[i - 1] + 2 * a[i - 2]
骨牌铺方格
在2×n的一个长方形方格中,用一个1× 2的骨牌铺满方格,输入n ,输出铺放方案的总数.
例如n=3时,为2× 3方格，骨牌的铺放方案有三种
分析：
这道题之前就把我卡住了，不过现在看到这么多难题之后反而觉得不难了…
因为骨牌的尺寸是1*2，因此横着摆放和竖着摆放是不同的，而竖着摆放一个就能填满，横着摆放两个才能填满，于是：
- 当前情况是n-1的时候多加了一块竖着的
- 当前情况是n-2的时候多加了两块横着的
于是有：
a[i] = a[i - 1] + a[i - 2]
阿牛的EOF牛肉串
长度为n的只由”E” “O” “F”三种字符组成的字符串（可以只有其中一种或两种字符，但绝对不能有其他字符）,阿牛同时禁止在串中出现O相邻的情况
分析：
末尾有两种可能，是O或者是其他的
- 是E或F，那么前面n-1就一定满足，即为a[n-1]
- 是O的话，O前一位一定是E或F，根据上面的，有a[n-2]
综合起来，于是有：
a[n] = 2 * (a[n - 1] + a[n - 2])
神、上帝以及老天爷
首先，所有参加晚会的人员都将一张写有自己名字的字条放入抽奖箱中；
然后，待所有字条加入完毕，每人从箱中取一个字条；
最后，如果取得的字条上写的就是自己的名字，那么“恭喜你，中奖了！”
大家可以想象一下当时的气氛之热烈，毕竟中奖者的奖品是大家梦寐以求的Twins签名照呀！不过，正如所有试图设计的喜剧往往以悲剧结尾，这次抽奖活动最后竟然没有一个人中奖！
我的神、上帝以及老天爷呀，怎么会这样呢？
不过，先不要激动，现在问题来了，你能计算一下发生这种情况的概率吗？
分析：
注：此处a[n]依旧是可能性而不是概率
这是一个错位排序的问题，增加一个元素考虑两种情况：
- 前面n-1已经构成错排，那么直接把最后一个和前面n-1任意一个交换就可以了，即为(n - 1) * a[n - 1]
- 前面n-1不构成错排，新加的元素交换之后构成错排，于是有n-2个元素构成错排，而不构成的元素有n - 1种情况，即为(n -1) * a[n - 2]
于是有：
a[n] = (a[n - 1] + a[n - 2]) * (n - 1)
考新郎
假设一共有N对新婚夫妇,其中有M个新郎找错了新娘,求发生这种情况一共有多少种可能.
分析：
这也是一道错排的题，和上面几乎一样。不过是M个错排，另外N-M个是组合
于是有：
a[n] = (a[n - 1] + a[n - 2]) (n - 1)
rst = a[n] C(N,M)
注：a[n]是错排的可能性，rst才是结果
折线分割平面
我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。
分析：
直线相交的时候每增加N个交点会增加N+1个平面
1.N条直线相交，平面数为
1 + 1 + 2 + .. + n = 1 + n * (n + 1) / 2
2.N组平行线相交
第N次添加的时候，会增加两个2N-2个交点，此时会增加两个2N-1个平面，此时平面数为
1 + 2 + 6 + … + 4n - 2 = 2 n n + 1
3.N组折线相交
相比上面，每组直线相交就会少一个平面，于是少N个平面，平面数就是上面的减N
2 n n + 1 - n
最后
这部分代码并不难，难的是找出递推关系。
这么多组下来之后可以发现很多都是与前两次的状态有关的，因为根据特殊的条件可以分成两种情况讨论，不过找出这个讨论的条件也不是一件容易的事情。希望这次的踩坑能给之后的带来一些帮助吧！