学号：1753910 姓名：马思腾
简介
青蛙跳台阶问题是算法设计中较基础但十分重要的问题之一
问题题干如下：
青蛙跳台阶问题。
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级台阶。求该青蛙跳上 1 个 n 级的台阶总共有多少种跳法。
算法设计思路
这个问题的求解实质是求解其计算思路及通项公式，因为这个问题的规模不是通过手动计算可以解决的。
由组合数学课上学到的算法思路，由加法法则，青蛙跳上n级台阶之前，可能先跳上n-1级台阶，最后跳一级、也可能先跳上n-2级台阶，最后跳2级，因此，设跳上n级台阶的跳法为G(n),则
G(n)=G(n-2)+G(n-1)，其中，G(0)=0,G(1)=1,G(2)=2
这是一个类斐波那契数列的表达式，这类表达式的解法可以使用递归算法，也可使用迭代算法，由于要保证时间效率，因此我们会选择实现较复杂，但时间复杂度更低的迭代算法
迭代算法的主要实现代码为
int lad1 = 1， lad2 = 2;
for (int x = 3; x <= n; x++)
{ method.push_back(lad1 + lad2);//将此元素存入数组
lad1 = lad2; lad2 = method[x];//lad1和lad2向后迭代
}
时间复杂度为：O(n)
代码实现
故围绕迭代算法，我们用C++代码进行青蛙跳算法的实现：
1.台阶问题类的实现
class ladder_question {
public:
ladder_question(int n) :ladder_number(n) { //构造类时将要求的阶梯数传入
method.push_back(0);
method.push_back(1);
method.push_back(2);//将method数组前三项特殊项先行存入
};
~ladder_question() { };//析构函数
long long int find_method();
private:
long long int ladder_number, lad1, lad2;
vector<long long int> method;
};
long long int ladder_question::find_method()//计算方案数函数实现
{
if (ladder_number == 0)
return 0;
else if (ladder_number == 1)
return 1;
else if (ladder_number == 2)
return 2;
else//当阶梯数大于或等于3时
{ lad1 = 1; lad2 = 2;
for (int x = 3; x <= ladder_number; x++)
{ method.push_back(lad1 + lad2);//将此元素存入数组
lad1 = lad2; lad2 = method[x];//lad1和lad2向后迭代
}
return method[ladder_number];//数组的第n项代表其对应n阶台阶的方案数
}
}
算法测试截图
1.功能测试：
2.边界测试：
3.性能测试：
