算法实现.txt

详细介绍了24点游戏的规则

附录：

1。根据算法1计算24点的代码

#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。根据算法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[no
de.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[no
de.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[no
de.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).val
ue) ) {
                        bestValue = (*iter).value;
                        bestIter  = iter;
                }
        }       
        fout << bestValue << endl;
        PrintExpression(fout, *bestIter );
        fout << endl;
}

int main()
{
        ReadData();
        Solve();
        Output();
        return 0;
}