II.-递归

目录

A.汉诺塔

B.N皇后

C.波兰表达式

D.表达式求值

E.爬楼梯

F.放苹果

---

一个函数调用其自身，就是递归

• 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 
 
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 
#include 
 
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
        {
            printf("%d ",queenPos[i]+1);
        }
        printf("\n");
        return;
    }
    for( i=0 ;i
    {
        int j;
        for( j=0 ;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 
#include 
 
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.4

7+8.3

3+4.5*(7+2)*(3)*((3+4)*(2+3.5)/(4+5))-34*(7-(2+3))

输出

一行，该表达式的值，保留小数点后面两位

3.40

15.30

454.75

题目解答（x）

表达式是个递归的定义

 

#include 
#include 
#include 
 
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 
 
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 
 
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;
}