任务描述
本关任务:计算逆波兰表达式的值。
相关知识
放苹果问题
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?
注意:5,1,1和1,5,1 是同一种分法。
我们可以先假设有一个函数count(m,n)能告诉我们m个苹果放n个盘子有多少种放法,然后在此基础上进行分析:
根据m和n之间的关系,可以分成以下两种情况来讨论:
①. 如果m小于n,即苹果(m)数比盘子(n)数小,那么无论怎么放,总是会至少有n - m个空盘子。因此可以得到:count(m,n) = count(m,m)。
②. 如果m大于等于n,即苹果数比盘子数多,或者相同,则有两种放置方法:
所有盘子都要放苹果。这个时候苹果中的**n个的位置已经固定**,只要考虑剩下m-n个,因此可以得到:count(m,n) = count(m - n,n)。
有盘子不放苹果。在这种情况中,我们可以只考虑有一个盘子不放。因为在不断的往下递的过程中,盘子数可以不断的减一,隐含了在m个苹果放在n - 1 ,n - 2 ... 2 ,1个盘子中的情况。这个时候可以得到count(m,n) = count(m,n - 1)。
综合以上两点,可以得到代码:
int count(int m,int n)
{
if(m < n)
return count(m,m);
else
return count(m - n,n) + count(m,n - 1); //两种放置方法的和
}
现在还差一个终止条件。考虑盘子数或者苹果数各为1或者0时,有:
盘子数为0或者1,苹果无论有多少都只有一种分配方法。
苹果数为0或者1,无论如何都只能放在一个盘子里。
即得到:
if(m <=1 || n <= 1)
return 1;
上下两段代码组合起来,就得到:
int count(int m,int n)
{
if(m <=1 || n <= 1)
return 1;
if(m < n)
return count(m,m);
else
return count(m - n,n) + count(m,n - 1); //两种放置方法的和
}
当我们输入2 2时,即count(2,2),得到的结果是:
2
即两种放法:每个盘子放一个苹果,或者两个苹果放在一个盘子里。
总的来说,利用递归进行自动分析的方法如下:
先假设有一个函数能给出答案。
再利用这个函数,分析如何解决问题。
搞清楚最简单的情况下答案是什么。
编程要求
逆波兰表达式是一种把运算符前置的算术表达式,如:
2 + 3的逆波兰表示法为+ 2 3。
(2 + 3) * 4的逆波兰表示法为* + 2 3 4。
现在请你编写一个程序,读取一段正确的逆波兰表达式,计算并输出它的结果。
输入的表达式中只有+ - * /四种运算符,且数字均为**1位,但是运算时要按照浮点数float**来运算。
请在右侧编辑器的Cal函数中,读取输入的逆波兰表达式,计算并输出结果,占一行。
输入数据需要学员自己读取。具体见测试说明。
测试说明
平台会对你编写的代码进行测试:
预期输入:+ 2 3
预期输出:5
预期输入:* + 2 3 4
预期输出:20
参考代码:
#include <iostream>
#include <cstdlib>
using namespace std;
/********** Begin **********/
//可以在此增加其他函数
float exp() {
char s[20];
cin >> s;
switch (s[0]) {
case '+':
return exp() + exp();
case '-':
return exp() - exp();
case '*':
return exp() * exp();
case '/':
return exp() / exp();
default:
return atof(s);
}
}
void Cal() {
//在此补充代码完成函数功能
cout << exp() << endl;
}
/********** End **********/
标签:count,return,函数,递归,int,苹果,exp,程序设计,盘子
From: https://blog.csdn.net/Whovian_Z/article/details/140964410