其他
动图演示 | 青蛙跳跳，斐波那契
The following article is from 爱码有道 Author 点击关注👉👉
如若转载请联系原公众号
一. 分析和动图示例
当n=2时，青蛙自己占据一个荷叶，前面还有一个荷叶，直接跳过去就行，可选的方法数为1，即F(2)=1;
当n=3时，青蛙自己占据一个荷叶，前面还有两个荷叶，青蛙可以选择先跳一步，再跳一步。青蛙也可以选择直接跳两步。可选的方法数为2，即F(3)=2;
跳到下个荷叶上
跳到下下个荷叶上
假设青蛙第一跳是跳到下个荷叶上，那么青蛙发现，接下来要面临类似的选择问题，只是荷叶的数量变小了1个。此时，未来之路的方法数为F(n-1)，如动图所示：
假设青蛙第一跳是跳到下下个荷叶上，那么青蛙发现，接下来要面临类似的选择问题，只是荷叶的数量变小了2个。此时，未来之路的方法数为F(n-2)，如动图所示：
| 荷叶数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 |
化大为小，递归求解，是一种重要的思想。这是我第一次做动图，期待给予鼓励哦。我们也会一步一个脚印，争取每篇文章讲清讲透一件事，也希望大家阅读后有所收获，心情愉快。
推荐阅读：
每日打卡赢积分兑换书籍入口