problem
- 给定4个数,加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。
- 问是否存在一种方式使得得到的表达式的结果等于24。
solution
正常的中缀表达式枚举和计算难度都约等于0,麻烦的是括号的枚举和处理。
这里只要求满足的结果,所以换一种方式拿掉括号——打乱顺序即可(括号的用处本质就是改变运算顺序),,
- 做法就是通过枚举排列或者随机运算的方式去掉括号,剩余的运算符和数字丢到一起DFS即可。
- 具体写法就是每次从剩余的数中随机取出两个数,并用加减乘除合并它们。
- 小技巧:用排序代替数组来去掉不用位置写起来比较简单。(避免枚举的时候判断,也优化了效率。
codes
#include
#include
#include
using namespace std;
const int uinf = -10000000;//过程值可以为负,所以要够小
double a[5]; bool flag;
double opv(double x, double y, int op){
if(op==1)return x+y;
if(op==2)return x-y;
if(op==3)return x*y;
if(op==4)return x/y;
}
void dfs(int x){
sort(a+1,a+5);//用排序的方法把位置去掉
if(flag)return ;
if(x == 4){
if(abs(a[4]-24)>a[1]>>a[2]>>a[3]>>a[4] && a[1]){
flag = 0;
dfs(1);
if(flag)cout
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net