alg_ans.h

一个计算任意个数是否可以通过一系列运算得到想要的结果的程序,程序中主要利用递归方式实现

#include<iostream>
#include<vector>
#include<string>
#include <cmath> 
using namespace std;
const double PRECISION = 1E-6;		//精度，以防在做一些除法运算时由于精度问题导致出错

/*递归函数Compute*/
/*************************************************************************/
/*一 递归算法值得注意考虑的地方
	  1 递归中需要考虑临时变量的生存时间，在递归函数中定义到的临时变量，其实质上相当于在
		不同的函数定义了一个相同的变量名 如int a；这个变量在每一层递归中都重新赋值，而在
        每一层递归结束时，返回到上一层，该变量则又从堆栈中返回，这是递归的巧妙之处，该递
		归返回可以用于回溯一路过来的数据
	  2 再说临时变量问题，由于临时变量仅在每一层递归中存在一个值，在深一层其会重新由于定
        义而重新被初始化，所以其值如果要在下一层利用，则需要用一个全局变量（我觉得用递归
		的形式参数可以）把它存储起来，然后在深一层递归中利用。例如对下面的变量c,利用了vector
        存储起来。而对于返回时，由于“错位”（个人认为叫错位）导致返回时的变量不是同一层次时
        如下面Compute函数，如果仅仅设置一个变量Exp，两者在合成一个表达式Exp后，由于合并在上一层，
		而如果返回的话，得到的结果将会觉得不是同一层次的数据，而且无法把它分离开重新调用递归，
		故需要设置变量把其分离开Exp1，Exp2，这样的话，返回的a，b 将和Exp1，Exp2在同一层次，
		可以很好把表达式列出来
	  3	到目前的程序为止，都是将递归中的形式参数作为该递归函数的“全局变量”，用于存储数据进入
		深一层的递归，如Number，Exp
  二，利用递归的思想考虑问题
	  到目前为止所编写的利用递归思想进行的算法，包括字符排列，汉诺塔，24点算术等，这些问题中
	  都要考虑到一个问题的相似性，如字符排列的去一字符对余下字符进行全排列，汉诺塔的经典递归，
	  24点算术中递归对所有可能的算术结果，这些问题都是比较循环得到，只是在各层递归中，所进行
	  一些操作不同，包括递归中的循环，递归中的排列等。
  三 一些小问题
		递归函数的bool值，返回利用一层一层的返回return true/false，要注意的是要保证出口唯一而
		且一定存在出口，小心忘记return false，最好把这句放到递归的最后一层，还有函数的结束，因为
		如果递归结束时是返回上一层的最后一行程序，所以可以很好的返回上一层的递归结果
*/

/*思想：a,b,c,d => a,b,(c+*-/d)=>a,b,c=>a,c=>c==Ans?然后逐层返回计算
*/
bool Compute_Ans(vector<double>Number,string Exp,int Ans,int Con_record = 0)	
{
	if(Number.size() == 1)
	{
		if(fabs(Number[0]-Ans)<PRECISION)
		{
			cout<<"Success..."<<endl;
			cout<<Exp<<" = "<<Ans<<endl;
			return true;
		}
		else
		{
			return false;
		}
	}
	else
	{
		string Exp1,Exp2;
		double a,b,c;
		char ch_a,ch_b;
		Exp1 = Exp;

		a = Number[Number.size()-1];
		ch_a = a+48;
		Number.pop_back();
		b = Number[Number.size()-1];
		ch_b = b+48;
		Exp2 = ch_b;
		Number.pop_back();
		c = a+b;
		Number.push_back(c);

		if(Con_record>0)
		{
			Exp1 = ch_a;
		}
		Exp = '('+Exp1+'+'+Exp2+')';
		if(Compute_Ans(Number,Exp,Ans)) return true;
		
		Number.pop_back();
		c = a*b;
		Number.push_back(c);
		Exp = '('+Exp1+'*'+Exp2+')';
		if(Compute_Ans(Number,Exp,Ans)) return true;

		Number.pop_back();
		{
			if(a>b)
			{
				c = a-b;
				Number.push_back(c);
				Exp = '('+Exp1+'-'+Exp2+')';
			}
			else
			{
				c = b-a;
				Number.push_back(c);
				Exp = '('+Exp2+'-'+Exp1+')';
			}
		}
		if(Compute_Ans(Number,Exp,Ans)) return true;

		Number.pop_back();
		if(fabs(b)>PRECISION)
		{
			c = a/b;
			Number.push_back(c);
			Exp = '('+Exp1+'/'+Exp2+')';
			if(Compute_Ans(Number,Exp,Ans)) return true;
		}

	 	Number.pop_back();
		if(fabs(a)>PRECISION)
		{
			c = b/a;
			Number.push_back(c);
			Exp = '('+Exp2+'/'+Exp1+')';
			if(Compute_Ans(Number,Exp,Ans)) return true;
		}
	}
	return false;
}

/*Insert_Char函数用于在某一位置插入字符*/
void Insert_Char(char c1,string &str,int i)
{
	if(i == 0)
	{
		str = c1 + str;
	}
	else
	{
		string Temp_str = str.substr(i);
		str.erase(i,str.size()-i);
		str = str + c1 +Temp_str;
	}
}
/*Rotate 函数用来对所输入的数字进行全排列，利用的是非递归的全排列方式，主要是因为在某一情况下
计算算式中已经利用到了递归的方法，故另外利用函数编写一个非递归的，可以从中调用递归函数，而且这
样会减少占用栈空间
对输入数字进行全排列的方法是：1首先对下标进行全排列。
							  2然后将各个数字按所排列好的下标取数字即可得到某一数列的全排列
*/
void Rotate(vector<double>Number,string Exp,int Ans,int Con_record)
{
	int count = Number.size();
	
	vector<string>temp;
	vector<string>store;

	store.push_back("0");
	
	string T_Str;
	char ch_i;

	for(int i = 1;i<count;i++)  //递推方法 隔位插入字符，得到全排列
	{
		for(int j = 0;j<store.size();j++)
		{
			T_Str = store[j];
			for(int t = 0;t<=store[j].size();t++)
			{
				ch_i = i+48;
				Insert_Char(ch_i,T_Str,t);
				temp.push_back(T_Str);
				T_Str = store[j];
			}
		}
		while(!store.empty())
		{
			store.pop_back();
		}
  		store = temp;
		while(!temp.empty())
		{
			temp.pop_back();
		}
	}
//以上得出下标排列
	
	vector<double>Sort_Number;
	int T_int;
	bool test = false;
	for(i = 0;i<store.size();i++)
	{
		for(int j = 0;j<Number.size();j++)
		{
			T_int = store[i][j];
			T_int = T_int-48;
			Sort_Number.push_back(Number[T_int]);
		}
		if(Compute_Ans(Sort_Number,Exp,Ans,Con_record))
		{
			test = true;
			break;
		}
		while(!Sort_Number.empty())
		{
			Sort_Number.pop_back();
		}

	}
	if(!test)
		cout<<"Fail To Compute..."<<endl;

}