纠正:
若N为偶数,则满足要求的数量是G=C(N,1)+C(N-1,2)+...+C(K+1,K) + 1,其中K=N/2
代码如下:
// 求n取m的组合
static __int64 ComputeC( unsigned int n, unsigned int m )
{
__int64 iResult = 0;
double dResult = 0;
__int64 iDev;
if ( m <= n )
{
if ( m > ( n / 2 ) )
{
m = n - m;
}
iResult = 1;
for( unsigned int i = 0; i < m; i++ )
{
iResult *= ( n - i );
iDev = i + 1;
iResult /= iDev;
}
}
return iResult;
}
// 计算bits个比特为不含任意连续1的所有可能取值
static __int64 ComputeA( unsigned int bits )
{
__int64 iResult = 0;
unsigned int k = ( bits + 1 ) / 2;
if ( !( bits & 1 ) )
{
k++;
}
for( unsigned int i = k; i <= bits; i++ )
{
iResult += ComputeC( i, bits - i + 1 );
}
return iResult + 1;
}
有点惊讶,其结果符合兔子数的规律:
001 -->
2
002 -->
3
003 -->
5
004 -->
8
005 -->
13
006 -->
21
007 -->
34
008 -->
55
009 -->
89
010 -->
144
011 -->
233
012 -->
377
013 -->
610
014 -->
987
015 -->
1597
016 -->
2584
017 -->
4181
018 -->
6765
019 -->
10946
020 -->
17711
021 -->
28657
022 -->
46368
023 -->
75025
024 -->
121393
025 -->
196418
026 -->
317811
027 -->
514229
028 -->
832040
029 -->
1346269
030 -->
2178309
031 -->
3524578
032 -->
5702887
033 -->
9227465
034 -->
14930352
035 -->
24157817
036 -->
39088169
037 -->
63245986
038 -->
102334155
039 -->
165580141
040 -->
267914296
041 -->
433494437
042 -->
701408733
043 -->
1134903170
044 -->
1836311903
045 -->
2971215073
046 -->
4807526976
047 -->
7778742049
048 -->
12586269025
049 -->
20365011074
050 -->
32951280099
051 -->
53316291173
052 -->
86267571272
053 -->
139583862445
054 -->
225851433717
055 -->
365435296162
056 -->
591286729879
057 -->
956722026041
058 -->
1548008755920
059 -->
2504730781961
060 -->
4052739537881
061 -->
6557470319842
062 -->
10610209857723
063 -->
17167680177565
064 -->
27777890035288
065 -->
44945570212853
066 -->
72723460248141
067 -->
117669030460994
068 -->
190392490709135
069 -->
308061521170129
070 -->
498454011879264