前言
C语言初学者在学习“递归与循环”章节时，一定会遇到“不死兔子”这道经典例题。
简而言之，它就是一个数列，除了第一项与第二项值为1以外，所有的项的值都等于其前两项的值之和：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
在编程学习中，当单考斐波那契数列，即题目直接要求编写斐波那契数列代码时，许多同学并不会被难到。然而，当题干转变提问思路，转而提问“青蛙跳台阶有几种跳法”“小矩形摆大矩形有几种摆法”时，许多人就懵了：没有意识到其实这样的题干本质上还是在考察斐波那契数列的实现。
是的，斐波那契数列考题（或者说有很多的应用题），难点或许并不在代码实现，而在如何从看似有些“莫名其妙”的题干中分析出，这是一道考xxx的例题。
一些同学疑惑，自己怎么能想到用斐波那契数列求解呢？事实上，我们只需要会分析出恰当的办法解出来就好了，而不必纠结于“我看不出这用斐波那契写啊，那我就不会做了”。分析的过程是最重要的，无非是我们经过一番分析发现，恰好我们的解题思路和斐波那契一样，而不是早就知道了用这个方法，然后往题目里套。
因而，本文以应用题“青蛙跳台阶”为引例，讲解如何破题并分析出题干背后的考点；并在文末贴上另一道相对而言少见的相关题目：矩形覆盖问题。
这两道题都将附上详解，希望各位读者能有所收获。
一、斐波那契阿数列基础知识
本文默认大家都熟悉斐波那契数列的基础知识：包括最基础的代码编写思路和具体实现。不过还是考虑到也许一些同学一下子反应不过来把基础知识给忘了，因而在正文开始前，先贴上斐波那契数列的代码实现。不需要的同学可以直接跳过。
1. 斐波那契数列定义：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
2. 求斐波那契数列的第N项
//求Fib数列第n项 //非递归 int main(){ int f1 = 1; int f2 = 1; int fn,n; scanf("%d",&n); for(int i = 3; i <= n; i++){ fn = f1 + f2; f1 = f2; f2 = fn; } printf("%d",fn); return 0; } //递归 int Fib(int n){ if(n <= 0){ return 0; } if(n == 1){ return 1; } return Fib(n - 1) + Fib(n - 2) }
3. 实现思路
从Fib的数学定义可以非常简单地得出递归思路：除了第1项和第2项值为1（第0项或负数项，这里默认为0），所有的项的值都是前两项之和F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)
非递归的思路类似于“滚车轮”，示意图如下：
如图：通过f1 = f2;f2 = fn实现迭代
f1和f2像两只“脚”，通过将三个数中的后一个赋值给前一个，实现整体向右不断叠加计算。
基础铺垫的部分简单地说明到这里，如果还有朋友们有不理解的地方，可以移步别的博主的优秀解析。本文在此不再赘述。
二、引例：青蛙跳台阶
牛客网习题链接
题干如下
题感较好或是曾经刷到过该题的同学应当一眼就能看出，该题就是斐波那契数列的经典习题。事实上题目暗示的也很明确：“一次可以走1级或2级台阶”“一共有多少种走法”。在谈到“一共有多少种办法”的时候，也许想到不断叠加是一件很自然的事情；或者干脆直接死记硬背地记住。从单题的角度看，固然是可行的，但对大多数第一次接触的同学而言，这样的解释和“马后炮”一样，并不靠谱。
采取上述方法的同学可以先尝试直接跳到最后的拓展例题（如果没接触那个例题的话），或者思考如果自己并不提前知道这两道应用题的解法而是从头分析，能不能分析出来。如果不能，那么以上的方式或许就有些欠妥（当然，应付学校的考试是没问题的）。
在分析问题时，我们一般采用这样的方法：题目表意 ----> 模型 ----> 代码，即从题干字面意思中转换成解题的模型（姑且这么叫吧），然后再根据模型逐步求精，编写代码。下面就第一步 表意--模型，展开详细的介绍。
青蛙跳台阶：我如何得知它是一道斐波那契数列题？——应用题破题“三板斧”（二）+ https://developer.aliyun.com/article/1518376?spm=a2c6h.13148508.setting.14.16ee4f0ePJ4B4k
