题解 | #24点运算#
24点运算
http://www.nowcoder.com/practice/7e124483271e4c979a82eb2956544f9d
题目有点问题
对于一个用例 K Q 6 K 明明有解为K-Q/6+K 但是给出的答案是输出 NONE
代码如下,应该是没问题的,没有什么更好的精妙解法了,差不多是直接暴力的,但是因为总共的选择有限,所以程序运行起来还是很快
#include<bits/stdc++.h>
using namespace std;
map<int,string> revmap;
void coutX(int a,int b,int c,int d,char op1,char op2,char op3){
string s;
vector<int> tt{a,b,c,d};
vector<char> opp{op1,op2,op3};
for(int i=0;i<4;i++){
int x=tt[i];
if(x>=2&&x<=9){
s=s+to_string(x);
}else{
s=s+revmap[x];
}
if(i<3){
s=s+opp[i];
}
}
cout<<s<<endl;
}
int count(int left,int right,char op){
if(op=='*'){
return left*right;
}else if(op=='/'){
return left/right;
}else if(op=='+'){
return left+right;
}else if(op=='-')return left-right;
cout<<"出错!"<<endl;
return 0;
}
bool twentyFour(int a,int b,int c,int d){
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl;
int aa=a,bb=b,cc=c,dd=d;
vector<char> operatorT={'+','-','*','/'};
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
a=aa,b=bb,c=cc,d=dd;//需要每次都初始化。。。。
char op1=operatorT[i];
char op2=operatorT[j];
char op3=operatorT[k];
if(i>=2){//第一个运算符为* / 优先级比较高
a=count(a,b,op1);
if(j>=2||k<2){
a=count(a,c,op2);
a=count(a,d,op3);
if(a==24){
coutX(aa,bb,cc,dd,op1,op2,op3);
return true;
}
}else{
if(k>=2){
c=count(c,d,op3);
a=count(a,c,op2);
if(a==24){
coutX(aa,bb,cc,dd,op1,op2,op3);
return true;
}
}
}
}else{//第一个不为* /
if(j>=2){
b=count(b,c,op2);
if(k>=2){
b=count(b,d,op3);
a=count(a,b,op1);
if(a==24){
coutX(aa,bb,cc,dd,op1,op2,op3);
return true;
}
}else{
//cout<<b<<" ";
a=count(a,b,op1);
//cout<<a<<" ";
a=count(a,d,op3);
//cout<<a<<" ";
if(a==24){
//cout<<aa<<op1<<bb<<op2<<cc<<op3<<dd<<endl;
coutX(aa,bb,cc,dd,op1,op2,op3);
return true;
}
}
}else{
if(k>=2){
c=count(c,d,op3);
a=count(a,b,op1);
a=count(a,c,op2);
if(a==24){
coutX(aa,bb,cc,dd,op1,op2,op3);
return true;
}
}else{
a=count(a,b,op1);
a=count(a,c,op2);
a=count(a,d,op3);
if(a==24){
coutX(aa,bb,cc,dd,op1,op2,op3);
return true;
}
}
}
}
}
}
}
return false;
}
int main(){
vector<string> s(4);
map<string,int> mp;
mp.insert(pair<string,int>("10",10));
mp.insert(pair<string,int>("A",1));
mp.insert(pair<string,int>("J",11));
mp.insert(pair<string,int>("Q",12));
mp.insert(pair<string,int>("K",13));
revmap.insert(pair<int,string>(10,"10"));
revmap.insert(pair<int,string>(1,"A"));
revmap.insert(pair<int,string>(11,"J"));
revmap.insert(pair<int,string>(12,"Q"));
revmap.insert(pair<int,string>(13,"K"));
while(cin>>s[0]>>s[1]>>s[2]>>s[3]){
if(s[0].size()>2||s[1].size()>2||s[2].size()>2||s[3].size()>2){
cout<<"ERROR"<<endl;
continue;
}
vector<int> model(4);
for(int i=0;i<4;i++)
if(s[i][0]>='2'&&s[i][0]<='9'){
model[i]=stoi(s[i]);
//cout<<model[i]<<" ";
}else{
model[i]=mp[s[i]];
//cout<<model[i]<<" ";
}
//接下来也许是一个四重循环来排列元素
/*for(auto x:model){
cout<<x<<" ";
}*/
//cout<<endl;
bool fin=false;
for(int i=0;i<4;i++){
if(fin)break;
for(int j=0;j<4;j++){
if(fin)break;
for(int k=0;k<4;k++){
if(fin)break;
for(int l=0;l<4;l++){
if(fin)break;
if(i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l){//每个元素各取一次
//cout<<i<<j<<k<<l<<endl;
int a=model[i],b=model[j],c=model[k],d=model[l];
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<endl;
if(twentyFour(a,b,c,d)){
fin=true;
}
}
}
}
}
}
if(!fin)//找不到时的输出
cout<<"NONE"<<endl;
}
return 0;
}
科大讯飞公司氛围 455人发布