taohui.cpp

可以处理股市的套汇问题

#include "iostream"
#include "algorithm"
#include "vector"
#include <fstream>
using namespace std;
vector<int> vect;//用一个向量的全局变量,以标记递归时的路径
float sum=1;//当前vect中的汇率乘积，避免了重复计算

void findcy(float ** mtx,int scale,int *sign)//传入矩阵，矩阵大小，以及用sign数组标记该货币标号是否以被加入环中
{
	for(int i=0;i<scale;i++)//在每层递归中，循环置入货币标号，构成路径
	{
		if(sign[i]<0)//若已被加入，则不加入，开始下一个标号的操作
			continue;
		
		float temp;//加入该标号后，考察环路汇率乘积
        if(vect.size()!= 0)
		{
		sum=sum*mtx[vect.back()][i];
		temp=sum*mtx[i][vect.front()];
		}
		
		sign[i]=-1;//该标号已访问过
		vect.push_back(i);//把该标号加入向量末尾
		
		if(temp > 1.00001)//若汇率积大于1，则输出
		{
			cout<<"Have a dividen path:";
			copy(vect.begin(),vect.end(),ostream_iterator<int>(cout,"-"));
			cout<<vect.front();
			cout<<"\t"<<"the dividen is "<<temp<<endl; 
		}
		
		findcy(mtx,scale,sign);//进行下一级递归

		sign[i]=1;//维护数组及向量保持原来的状态，进行下一次循环准备
		vect.pop_back();
		if(vect.size()!= 0)
		   sum=sum/mtx[vect.back()][i];

	}
	
	return;	

}

void main()
{
	ifstream ifs("data.txt");//从客户文件中读取汇率矩阵及规模
	int scale;
	ifs>>scale;
	

	float ** mtx=new float*[scale];//给二维数组分配动态内存空间
	for(int i=0;i<scale;i++)
	{
	   mtx[i]=new float[scale];
	} 
	
	
	int m,n;//把矩阵信息存入二维数组
	for(m=0;m<scale;m++)
		for(n=0;n<scale;n++)
			ifs>>mtx[m][n];
	ifs.close();

	int * sign=new int[scale];//建立标记数组sign,并把起初是化为元素均为1
	for(int j=0;j<scale;j++)
		sign[j]=1;
	
	findcy( mtx, scale, sign);//进行递归调用，找到所有的路径

	return;
}