一个智力题~

This topic created in 5051 days ago, the information mentioned may be changed or developed.

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

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

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

7 replies • 1970-01-01 08:00:00 +08:00

Air_Mu

Aug 13, 2012

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

hyh1048576

Aug 13, 2012

@Air_Mu 哪里不严谨了？

hyh1048576

Aug 13, 2012

@Air_Mu 我承认不够严谨。

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

zorksylar

Aug 13, 2012

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

Oct 11, 2012

按最后一位的数字分类递推一下(包含了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

Oct 11, 2012

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

Parallel

Oct 11, 2012

@zorksylar DP正解。