找出没有相邻的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。”递归”和”分治”不分家，所以很容易写出下面的程序。
以下是错误的代码。
错误的代码
1 int calculate(int n)2 {3if(n==1);5if(p[n]!=0)6return p[n];7int div=n/2;8return (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 1000p[MAX]={0};calculate(int n); main()10 {11int n=6;12int result=calculate(n);,result);;15 }calculate(int n)18 {19if(n<1);21if(n==1);23if(p[n]!=0)24return p[n];25int div=n/2;26return (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……可以看出这是一个斐波拉契数列。
如果你觉得我的文章对你有帮助，请推荐一下，非常感谢!
posted on
Copyright ©2013 NeilHappy Powered by: 博客园 模板提供：沪江博客
踮起脚尖，我们就能离幸福更近点吗？
