青蛙跳台阶问题

【问题】：一只青蛙前面有一座台阶；青蛙一次可以跳上1级台阶，也可以跳上2级；若此台阶有n级，则青蛙跳到第n级台阶有多少种跳法？

【答案】：设f(n)表示跳到第n级台阶的跳法数，则f(n)=f(n-1)+f(n-2)，(n>2)，且f(1)=1，f(2)=2

【分析】：
青蛙一次可以跳上1级台阶，也可以跳上2级，则跳到第1级台阶有1种跳法；跳到第2级台阶有2种跳法。

当台阶有3级时，跳到第3级台阶有两种方法：一种从第2级台阶跳、一种从第1级台阶跳，由前已知，跳到第2级台阶有2种跳法，跳到第1级台阶有1种跳法，所以跳到第3级台阶有2+1=3种跳法。

当台阶有4级时，跳到第4级台阶有两种方法：一种从第3级台阶跳、一种从第2级台阶跳，由前已知，跳到第3级台阶有3种跳法，跳到第2级台阶有2种跳法，所以跳到第4级台阶有3+2=5种跳法。

当台阶有5级时，跳到第5级台阶有两种方法：一种从第4级台阶跳、一种从第3级台阶跳，由前已知，跳到第4级台阶有5种跳法，跳到第3级台阶有3种跳法，所以跳到第5级台阶有5+3=8种跳法。

当台阶有n级时，跳到第n级台阶有两种方法：一种从第n-1级台阶跳、一种从第n-2级台阶跳，所以，跳到第n级台阶的跳法=跳到第n-1级台阶的跳法+跳到第n-2级台阶的跳法

【编程】：

语言：C++

两种方法：递归，非递归。后者在较大输入时有更快的效率。注意：n>45时结果对int型数据溢出

#include
using namespace std;

//f函数，递归
int f(int n) {
	if (n <= 0)return 0;//非法输入的处理
	if (n == 1)return 1;
	if (n == 2)return 2;

	return f(n - 1) + f(n - 2);//递归调用f函数
}
//非递归
int jumpMethod(int n) {
	if (n <= 0)return 0;//非法输入的处理
	int* array = new int[n];//开辟动态数组空间
	for (int i = 0; i < n; i++) {//为数组各元素赋值
		switch (i) {
		case 0:array[i] = 1; break;
		case 1:array[i] = 2; break;
		default:array[i] = array[i - 1] + array[i - 2];
		}
	}
	return array[n - 1];//数组最后一个元素的值就是结果
}

int main() {
	int n;
	cout << "请输入台阶数：";
	cin >> n;

	//非递归方法
	cout << "跳到第" << n << "级台阶有" << jumpMethod(n) << "种跳法" << endl;
	//递归方法
	cout << "跳到第" << n << "级台阶有" << f(n) << "种跳法" << endl;

	return 0;
}