| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

Помогите решить задачу. Проблема чисто техническая.

Glex ©   (2006-01-27 17:06:00) 

Задача C."Треугольник" (15 баллов)

Исходный текст программы: Cnn.PAS | Cnn.C | Cnn.CPP | Cnn.BAS

Входной файл: INPUT.TXT.  Выходной файл: OUTPUT.TXT.

Ограничение по времени: 1 секунда на тест

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

Вход.  Входной файл содержит несколько строк. В первой строке записано целое число N (1<=N<=100) - количество строк треугольника. В следующих N строках файла содержатся строки треугольника, состоящие из 1, 2, ..., N чисел. Все числа целые и не превосходят по модулю 1000000.

Выход. В выходной файл следует вывести найденную максимальную сумму.

Примеры входа и выхода

input.txt

output.txt

3

11

 1



2 3



5 7 6



input.txt

output.txt

5

37

     1



    2  3



  5  7   6



-11 -3  0  9



40  1  2  3  4
---------------------

Условие с нормальным оформлением: http://www.edu.baltinform.ru/data/smod/MTape/3/29/PROBLEMS.htm

В общем, я придумал решать так:

1) Загружаем данные в массив
procedure readdata;
var i, j: byte;
t: array of array of integer;
begin
Assign(input, 'input.txt');
Reset(input);
Readln(input, N);
setlength(t,N);
for i:=0 to N-1 do setlength(t[i],i+1);

for i:=0 to N-1 do begin
 for j:=0 to i do begin
   read(input, t[i][j]);
   end;
 readln(input);
 end;
close(input);
end;

Работает

2) Создаём из массива бинарноедерево.

3) Делаем обход до последнего уровня веток с вычислением суммы, каждый раз занося результат в массив.

4) Выбираем наибольшее значение из массива и пишем в выходной файл.
--------------

Проблемы с шагом 2. Как реализовать такое бинарное дерево и работать с ним? Если подскажете, с шагом 3 наверное смогу и сам разобраться.

например, для треугольника
 1
2 3
5 7 6

Дерево должно быть

    1
   /  \
  2    3
 /\    /\
5  7  7  6

-------------

Никогда не работал с этим. Меня сейчас вы наверное пошлёте на ссылки и книжки)
Но буду очень признателен, если кто-нибудь напишет часть 2. Я честно пробовал, не получилось(

---

Glex   (2006-01-30 19:41:00) [1]

program Cnn;

{$APPTYPE CONSOLE}

uses
 SysUtils, StrUtils;

var
 N: byte;
 a: array of array of integer;
 RecursiveOdd: boolean;
 path: array of string;
 passcounter: int64;
 passtring: string;
 Sum, PrevSum: integer;
 Turn: boolean = true;

procedure readdata;
var i, j: byte;
begin
Assign(input, 'input.txt');
Reset(input);
Readln(input, N);
setlength(a,N);
for i:=0 to N-1 do setlength(a[i],i+1);
 for i:=0 to N-1 do begin
   for j:=0 to i do begin
     read(input, a[i][j]);
     end;
 readln(input);
 end;
setlength(path, 2 shl (N-2));
close(input);
end;

function DecToBin(a: integer): integer;
var shag, ost: integer;
answ: string;
begin
if a=0 then result:=0 else begin
 while a <> 0 do begin
   ost:= a mod 2;
   a:= a div 2;
   answ:= intTostr(ost) +  answ;
   end;
 result:= strtoint(answ);
 end;
end;

procedure ArrayPass;
var i, j, k: integer;
prev: byte;
begin
for i:=0 to high(path) do begin
path[i]:= inttostr(DecToBin(i));
if length(path[i])<N-1 then for j:=1 to N-1-length(path[i]) do path[i]:= '0'+path[i];
 end;

for k:=0 to high(path) do begin
prev:=0;
j:=1;
Sum:= a[0][0];
for i:=1 to N-1 do begin
 if path[k][i]='0'
   then Sum:= Sum + a[j][prev]
   else begin
     Sum:= Sum + a[j][prev+1];
     inc(prev);
     end;
 inc(j);
 end;
if k=0 then PrevSum:=Sum;
if Sum>PrevSum then PrevSum:=Sum;
end;
end;

procedure evaluate;
begin
ArrayPass;
end;

procedure outdata;
begin
Assign(output, 'output.txt');
Rewrite(output);
write(Output, PrevSum);
close(output);
end;

begin
 readdata;
 evaluate;
 outdata;
end.


---

MBo   (2006-01-27 18:45:00) [2]

Полный перебор (проще написать рекурсивно ) дает 2^(N-1) путей, т.е. экспоненциальный алгоритм, нереальный при больших N. Мне сдается, что это задача на динамическое программирование.

---

Trilon1   (2006-01-27 18:13:00) [3]

Покажешь решение?
Просто интересно посмотреть.

---

Glex   (2006-01-27 18:04:00) [4]

MBo

Спасибо, попробую

---

MBo   (2006-01-27 17:39:00) [5]

бинарное дерево создавать не нужно, просто логика обхода массива должна быть подобной.

---

Glex   (2006-01-27 17:14:00) [6]

Наверное я написал слишком длинный пост и всем лень читать(

---

Наверх