用C语言实现青蛙跳台阶问题

用C语言实现青蛙跳台阶问题

  今天刚学完函数的一个很重要的知识点，函数的递归，随即看到的一个很有趣的问题，就是，青蛙跳台阶的一个问题。

  假设一只青蛙一次可以跳上1级台阶，也可以跳上2级。求青蛙跳上一个n级的台阶共有多少种跳法（先后次序不同算不同的结果）。下面来展开讨论一下。

  首先，我们知道n为台阶的级数，以n为变量列举以下几种情况：

  假设n=1，青蛙只有1种跳法，就是1；

  假设n=2，青蛙有2种跳法，就是2，（1，1）；

  假设n=3，青蛙有3种跳法，就是（1，1，1），（1，2），（2，1）；

  假设n=4，青蛙有5种跳法，就是（1，1，1，1），（1，1，2），（1，2，1），（2，1，1）（2，2）；

  假设n=5，青蛙有8种跳法，就是（1，1，1，1，1），（1，1，1，2）（1，1，2，1），（1，2，1，1），（2，1，1，1），（2，2，1），（2，1，2），（1，2，2）；

  这5种情况的结果分别是1，2，3，5，8。也就是可以写成，1，1，2，3，5，8。从这组数列我们可以很直观的看到，其实是一组斐波那契数列，这个数列可以用公式来表达，假设fib(n)，n为第n个斐波那契数，那么其实一组斐波那契数列是必须要第一和第二个数存在才可以求出第三个数，以此数列为例，我们就可以推断出此规律：当n<=2时候，也就是第一个和第二个斐波那契数都是1，第2种情况就是，当n>2时，第n个斐波那契数就是等于fib(n-1)+fib(n-2)，意思就是n的前两个数加在一起，结果就是第n个斐波那契数。

  那么我们如何用代码来实现这个斐波那契数列呢，现在就不妨先用函数的递归来写一下。

#define _CRT_SECURE_NO_WARNINGS 1

#include

int fib(int n)
{
    if(n <= 2)
      return 1;

    else
      return fib(n - 1) + fib(n - 2);

}


int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = fib(n);
    printf("%dn",ret);
    return 0;
}

    我们可以像上图一样，先设一个函数fib，然后用递归的方式进行，假设此时输入的数为6，求第6个斐波那契数，程序运行效果如下图所示：

   但是如果此时输入的数是50，我们会发现，程序运行起来过了很长一段时间都不出现结果，这个时候并不是计算机在偷懒，而是要计算的数字太过于庞大，如下图效果所示：

   这是为什么呢，我们来画图演示以下。

  当求第50个斐波那契数的时候，我们要先求出第49和第48个数，要递归进去求出第49个数的时候又要求出第48和第47个数，求第48个数又要求出对应的第46和第47个数，以此一直递归下去，是一个非常非常庞大的计算，在第一层就要求49和48两个数，第二层要求四个数，是一个指数增长的形式，这样写下去我们求到第50个数，至少有2的48次方个数，而且我们可以看到在每一层递归都会出现要算重复数字的情况，我们接下来可以写出一段代码来看一看实际这种运算的效果。

#define _CRT_SECURE_NO_WARNINGS 1

#include

int count = 0;

int fib(int n)
{
    if (n == 3)
      count++;

    if (n <= 2)
      return 1;

    else
      return fib(n - 1) + fib(n - 2);

}


int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = fib(n);
    printf("%dn",ret);

    printf("ncount = %dn", count);
    return 0;
}

  我们在函数外头创建一个全局变量count，然后再加上一个判断条件，当n=3的时候，count++，也就是这一步其实在累加在计算过程中第3个斐波那契数被重复计算的次数，最后打印count看看一共重复计算了多少次第3个斐波那契数，假设现在要求第40个斐波那契数，程序运行，结果如下图所示：

   这里可以直观的看到，在计算第40个斐波那契数的时候，第3个斐波那契数一共被重复计算了39088169次，这可想而知浪费了很多时间，效率很低，所以这青蛙跳台阶的问题，也就是斐波那契数列问题，用函数递归的方式是不太合适的，为了改善这种情况，我们可以用到迭代的方法来处理，也就是最简单的循环。代码可以像以下这样设计：

#define _CRT_SECURE_NO_WARNINGS 1

#include


int fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;

   while(n > 2)
  {
     c = a + b;
     a = b;
     b = c;
     n--;
  } 
      return c;
}


int main()
{
    int n = 0;
    scanf("%d", &n);
    int ret = fib(n);
    printf("%dn",ret);

    return 0;
}

  设两个变量分别为a，b当作要求的斐波那契数的前两个数，当n>2的时候，也就是从第三个数开始，每一次要求的斐波那契数c都等于前两个数a，b之和，当要求后一个斐波那契数的时候再进行赋值，把前一个斐波那契数c赋给b，b赋给a，以此来循环程序，最后程序运行看看效果，假设这里要求第50个斐波那契数，结果如下图所示：

   可以看到计算机一下子就能把结果算出来，当然我们求证不了这个数是否正确，因为整型int里面放不进去那么庞大的数据，但是这题青蛙跳台阶斐波那契数列用迭代的方法确实比递归效率高多了。

  总结

  1.许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

  2.这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

  3.当一个问题相当复杂，难以用迭代实现，此时以递归实现的简洁性便可以补偿它所带来的运行时开销。