ACM递推归纳

Author Avatar
Patrick 2月 18, 2017

ACM递推归纳

递推是我众多不擅长的项目中的比较显著的一个…题目做得太艰难了。

注意

递推中增加一个元素,在头部加和尾部加是同一种情况!!!因此考虑了尾部就不用考虑头部了!!!吃了好多亏orz。

超级楼梯

有一楼梯共M级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第M级,共有多少种走法?

分析:

因为只能走一级或者两级,所以最后一步有两种情况:

  1. 走一步,剩下n-1和之前的相同
  2. 走两步,剩下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难题

有排成一行的n个方格,用红(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

最后

这部分代码并不难,难的是找出递推关系。

这么多组下来之后可以发现很多都是与前两次的状态有关的,因为根据特殊的条件可以分成两种情况讨论,不过找出这个讨论的条件也不是一件容易的事情。希望这次的踩坑能给之后的带来一些帮助吧!