无优先级运算问题.cpp

给定n 个正整数和4 个运算符＋、－、*、/

#include <iostream>
using namespace std;
#include <string>
#include <cstring>
#include <fstream>
#include <vector>

int *x,*s;            // 读入数据 s是表示各个数的状态,stats简称
int n,m,k;            // k = n
int *a; 
char *b;
int res=1000000;               //  输出结果
int isModify = 0;
int record = 0;       // ·记录第一次所取数的下标
void ReadData();
void process();
void output();  
void backTrack(int time,int *no,char *sn,double result);

int main(int argc, char* argv[])
{
	ReadData();     // 读取数据
	process();      // 对数据处理
	output();       // 输出结果
	return 0;
}

void process()
{
	int *no;                // 记录排列时需要记录的数
	char *sn;               // 记录排列时需要记录的符号
	no = new int[k+1];
	sn = new char[k+1];
	a = new int[k+1];
	b = new char[k+1];
	res = 4 ;               // ·增量式搜索，回溯，即剪枝的策略三
	int i =0;			 
	while(true){ 
		i++;
		res +=2;            // ·增量式搜索，回溯，即剪枝的策略三

	for(int i =1;i<=k;i++)  // 从第一层开始，即从n个数开始记数
	{
		record = i;
		no[1] = x[i];       // 记录第1个数
		s[i] = 1;           // 表明刚才记录的数的状态是已经记录的
		backTrack(1,no,sn,x[i]);   // 回溯开始了
		s[i] = 0;           // 现场恢复
	}
	if ((isModify == 1)||(res>n)) return;
	}
}

void ReadData()
{	
	ifstream inStream;            
	inStream.open("input.txt");   	
	if(!inStream )
	{
		cerr << "Error open file.\n";
		return;
	}
	inStream>>n;
	inStream>>m;
	k = n;
	x=new int[2*n+1];
	s=new int[n+1];
	for(int i =1;i<=n;i++)
	{
		inStream>>x[i];
	}
	for(i = 1;i<=n;i++)
	{
		s[i] =0;
	}
	for(i=1;i<=n;i++)
	{
		x[n+i]=x[i];
	}

}

void output()
{
	ofstream outStream;
	outStream.open("output.txt");
	if(!outStream)
	{
		cerr << "Error open file.\n";
		return;
	}
	for(int i =1;i<k;i++)
	{
		if(x[i]==m)
		{
			outStream<<0<<endl;
			outStream<<x[i];
			return;
		}
	}
	if (isModify==0) {outStream<<"NO SOLUTION";return;}
	outStream<<res<<endl;
	outStream<<a[1];
	for( i=1;i<=res;i++)
		outStream<<b[i]<<a[i+1];
	cout<<res<<endl;
	cout<<a[1];
	for( i=1;i<=res;i++)
		cout<<b[i]<<a[i+1];
	cout<<endl;
}

void backTrack(int time,int *no,char *sn,double result)
{             // time:层数,no:记录数, sn:记录符号,result:上次计算的结果
	int i = 1;
	if ( time >= k ) return;   // 1.回溯返回的条件
	if (time>=res) return;
	for(i=1;i<=k;i++)          // 2.对所有的数再进行操作
	{
		if ((s[i]==0))  // 2.1第一个判断其状态是否已经记录过，
		{
			if (result+x[i] !=m)
			{
				if (!((time==1)&&(record>i))){          // ·对应剪枝的策略二
				if (!((isModify==1)&&(time>=res-1)))    // ·对应剪枝的策略一
				{
				no[time+1] = x[i];   //2.2.1 不等m，就记录该树及符号，继续往下找，层次加1
				sn[time] = '+';
				s[i] = 1;
				backTrack(time+1,no,sn,result+x[i]);
				}
				}
			}else{
				if (time<res)        //2.2.2 等于m,判断其层次是否最短，最短就记录该数及符号，
				{                         // 再把记录的数及符号使用a,b保留起来
					res = time;           // 以下其他操作类似
					no[time+1] = x[i];
					isModify = 1;
					sn[time] = '+';
					a[1] = no[1];
					for(int j =1;j<=time;j++)
					{
						a[j+1] = no[j+1];
						b[j] = sn[j];						
					}
					return;
				}
			}
			s[i] = 0;                //2.3 现场恢复
			if (result-x[i] !=m)
			{
				if(!((isModify==1)&&(time>=res-1))){
				no[time+1] = x[i];
				sn[time] = '-';
				s[i] = 1;
				backTrack(time+1,no,sn,result-x[i]);
				}
			}else{
				if (time<res)
				{
					res = time;
					no[time+1] = x[i];
					sn[time] = '-';
					isModify = 1;
					a[1] = no[1];
					for(int j =1;j<=time;j++)
					{
						a[j+1] = no[j+1];
						b[j] = sn[j];						
					}
					return;
				}
			}
			s[i] = 0;
			if (result*x[i] !=m)
			{
				if (!((time==1)&&(record>i))){
				if(!((isModify==1)&&(time>=res-1))){
				no[time+1] = x[i];
				sn[time] = '*';
				s[i] = 1;
				backTrack(time+1,no,sn,result*x[i]);
				}
				}
			}else{
				if (time<res)
				{
					res = time;
					no[time+1] = x[i];
					sn[time] = '*';
					isModify = 1;
					a[1] = no[1];
					for(int j =1;j<=time;j++)
					{
						a[j+1] = no[j+1];
						b[j] = sn[j];						
					}
					return;
				}
			}
			s[i] = 0;
			if (result/x[i] !=m)
			{
				if(!((isModify==1)&&(time>=res-1))){
				no[time+1] = x[i];
				sn[time] = '/';
				s[i] = 1;
				backTrack(time+1,no,sn,result/x[i]);
				}
			}else{
				if (time<res)
				{
					res = time;
					no[time+1] = x[i];
					sn[time] = '/';
					isModify = 1;
					a[1] = no[1];
					for(int j =1;j<=time;j++)
					{
						a[j+1] = no[j+1];
						b[j] = sn[j];						
					}
					return;
				}
			}
			s[i] = 0;
		}
	}
}