24点是：一副牌中抽去大小王剩下52张牌），任意抽取4张牌，用加、减、乘、除（可加括号）把牌面上的数算成24。每张牌必须用一次且只能用一次，如抽出的牌是3、8、8、9，那么算式为
（ 9—8 ） ×8×3
（6-3）*10-6=24
主要形式及方法：
1.全部用加减法可以计算。（由于用技巧的思维惯性，这个容易疏忽）；
2.有1.2.3.4.6.8.12的牌，优先排除而算其他三张牌得到另一个符合的数；
3. 2张牌得一个数，另外两张牌得一个数，两者运算得24；
4. 比较特殊的（老师可能会考哦），要考虑分数的方法：举例 3，7，3，7
答案为（3+3/7）*7 = 24；
5. 大数 4，10，4，10答案为 （10*10-4）/4
网上代码
/**//*如题，不过这个24点与一般看到的程序实现方法不同，既没有波兰树，也没有像一役的那像产生所有的表达示然后，递归处理表达示，虽然这两个算法都不难但是我害怕写长的程序，所以自己用了一个相当很容易实现的方法。
f(s)=f(s-[r1,r2]+r1cmbr2)
其中的+ -为集合运算S为集合 cmb表示所胡的四则运算。*/
#include "stdafx.h"
#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
const int NUM_CAL = 24;
const int NUM_NUM = 4;
const double ERR = 1E-6;
double num[NUM_NUM];
string ans[NUM_NUM];
bool Search(int n)
{
if (n == 1) {
if (fabs(num[0] - NUM_CAL) < ERR) {
cout << ans[0] << "=24" << endl;
return true;
}
else {
return false;
}
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
double a, b;
string ansa, ansb;
a = num[i];
b = num[j];
num[j] = num[n-1];
ansa = ans[i];
ansb = ans[j];
ans[j] = ans[n-1];
num[i] = a + b;
ans[i] = "(" + ansa + "+" + ansb + ")";
if (Search(n - 1)) return true;
num[i] = a - b;
ans[i] = "(" + ansa + "-" + ansb + ")";
if (Search(n - 1)) return true;
num[i] = b - a;
ans[i] = "(" + ansb + "-" + ansa + ")";
if (Search(n - 1)) return true;
num[i] = a * b;
ans[i] = ansa + "*" +ansb;
if (Search(n - 1)) return true;
if (b != 0) {
num[i] = a/b;
ans[i] = ansa + "/" + ansb;
if (Search(n - 1)) return true;
}
if (a != 0) {
num[i] = b/a;
ans[i] = ansb + "/" + ansa;
if (Search(n - 1)) return true;
}
num[i] = a;
num[j] = b;
ans[i] = ansa;
ans[j] = ansb;
}
return false;
}
int _tmain(int argc, _TCHAR* argv[])
{
for (int i = 0; i < NUM_NUM; i++) {
char buf[20];
int x;
cin >> x;
num[i] = x;
itoa(x, buf, 10);
ans[i] = buf;
}
if (!Search(NUM_NUM)) cout << "No answan!!" << endl;
getchar(); getchar();
return 0;
}
本人思路:(1)
四个数，选两个组合，产生第5个，在上下的两个和新产生的1个里再选两个，产生第6个，此时就有2个尚未用的(包括刚产生的)，再次组合，产生结果，判断是不是24.注：每次组合有+/-/*/除四种情况。
不过写代码时思路错了点
错误代码
我的代码
/**//*#include <iostream>
#include <sstream>
#include <cmath>
using namespace std;
const int NUM_CAL = 24;
const int NUM_NUM = 4;
const double ERR = 1E-6;
double num[NUM_NUM];
string ans[NUM_NUM];
bool Search(int n)
{
if (n == 1) {
if (fabs(num[0] - NUM_CAL) < ERR) {
//cout << ans[0] << "=24" << endl;
cout<<"YES"<<endl;
return true;
}
else {
return false;
}
}
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
double a, b;
string ansa, ansb;
a = num[i];
b = num[j];
num[j] = num[n-1];
ansa = ans[i];
ansb = ans[j];
ans[j] = ans[n-1];
num[i] = a + b;
ans[i] = "(" + ansa + "+" + ansb + ")";
if (Search(n - 1)) return true;
num[i] = a - b;
ans[i] = "(" + ansa + "-" + ansb + ")";
if (Search(n - 1)) return true;
num[i] = b - a;
ans[i] = "(" + ansb + "-" + ansa + ")";
if (Search(n - 1)) return true;
num[i] = a * b;
ans[i] = ansa + "*" +ansb;
if (Search(n - 1)) return true;
if (b != 0) {
num[i] = a/b;
ans[i] = ansa + "/" + ansb;
if (Search(n - 1)) return true;
}
if (a != 0) {
num[i] = b/a;
ans[i] = ansb + "/" + ansa;
if (Search(n - 1)) return true;
}
num[i] = a;
num[j] = b;
ans[i] = ansa;
ans[j] = ansb;
}
return false;
}
int main()
{
bool flag=true;
char c;
char a[10];
while(flag)
{
c=cin.peek();
//cin.putback(c);
if(c=='E')
{
break;
}
for (int i = 0; i < NUM_NUM; i++) {
char buf[20];
int x;
cin >> x;
num[i] = x;
itoa(x, buf, 10);
ans[i] = buf;
}
if (!Search(NUM_NUM)) cout << "No" << endl;
cin.getline(a,10);
}
return 0;
}
// istream putback
#include <iostream>
using namespace std;
int main () {
char c;
int n;
char str[256];
while(1)
{
cout << "Enter a number or a word: ";
c = cin.get();
cin.putback (c);
cout<<"c->WWW:"<<c<<endl;
if(c=='E')
break;
if ( (c >= '0') && (c <= '9') )
{
cin >> n;
cout << "You have entered number " << n << endl;
}
else
{
cin >> str;
cout << " You have entered word " << str << endl;
}
cin.get();
}
return 0;
}*/
#include<iostream>
#include <sstream>
#include <cmath>
using namespace std;
double card[7];
int used[7];
int i,cLength;
double ans,err=1e-6;
bool isSuc;
string strAns[4];
void DFS(int n)
{
if(n==4 && fabs(ans-24.0)<err)
{
isSuc=true;
return ;
}
else if(n>=4)
return;
for(int j=n;j<4 && !isSuc;j++)
for(int k=j+1;k<4+j && !isSuc;k++)
{
if(!used[j] && !used[k])
{
string strA,strB;
strA=card[j];strB=card[k];
used[j]=used[k]=1;
//+
ans=card[j]+card[k];
card[4+j]=ans;
strAns[i]="("+strA+"+"+strB+")";
DFS(n+1);
//前-后
ans=card[j]-card[k];
card[4+j]=ans;
strAns[i]="("+strA+"-"+strB+")";
DFS(n+1);
//后-前
ans=card[k]-card[j];
card[4+j]=ans;
strAns[i]="("+strB+"-"+strA+")";
DFS(n+1);
//*
ans=card[j]*card[k];
card[4+j]=ans;
strAns[i]="("+strA+"*"+strB+")";
DFS(n+1);
//前除后
if(card[k]!=0)
{
ans=card[j]/card[k];
card[4+j]=ans;
//strAns[i]="("+strA+"/"+strB+")";
DFS(n+1);
}
//后除前
if(card[j]!=0)
{
ans=card[k]/card[j];
card[4+j]=ans;
strAns[i]="("+strB+"/"+strA+")";
DFS(n+1);
}
used[j]=used[k]=0;
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
char isEnd;
while(1)
{
isEnd=cin.get();
if(isEnd=='E')
break;
cin.putback(isEnd);
cLength=0;
isSuc=false;
ans=0.0;
//strAns=strTemp="";
memset(used,0,sizeof(used));
memset(card,0,sizeof(card));
for(i=0;i<4;i++)
{
char buf[20];
strAns[i]=buf;
cin>>card[i];
}
// for(i=0;i<4;i++)
// cout<<card[i]<<" ";
// cout<<endl;
DFS(1);
if(isSuc)
{
//cout<<strAns<<endl;
cout<<"YES\n";
}
else
cout<<"NO\n";
cin.get();
}
return 0;
}
思路2：直接穷举，思路看了就明白了，郁闷的是提交老是超时（
http://coder.buct.edu.cn/oj/Problem.aspx?pid=1634）郁闷.......屏蔽部分是输出的运算式
code
#include<iostream>
#include <sstream>
#include <cmath>
using namespace std;
double card[4];
int used[4];
int cLength;
//string str;
double ans,err=0.0000001;
bool isSuc;
void DFS(int n)
{
if(n==3 && fabs(ans-24.0)<err)
{
isSuc=true;
//str+="=24";
//cout<<str<<endl;
return ;
}
else if(isSuc|| n>3)
return;
for(int j=0;!isSuc && j<4;j++)
if(!used[j])
{
//string strtemp=str,temp;
//stringstream sstream;
double tempans=ans;
used[j]=1;
//+
ans+=card[j];
//sstream<<card[j];
//sstream>>temp;
//str="("+str+"+"+temp+")";
DFS(n+1);
//sstream.clear();
ans=tempans;
//str=strtemp;
//前-后
ans-=card[j];
//sstream<<card[j];
//sstream>>temp;
//str="("+str+"-"+temp+")";
DFS(n+1);
//sstream.clear();
ans=tempans;
//str=strtemp;
//后-前
ans=card[j]-ans;
//sstream<<card[j];
//sstream>>temp;
//str+="("+temp+"-"+str+")";
DFS(n+1);
//sstream.clear();
//str=strtemp;
ans=tempans;
//*
ans*=card[j];
//sstream<<card[j];
//sstream>>temp;
//str=str+"*"+temp;
DFS(n+1);
//sstream.clear();
//str=strtemp;
ans=tempans;
//前除后
if(card[j]!=0)
{
ans/=card[j];
//sstream<<card[j];
//sstream>>temp;
//str=str+"/"+temp;
DFS(n+1);
//sstream.clear();
//str=strtemp;
ans=tempans;
}
//后除前
if(ans!=0)
{
ans=card[j]/ans;
//sstream<<card[j];
//sstream>>temp;
//str=temp+"/"+str;
DFS(n+1);
//sstream.clear();
//str=strtemp;
ans=tempans;
}
used[j]=0;
}
}
void search()
{
stringstream sstream;
for(int i=0;i<4 && !isSuc;i++)
{
//str="";
ans=card[i];
used[i]=1;
//sstream<<card[i];
//sstream>>str;
DFS(0);
//sstream.clear();
used[i]=0;
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
char isEnd;
int i;
while(1)
{
isEnd=cin.peek();
if(isEnd=='E')
break;
//cin.putback(isEnd);
isSuc=false;
memset(used,0,4);
memset(card,0,4);
for(i=0;i<4;i++)
{
scanf("%lf",&card[i]);
}
search();
if(isSuc)
{
printf("YES\n");
}
else
printf("NO\n");
cin.get();
}
return 0;
}
思路3：对4个数进行全列，每种排列对符号进行穷举（错误原因：依此计算，没考虑两两组合，所得结果再组合的情况）
#include<iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
using namespace std;
double card[4];
double exp[
double ans,ans2,ans3,err=0.0000001;
bool isSuc;
int i,j,k,c;
inline char getopr(int ope)
{
if(ope==0)
return '+';
else if(ope==1)
return '-';
else if(ope==2)
return '*';
else if(ope==3)
return '/';
else
return ' ';
}
inline double oper(double *d1,double *d2,int ope)
{
if(ope==0)
return (*d1)+(*d2);
else if(ope==1)
return (*d1)-(*d2);
else if(ope==2)
return (*d1) * (*d2);
else if(ope==3)
return (*d1)/(*d2);
}
void DFS()
{
for(i=0;i<4;i++)
{
if(i==3 && fabs(card[1]-24)<err)
continue;
ans2=oper(&card[0],&card[1],i);
for (j=0;j<4;j++)
{
if(j==3 && fabs(card[2]-24)<err)
continue;
ans3=oper(&ans2,&card[2],j);
if(ans3<1.84616 || ans3>312.0)
{
continue;
}
for (k=0;k<4;k++)
{
if(k==3 && fabs(card[3]-24)<err)
continue;
if(fabs(oper(&ans3,&card[3],k)-24.0)<err)
{
isSuc=true;
printf("\n((%g%c%g)%c%g)%c%g=24",card[0],getopr(i),card[1],getopr(j),card[2],getopr(k),card[3]);
return;
}
}
}
}
}
void search()
{
for(int m=0;!isSuc && m<23;m++)
{
DFS();
next_permutation(card,card+4);
}
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
char isEnd;
c=0;
while(1)
{
isEnd=cin.peek();
if(isEnd=='E')
break;
//cin.putback(isEnd);
isSuc=false;
memset(card,0,4);
for(i=0;i<4;i++)
{
scanf("%lf",&card[i]);
}
search();
if(c++!=0)
printf("\n");
if(isSuc)
{
printf("YES");
}
else
printf("NO");
cin.get();
}
return 0;
}
更多链接：
http://zhidao.baidu.com/question/79907925.htmlhttp://www.3800hk.com/Article/cxsj/vc/bcjqvc/2005-08-06/Article_32541.html