一个智力题~

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 4476 天前的主题，其中的信息可能已经有所发展或是发生改变。

先放难的版本：不超过 n 位，只包含 0、1、2，且 2 不在 1 后面的数有几个？

下面放一个容易一些的版本，想不出这个的可以看下面那道当提示。

n 个杯子摆成一排，往里面投入硬币 0 - ⎡n/2⎤ 枚，要求每个杯子至多一枚，且任意两枚 coin 所在的杯子不相邻，有几种投法？

7 条回复 • 1970-01-01 08:00:00 +08:00

Air_Mu

2012-08-13 03:27:07 +08:00

出题要严谨这样组织语言还是别出了。我说前面那个

hyh1048576

2012-08-13 05:13:12 +08:00

@Air_Mu 哪里不严谨了？

hyh1048576

2012-08-13 07:34:35 +08:00

@Air_Mu 我承认不够严谨。

这么说吧，由 A, B, C 组成且不含 AB 的长度为 n 的字符串有几个？

zorksylar

2012-08-13 14:33:15 +08:00

dp0[i] : 共i位，且含012，且2不在1后的方法数
dp1[i] : 共i位，且不含1的方法数
i >= 3
dp0[3] = 2
dp1[3] = 4

dp0[i] = dp0[i-1] * 2 + dp1[i-1]
dp1[i] = dp1[i-1] * 2

dp0[n] 为结果

leixiao

2012-10-11 11:00:42 +08:00

按最后一位的数字分类递推一下(包含了0可以在首位的情况):
发现其实是斐波那契数列
定义f(1)=1, f(2)=1, f(3)=2, f(4)=3, ... f(n)=f(n-1)+f(n-2)
那么不超过 n 位，只包含 0、1、2，且 2 不在 1 后面的数有f(2n+3)-2个

dreambt

2012-10-11 20:57:03 +08:00

@hyh1048576 2 不在 1 后面，是指2不能紧邻1后面，还是1必须在2左边出现（右边不可以）？
其次，简化问题并不等价于原问题：原题n位数，0肯定不能在最高位吧？而简化后的题目A可以在最左边

Parallel

2012-10-11 22:10:58 +08:00

@zorksylar DP正解。