一道关于斐波那契数列的题目小明同学在小的时候喜欢爬楼梯,不为什么,只是觉得这种阶梯状的建筑非常好玩等到他长大了,可以一次跨上一级,也可以跨两级所以,他想知道,有多少种不同的上

Question

一道关于斐波那契数列的题目
小明同学在小的时候喜欢爬楼梯,
不为什么,只是觉得
这种阶梯状的建筑非常好玩
等到他长大了,可以一次跨上一级,也可以跨两级
所以,他想知道,
有多少种不同的上到楼梯顶端的方案
输入格式 Input Format
一行,一个整数,表示楼梯的高度（小于15）
输出格式 Output Format
一行,一个整数,表示方案数.
样例输入 Sample Input
3
样例输出 Sample Output
3 请问这道题,为什么会用到斐波那契数列啊,

Answer 1

首先假设楼梯只有一级,那么小明只有一种爬法；
如果有2级,那么小明可以一级一级地往上爬,也可以一次就上两级,用算式表示为1+1或2,说明他上2级楼梯有2种不同的爬法；
如果有3级,小明的第一步可以上一级,也可以上二级.如果上一级,那么还剩下2级,上面已经讨论过了有2种不同的爬法；如果上二级,那么还剩下1级,上面也已经讨论过了,只有1种爬法；合计起来就有2+1=3种不同的爬法.有算式表示为3=1+2（2种不同的爬法）=2+1（1种不同的爬法）；
如果有4级,小明的第一步可以上一级,也可以上二级.如果上一级,那么还剩下3级,上面已经讨论过了有3种不同的爬法；如果上二级,那么还剩下2级,上面也已经讨论过了,有2种不同的爬法；合计起来就有3+2=5种不同的爬法.用算式表示为4=1+3（3种不同的爬法）=2+2（2种不同的爬法）；
……
照这样推下去,可以得一串斐波那契数列：1,2,3,5,8,13,21,34,55,89,……由此可知,爬上有10级台阶的楼梯,一共有89种不同的爬法