Posted on 2013-06-06 21:57
鑫龙 阅读(194)
评论(0) 编辑 收藏 引用 所属分类:
数据结构与算法
考虑n位二进制数，有多少个数中不存在两个相邻的1。例如，3位数中有5个数符合这一要求：000、001、010、100、101。
1、试找出其中的规律
2、请给出完整代码实现（参数输入代码可略）
3、试证明你找到的规律是正确的
1、 答：规律为2 n/2+2n-n/2-1。
2、 代码如下
#include<cmath>
using namespace std;
int Func(int n) {
if(n<0) { return -1; }
if(n==0) { return 0; }
return pow(2,(n/2))+pow(2,((n-(n/2)))-1;
}
3、 证明（构造法）
答：
1列出n位由1组成的2进制数a，111。。。。111；
2奇数位都用0取代得到数b，010。。。。010；
3偶数位也用0取代得到数c，101。。。。101；
4数b和数c中的任何一个1都可以被0取代，或不被取代，而构造出满足要求的数，且每个1的取代具有独立性。
5数b可以构造出2n/2个满足要求的数，同时数c可以构造出2n-n/2个满足要求的数。
6数b和数a都可以构造出全由0组成二进制数，因此统计存在一个重复。
7规律为2 n/2+2n-n/2-1；
-------------------------------------------------------------------------------------------------
n位的二进制,比如3位:000 001 010 100 101
什么规律呢，假设n位二进制有f(n)种不相邻的组合，
从最左边的位置开始放，可以放0，也可以放1。
如果最左边放0，那么将不影响第二位的放置，从第二位放起，即有f(n-1)种。
如果最左边放1，那么第二位则只能放0，从第三位放起，即有f(n-2)种。
所以f(n)=f(n-1)+f(n-2)种。
另外f(1)=2(因为可以放0或者1),f(2)=3(因为可以是00,01,10)。