1、数组逆序重放
描述
将一个数组中的值按逆序重新存放。例如，原来的顺序为8,6,5,4,1。要求改为1,4,5,6,8。
输入
输入为两行：第一行数组中元素的个数n（1<n<100)，第二行是n个整数，每两个整数之间用空格分隔。
输出
输出为一行：输出逆序后数组的整数，每两个整数之间用空格分隔。
样例输入
5
8 6 5 4 1
样例输出
1 4 5 6 8
代码
体会递归3大性质：1、规模缩小，问题不变。2、倒着想。3、递归树
#include <cstdio>
using namespace std;
const int N=1e5+10;
int n,a[N];
void ni(int u){
if(u>=n) return;
ni(u+1);
printf("%d ",a[u]);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
ni(0);
return 0;
}
2、逆波兰表达式
描述
逆波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值，其中运算符包括+ - * /四个。
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
输出
输出为一行，表达式的值。
可直接用printf(“%f\n”, v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
提示
可使用atof(str)把字符串转换为一个double类型的浮点数。atof定义在math.h中。
此题可使用函数递归调用的方法求解。
代码
#include <cstdio>
#include <cstdlib>
using namespace std;
char str[10];
double dfs(){
scanf("%s",str);
switch(str[0]){
case '+':return dfs()+dfs();
case '-':return dfs()-dfs();
case '*':return dfs()*dfs();
case '/':return dfs()/dfs();
default:return atof(str);
}
}
int main(){
double ans=dfs();
printf("%lf\n",ans);
return 0;
}
dfs函数的if写法
double dfs(){
scanf("%s",str);
if(str[0]!='\0'){
if(str[0]=='+') return dfs()+dfs();
else if(str[0]=='-') return dfs()-dfs();
else if(str[0]=='*') return dfs()*dfs();
else if(str[0]=='/') return dfs()/dfs();
else return atof(str);
}
}
3、汉诺塔问题
描述
约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆，最左边的杆上自上而下、由小到大顺序串着由64个圆盘构成的塔。目的是将最左边杆上的盘全部移到中间的杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。
这是一个著名的问题，几乎所有的教材上都有这个问题。由于条件是一次只能移动一个盘，且不允许大盘放在小盘上面，所以64个盘的移动次数是：18,446,744,073,709,551,615
这是一个天文数字，若每一微秒可能计算(并不输出)一次移动，那么也需要几乎一百万年。我们仅能找出问题的解决方法并解决较小N值时的汉诺塔，但很难用计算机解决64层的汉诺塔。
假定圆盘从小到大编号为1, 2, …
输入
输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。
输出
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如 a->3->b 的形式，即把编号为3的盘子从a杆移至b杆。
样例输入
2 a b c
样例输出
a->1->c
a->2->b
c->1->b
代码
#include<iostream>
using namespace std;
//先把n-1个从a->c，再把最后一个a->b,最后把c上的n-1个c->b(同样问题，缩小规模）
void f(int n,char a,char b,char c){
//从a移动到b，c是辅助的
if(n==0)return;
if(n==1)cout<<a<<"->"<<n<<"->"<<b<<endl;
else{
f(n-1,a,c,b);//将n-1个盘子从a移动到c,b是辅助的
cout<<a<<"->"<<n<<"->"<<b<<endl;//然后将第n个柱子 由a 移到 b即可
f(n-1,c,b,a);//剩下的 再将n-1个盘子 由c移到b 其中a为辅助柱子
}
}
int main(){
int n;
char a,b,c;
cin>>n>>a>>b>>c;
f(n,a,b,c);
}
4、放苹果
描述
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
1
7 3
样例输出
8
#include <cstdio>
using namespace std;
int m,n,t;
int dfs(int m,int n){
if(n>m) return dfs(m,m);
if(m==0) return 1;//虽然题目m>=1,但递归时会出现m=0的情况
if(n==0) return 0;
return dfs(m,n-1)+dfs(m-n,n);
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d%d",&m,&n);
int ans=dfs(m,n);
printf("%d\n",ans);
}
return 0;
}
5、排队游戏
描述
在幼儿园中，老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中，每个小孩按其在队列中的位置发给一个编号（编 号从0开始）。然后老师告诉小朋友们，站在前边的小男孩可以和他后边相邻的小女孩手拉手离开队列，剩余的小朋友重新站拢，再按前后相邻的小男孩小女孩手拉 手离开队列游戏，如此往复。由于教师精心的安排，恰好可以保证每两个小朋友都能手拉手离开队列，并且最后离开的两个小朋友是编号最小的和最大的两个小朋 友。（注：只有小男孩在前，小女孩在后，且他们两之间没有其他的小朋友，他们才能手拉手离开队列）。请根据老师的排队，按小女孩编号从小到大的顺序，给出 所有手拉手离开队列的小男孩和小女孩的编号对。
输入
用一个字符串代表小朋友队列。字符串中只会出现两个字符，分别代表小男孩和小女孩，首先出现的字符代表小男孩，另一个字符代表小女孩。小孩总数不超过100
输出
按小女孩编号顺序，顺序输出手拉手离开队列的小男孩和小女孩的编号对，每行一对编号，编号之间用一个空格分隔。
样例输入
((()(())())(()))
样例输出
2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15
#include <cstdio>
using namespace std;
char boy,str[110];
int fun(int u){
//两层意思，一，不是boy则是girl并返回下标。二、不是boy是空字符返回并结束
if(str[u]!=boy) return u;
int v=fun(u+1);
printf("%d %d\n",u,v);
return fun(v+1);
}
int main(){
scanf("%s",str);
boy=str[0];
fun(0);
return 0;
}
