New Page 1

    一个解决古老游戏的小程序

    A.第一版

    这个小程序是最初的版本，计划最近增强功能以便解决数字不重复的解法。

    1。 游戏的基本说明：大家应该都玩过这个游戏，就是用若干个10以内数字，通过加减乘除组合结果为24。

    2。 游戏程序思路：通常用加括号的办法可以改变同一顺序的一组数字的运算先后，可是初步考虑这可是编译器级别的难题，因此我想通过

    组成不同排序的数字来穷尽所有的组合，这样逻辑的计算顺序是由数字的顺序决定的，要容易的多。

    3。 主要函数介绍：

    	A. Operation 是一个函数数组，用来存储加减乘除四则运算。

>     double Add(double , double);
>     double Mul(double , double);
>     double Min(double , double);
>     double Div(double , double);
>     double (*Operation[4])(double , double)= {Add,  Min, Mul, Div};

>     B. inputNumber是一个产生所有数字组合的函数，其麻烦处在于每次变化一个数字就返回，我用了一个类似进位的小算法，每次第一位

>     数总加一，到九就便为一，同时下一位数进一，如果下一位数也是九，那么就再进一位，如果最后一位也变为九了说明穷尽了，返回假。

>     bool inputNumber()

>     C. display原本是为了屏幕输出，后来结果太多改为文件输出，才加了文件参数。他又有三个内部函数。

>     	1。void addNumber();很简单把选定的数字组合放入数组的偶数Index位置，操作符号在奇数的Index位置。

>     	2。void addParenthesis();是加括号的函数，我的算法是只有当加减号在乘除号之前出现时候才加挂号。它内部又有一个移动拷贝数组

>     	的内部小函数，很普通的了。

>     	3。void displaySolution(ofstream& f);原本是屏幕输出，现在改为可以同时写结果入文件。

>     void display(bool succeed, ofstream& f)
>     {
>     	void addNumber();
>     	void addParenthesis();
>     	void displaySolution(ofstream& f);

>     }

>     D. findSolution是真正的核心函数，我为了图省事，避免用树形结构，结果最后费尽心机，还是用数组实现了一个树形的存储，不过非常的笨拙。

>     1。先把第一与第二个数的四则运算结果存入临时数组total的0到四位，然后下面的一个数字与前一个结果就是接着存下去。也就是4的前n次幂的和。

>     2。total[second] = Operation[j -10](total[first], Operand[count+2]);这一句就是前一次的结果与下一个数字的四则运算。

>     3。我无法解决先除后乘为整数的结果判断，只好用精确值在0.01来判断。好像也还不错。

> >     if ((count==Number-3)&&fabs(total[second]-24)<0.01)
> >     				{
> >     					writeRecord(second);
> >     					result = true;
> >     				}

>     bool findSolution(ofstream& f);

>     E. writeRecord是findSolution的一个内部函数，目的是根据D3的判断来倒推出各个步骤的操作符号，我用了类似辗转除法，就是类似10进制转

>     二进制的那种，每次的余数就是操作符号的顺序数字减十（因为，为了把数字和符号同存在一个数组里，我定符号从10开始。）

>     void writeRecord(int num)

    4。 不足之处：

    	A.还没有找出取不同数字的简单算法，各位有主意告诉我。（就是inputNumber里产生不重复数字，即不产生 2，2，3，4的组合。）

    	B.输出结果能否排列，或剔除相似的结果。（Forget it, it is too hard!)

    	C.输入数字个数改为3， 或者5等等，实际上我的程序是可以的，可是不知道那里有小虫子，还没有找到。

    5. 输出的结果文件在此。

    #include <iostream>
    #include <fstream>
    #include <cmath>

    using namespace std;

    const int Number = 4;
    const int OpNum = 6;
    const int SignNum =4;

    enum Op
    {ADD=10, MIN=11, MUL=12, DIV=13, LEFT=14, RIGHT=15};

    int OpCount = 0;
    int NumCount = 0;

    char *OpStr[OpNum]= {"Addition", "Minus", "Multiply", "Divide", "Left", "Right"};

    char *OpSign[OpNum] = {"+", "-", "x", "/", "(", ")"};

    int Operand[Number] = {0};

    int Operator[Number*3]= {0};

    void initialize();

    void display(bool succeed, ofstream& f);

    bool inputNumber();

    bool findSolution(ofstream& f);

    double Add(double , double);
    double Mul(double , double);
    double Min(double , double);
    double Div(double , double);

    double (*Operation[4])(double , double)= {Add,  Min, Mul, Div};

    int main()
    {
    	int temp=0, times=0;
    	initialize();
    	ofstream f;
    	f.open("c:\\game24.txt");
    	while (inputNumber())
    	{
    		if (findSolution(f))
    		{
    		//	display(true, f);
    //			temp++;
    			;
    		}
    		else
    			;
    		times++;
    		//	display(false);   //in order to see clearly, omit the no solution display
    	}
    	cout<<"\nTotal "<<NumCount<<" solutions\n";
    	cout<<"\nAnd total number is"<<times<<endl;
    	f<<"\nTotal "<<NumCount<<" solutions out of "<<times<<" combinations\n";

    	return 0;
    }

    double Add(double num1, double num2)
    {
    	return num1 + num2;
    }

    double Mul(double num1, double num2)
    {
    	return num1 * num2;
    }

    double Min(double num1, double num2)
    {
    	return num1 -num2;
    }

    double Div(double num1, double num2)
    {
    	return num1/num2;
    }

    bool findSolution(ofstream& f)
    {
    	void writeRecord(int num);

    	double total[1000] = {0};
    	int first=0, second=0, last=0, now=0;
    	bool result = false;

    	for (int i=0; i< SignNum; i++)
    	{
    		total[i] = Operation[i](Operand[0], Operand[1]);
    	}

    	for (int count = 0; count< Number-2; count++)
    	{
    		last += (count==0?0:pow(SignNum,count));
    		now += pow(SignNum, count+1);
    		second = now;
    		for (int first = last; first< now; first++)
    		{
    			for (int j= ADD; j<=DIV; j++)  //control op
    			{
    				total[second] = Operation[j -10](total[first], Operand[count+2]);
    				if ((count==Number-3)&&fabs(total[second]-24)<0.01)
    				{
    					writeRecord(second);
    					display(true, f);
    					result = true;
    					NumCount++;
    				}
    				second++;
    			}
    		}

    	}
    	return result;
    }

    void writeRecord(int num)
    {
    	int pos=num;
    	for (int i=1; i< Number-1; i++)
    	{
    		pos -= pow(SignNum, i);
    	}

    	for (i=Number -2; i>=0; i--)
    	{
    		Operator[i*2+1]= pos%SignNum+10;  //from back to front, and
    		pos = pos/SignNum;
    	}
    }

    void initialize()
    {
    	for (int i=0; i< Number; i++)
    	{
    		Operand[i] = 1;
    	}
    	Operand[0] = 0; //this is ugly as I need to add 1 at each time,so make it zero to add 1
    }

    bool inputNumber()
    {
    	int i=0;
    	while (true)
    	{
    		if (Operand[i]< 9)   //increase one by one number
    		{
    			Operand[i] ++;
    			return true;
    		}
    		else
    		{
    			if (i==Number -1)
    				break;
    			Operand[i] = 1;   //this is something like "进位"
    			i++;
    		}
    	}
    	return false;
    }

    void display(bool succeed, ofstream& f)
    {
    	void addNumber();
    	void addParenthesis();
    	void displaySolution(ofstream& f);

    	if (succeed)
    	{
    		addNumber();
    		addParenthesis();
    		displaySolution(f);
    	}
    	else
    	{
    		cout<<"\nNo solution for these numbers:\n";
    		for (int i=0; i< Number; i++)
    		{
    			cout<<Operand[i]<<'\t';
    		}
    		cout<<endl;
    	}
    }
    void displaySolution(ofstream& f)
    {
    	cout<<"\nThe solution is:\n";
    	for (int i =0; i< OpCount; i++)
    	{
    		if (Operator[i]< 10)
    		{
    			cout<<Operator[i];
    			f<<Operator[i];
    		}
    		else
    		{
    			cout<<" "<<OpSign[Operator[i] - 10]<<" ";
    			f<<" "<<OpSign[Operator[i] - 10]<<" ";
    		}
    	}
    	f<<'\n';
    }

    void addNumber()
    {
    	for (int i=0; i< Number; i++)
    	{
    		Operator[i*2] = Operand[i];
    	}
    	OpCount = Number * 2 - 1;
    }

    void addParenthesis()
    {
    	void insertParenthesis(int pos);

    	bool findLow= false, findHigh= false;

    	for (int i =0; i <OpCount; i++)
    	{
    		if (Operator[i]==11||Operator[i]==10)   //add, min
    			findLow = true;
    		else
    		{
    			if (Operator[i]==12||Operator[i]==13)  //mul, div
    			{
    				if (findLow)              //only find add, min then findHigh is meaningful
    					findHigh = true;
    			}
    		}
    		if (findLow&&findHigh)
    		{
    			insertParenthesis(i);
    			findLow = false;
    			findHigh = false;
    		}
    	}
    }

    void insertParenthesis(int pos)
    {
    	void insert(int pos, int item);
    	insert(pos, RIGHT);   //Sequence is important due to pos++
    	insert(0, LEFT);

    }

    void insert(int start, int item)
    {
    	int hold1, hold2;

    	hold1 = Operator[start];
    	hold2 = Operator[start+1];

    	for (int i = start; i< OpCount; i++)
    	{
    		Operator[i + 1] = hold1;

    		hold1 = hold2;
    		hold2 = Operator[i+2];

    	}
    	Operator[start] = item;
    	OpCount++;
    }

    A glimpse of the output in screen. Click to maximize and here is the total outcome file again.