1.cpp

利用全排列的算法编的判断套汇路径的算法

//宏定义,输入的货币代码长度小于20
#define MAXLENGTH 20
#include <iostream.h>
//计算货币编号序列Array中第m项货币倒第n项货币的汇率积，并返回汇率积
double ExchangeRateProduct(double** Matrix,int* Array,int m,int n)
{//传入的参数依次为：汇率矩阵Matrix，货币编号序列Array
 //货币编号序列Array第m项货币，货币编号序列Array第n项货币
	double Product;
	//初始化汇率积
	Product=1;
	//计算货币编号序列Array中第m项货币倒第n项货币的汇率积
	for(int i=m;i<n-1;i++)
	{
		Product=Product*Matrix[Array[i]][Array[i+1]];
	}
	Product=Product*Matrix[Array[n-1]][Array[m]];
	//返回汇率积
	return Product;
}
//选择判断函数，判断货币编号序列Array的全排列中前m项是否为升序排列
bool Select(int* Array,int m)
{//传入的参数依次为：货币编号序列Array,货币编号序列Array中第m项货币
	int i;
	for(i=0;i<m-1;i++)
	{
		//如果货币编号序列Array的前m项不是升序则返回值为假
		if(Array[i]!=i)return false;
	}
	//货币编号序列Array的前m项是升序则返回值为真
	return true;
}
//排列函数，产生所有任意i(i<=n)种货币的全排列，并判断产生的货币排列是否可以套汇，并输出
void Range(double** Matrix,int* Array,int n,int m,char** Name,int& num)
{//传入的参数依次为：汇率矩阵Matrix，货币编号序列Array
 //货币编号序列Array第m项货币，货币编号序列Array第n项货币，套汇路径计数器num
    //当m=n-1时，完成一次n-1种货币的全排列，全排列保存在货币编号序列Array中
	if(m==n-1)
	{
		int i=0;
        //从n-1种货币的全排列序列Array中选出前i项为升序的排列，得到剩余n-i种货币的全排列
		//这样保证每种排列都遍历了一遍，既不会漏，也不会重复
		while(i<n-1)
		{
			//从全排列序列Array选出前i项为升序的排列，即判断Select(Array,i)是否为真
			//并判断剩余n-i种货币的全排列是否存在套汇路径
			//即判断ExchangeRateProduct(Matrix,Array,i,n)是否大于1
			if(Select(Array,i)&&ExchangeRateProduct(Matrix,Array,i,n)>1)
			{
				//计数器，统计所有出现的套汇路径数
	            num++;
				int j;
				//将套汇路径中的货币依次输出
				for(j=i;j<n-1;j++)
				{
					//按套汇排列的顺序，从存储货币名称的二维数组中依次调出货币名称并输出
					cout<<Name[Array[j]]<<"--->";
				}
				//完整输出套汇路径和最终的套汇率
				cout<<Name[Array[n-1]]<<"--->"<<ExchangeRateProduct(Matrix,Array,i,n)<<Name[Array[i]]<<endl;
			}
			//下一次考察n-i-1种货币的全排列
		    i++;
		}
	}
	//若m!=n-1则n-1种货币的全排列尚未完成，继续进行全排列程序
	else
	{
		int i=m;
		//递归产生全排列，这部分算法参考了《算法设计技巧去分析》
		while(i<n)
		{
			int temp;
			temp=Array[i];
			Array[i]=Array[m];
			Array[m]=temp;
			//递归调用Range函数
			Range(Matrix,Array,n,m+1,Name,num);
			Array[m]=Array[i];
			Array[i]=temp;
			i++;
		}
	}
}
//连接函数，实际上是用于联系主函数main和排列函数Range
int Connect(int n,int *Array)
{//传入参数为：货币种数n和货币编号序列Array
	//声明并初始化套汇计数器num
	int num=0;
	//声明存放货币名称的二维数组Name，并为其开辟相应空间
	char ** Name=new char *[n];
	cout<<"-------------------请输入货币的名称:------------------"<<endl;
	for(int i=0;i<n;i++)
		Name[i]=new char[MAXLENGTH];
	//输入货币名称，并存入Name[i]
	for(i=0;i<n;i++)
		cin>>Name[i];
	//声明存放回避汇率的矩阵Matrix，并为其开辟相应空间
	double ** Matrix=new double *[n];
	for(i=0;i<n;i++)
		Matrix[i]=new double[n];
    //输入货币汇率，并将货币汇率存入矩阵中
	for(i=0;i<n;i++)
	{
		//定义货币从自身兑换到自身的汇率为1
		Matrix[i][i]=1;
		//输入货币间的汇率
		for(int j=i+1;j<n;j++)
		{
			cout<<"请输入"<<Name[i]<<"兑换到"<<Name[j]<<"的汇率"<<endl;
		    cin>>Matrix[i][j];
			//简单起见，认为任意两种不同货币的汇率满足倒数的关系
            Matrix[j][i]=1/Matrix[i][j];
			//如果输入的汇率小于零则要求重新输入
			while(Matrix[i][j]<=0)
			{
				cout<<"请输入正确的汇率"<<endl;
				cin>>Matrix[i][j];
			}
			
		}
	}
	cout<<"---------------------套汇路径如下:--------------------"<<endl;
	cout<<endl;
	//调用Range函数，从货币编号序列Array第0项货币开始遍历，并判断遍历的路径是否可以套汇
    Range(Matrix,Array,n,0,Name,num);
	//返回套汇路径数
    return num;
}
//主函数
void main()
{   
	int num;
	//判断子，判断是否重新运行程序
	char key;
loop1:
	cout<<"------------------欢迎测试套汇判断程序:--------------- "<<endl;
	cout<<endl;
	cout<<"-------------请输入参与套汇测试的货币种数:------------ "<<endl;
	int n;
	//存入货币种数n
	cin>>n;
	//声明货币编号序列Array，并为其开辟相应空间
    int *Array=new int[n];
	//初始化货币编号序列Array，初始状态为升序排列
	for(int i=0;i<n;i++)
		Array[i]=i;
	//调用连接函数，计算套汇路径数传入参数为货币种数n和货币编号序列Array
	num=Connect(n,Array);
	if(num==0)
		cout<<"-----------------所输入货币中不存在套汇---------------"<<endl;
	else
	{
        cout<<endl;
		cout<<"--------------------共有"<<num<<"种套汇路径-------------------"<<endl;
	}
	cout<<endl;
	cout<<"-----------------------谢谢测试！---------------------"<<endl;
loop2:
	cout<<endl;
	cout<<"是否重新进行程序，(Y)es or (N)o?"<<endl;
	cin>>key;
	if(key=='y'||key=='Y')
		goto loop1;
	else if(key=='n'||key=='N')
		cout<<"-----------------------谢谢测试！---------------------"<<endl;
	else
	{
		cout<<"输入错误"<<endl;
	    goto loop2;
	}
}