问题描述:用G(n)表示在有n位的二进制数中没有相邻的两个1的二进制数个数。比如，当n=3时，000，001，010，011，100，101，110，111这8个数中只有000,001,010,100,101这5个是没有相邻为1的，故G(3)=5。请写一个程序，输出G(n)的值。
错误的思路(考虑的不周全):采用"分治"的方法，比如n=3，每次都将处理原问题规模的二分之一，直到n=1时，就很容易可以知道有两种情况。前面是"分"，然后是"合"。比如把规模为n的问题分成了p1和p2部分，而且p1和p2问题都已经解决，个数已经知道。那么，把p1和p2合起来的时候就只需要注意p1的最右边和p2的最左边的数不能同时为1，即:合起来的总的个数是:1*(p2-1)+(p1-1)*p2。"递归"和"分治"不分家，所以很容易写出下面的程序。
以下是错误的代码。
错误的代码
1 int calculate(int n)
2 {
3 if(n==1)
4 return 2;
5 if(p[n]!=0)
6 return p[n];
7 int div=n/2;
8 return (p[n]=calculate(n-div)-1 + (calculate(div)-1)*calculate(n-div));
9 }
正确的思路:算法的核心思想不变，依然是"分治"。"分"的部分很好处理，"合"的时候就容易出错了。我之前就是在合并的时候没有考虑周全。依然是把规模为n的问题分成p1和p2部分,令div=n/2，那么p1中有div个元素，p2中有n-div个元素。合并的时候，已经保证p1,p2部分分别都没有相邻的两个1了，这时需要注意的就只是p1的最右边一个数和p2的最左边的一个数了。分两种情况(要用到排列组合的基础知识):
将p1中最右边的数记为A，p2中最左边的数记为B，方便下面的文字描述。
1.A不为1。这种情况比下一种情况简单一些。在p1中，A不为1，那么A就是0了。这种情况下,G(div)=G(div-1)。再来考虑p2。既然A为0，那么B即使为1也没关系了。所以，这种情况下的结果就是G(div-1)*G(n-div)。
2.A为1。因为A为1，那么A左边的第一个数必然为0(因为p1中没有两个相邻的1)，所以在这种情况下G(div)=G(div-2)。再来考虑p2。既然A为1，那么B肯定得为0了，那么B右边的数也就没有限制了，即G(n-div-1)。所以，这种情况下的结果就是G(div-2)*G(n-div-1)。
代码如下:
1 #include <stdio.h>
2 #define MAX 1000
3
4 int p[MAX]={0};
5
6 //prototype
7 int calculate(int n);
8
9 int main()
10 {
11 int n=6;
12 int result=calculate(n);
13 printf("%d\n",result);
14 return 0;
15 }
16
17 int calculate(int n)
18 {
19 if(n<1)
20 return 1;
21 if(n==1)
22 return 2;
23 if(p[n]!=0)
24 return p[n];
25 int div=n/2;
26 return (p[n]=(calculate(div-2) * (calculate(n-div-1)) + calculate(div-1)*calculate(n-div)));
27 }
通过程序，可以得到G(1)=2,G(2)=3,G(3)=5,G(4)=8,G(5)=13,G(6)=21......可以看出这是一个斐波拉契数列。
本文转自NeilHappy 51CTO博客，原文链接：http://blog.51cto.com/neilhappy/1134394，如需转载请自行联系原作者
