动图演示 | 青蛙跳跳，斐波那契

 关注

“脚本之家

”，与百万开发者在一起

出处：爱码有道（ID：aimayoudao）

如若转载请联系原公众号

大家好，我是道哥。今天是我第一次做动图，感谢大家支持。我们来看一个与青蛙跳跳相关的算法问题，来看看题目的描述和要求：

青蛙站在第一个荷叶上，准备跳到最后一个荷叶上。青蛙每次只能跳一步或者两步，如果想顺利跳到最后一个荷叶上去，求方法数。

是不是感觉无从下手呢？嗯，青蛙绞尽脑汁，万般思索，万一跳不好，那就会跳到水中去了，好在也没那么可怕，至少不怕水淹。

一. 分析和动图示例

假设有n个荷叶，青蛙跳跃的方法数为F(n), 显然有n>=2, 我们很容易知道：

• 当n=2时，青蛙自己占据一个荷叶，前面还有一个荷叶，直接跳过去就行，可选的方法数为1，即F(2)=1;

• 当n=3时，青蛙自己占据一个荷叶，前面还有两个荷叶，青蛙可以选择先跳一步，再跳一步。青蛙也可以选择直接跳两步。可选的方法数为2，即F(3)=2;

我们来考虑更一般的情况，当青蛙站在第1个荷叶上，此时此刻，青蛙紧张，忧心忡忡。

不管如何煎熬，青蛙总是要进行第一跳的。对于青蛙而言，它的第一跳有两种选择：

• 跳到下个荷叶上

• 跳到下下个荷叶上

接下来，我们分情况进行讨论，看看更一般的情况：

• 假设青蛙第一跳是跳到下个荷叶上，那么青蛙发现，接下来要面临类似的选择问题，只是荷叶的数量变小了1个。此时，未来之路的方法数为F(n-1)，如动图所示：

• 假设青蛙第一跳是跳到下下个荷叶上，那么青蛙发现，接下来要面临类似的选择问题，只是荷叶的数量变小了2个。此时，未来之路的方法数为F(n-2)，如动图所示：

所以，对于青蛙而言，当有n(n>=4)个荷叶时，跳跃的方法数F(n)可以表示为：

F(n) = F(n - 1) + F(n - 2)

可以看到，虽然我们没法找到直接计算F(n)的方法，但通过分析，把问题化解成了同类型的更小规模的问题，并给出了递推公式，总结如下：

荷叶数n	跳跃的方法数F(n)
n <= 1	无意义
n = 2	F(2) = 1
n = 3	F(3) = 2
n >= 4	F(n) = F(n-1) + F(n-2)

其实，这是一个典型的斐波那契数列，是非常典型的递归问题。当然，F(n)的通项公式肯定可以通过数学方法求出来，但这并不是本文的目的。

二. 递归的编程实现

既然知道了递推公式，那编程就简单啦，直接用递归的方法来做，C++代码如下：

#include <iostream>
using namespace std;

int frogJump(int n) 
{
  if(n <= 1)
  {
    return 0;
  }

  if(2 == n)
  {
    return 1;
  }

  if(3 == n)
  {
    return 2;
  }
  
  return frogJump(n - 1) + frogJump(n - 2);
}

int main()
{
  for (int n = 2; n <= 10; n++)
  {
    cout << frogJump(n) << endl;
  }

  return 0;
}

结果如下：

1

2

3

5

8

13

21

34

55

看到规律了吧，典型的斐波那契数列，我们在表格中呈现一下：

荷叶数n	跳跃的方法数F(n)
n <= 1	无意义
n = 2	F(2) = 1
n = 3	F(3) = 2
n = 4	F(4) = 3
n = 5	F(5) = 5
n = 6	F(6) = 8
n = 7	F(7) = 13
n = 8	F(8) = 21
n = 9	F(9) = 34
n = 10	F(10) = 55

化大为小，递归求解，是一种重要的思想。这是我第一次做动图，期待给予鼓励哦。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。

  推荐阅读：

每日打卡赢积分兑换书籍入口