目录
一个函数调用其自身，就是递归
- 1) 替代多重循环
- 2) 解决本来就是用递归形式定义的问题
- 3) 将问题分解为规模更小的子问题进行求解
A.汉诺塔
问题描述
有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆： 每次只能移动一个圆盘； 大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。
问：如何移？最少要移动多少次？
汉诺塔示意图如下：
三个盘的移动：
输入
输入为一个整数后面跟三个单字符字符串。
整数为盘子的数目，后三个字符表示三个杆子的编号。
3 a b c输出
输出每一步移动盘子的记录。一次移动一行。
每次移动的记录为例如3:a->b 的形式，即把编号为3的盘子从a杆移至b杆。
我们约定圆盘从小到大编号为1, 2, ...n。即最上面那个最小的圆盘编号为1，最下面最大的圆盘编号为n。
1:a->c
2:a->b
1:c->b
3:a->c
1:b->a
2:b->c
1:a->c题目解答
解法的基本思想是递归。假设有A、B、C三个塔，A塔有N块盘，目标是把这些盘全部移到C塔。那么先把A塔顶部的N-1块盘移动到B塔，再把A塔剩下的大盘移到C，最后把B塔的N-1块盘移到C。 每次移动多于一块盘时，则再次使用上述算法来移动。
#include <stdio.h>
void Hanoi(int n,char src,char mid,char dest)
//将src座上的n个盘子，以mid座为中转，移动到dest座
{
if(n==1)//只需移动一个盘子
{
printf("%d %c->%c\n",n,src,dest);//直接将盘子从src移动到dest即可
return;
}
else
{
Hanoi(n-1,src,dest,mid); //先将n-1个盘子从src移动到mid
printf("%d %c->%c\n",n,src,dest);//再将一个盘子从src移动到dest
Hanoi(n-1,mid,src,dest); //最后将n-1个盘子从mid移动到dest
return;
}
}
int main()
{
int n;
scanf("%d",&n);
Hanoi(n ,'A','B','C');
return 0;
}
B.N皇后
题目描述
输入一个正整数N，则程序输出N皇后问题的全部摆法。输出结果里的每一行都代表一种摆法。行里的第i个数字如
果是n，就代表第i行的皇后应该放在第n列。
皇后的行、列编号都是从1开始算。
输入
4输出
2 4 1 3
3 1 4 2题目解答
用递归解决，一行一行的排查存在的可能性
#include <stdio.h>
#include <math.h>
int N;
int queenPos[100];//用来存放算好的皇后位置。最左上角是(0,0)
void NQueen (int k)//在0~k-1行皇后已经摆好的情况下，摆第k行及其后的皇后
{
int i;
if( k == N )// N 个皇后已经摆好
{
for( i=0 ;i<N ;i++)
{
printf("%d ",queenPos[i]+1);
}
printf("\n");
return;
}
for( i=0 ;i<N ;i++)
{
int j;
for( j=0 ;j<k ;j++)//和已经摆好的 k 个皇后的位置比较，看是否冲突
{
if( queenPos[j] == i || fabs(queenPos[j]-i) == fabs(k-j) )
break;//冲突，则试下一个位置
}
if( j == k )//当前选的位置 i 不冲突
{
queenPos[k] = i; //将第k个皇后摆放在位置 i
NQueen(k+1);
}
}
}
int main()
{
scanf("%d",&N);
NQueen(0); //从第0行开始摆皇后
return 0;
}
C.波兰表达式
题目描述
波兰表达式是一种把运算符前置的算术表达式，例如普通的表达式2 + 3的波兰表示法为+ 2 3。波兰表达式的优点是运算符之间不必有优先级关系，也不必用括号改变运算次序，例如(2 + 3) * 4的波兰表示法为* + 2 3 4。本题求解波兰表达式的值，其中运算符包括+ - * /四个。
输入
输入为一行，其中运算符和运算数之间都用空格分隔，运算数是浮点数。
* + 11.0 12.0 + 24.0 35.0输出
输出为一行，表达式的值。
可直接用printf("%f\n", v)输出表达式的值v。
1357.000000提示
(11.0+12.0)*(24.0+35.0)
题目解答
#include <stdio.h>
#include <stdlib.h>
double exp()//读入一个逆波兰表达式，并计算其值
{
char s[20];
scanf("%s",s);
switch(s[0])
{
case '+':
return exp() + exp();
break;
case '-':
return exp() + exp();
break;
case '*':
return exp() * exp();
break;
case '/':
return exp() / exp();
break;
default://输入的为数字直接进行运算
return atof(s);
break;
}
}
int main()
{
printf("%lf",exp());
return 0;
}
D.表达式求值
题目描述
求一个可以带括号的小学算术四则运算表达式的值
输入
一行，一个四则运算表达式。'*'表示乘法，'/'表示除法
3.47+8.33+4.5*(7+2)*(3)*((3+4)*(2+3.5)/(4+5))-34*(7-(2+3))输出
一行，该表达式的值，保留小数点后面两位
3.4015.30454.75题目解答（x）
表达式是个递归的定义
#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>
int expression_value()//求一个表达式的值
{
int result = term_value();//求第一项的值
bool more = true;
while(more)
{
char op = cin.peek();//看一个字符,不取走
if ( op == '+' || op == '-')
{
op =getchar();//从输入中取走一个字符
int value = term_value();
if( op == '+')
result += value;
else
result -= value;
}
else
more = false;
}
return result;
}
int term_value()//求一个项的值
{
int result = factor_value();//求第一个因子的值
while(true)
{
char op =getchar();
if( op == '*' || op == '/')
{
op = cin.peek();//看一个字符,不取走
int value = factor_value();
if( op == '*')
result *=value;
else
result /=value;
}
else
break;
}
return result;
}
int factor_value()
{
int result = 0;
char c = cin.peek();//看一个字符,不取走
if( c == '(')
{
c =getchar();
result =expression_value();
c =getchar();
}
else
{
while( isdigit(c) )
{
result = 10 * result + c - '0';
c =getchar();
c = cin.peek();//看一个字符,不取走
}
}
return result;
}
int main()
{
printf("%d",expression_value() );
return 0;
}
E.爬楼梯
题目描述
树老师爬楼梯，他可以每次走1级或者2级，输入楼梯的级数，求不同的走法数
例如：楼梯一共有3级，他可以每次都走一级，或者第一次走一级，第二次走两级
也可以第一次走两级，第二次走一级，一共3种方法。
输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 30
5
8
10输出
不同的走法数，每一行输入对应一行输出
8
34
89题目解答
n级台阶的走法 = 先走一级后，n-1级台阶的走法 + 先走两级后，n-2级台阶的走法
f(n) = f(n-1) + f(n-2)边界条件： n < 0 0 n = 0 1 n = 1 1
n = 0 1 n = 1 1 n = 2 2
#include <stdio.h>
int N;
int stairs(int n)
{
if( n < 0)
return 0;
if( n == 0)
return 1;
return stairs(n-1) + stairs(n-2);
}
int main()
{
scanf("%d",&N);
while(N)
{
printf("%d",stairs(N) );
}
return 0;
}
F.放苹果
题目描述
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
1
7 3输出
对输入的每组数据M和N，用一行输出相应的K。
8题目解答
设i个苹果放在k个盘子里放法总数是 f(i,k)，则：
k > i 时， f(i,k) = f(i,i)
k <= i 时，总放法 = 有盘子为空的放法+没盘子为空的放法
f(i,k) = f(i,k-1) + f(i-k,k)
边界条件：没有苹果或者没有盘子；
#include <stdio.h>
int f( int m,int n)
{
if( n > m)
return f(m,m);
else if( m == 0)
return 1;
else if( n <= 0)
return 0;
else
return f(m,n-1) +f (m-n,n);
}
int main()
{
int t;
scanf("%d",&t);
while( t--)
{
int m,n;
scanf("%d %d",&m,&n);
printf("%d",f(m,n) );
}
return 0;
}
