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

最后附上一张自制体现递归过程的图

 

        /// <summary>
        /// 
        /// </summary>
        /// <param name="targetNumberIndex">指定斐波那契数列第几位</param>
        /// <param name="previous">前一个数的值</param>
        /// <param name="currentResult">当前累加结果</param>
        /// <param name="currentNumberIndex">当前累加到第几位</param>
        /// <returns></returns>
        public static double FibonacciWithRecursion(int targetNumberIndex, int previous = 1, int currentResult = 1, int currentNumberIndex = 2)
        {

            if (targetNumberIndex > 2 && currentNumberIndex <= targetNumberIndex)
            {
                currentNumberIndex += 1;
                Console.WriteLine(currentResult);
                var temp = currentResult;
                currentResult = currentResult + previous;
                return FibonacciWithRecursion(targetNumberIndex, temp, currentResult, currentNumberIndex);
            }
            else 
            {
                return 1;
            }
        }

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

2.
在分析上面那句话,“卖去所赶鸭子的一半又一只”,这表明了重复的计算方式,但是这里有两种思维方式:

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

 

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

如果从结果推出初始条件,等式可以写为,[(2+1)*2+1]*2 +1… = x;
重复过程为result = (result*2 +
1),出口为重复天数,直到天数等于给予的天数7

 

        //n*(n-1)*(n-1-1)*(n-1-1-1)...
        //解析n *(n-1) *(n-1-1)
        //阶乘的过程归纳为一个乘法运算的重复 *(n-1)
        public static double FactorialWithRecursion(int n) 
        {
            var result = 1;
            int temp;

            if (n > 1)
            {
                result = n * (n - 1);
                {
                    temp = n - 1;
                    if (temp > 1)//可以看到往下都是一个重复的过程,可以看作是一个递归方法调用的展开 
                    {
                        result = result * (temp - 1);
                        temp = temp - 1;

                        if (temp > 1) 
                        {
                            result = result * (temp - 1);
                            temp = temp - 1;

                            if (temp > 1) 
                            {
                                result = result * (temp - 1);//可以把重复的代码抽离出来写出一个方法
                                ...
                            }
                        }
                    }
                }
                return result;
            }
            else 
            {
                return result;
            }
        }

 

 

 

2)计算剩下的鸭子数量, y=x/2-1;

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

通俗的说就是能把大问题等价于一个小问题的循环重复,从而通过解决一个小问题来达到解决大问题的目的。

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

递归算法(recursion
algorithm)在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。

分析;

让我们来看几个例子,并且对比使用递归算法以及不使用递归的差异,了解一下使用递归的心路历程。

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

        public static double FactorialWithRecursion(int n) 
        {
            if (n > 1)//明确终止条件
            {
                Console.Write(n+"*");
                return n * FactorialWithRecursion(n - 1);
            }
            else //当不满足终止条件时的处理,即断开自我循环调用的点
            {
                Console.WriteLine(1);
                return 1;
            }
        }

 

这边采用的是一个正向思维,即F(n) = F(n-1)+F(n-2).
上图中并不是一个优秀的实现,但是便于理解。

具体做法是:用2整除十进制整数,可以得到一个商和余数,再用2去除商,又会得到一个商和余数,如此进行,直到商为0时为止,然后把先得到的余数作为二进制数的低位有效位,后得到的余数作为二进制数的高位有效位,依次排列起来。

经过抽离重复的代码,可以改进为如下。

 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 }

读者可以自己尝试着去实现这两种不同的方式。

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

永利网址 1

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

斐波纳契数列以如下被以递归的方法定义:F(1)=1,F(2)=1,
F(n)=F(n-1)+F(n-2)(n>=2,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)种,其实就是斐波那契数列。

阐述: 斐波那契数列 1、1、2、3、5、8、13、21、34 

一些关于斐波那契的变种

题目:一个人赶着鸭子去每个村庄卖,每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子,问他出发时共赶多少只鸭子?

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

永利网址, 

F1=F2=1

 1. 阶乘

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

3.
再看“经过了七个村子后还剩两只鸭子,问他出发时共赶多少只鸭子“,可以得出这是一个根据结果推出初始条件的问题。

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

1) 计算卖出去的鸭子数量,y=x/2+1;

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

假设初始有X只鸭子,等式为 [(x/2-1)/2 -1]/2 -1…= 2; 重复过程为result
=(result/2 -1), 出口即为重复天数,直到天数为零

再次看递归的优缺点

 

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

永利网址 2

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

  1. 一次自调用的结果,应该是下一次调用的初始值

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

这里的循环重复,和普通的loop 语句不太一样,在代码中体现为方法的自调用。

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

众所周知,循环的过程必须有一个控制条件来断开循环,否则就会无限循环下去。

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

各种算法的思想,永远是程序猿的必备利器。

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