一:习题讲解:跳级
先把题目贴出来:
跳级
题目描述
小明共有n个年级要读,每一次他可以向上升1级,升2级或者升3级,请问共有多少种不同的升级方法。例如n=3时共有四种升级方法:可以先升1级再升2级,或者先升2级再升1级,或者每次都升1级,或者直接升3级。请问共有多少种升级方法可以正好走完n级。
输入输出格式
输入格式
输入文件level.in 输入一个正整数n(n<=50)
输出格式
输出文件level.out 输出一个正整数。
输入输出样例
输入样例#1:
3
输出样例#1:
4
输入样例#2:
4
输出样例#2:
7
从题目的描述中,我们很容易得到递推式f[i]=f[i-1]+f[i-2]+f[i-3]
接下来就很好办,本蒟蒻就先不多说了,直接给出标程:
include[HTML_REMOVED]
using namespace std;
long long f[100]={1,1,2};
int main(){
freopen(“level.in”,”r”,stdin);
freopen(“level.out”,”w”,stdout);
int n;
cin>>n;
for(int i=3;i<=n;++i){
f[i]=f[i-1]+f[i-2]+f[i-3];
}
cout<[HTML_REMOVED]=4时,增长速度简直快到惊人
分析:我们根据“书籍内容”的那个例子可以知道递归如果没有边界,便会发生死循环
所以我们可以把m=0和n=0当做边界
函数如下:
int ack(int m,int n){
while(m!=0){
if(n==0) n=1;
else{
n=ack(m, n-1);
}
m–;
}
return n+1;
}
总结:一个递归函数必须拥有边界和递归式,否则会陷入死循环(这条尤其重要!!!!!!!!!)
练习:最大公约数
题目描述
请写一个程序,输入是两个正整数,输出他们的最大公约数。
输入输出格式
输入格式
输入文件gcd.in 输入两个整数,均不超过10000。
输出格式
输出文件gcd.out 输出一个整数。
输入输出样例
输入样例#1:
48 32
输出样例#1:
16
本章练习 鼓励使用 递归 和 非递归 两种方法哦