evg

Дан треугольник, составленный из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.

Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.

Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.

Входные данные:
Первым числом во входном файле с именем INPUT.TXT является количество строк в треугольнике. Пример файла исходных данных представлен ниже.

 5
 7
 3 8
 8 1 0
 2 7 4 4
 4 5 2 6 5

Выходные данные:
В выходной файл с именем OUTPUT.TXT записывается только наибольшая сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных выше исходных данных. 7+3+8+7+5=30

Решение:

Для хранения треугольника заведем массив 100*100 из элементов word, т.к. будет использоваться для передачи суммы в следующую строку. Начнем анализировать треугольник, двигаясь от предпоследней строки к первой (такой тип движения избавит нас от части частных случаев). Итак, смотрим на предпоследнюю строку. У нее по диагонали снизу есть два соседа (в треугольном массиве это число которое находится на 1 клетку ниже и число, на 1 клетку ниже и правее данного) - выберем из них наибольший и прибавим к значению элемента значение наибольшего из нижних соседей. Повторяя эту операцию для каждой строки до вершины и для самой вершины, в вершине (элемент (1;1)) получим искомую сумму. Если бы мы двигались сверху вниз, то возникал бы случай для крайних элементов, у которых всего один сосед.


var inp:array[1..100,1..100] of word;
     scount,i,j,row:byte;
     f:text;
     t,t1,t2:word;

 begin
  assign(f,'input.txt');
  reset(f);
  readln(f,scount);  
  for i:=1 to scount do 
    for j:=1 to i do begin
     read(f, inp[i][j]);     
     end;  
  close(f);
  
  row := scount - 1;
  while (row > 0) do begin  
    for j:=1 to row do begin
      t:= inp[row][j];
      t1:=inp[row+1][j];
      t2:=inp[row+1][j+1];
      if t1 > t2 then inp[row][j]:=t+t1 else inp[row][j]:=t+t2;
    end;
    dec(row);
  end;      
  
  assign(f,'output.txt');
  rewrite(f);
  write(f,inp[1][1]);
  close(f);
  
 end.

Коментарии