二十四点"/>
CCF算法笔记2 二十四点
分析:题目很容易理解,我们只需要模拟四则运算即可,题目设限简单,我们只需要进行四个个位数的加减乘除运算即可,并且还不包括括号。当结果等于24时,即可输出结果“Yes”,否则输出“No”。
这道题的解题方法有很多,
- 首先最简单的暴力法,因为只设计到四个个个位数加减,我们只需要把所有情况都列出来即可,一共4^3=64种,这种方法空间占用比较少,因为没有涉及到STL,但是时间比较多,因为需要逐个判断。
- 经典的四则运算用到的栈的方法,生成两个栈,分别保存数字和符号,当遇到+、-时符号直接入栈,当遇到*、/时,先计算符号前后两个数再入栈,最后遍历数字栈,插入+、-号,通过数字出栈入栈,栈得到的最后一个数即最终结果。
代码,穷举法的:
#include <iostream> //头文件不需要这么多,习惯粘上所有的
#include <cstdio>
#include <set> //自动排序, 不可重复 unordered_set
#include <sstream>
#include <string> //char[] , string
#include <typeinfo>
#include <algorithm> //sort() cmp
#include <vector>
#include <map> //map a; a.insert(pair<,>,()) a[10]="qewe";
#include <cctype>
#include <iomanip> //cout<<setw(10)<<left
#include <queue>
#include <cmath>//printf("%.2f",a)
using namespace std;int main()
{int n;cin>>n;while(n--){int r=0;int a=0,b=0,c=0,d=0;string s;cin>>s;a=s[0]-'0';b=s[2]-'0';c=s[4]-'0';d=s[6]-'0';//暴力循环if(s[1]=='+'){ if(s[3]=='+'){if(s[5]=='+') r=a+b+c+d;else if(s[5]=='-') r=a+b+c-d;else if(s[5]=='/') r=a+b+c/d;else r=a+b+c*d;}else if(s[3]=='-') {if(s[5]=='+') r=a+b-c+d;else if(s[5]=='-') r=a+b-c-d;else if(s[5]=='/')r=a+b-c/d;else r=a+b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a+b/c+d;else if(s[5]=='-') r=a+b/c-d;else if(s[5]=='/') r=a+b/c/d;else r=a+b/c*d;}else {if(s[5]=='+') r=a+b*c+d;else if(s[5]=='-') r=a+b*c-d;else if(s[5]=='/')r=a+b*c/d;else r=a+b*c*d;}}else if(s[1]=='-') { if(s[3]=='+'){if(s[5]=='+') r=a-b+c+d;else if(s[5]=='-') r=a-b+c-d;else if(s[5]=='/')r=a-b+c/d;else r=a-b+c*d;}else if(s[3]=='-') {if(s[5]=='+') r=a-b-c+d;else if(s[5]=='-') r=a-b-c-d;else if(s[5]=='/')r=a-b-c/d;else r=a-b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a-b/c+d;else if(s[5]=='-') r=a-b/c-d;else if(s[5]=='/') r=a-b/c/d;else r=a-b/c*d;}else {if(s[5]=='+') r=a-b*c+d;else if(s[5]=='-') r=a-b*c-d;else if(s[5]=='/')r=a-b*c/d;else r=a-b*c*d;}}else if(s[1]=='/'){ if(s[3]=='+'){if(s[5]=='+') r=a/b+c+d;else if(s[5]=='-') r=a/b+c-d;else if(s[5]=='/')r=a/b+c/d;else r=a/b+c*d;}else if(s[3]=='-') {if(s[5]=='+')r=a/b-c+d;else if(s[5]=='-') r=a/b-c-d;else if(s[5]=='/')r=a/b-c/d;else r=a/b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a/b/c+d;else if(s[5]=='-') r=a/b/c-d;else if(s[5]=='/')r=a/b/c/d;else r=a/b/c*d;}else {if(s[5]=='+') r=a/b*c+d;else if(s[5]=='-') r=a/b*c-d;else if(s[5]=='/') r=a/b*c/d;else r=a/b*c*d;}}else { if(s[3]=='+'){if(s[5]=='+') r=a*b+c+d;else if(s[5]=='-') r=a*b+c-d;else if(s[5]=='/')r=a*b+c/d;else r=a*b+c*d;}else if(s[3]=='-') {if(s[5]=='+')r=a*b-c+d;else if(s[5]=='-') r=a*b-c-d;else if(s[5]=='/')r=a*b-c/d;else r=a*b-c*d;}else if(s[3]=='/'){if(s[5]=='+') r=a*b/c+d;else if(s[5]=='-') r=a*b/c-d;else if(s[5]=='/')r=a*b/c/d;else r=a*b/c*d;}else {if(s[5]=='+') r=a*b*c+d;else if(s[5]=='-') r=a*b*c-d;else if(s[5]=='/') r=a*b*c/d;else r=a*b*c*d;}}// cout<<r<<endl;if(r==24) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
栈的方法,这个是我自己写的,测试没有问题,但是有部分测试点无法通过,有大神知道问题可以给我说一下,,
#include <iostream>
#include <cstdio>
#include <set> //自动排序, 不可重复 unordered_set
#include <sstream>
#include <string> //擦汗ar[] , string
#include <typeinfo>
#include <algorithm> //sort() cmp
#include <vector>
#include <map> //map a; a.insert(pair<,>,()) a[10]="qewe";
#include <cctype>
#include <iomanip> //cout<<setw(10)<<left
#include <queue>
#include <cmath>//printf("%.2f",a)
#include <stack>
using namespace std;int main()
{int n;cin>>n;while(n--){int r=0;string s;cin>>s;stack<int> shu;stack<char> fu; //×//利用栈的思想,构造两个栈,遇到乘除优先计算后再入栈,加减直接入栈for(int i=0;i<7;i++){if(s[i]>='0' &&s[i]<='9')//数字入栈 shu.push(s[i]-'0');else {if(s[i]=='+' ||s[i]=='-'){fu.push(s[i]);}else if(s[i]=='/'){//int n;n=shu.top()/(s[i+1]-'0');shu.pop();shu.push(n);// cout<<"n="<<n<<endl;i++; }else {int n;n=shu.top()*(s[i+1]-'0');shu.pop();shu.push(n);// cout<<"n="<<n<<endl;i++; }}}while(shu.size()-1) {//当数字栈中至少存在两个元素时,进行加减 int a=shu.top();shu.pop();int b=shu.top();shu.pop();if(fu.top()=='+'){int c=a+b;shu.push(c);// cout<<"c+="<<c<<endl;}else if(fu.top()=='-'){int c=b-a;shu.push(c);// cout<<"c-="<<c<<endl;}else break;}r=shu.top();if(r==24) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}
下面推荐别人写的栈的方法,参见链接:添加链接描述
#include<cstdio>
#include<cstring>
#include<iostream>
#include<stack>
using namespace std;int n;
char a[10];stack<int> num;
stack<char> sign;
int all;
int main()
{cin>>n;getchar();for(int i=1;i<=n;i++){gets(a);all=0;while(!num.empty())num.pop();while(!sign.empty())sign.pop();int j=0;while(j<strlen(a)){if(a[j]<='9'&&a[j]>='0'){num.push(a[j]-'0');}elseif(a[j]=='+'){sign.push(a[j]);}elseif(a[j]=='-'){sign.push('+');num.push((a[j+1]-'0')*(-1));j++;}elseif(a[j]=='x'){int ans=num.top();num.pop();num.push(ans*(a[j+1]-'0'));j++;}else{int ans=num.top();num.pop();num.push(ans/(a[j+1]-'0'));j++;}j++;}while(!num.empty()){all+=num.top();num.pop();}if(all==24) printf("Yes\n");else printf("No\n");
}return 0;
}
更多推荐
CCF算法笔记2 二十四点
发布评论