开发者社区> ghost丶桃子> 正文

斐波那契数列和反向计算问题

简介:
+关注继续查看

反向计算:编写一个函数将一个整型转换为二进制形式

反向计算问题,递归比循环更简单

分析:需要理解,奇数的二进制最后一位是1,偶数的二进制最后一位一定是0,联想记忆,这个和整型的奇偶性是一致的,1本身就是奇数,0本身是偶数。


 
 
十进制整数转换为二进制整数采用"除2取余,逆序排列"法。
具体做法是:用2整除十进制整数,可以得到一个商和余数,再用2去除商,又会得到一个商和余数,如此进行,直到商为0时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。
对于数值n,二进制最后一位=n%2;计算得到的结果是最后要输出的结果,使用递归函数,联系递归的特点:在递归语句之前计算n%2,在递归调用语句之后输出结果,这样先计算的结果反而在最后输出。

 

使用了10进制转2进制的反复相除,余数倒置法;

复制代码
 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 void toBinary(unsigned long);
 4 int main()
 5 {
 6     unsigned long num;
 7     printf("输入一个正整数:q退出\n");
 8     while(scanf_s("%ul", &num) == 1)
 9     {
10         toBinary(num);
11         putchar('\n');
12         printf("输入一个正整数:\n");
13     }
14     system("pause");
15     return 0;
16 }
17 //递归函数
18 void toBinary(unsigned long num)
19 {
20     int r;
21     r = num % 2;//最后一位要输出的,即使参数=1,还是要计算到这里结束,只取出余数就ok了。然后顺次返回上一级主调函数,继续执行剩下的……
22     //如果商 1 / 2 = 0,计算就可以终止了,不需要再算
23     if (num >= 2)
24     {
25         //精华,联系10进制转2进制的算法,每次除以2,取出余数,然后用新的商继续除以2,取出新余数……直到商为0,余数逆序输出即可
26         toBinary(num / 2);//把新的商作为参数递归调用
27     }
28     //在递归语句之后输出,这样就是倒叙输出
29     printf("%d", r);
30 }
复制代码

当然使用位操作,也能实现这个算法:

复制代码
//将无符号十进制数转化为标准16位二进制数
int main()
{
    unsigned short i;
    
    cout << "请输入一个小于65536的正整数" << endl;
    cin >> i;
    //for语句从15递减到0,一共16次对二进制数的每一位的判断作操作。
    for(int j = 15; j >= 0; j--)
    {
        //<<运算表示把1的二进制形式整体向左移j位,左移后低位补0,移出的高位部分被舍弃。
        if (i & (1 << j)){
            //i&(1<<j)的值相当于把i的二进制的第j位取出来(i的第j位与(1<<j)的第j位与,i的第j位为1时值为真)循环后既得i的二进制形式。
            cout << "1";
        }
        else{
            cout << "0";
        }
    }
    
    cout << endl;
    
    return 0;
}
复制代码

<<运算表示把1的二进制形式整体向左移j位,左移后低位补0,移出的高位部分被舍弃。

例如,当j为15时,表达式(1<<j)的值为1000000000000000;当j为10时,值为0000010000000000。

位运算的“个性”决定了它直接对数据的二进制形式进行操作的快捷性(一般计算机的数据存储基本形式为二进制形式),两个相同算法的程序,用了位运算后会使程序速度上有提高。

使用现成的转换函数也是可以的

_itoa(120, &buffer, 16); 第一个参数是要转换的数,第二个是地址,第三个是进制数

再次看递归的优缺点

 

优点:为一些编程问题提供了简单的办法,比如上题还有斐贝纳契数列问题等,二个数字是1,其余的每个数字都是前两个数字的和。这使用递归很好。

缺点:占据内存大,耗资源,速度慢,一般难以维护和阅读。比如斐波纳契数列递归函数:

斐波那契数列问题

问题的由来:13世纪的意大利数学家斐波纳契(Fibonacci)写了一本商用的算术和代数手册<<Liber abaci>>。在这本书里,他提出了这么一个有趣的问题:

假定一对兔子在它们从出生整整两个月以后可以生一对小兔子,其后每隔一个月又可以再生一对小兔子。假定现在在一个笼子里有一对刚生下来的小兔子,请问一年以后笼子里应该有几对兔子?

让我们仔细地算一下。

第一、第二个月,小兔子长成大兔子,但还没成熟不能生小兔子,所以总共只有一对。

第三个月,原有的一对大兔子生了一对小兔子,现在一共有二对了。

第四个月,大兔子又生了一对小兔子,但是第二代的那对小兔子还没成熟,还不能生小兔子,所以总共有三对。

第五个月,第一、二两代的两对兔子各生了一对小兔子,连同四月份原有的三对,现在一共有五对了。

第六个月,在四月份已经有的三对兔子各生一对小兔了,连同五月份原有的五对兔子,现在一共有八对了。

依此类推,每个月份所有的兔子对数应该等于其上一个月所有的兔子对数(也就是原有的兔子对数)及其上上个月所有的兔子对数(这些兔子各生了一对小兔子)的总和。

所以每个月的兔子对数应该是1、1、2、3、5、8、13、21、34、55、89、144、233……

每一项都是前两项之和。因此,一年后笼子里应该有233对兔子

这些兔子的数目我们称之为斐波纳契数字(Fibonacci numbers)。

为方便起见,我们用 Fn表示第 n 代兔子的数目。

我们观察到:

F1=F2=1

而当n≧3时,Fn=Fn-1+Fn-2

最简单,但是时间复杂度最大的解法是递归算法, 算法时间复杂度O(n^2)

复制代码
long long fibonacciRecursion(unsigned int n ){
    if (0 == n){
        return 0;
    }
    else if (1 == n){
        return 1;
    }
    else{
        return fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2);
    }
}
复制代码

注意:c和 c++中所有函数的地位平等,都可以调用其他任何函数的同时,被其他任何函数调用。比如,main虽然是程序入口函数,但是main也可以递归,或者被其他函数调用,只不过不经常这样做。

下面分析一下这个递归解斐波那契数列的过程。以 f(10)为例子,想求 f(10),就要求 f(9)和 f(8),同理,求 f(9),先求 f(8)和 f(7)……使用递归树来表示:

 

发现这是一个双重递归,即每次函数对本身进行了两次调用(不是一次调用一次,而是每次递归对自己调用两次),这样出现了指数变量阶的问题,就是每次递归调用产生的变量集合是指数阶增长的,如递归树所示,很多结点是重复计算的,是浪费的。这样就很容易程序崩溃。这是一个典型极端例子,提醒我们要谨慎使用,结合效率。

改进的办法很自然就是避免重复计算

可以把中间的结果,提前保存起来,以备后用,下次计算的时候直接使用,无需重复计算。使用迭代递推的方法。

复制代码
//递推的解法,非递归
long long fibonacciRecursion(unsigned int n ){
    //先判断 n=0和1的时候
    if (0 == n){
        return 0;
    }
    else if (1 == n){
        return 1;
    }
    else
    {
        long n0 = 0;
        long n1 = 1;
        long fn = 0;
        for (int i = 2; i <= n; i++){
            fn = n1 + n0;
            n0 = n1;
            n1 = fn;//这是递推的过程
        }
        
        return fn;
    }
}
复制代码

算法时间复杂度O(n),很容易理解,也是很实用的解法。在实际开发中,不会使用第一种递归解法,因为效率很低,而第二种方法(也激素迭代),把递归用循环处理,极大的提高了时间效率。比较常用。

一些关于斐波那契的变种

问:一只青蛙一次可以跳上一级台阶,或者一次跳上两级台阶,求该青蛙跳上一个n 级的台阶总共有多少种跳法?

分析;

如果只有一级台阶,那么一共一种跳法,两级台阶,那么一共两种跳法,假设有 n 级台阶,那么把跳法记为 f(n),当 n>2的时候,第一次跳的时候有两种选择,如果第一次只跳一级,此时跳法数为后面剩下的n-1级台阶的跳法数目,也就是为 f(n-1)种,如果第一次跳两级,此时跳法数目为后面剩下的n-2级台阶的跳法数目,也就是 f(n-2),故一共为f(n)=f(n-1)+f(n-2)种,其实就是斐波那契数列。

问:用2x1的小矩形横放或者竖放去覆盖更大的矩形,请问用8个2x1的小矩形无重叠的覆盖一个2x8的大矩形,一共有多少种方法?

把2x8的覆盖方法记为 f(8),第一个1x2的小矩形去覆盖大矩形最左边有两个选择,竖放或者横放,当竖着放的时候,右边还有2x7个小区域,这种情况下的覆盖方法记为 f(7),如果横着放,当1x2的小矩形横着放在左上角的时候,左下角必须也横着放一个1x2的小矩形,而在右边还有2x6的区域,这时的覆盖方法记为 f(6),因此f(8)=f(7)+f(6),这仍然是斐波那契数列。

 

辛苦的劳动,转载请注明出处,谢谢……
http://www.cnblogs.com/kubixuesheng/p/4385682.html

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
复习C部分:1.for循环 2.do while循环语句 3.在一个有序数组中查找某个数,例如在1~10之间找7(例题包含计算n的阶乘+打印1~10的奇数+二分法)
复习C部分:1.for循环 2.do while循环语句 3.在一个有序数组中查找某个数,例如在1~10之间找7(例题包含计算n的阶乘+打印1~10的奇数+二分法)
12 0
算法 | 两种方式实现斐波那契数
斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardo Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”
42 0
巧用递归解决矩阵最大序列和问题
巧用递归解决矩阵最大序列和问题
37 0
[解题报告]【第03题】给定 a 和 b ,交换它们的值并输出 | 四种解法
[解题报告]【第03题】给定 a 和 b ,交换它们的值并输出 | 四种解法
71 0
线性递归和迭代---分析阶乘
为了帮助更多编程者入门,我决定通过计算机程序解释与构造这本书上的例子来引出几个例子,帮助别人同时,也等于给自己复习,我们来看一个简单的例子----阶乘      如果我问5的阶乘是多少,那么根据公式可以推倒出:5!=5*4*3*2*1 = 120      这个算法其实很简单,实现如下:      n! = n * (n -1) * (n - 2) ... * 3 * 2 * 1 ;      仔细观察,不难发现一个通项公式: n * (n -1)  。
713 0
【递归】斐波那契数列第n个数
递归、递推计算斐波那契数列第n项的值: 1 #include 2 long long fact(int n); //【递推】计算波那契数列第n个数 3 long long fact2(int n);//【递归】 4 int main(int argc, char *arg...
978 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载