版权和使用规则请查看出处，有事请联系原作者。
程序1和2出处：http://www.ieee.org.cn/dispbbs.asp?boardID=60&ID=15720
程序3出处：http://www.joansky.com/95.html
程序1：
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
const double PRECISION = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int NUMBER_TO_CAL = 24;
double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];
bool Search(int n)
{
if (n == 1) {
if ( fabs(number[0] - NUMBER_TO_CAL) < PRECISION ) {
cout << expression[0] << 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 expa, expb;
a = number[i];
b = number[j];
number[j] = number[n - 1];
expa = expression[i];
expb = expression[j];
expression[j] = expression[n - 1];
expression[i] = '(' + expa + '+' + expb + ')';
number[i] = a + b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '-' + expb + ')';
number[i] = a - b;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expb + '-' + expa + ')';
number[i] = b - a;
if ( Search(n - 1) ) return true;
expression[i] = '(' + expa + '*' + expb + ')';
number[i] = a * b;
if ( Search(n - 1) ) return true;
if (b != 0) {
expression[i] = '(' + expa + '/' + expb + ')';
number[i] = a / b;
if ( Search(n - 1) ) return true;
}
if (a != 0) {
expression[i] = '(' + expb + '/' + expa + ')';
number[i] = b / a;
if ( Search(n - 1) ) return true;
}
number[i] = a;
number[j] = b;
expression[i] = expa;
expression[j] = expb;
}
}
return false;
}
void main()
{
for (int i = 0; i < COUNT_OF_NUMBER; i++) {
char buffer[20];
int x;
cin >> x;
number[i] = x;
itoa(x, buffer, 10);
expression[i] = buffer;
}
if ( Search(COUNT_OF_NUMBER) ) {
cout << "Success." << endl;
} else {
cout << "Fail." << endl;
}
}
程序2：计算任意值，求出最接近值
#include <fstream>
#include <algorithm>
#include <string>
#include <sstream>
#include <list>
#include <cmath>
#include <climits>
#include <bitset>
using namespace std;
const char* INPUT_FILE = "game.in";
const char* OUTPUT_FILE = "game.out";
const int NUMBER_COUNT = 6;
const int STATE_COUNT = (1 << NUMBER_COUNT);
const int MAX_NUMBER = 100;
const int MAX_EXPECTION = 1000;
const int MAX_VALUE = MAX_EXPECTION * MAX_NUMBER;
struct Node {
int value;
int left, right;
int leftvalue, rightvalue;
char opr;
};
typedef list<Node> NodeList;
struct State {
bitset<MAX_VALUE+10> exist;
NodeList nodelist;
};
int number[NUMBER_COUNT], expection;
State state[STATE_COUNT];
void ReadData()
{
ifstream fin(INPUT_FILE);
for (int i = 0; i < NUMBER_COUNT; i++) {
fin >> number[i];
}
fin >> expection;
}
void Init()
{
Node node ;
for (int i = 0; i < NUMBER_COUNT; i++) {
node.value = number[i];
node.left = node.right = -1;
state[(1 << i)].nodelist.push_back(node);
state[(1 << i)].exist[node.value] = true;
}
}
void Merge(int a, int b, int x)
{
Node node;
NodeList::const_iterator i, j;
for (i = state[a].nodelist.begin(); i != state[a].nodelist.end();
i++) {
for (j = state[b].nodelist.begin(); j != state[b].nodelist.en
d(); j++)
{
node.value = (*i).value + (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '+';
if ( (node.value <= MAX_VALUE) && (!state[x].exist[node.value]) ) {
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////
double tmp = double((*i).value) * double((*j).value);
if (tmp < INT_MAX) {
node.value = (*i).value * (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '*';
if ( (node.value <= MAX_VALUE) && (!state[x].exist[node.value]) )
{
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
}
/////////////////////////////////////////////////////
if ((*i).value >= (*j).value) {
node.value = (*i).value - (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '-';
} else {
node.value = (*j).value - (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '-';
}
if ( (node.value <= MAX_VALUE) && (!state[x].exist[node.value]) ) {
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////
if ( ((*j).value != 0) && ((*i).value >= (*j).value) &&
((*i).value % (*j).value == 0) )
{
node.value = (*i).value / (*j).value;
node.left = a;
node.right = b;
node.leftvalue = (*i).value;
node.rightvalue = (*j).value;
node.opr = '/';
} else if ( ((*i).value != 0) && ((*j).value >= (*i).value) &&
((*j).value % (*i).value == 0) )
{
node.value = (*j).value / (*i).value;
node.left = b;
node.right = a;
node.leftvalue = (*j).value;
node.rightvalue = (*i).value;
node.opr = '/';
}
if ( (node.value <= MAX_VALUE) && (!state[x].exist[node.value]) )
{
state[x].nodelist.push_back(node);
state[x].exist[node.value] = true;
}
/////////////////////////////////////////////////////
}
}
}
void Solve()
{
Init();
for (int x = 2; x < STATE_COUNT; x++) {
for (int i = 1; i < x; i++) {
if ( (x & i) == i ) {
int j = x - i;
if (i <= j) {
Merge(i, j, x);
}
}
}
}
}
void PrintExpression(ostream& out, Node node)
{
if (node.left == -1) {
out << node.value;
} else {
NodeList::const_iterator iter;
out << "(";
for (iter = state[node.left].nodelist.begin();
iter != state[node.left].nodelist.end();
iter++)
{
if ((*iter).value == node.leftvalue) {
PrintExpression(out, *iter);
break;
}
}
out << node.opr;
for (iter = state[node.right].nodelist.begin();
iter != state[node.right].nodelist.end();
iter++)
{
if ((*iter).value == node.rightvalue) {
PrintExpression(out, *iter);
break;
}
}
out << ")";
}
}
void Output()
{
ofstream fout(OUTPUT_FILE);
int bestValue = -INT_MAX;
NodeList::const_iterator iter, bestIter;
NodeList& nodelist = state[STATE_COUNT-1].nodelist;
for (iter = nodelist.begin(); iter != nodelist.end(); iter++)
{
if ( ((*iter).value <= expection) && (bestValue < (*iter).value) ) {
bestValue = (*iter).value;
bestIter = iter;
}
}
fout << bestValue << endl;
PrintExpression(fout, *bestIter );
fout << endl;
}
int main()
{
ReadData();
Solve();
Output();
return 0;
}
程序3：列出所有结果
#include<stdio.h>
int x[100];
//保存四个数的所有组合
int arrange[100][100];
//保存读入的四个数
int num[100];
//标记该数是否被访问过
int a[100] = {0};
char sym[5]={'0','+','-','*','/'};
//保存使用的算术运算符
int bol[100];
// 标记运算符是否被访问过
int b[100]={0};
//保存四个数的组合总数
int sum = 0;
int n,r;
int ok=1;
//保存所有可能的组合数
void save(int sum)
{
int i;
for(i=0;i<4;++i)
{
arrange[sum][i] = x[i];
}
}
//判断使用该运算符是否合法
int symbollegal(int t,int i,int sum,int layer)
{
switch(i)
{
case 1:
if(arrange[layer][t]+sum>24)
return 0;
else return arrange[layer][t]+sum;
case 2:
if(sum-arrange[layer][t]<0)
return 0;
else return sum-arrange[layer][t];
case 3:
if(arrange[layer][t]*sum>24)
return 0;
else return arrange[layer][t]*sum;
case 4:
if(arrange[layer][t]!=0&&sum%arrange[layer][t]!=0)
return 0;
else return sum/arrange[layer][t];
}
}
// 打印结果
void pri(int layer)
{
int i,temp;
int totle = arrange[layer][0];
for(i= 1;i<=3;++i)
{
if(totle > arrange[layer][i])
{
temp = symbollegal(i,bol[i],totle,layer);
printf("%d %c %d = %d\n",totle,sym[bol[i]],arrange[layer][i],temp);
}
else
{
temp = symbollegal(i,bol[i],totle,layer);
printf("%d %c %d = %d\n",arrange[layer][i],sym[bol[i]],totle,temp);
}
totle = temp;
}
printf("\n");
}
//回溯计算四个组合数出现的情况
void backtrack(int t)
{
int i;
//遍历四个数
for(i = 1;i<= 4;++i)
{
x[t] = num[i];
//如果当前这个数没有被选择
if(a[i]==0)
{
//标记该数已经选择
a[i] = 1;
//结束条件：已经找到符合条件的四个数
if(t == 3 )
{
save(sum);
++sum;
}
else
{
backtrack(t+1);
}
//不符合条件，恢复该数的访问权限
a[i] = 0;
}
}
}
// 计算该组合数能得出24的情况
void find(int sum,int t,int layer)
{
int i,temp,sign;
//遍历加、减、乘、除四个符合
for(i=1;i<=4;++i)
{
bol[t] = i;
//如果选择的符号满足条件
if( (temp = symbollegal(t,i,sum,layer)))
{
//标记该符号已经选择并修改sum值
b[i] = 1;
sign = sum;
sum = temp;
//结束条件：四个数都已经完成运算
if(t == 3)
{
//结果是24点，则打印
if(sum==24)
{
ok=0;
pri(layer);
}
}
else
{
find(sum,t+1,layer);
}
//不符合条件，恢复该符号的访问权限与sum的值
b[i] = 0;
sum = sign;
}
}
}
int main()
{
int i,j;
for(i=1;i<=4;++i)
scanf("%d",&num[i]);
backtrack(0);
// 遍历所有的组合数
for(i=0;i<sum;++i)
{
find(arrange[i][0],1,i);
}
if(ok)
{
printf("No answer!\n");
}
system("pause");
return 0;
}
No comments:
Post a Comment