一、汉诺塔
假设所有的盘子都在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;
}
