Научная работа

PASCAL: Алгоритм решения задачи "Треугольник"
Сазонов Д.О.

Года три или четыре назад на одной из студенческих олимпиад по информатике во втором туре была предложена задача:
«Дан треугольник целых чисел. Напишите программу, которая вычисляет наибольшую сумму числе, расположенных на пути, начинающимся в верхней точке и заканчивающимся на основании треугольника». Эта же задача была и в олимпиаде по информатике в ВГПУ (олимпиада проводилась в рамках недели информатики 2000г). Было очень много вариантов решения, но толком ее так никто и не решил. По сему я решил выложить свое решение данной задачи (рекурсивным методом). Вроде все работает нормально без багов.

{Задача про треугольник}
uses crt;

const max:integer=0;
      n:integer=6;

var a:array[1..10,1..5] of integer;
    path,result:array[1..10] of byte;
    max_temp:integer;
    i,j:integer;

procedure view;
var i,j:integer;
begin
 randomize;
 for i:=1 to n do
   begin
     gotoxy(40-i,i+2);
       for j:=1 to i do
        begin
          a[i,j]:=random(9);
          write(a[i,j],' ');
        end;
   end;
end;
 

procedure find(i,j:integer);

begin
if (i<=n) then
   begin
        path[i]:=a[i,j];
        find(i+1,j);
        find(i+1,j+1);
   end else begin
              max_temp:=0;
              for i:=1 to n do inc(max_temp,path[i]);
               if max=0 then max:=max_temp else
                   if max_temp>max then
                     begin
                       max:=max_temp;
                       result:=path;
                     end;
            end;
end;

begin
clrscr;

view;
writeln;
find(1,1);
writeln('Наибольший маршрут:');
for i:=1 to n do
 write(result[i],' ');
readln;
end.