result.h

功能：四阶幻方全解 运算时间：3、40秒 结果：7040个 环境：Visual Studio.net 2003的vc++的控制台项目

const int RESULTSIZE = 7100;
const int RSTINCREASMENT = 10;
/////////////////////////////////////
class Result:public Matrix
{
	int (*result)[DIM][DIM];
	int rstspace;
	int rstlength;
	Matrix matrix1;
	unsigned long Jie(int);
	void Pailie(int, int [], int *);	
	void AppendRst(int *rsttemp[DIM], int *prow);
	bool IfResult(int *rsttemp[DIM], int *prow, int &cause);
	int CountOneMatrix(int *rsttemp[DIM]);	
public:
	Result()
	{
		result = new int[RESULTSIZE][DIM][DIM];
		rstspace = RESULTSIZE;
		rstlength = 0;
		matrix1.CountAllMatrix();
	}
	~Result()
	{
		delete []result;
		result = NULL;
	}
	int GetRLength()
	{
		return rstlength;
	}
	void Display(int *rst[DIM]);
	void DisplayScope(int from, int to);
	void CountAllResult();
};
//////////////////////////////////////////////

//////////////////////////////////////////////
bool Result::IfResult(int *rsttemp[DIM], int *prow, int &cause)
{	
	int sum;
	/////////////////判断列是否成立
	if (cause == 0) 
	{
   
		for ( int j = 0; j < DIM-1; j++)
		{
			sum = 0;
			for (int k = 0; k < DIM; k++)
			{
				sum += *(rsttemp[k] + j);
			}
			if (sum != SUM)
			{
				cause = 1;
				return false;
			}
		}
	}
	////////////////判断对角线1是否成立 
	sum = 0;
	for (int j = 0; j < DIM; j++)
	{
		sum += *(rsttemp[prow[j]] + j);
	}
	if (sum != SUM)
	{
		cause = 2;
		return false;
	}
	////////////////判断对角线2是否成立 
	sum = 0;
	for (int j = 0; j < DIM; j++)
	{
		sum += *(rsttemp[prow[j]] + DIM - 1 -j);
	}
	if (sum != SUM)
	{
		cause = 2;
		return false;
	}

	/////////////////
	cause = 3;
	return true;
}
/////////////////////////////////////////////////////////
int Result::CountOneMatrix(int *rsttemp[DIM])
{
	int num = Jie(DIM);
	int len = num * DIM;
	int *rowpailie = NULL, *linepailie[DIM];
	int *prow = NULL;	
	int row[DIM];
	rowpailie = new int[len];
	prow = rowpailie;

	for (int i = 0; i < DIM; i++)
	{
		row[i] = i;
	}
	Pailie(DIM, row, rowpailie);

	
	for (int i = 0; i < DIM; i++)
	{
		linepailie[i] = new int[len];
		Pailie(DIM, rsttemp[i], linepailie[i]);
	}
	int flagx = 0;
	int flag[DIM];	//每行取到第几个排列(1~DIM!)
	int total = 0;
	for (int i = 0; i < DIM; i++)
	{
		flag[i] = 1;
		rsttemp[i] = linepailie[i];
	}
	
	while(true)
	{
		int cause = 0;//
		prow = rowpailie;
		for (int flagrow = 0; flagrow < num; flagrow++,prow += DIM)
		{
			if (IfResult(rsttemp, prow, cause))//cause：3表示是结果，返回true; 1表示由于列不满足而返回false，2返回false是由于对角线不满足。
			{
				AppendRst(rsttemp, prow);
				total++;
				//Display(rsttemp);
			}
			else
			{
				if (cause == 1)
				{
					break;
				}
			}
		}            

		flagx = -1;
		for ( int i = DIM-1; i > -1; i--)
		{
			if (flag[i] < num)
			{
				flagx = i;
				break;
			}
		}
		if (flagx < 0)
		{
			break;
		}
		flag[flagx]++;
		rsttemp[flagx] += DIM;
		for (int i = flagx+1; i < DIM; i++)
		{
			flag[i] = 1;
			rsttemp[i] = linepailie[i];
		}
	}//while
	return total;
}
/////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////
void Result::Display(int *rst[DIM])//显示结果。
{
	int *prst1[DIM], *prst2;
	for (int i = 0; i < DIM; i++)
	{
		prst1[i] = rst[i];
	}
	for (int i = 0; i < DIM; i++)
	{
		prst2 = prst1[i];
		for (int j = 0; j < DIM; j++,prst2++)
		{
			cout << *prst2 << "    " ;
		}
		cout << endl;
	}
	cout << endl;
}
//////////////////////////////////////////////
void Result::DisplayScope(int from, int to)
{
	int *pdisp = result[from-1][0];
	for (int i = from; i < to+1; i++)
	{
		for (int j = 0; j < DIM; j++)
		{
			for (int k = 0; k < DIM; k++)
			{
				cout << setw(4) << *pdisp ;
				pdisp++;
			}
			cout << endl;
		}
		cout << endl;
	}
	cout << endl << "从第 " << from << " 个到第 " << to << " 个结果" << endl;
}
//////////////////////////////////////////////

unsigned long Result::Jie(int n)//n!
{
    if (n == 0)
    {
        return 1;
    }
    else
    {
        return (unsigned long)n*Jie(n-1);
    }
}
///////////////////////////////////////////////
void Result::Pailie(int n,int s[], int *a)//求s[0]~s[n-1]共n个整数的排列，结果放在a[0]~a[n-1],a[n]~a[n+n-1],...... 中
{
    if (n == 2)
    {
        a[0] = s[0];
        a[1] = s[1];
        a[2] = s[1];
        a[3] = s[0];
        return;
    }
    unsigned long jc, group;    
    int *ps, *b;    
    group = Jie(n-1);
    jc = group * (n-1);
    b = new int[jc];
    ps = s + 1;
    Pailie(n-1, ps, b);
    int *pa = a, *pb = b, *ppb = b;

    for (unsigned long i = 0; i < group; i++)
    { 
        if (i)
        {
            ppb += (n-1);
        }
        for (int j = 0; j < n; j++)
        {            
            pb = ppb;
            for ( int k = 0; k < n; k++)
            {
                if (j == k)
                {
                    *pa++ = s[0];
                }
                if (k < n-1)
                {
                    *pa++ = *pb++;
                }
            }
        }
    }
    return;
}
///////////////////////////////////////////////////////////
void Result::AppendRst(int *rsttemp[DIM], int *prow)
{
	if (rstlength >= rstspace)
	{
		result = (int (*)[DIM][DIM])realloc(result, (rstspace + RSTINCREASMENT)*DIM*DIM*sizeof(int));
		if (!result)
		{
			exit(0);
		}
		rstspace += RSTINCREASMENT;
	}
	for (int i = 0; i < DIM; i++)
	{
		for (int j = 0; j < DIM; j++)
		{
			result[rstlength][i][j] = *(rsttemp[prow[i]] + j);
		}
	}	
	rstlength++;
}

///////////////////////////////////////////////
void Result::CountAllResult()
{
	char timebuf[2][11];
	_strtime(timebuf[0]);
	int *rsttemp[DIM];
	
	int c = 0;
	for (int i = 0; i < matrix1.GetMLength(); i++)
	{
		c = 0;
		for( int j = 0; j < DIM; j++)
		{
			rsttemp[j] = matrix1.matrix[i][j];
		}
		c =CountOneMatrix(rsttemp);
		//cout << "第 " << 350 << " 组共有" << c << "个" << endl; 
	}
	_strtime(timebuf[1]);
	cout << "运行时间从  " << timebuf[0] << "  到  " << timebuf[1] << endl;

	




}