デジタル三角形はn行の数字からなるデジタル三角形を与え、アルゴリズムを設計して、三角形の一番上から一番下までのパスを計算して、パスが通る数字の総和を最大にします(ステップごとに1つの数から次の層の上と一番近い左の数または右の数までしか歩けません).
1302 ワード
n行の数字からなるデジタル三角形を与え、三角形の一番上から一番下までのパスを計算し、パスが通る数字の総和を最大にするアルゴリズムを設計してみます(ステップごとに1つの数から次の層の一番近い左の数または右の数までしか歩けません)。
问题:n行の数字からなる数字の三角形を与えて、下図のように:7 3 8 8 1 0 2 7 4 4 4 4 5 6 5试みに1つのアルゴリズムを设计して、三角形の上から底までの1本の経路を计算して、この経路の通る数字の総和を最大にします(ステップごとに1つの数から次の阶の上でそれに最も近い左の数あるいは右の数まで歩くことしかできません).入力:最初の行はデジタル三角形の行数で、次のn行はデジタル三角形の数字です.たとえば、5 7 3 8 8 1 0 2 7 4 4 4 5 6 5出力:この最大値を出力します.ここではコードのみが与えられ、ステップ分析はリンクを参照します:ステップ詳細
コード実装:コード注釈の部分構成方法二
#include
#include
#include
#define N 5
int a[6][6];
int sum[6][6];
int sum_two[6];
int main()
{
int i,j;
for (i=1;i<=5;i++)
for (j=1;j<=i;j++)
scanf("%d",&a[i][j]);
for (i=1;i<6;i++)
{
sum[5][i] = a[5][i];
// sum_two[i] = a[5][i];
}
for (i=5-1;i>=1;i--)
for (j=1;j<=i;j++)
{
sum[i][j] = max(sum[i+1][j],sum[i+1][j+1]) + a[i][j];
//sum_two[j] = a[i][j] + max(sum_two[j],sum_two[j+1]);
}
for (i=1;i<6;i++)
{
for (j=1;j<=i;j++)
printf("%3d",sum[i][j]);
printf("
");
}
//printf("%d",sum_two[1]);
return 0;
}