数字三角形问题.cpp

/*数字三角形问题 问题描述： 给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 7 3 8 8 1 0 2 7 4 4 4

/*数字三角形问题
问题描述：
     给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。
  7
  3   8
  8   1   0
2   7   4   4
4   5   2   6   5 
编程任务：
    对于给定的由n行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。

#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <fstream.h>
#include <iomanip.h>

void main()
{
	ifstream fin("input.txt");
	ofstream fout;
    
	int n;
    fin>>n;
	if((n<1)||(n>100)){cout<<"Error!n must be in [1,100]";exit(0);}
int * y=new int[n];

int s;
int row;//每次处理的行数（可变）
int num=0;
int j;

for(int i=0;i<n;i++)num+=i+1;//num是数字的总个数;
int * x=new int[num];
//
for(i=0;i<n;i++)y[i]=0;
//
	for(i=0;i<num;i++)
		fin>>x[i];

	for(row=n;row>=1;row--)
	{s=(row*(row-1))/2;//s是由行数换算成的该行首个元素对应数组中的位置
		for(j=0,i=row;i>=1;i--)
		{
		x[s+j]+=y[j];j++;}

		for(j=0,i=row;i>1;i--)
		{
		if(x[s+j]>x[s+j+1])
		y[j]=x[s+j];
		else y[j]=x[s+j+1];
		j++;}
	}

   fout.open("output.txt");
   fout<<x[0]<<endl;
   fin.close();
   fout.close();
}