递归练习

一、汉诺塔

假设所有的盘子都在A柱，需要移动到C柱。
输入盘子的数量，输出移动的步骤。

#include<iostream>
using namespace std;

void hanoi(int n, char a, char b, char c)
{
    if(n != 1)
    {
        hanoi(n - 1, a, c, b);
        cout<<"把一个盘子从"<<a<<"移到"<<c<<endl;
        hanoi(n - 1, b, a, c);
    }
    else if(n == 1)
    {
        cout<<"把一个盘子从"<<a<<"移到"<<c<<endl;
    }
}

int main() 
{
    int n;
    char a = 'a', b = 'b', c = 'c';
    cin>>n;
    hanoi(n, a, b, c); 
    return 0;    
}

二、放苹果

把m个苹果放到n个盘子里，可以有空盘子。求有多少种算法？

例：

输入：7 3
输出：8

注：

不考虑盘子顺序，即1,5,1和5,1,1视作同一种放法

int apple(int m, int n)
{
    int x, emptyExist = 0;
    if( m == 1 && n == 1)
        return 1;
    else if(n > m)
    {
        return apple(m, m);
    }
    else if(m != 0 && n == 0)
    return 0;
    else if(m == 0)
    return 1;
    else if( n <= m)
    {
        return apple(m - n, n) + apple(m, n - 1);
    }
}           //在main函数里输入m和n后，输出apple(m, n)即可

三、求解理解错误的逆波兰表达式的值

写程序之前，理解错了逆波兰表达式的概念。
这一段里的逆波兰表达式的计算方法为：
输入一个待求解的逆波兰表达式input：
float input[] = {'/', '+', '/', 11, 22, 24, 20};
如上input的计算方式为 ： 20 / (24 + (22 / 11))

这种解法貌似有点儿笨

思路：

思路

代码：

#include<stdio.h>
#include<math.h>

float compute(float before[], int sizebefore, float after[], int sizeafter);
float reverse(float a[], int l);
float input[] = {'/', '+', '/', 11, 22, 24, 20};
float output[] = {'+', 11, 12};

float reverse(float a[], int l)
{
    int i;
    float b[l - 2];
    if(l == 3)
    {
        switch((int)a[0])           //a[2] 运算符 a[1]
        {
            case '+':
                return a[2] * 1.0 + a[1];
                break;
            case '-':
                return a[2] * 1.0 - a[1];
                break;
            case '*':
                return a[2] * 1.0 * a[1];
                break;
            case '/':
                return a[2] * 1.0 / a[1];
                break;
        }
    }
    else
    {
        for(i = 1; i <= l - 2; i++)
        {
            b[i - 1] = a[i];        //b[] 为 a[] 除去头和尾，即下一次递归的a[]
        }
        return compute(a, l, b, l - 2);     //a[l - 2] * reverse(b[])
    }
}
float compute(float before[], int sizebefore, float after[], int sizeafter)
{
    switch((int)before[0])
    {
        case '+':
            return before[sizebefore - 1] * 1.0 + reverse(after, sizeafter);
            break;
        case '-':
            return before[sizebefore - 1] * 1.0 - reverse(after, sizeafter);
            break;
        case '*':
            return before[sizebefore - 1] * 1.0 * reverse(after, sizeafter);
            break;
        case '/':
            return before[sizebefore - 1] * 1.0 / reverse(after, sizeafter);
            break;
    }
}
int main()
{
    float toBeSolved[];
    int sizeOf;                 //自行输入逆波兰表达式，To be continued
    printf("%f", reverse(input, sizeof(input) / sizeof(input[0])));
    return 0;
}

四、真·逆波兰表达式

真·逆波兰表达式的形式示意：
表达式：* / + 12 36 + 1 3 - 15 8
含义：((12 + 36) / (1 + 3)) * (15 - 8)
结果：84

思路：
定义一个返回表达式的值的函数。
输入，并将输入作为字符串处理。
若字符串第一个字符为运算符+,-,*,/，则接下来输入的肯定是连续两个逆波兰表达式，即再调用两次此函数，且这两个函数相加减乘除。
若字符串内第一个字符为数字，则调用atof()函数将数字转换为浮点数作为返回值。
注：若第一个字符为-，可能是遇到了负数，因此需在此中情形里加入一个判断，如果字符串长度strlen() 为1，则按运算符处理，否则按数字处理。

代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

float reverse()
{
    char a[10];
    scanf("%s", a);
    switch(a[0])
    {
        case '+':   return reverse() + reverse();
        case '-':   if(strlen(a) == 1) return reverse() - reverse();
                    else return atof(a);
        case '*':   return reverse() * reverse();
        case '/':   return reverse() / reverse();
        default:    return atof(a);
    }
}

int main()
{
    float a = reverse();
    printf("%.2f", a);
    return 0;
}