agle2.cpp

包括GRAY码

#include<iostream.h>
#include<string.h>
#include<fstream.h>

void main()
{
   	ofstream outFile;
	ifstream inFile;
	outFile.open("output.txt");
	inFile.open("input.txt");

	int n;
	inFile>>n;

	int **a=new int*[n+1];               //存储数字三角形的值           
	for(int i=0;i<=n;i++)
		a[i]=new int[n+1];

	for(i=1;i<=n;i++){               //从文件中输入数字三角形到数组a
		for(int j=1;j<=i;j++)
			inFile>>a[i][j];
	}

	int **totalSum=new int*[n+1];        //存储自上而下计算到该点的和
	for(i=0;i<=n;i++)
		totalSum[i]=new int[n+1];
	
	totalSum[1][1]=a[1][1];

	for(i=2;i<=n;i++){
		for(int j=1;j<=i;j++)
		{
			totalSum[i][j]=-1;
	
			//如果从右斜线这个点下去和较大的话，选择右边
	        if(j!=1  && totalSum[i-1][j-1]+a[i][j]>totalSum[i][j])
		          totalSum[i][j]=totalSum[i-1][j-1]+a[i][j];
			//如果从左斜线这个点下去和较大的话，选择左边
	        if(j!=i && totalSum[i-1][j]+a[i][j]>totalSum[i][j])
		          totalSum[i][j]=totalSum[i-1][j]+a[i][j];
		}
	}
	int max=1;
	for(i=2;i<=n;i++){
		if(totalSum[n][i]>totalSum[n][max])
			max=i;
	}

	outFile<<totalSum[n][max];

	for(i=0;i<=n;i++)
	{
		delete []totalSum[i];
		delete []a[i];
	}
	delete []totalSum;
	delete []a;
	totalSum=0;
	a=0;
}