找出没有相邻的1的二进制数的个数---2013年2月17日

      问题描述:用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。"递归"和"分治"不分家，所以很容易写出下面的程序。

      以下是错误的代码。

错误的代码
 int calculate(int n)
  {
      if(n==1)
          return 2;
      if(p[n]!=0)
          return p[n];
      int div=n/2;
      return (p[n]=calculate(n-div)-1 + (calculate(div)-1)*calculate(n-div));
  }

       正确的思路:算法的核心思想不变，依然是"分治"。"分"的部分很好处理，"合"的时候就容易出错了。我之前就是在合并的时候没有考虑周全。依然是把规模为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)。

       代码如下:

#include 
 #define MAX 1000
 
 int p[MAX]={0};
 
 //prototype
 int calculate(int n);
 
 int main()
 {
     int n=6;
     int result=calculate(n);
     printf("%d\n",result);
     return 0;
 }
 
 int calculate(int n)
 {
     if(n<1)
         return 1;
     if(n==1)
         return 2;
     if(p[n]!=0)
         return p[n];
     int div=n/2;
     return (p[n]=(calculate(div-2) * (calculate(n-div-1)) + calculate(div-1)*calculate(n-div)));
 }

       通过程序，可以得到G(1)=2,G(2)=3,G(3)=5,G(4)=8,G(5)=13,G(6)=21......可以看出这是一个斐波拉契数列。

       如果你觉得我的文章对你有帮助，请赞一下，非常感谢!