由1和2组成的二进制数，有多少个数其所有位数之和是10

由1和2组成的二进制数，有多少个数其所有位数之和是10。
例：122122，1+2+2+1+2+2=10

从组合角度考虑，即：
1. 0个2的组合(10=10*1+0*2), C(0,10)
2. 1个2的组合(10=8*1+1*2)，C(1,9)
3. 2个2的组合(10=6*1+2*2)，C(2,8)
...
n+1. n个2的组合(10=(10-n)*1+n*2)，C(n,10-n)，n<=5
C(0,10)+C(1,9)+...C(5,5)=89

其实这是“上台阶，每次可走一台阶和两台阶，问上10个台阶有多少种走法”的变换，所以简单的解法是斐波那契数列f(10)=89。

抽象化后，由1和2组成的二进制数，有多少个数其所有位数之和是X。
n+1. n个2的组合(X=(X-n)*1+n*2)，C(n,X-n)，当X%2==0时，n<=X/2；当X%2==1时，n<=(X-1)/2；
即： C(0,X)+C(1,X-1)+...C(n,X-n)=f(X)

递归是通常计算斐波那契数列的常想到的（但非常不好的）方法，

long fibonacci(long l) {
		if (l == 1) {
			return 1;
		}
		if (l == 0) {
			return 0;
		}
		return fibonacci(l - 1) + fibonacci(l - 2);
	}

最好的方法（目前我认为，无论是在时间或空间上）是

long fibonacci(long l) {
		if (l == 0) {
			return 0;
		}
		long x = 0, y = 1;
		for (long i = 1; i <= l; i++) {
			y = x + y;
			x = y - x;
		}
		return y;
	}
	

评论

1 楼 chenhao112358 2011-03-22  

方法二是动态规划的思想，很好。