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

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

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

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

使用了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），这仍然是斐波那契数列。