洛谷【C++编程基础】递归函数初步 专题解题报告
T1-T89304 递归求和
题目描述
用递归的方法求1+2+3+4+…+(n-1)+n的值。
输入格式
一个整数n。（1<=n<=10000）.
输出格式
一个整数，数列的和。
输入输出样例
输入
10
输出
55
创新互联企业建站,十余年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于网站设计、做网站中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。
题目出处
题目要求：用递归的方法求1+2+3+4+…+(n-1)+n的值。
#includeusing namespace std;
int f(int a){if(a==1)return 1;//边界
return (a+f(a-1));//递归关系式
}
int main(){int n;
cin>>n;
cout<
T2-T89307 Hermite多项式
题目描述
用递归的方法求Hermite多项式的值
对给定的实数x和正整数n，求多项式值。
中间的Hermite图片
输入格式
两个数x，n。用空格隔开。(－1输出格式
一个数，函数值。(保留两位小数)
输入输出样例
输入
-0.10 1
输出
-0.20
题目出处
递归关系式已经给出来了，照着写呗。
#includeusing namespace std;
double n,x;//注意数据类型
double f(double n,double x){if(n==0)return 1;
if(n==1)return 2*x;
return 2*x*f(n-1,x)-2*(n-1)*f(n-2,x);//照着图片写呗
}
int main(){cin>>x>>n;
cout<
T3-T89310 递归函数求值1
题目描述
已知图片
用递归方法求解。
输入格式
一行有两个整数x和n，用空格隔开。（1输出格式
一个实数，即函数值。（保留两位小数）
输入输出样例
输入
24499 8564
输出
2.86
题目出处
这一题比上一题略麻烦一点儿，要自己分析。
递归关系：f(x,n)=[n+f(n-1)]/x
边界：n=1时 return (1+x)/x
（或：当n=0时return x）
#includeusing namespace std;
int n,x;
double f(double x,double n){if(n==1)return x/(1+x);
return x/(n+f(x,n-1));
}
int main(){cin>>x>>n;
cout<
T4-T89314 递归函数求值2
题目描述
已知
图片
根据x，n的值计算函数值。
输入格式
用空格隔开的两个数，实数x(0输出格式
函数值。保留两位小数。
输入输出样例
输入
4.2 10
输出
3.68
题目出处
递归关系：f(x,n)=sqrt(n+f(x,n-1))
边界：当n=1时return sqrt(1+x)
（或：当n=0时return x）
#includeusing namespace std;
float n,x;
double f(double x,double n){if(n==1)return sqrt(1+x);
return sqrt(n+f(x,n-1));
}
int main(){cin>>x>>n;
cout<
T5-T89316 汉诺塔问题
题目描述
如图，设有n个大小不等的中空圆盘，按照从小到大的顺序迭套在立柱A上，另有两根立柱B和C。现要求把全部圆盘从A柱（源柱）移到C柱（目标柱），移动过程中可借助B柱（中间柱）。移动时有如下的要求：
1、一次只许移动一个盘。
2、任何时候任何柱子上不允许把大盘放在小盘上边。
3、可使用任意一根立柱暂存圆盘。
问：如何用最少步数实现n个盘子的移动，请打印出方案。
输入格式
一个整数n(3<=n<=16)
输出格式
输出移动最少的方案，每行表示一次移动，如A－>B表示将A柱上最上面的圆盘移动到B柱上。
最后一行输出最少的步数。
图片
输入输出样例
输入
3
输出
A->C
A->B
C->B
A->C
B->A
B->C
A->C
7
题目出处
其实，可以将移动n个圆盘到目标柱理解为将(n-1)个圆盘移动到中间柱+移动第n个到目标柱+将(n-1)个圆盘移动到目标柱
也就是（递归关系式）
hanot(n-1,a,c,b);//(n-1)个圆盘移动到中间柱
cout<"<
边界
if(n==1)将这根柱子移动到目标柱
由于题目要步数，就设成了有返回值的（也可以定义全局变量替代）
#includeusing namespace std;
int n;
int hanot(int n,char a,char b,char c){//a目标柱,b中间柱，c目标柱
if(n==1){cout<"<"<cin>>n;
cout<
T6-T90615 字符串逆序
题目描述
输入一串以‘!’结束的字符，按逆序输出。（请用递归完成）
输入格式
一行字符串（以！结束）（字符串长度不超过100）
输出格式
逆序输出。
输入输出样例
输入
abc!
输出
!cba
题目出处
这是我一开始的程序：
#includeusing namespace std;
string s;
string f(string s){int pos=s.size();
if(pos==1)return s;
char er=s[pos-1];
string st;
for(int i=0;icin>>s;
cout<
现在发现太繁琐：
#includeusing namespace std;
string s;
int pos;//全局变量，以便用于递归（当然，可以通过传参代替）
void f(int n){if(ncin>>s;
pos=s.size();
f(0);
cout<
呸呸，更正！！！
测试数据太弱了，竟然没测出BUG！！！
（将
cin>>s;
改为
getline(cin,s);
）
当然，还可以这样做：
#includeusing namespace std;
int pos;
void f(){char fox;
cin>>fox;
if(fox=='!'){cout<<"!";
return;
}//边界
f();
cout<f();
cout<
但注意！！！这个的BUG也是不能输入空格。将
cin>>fox;
改为
fox=getchar();
即可。
T7-T90627 费波那契数列
1,1,2,3,5,8,13,…
这是著名的斐波那契（Leonardo Pisano ,Fibonacci, Leonardo Bigollo，1175-1250）发现的数列。其中，每两项都等于前二项之和（第1,2项是1）。
题目描述
1，1，2，3，5，8，13，21，34，55……从第三项起，每一项都是紧挨着的前两项的和。
以上就是斐波那契数列。
输入第几项，输出第几项的值。（请用递归完成）
输入格式
一个正整数n,<=30
输出格式
第n项的值
输入输出样例
输入
4
输出
3
题目出处
递归关系：f(n)=f(n-1)+f(n-2)
边界：当n==1或2时return 1
代码
#includeusing namespace std;
long long n,dp[110];//dp为记忆化数组，以空间换时间（当然本题数据较小，可以不用记忆化，并且可以不开long long）
long long f(long long n){if(n<=2){return 1;
}//边界
if(dp[n])return dp[n];
dp[n]=f(n-1)+f(n-2);
return dp[n];
}
int main(){cin>>n;
cout<
当然，还得展示一下我个人的奇葩代码，思路奇怪。（简直不能说是递归）像函数实现for循环
#includeusing namespace std;
int n,s=2;
int f(int a,int b){++s;
int c=a+b;
if(s==n)return c;
return f(b,c);
}
int main(){cin>>n;
if(n==1||n==2)cout<<1<
当然，再展示一下for循环代码
#includeusing namespace std;
long long n,dp[110];
int main(){cin>>n;
dp[1]=dp[2]=1;
for(int i=3;i<=n;++i)dp[i]=dp[i-1]+dp[i-2];
cout<
T8-T90628 F91
题目描述
麦卡锡是一个有名的计算机科学专家，在他的著作中，他定义了一个被称为"F91"的递归函数，这个函数是这样获得的：输入一个正整数N，按如下定义返回一个正整数：
If N ≤ 100, then f91(N) = f91(f91(N+11));
If N ≥ 101, then f91(N) = N-10
编写程序计算出麦卡锡的F91函数
输入格式
输入数据包含一系列的正整数，每个正整数大不超过1,000,000，每个正整数占一行，当遇到数字0时表示输入结束。注意数字0不是测试数据，仅代表结束标志。
输出格式
输出数据每行应包含一个测试结果，具体格式见输出样例，等号两侧各有一个空格。
输入输出样例
输入
91
622
1997
0
输出
f91(91) = 91
f91(622) = 612
f91(1997) = 1987
说明/提示
输入数据保证你用直接递归不会超时。
题目出处
既然题目给出了递归关系式，并保证“直接递归不会超时”，那就写呗。
#includeusing namespace std;
int s=1;
int f(int s){if(s<=100)return f(f(s+11));//递归关系
return s-10;
}
int main(){while(s!=0){cin>>s;
if(s!=0){ cout<<"f91("<
T9-T90630 大公约数与最小公倍数
题目描述
输入两个数，求他们的大公约数和最小公倍数。（请用递归完成）
输入格式
输入一行，两个正整数。
输出格式
输出一行，两个正整数（这两个正整数的大公约数和最小公倍数），用一个空格隔开。
输入输出样例
输入
18 20
输出
2 180
说明/提示
所有数据保证小于2^31-1
题目出处
既然是大公约数，肯定用“辗转相除法”。不了解的同学推荐看这篇C++辗转相除法详解，而大公倍数就是(设大公约数为x)(a/x)*(b/x)x=ab/x。可以参考这篇大公约数和最小公倍数的关系。
这题要递归实现（平常用的是迭代实现）
递归关系：f(a,b)=f(b,a%b)
边界：b==0时return a
附上我一开始的代码：
#includeusing namespace std;
int f(int a,int b){int c=b;
b=a%b;
a=c;
if(b==0)return a;
return f(a,b);
}
int main(){int n,a;
cin>>n>>a;
cout<
发现一种简洁优美的写法：（不会"? : "的同学可以看这篇C++中“?”的意思）
#includeusing namespace std;
long long a,b;
long long f(long long a,long long b){return b?f(b,a%b):a;
}
int main(){cin>>a>>b;
cout<
T10-T90632 十进制转八进制
题目描述
把任一给定的十进制正整数（<=32000）转换成八进制数后输出。（请用递归完成）
输入格式
一个十进制数。
输出格式
转换后的八进制数
输入输出样例
输入
100
输出
144
题目出处
额……先来演示一下通常做法：
#includeusing namespace std;
long long a,b,i=1;
int main(){cin>>a;
while(a>0){b+=a%8*i;
a/=8;
i*=10;//算位权
}
cout<
简洁吧。。。下一步演示递归：
#includeusing namespace std;
int f(int n){if(n<8)return n;//也可以将边界改为0
return n%8+f(n/8)*10;
}
int main(){int n;
cin>>n;
cout<
还可以这么做
#includeusing namespace std;
void f(int n){if(n/8)f(n/8);
cout<int n;
cin>>n;
f(n);
return 0;
}
T11-T90633 走台阶
题目描述
楼梯有n阶台阶,上楼可以一步上一阶,也可以一步上二阶。用递归的方法编一程序计算共有多少种不同的走法。（试用递归完成，会出现什么问题，如何解决）
输入格式
一个正整数n（n不超过90）
输出格式
一个整数，表示走法方案数。
输入输出样例
输入
4
输出
5
题目出处
我第一秒想到的是暴力……（造化低了）33分
#includeusing namespace std;
int n,cnt;
void f(int s){if(s==n){++cnt;
return;
}
if(s>n)return;
for(int i=1;i<=2;++i)
f(s+i);
return;
}
int main(){cin>>n;
f(0);
cout<
仔细对比数据，竟发现答案是斐波那契数列！！！
自制奇葩递归
#includeusing namespace std;
long long n,ans,vh[100];
void f(int s){if(s<3){if(s==2)cout<<3<cout<vh[0]=1;//这一行加上只是为了对比发现斐波那契，可删除
vh[1]=1;
vh[2]=2;
cin>>n;
f(3);
return 0;
}
标程：
#includeusing namespace std;
long long dp[110];//记忆化
long long f(long long n){if(dp[n])return dp[n];
if(n<=2)return n;//注意这个地方与标准斐波那契不同（因为这一题第n个答案是第(n+1)个斐波那契数，忘记的同学可以向上翻翻T7，这里原是return 1）
else dp[n]=f(n-1)+f(n-2);
return dp[n];
}
int main(){int n;
cin>>n;
cout<
刨根问底的同学可以继续看：
QUESTION:为什么答案是斐波那契数列？
ANSWER:上面我们用的是归纳的方法。下面主要介绍原因：
第1,2个台阶分别有1,2种走法（1）（1+1或2）
而从第3个开始，每一个数目（假设是第n个（n>2））都可以理解为第(n-1)的走法再走1级台阶或第(n-2)的走法再走2级台阶，自然就有第(n-1)，第(n-2)的走法总数和数量的方法。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前题目：洛谷【C++编程基础】递归函数初步专题解题报告-创新互联
本文来源：
http://csdahua.cn/article/igpic.html
