Помощь - Поиск - Пользователи - Календарь
Полная версия: Треугольник из чисел
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Ольга
На рисунке изображен треугольник из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника.

Код
                7                
            3        8            
        8        1        0        
    2        7        4        4    
4        5        2        6        5



- Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
- Число строк в треугольнике > 1 и <100.
- Треугольник составлен из целых чисел от 0 до 99.
Renbo
у тебя хоть написано что?
чем тебе помочь-то?
мисс_граффити
задание случайно не на деревья?
Lapp
Цитата(Ольга @ 3.05.2007 12:57) *

На рисунке изображен треугольник из чисел.

Этот треугольник представляет собой обычную матрицу, поеврнутую на 45 градусов. Ходить в такой матрице можно только направо или вниз. Реализуй ее как массив, а дальше - полный перебор.. Можно рекурсией попробовать, но стек может не выдержать..

Добавлено через 5 мин.
Вот как получится, если твой пример записать таким массивом:
Код
7 8 0 4 5              
3 1 4 6            
8 7 2
2 5
4

Матрица всегда будет треугольная.
Bard
а вот тебе и прога этой задачи:

var ar:array [1..100,1..100] of longint;
i,j,n,m:longint;
f,g:text;

{***********************************************************}
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
{***********************************************************}
procedure readdata;
begin
assign(f,'numtri.in'); reset(f);
read(f,n);
for i:=1 to n do
for j:=1 to i do read(f,ar[i,j]);
close(f);
end;
{***********************************************************}
procedure checker;
begin
for i:=2 to n do
for j:=1 to i do
if j=1 then ar[i,j]:=ar[i,j]+ar[i-1,j]
else
if j=i then ar[i,j]:=ar[i,j]+ar[i-1,j-1]
else ar[i,j]:=ar[i,j]+max(ar[i-1,j-1],ar[i-1,j]);
end;
{***********************************************************}
procedure writedata;
begin
assign(g,'numtri.out'); rewrite(g);
for i:=1 to n do
if ar[n,i]>m then m:=ar[n,i];
writeln(g,m);
close(g);
end;
{***********************************************************}
begin
readdata;
checker;
writedata;
end.

klem4
Алгоритм абсолютно не верный ...

для матрицы

1
1 1
1 1 1

Результат 11

Это как так ?
volvo
Странно... У меня на единичной треугольной матрице из 5 строк выдало 5, на исходном примере - 30... Вроде, все в порядке с алгоритмом (правда, я задавал значения как константы, может с чтением из файла не то что-нибудь?)
klem4
Да, проблема в неверном чтении из файла
Bard
да нет же мой алгоритм абсолютно верен просто мой ввод из файла таков:
Код

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Ольга
Подскажите, пожалуйста, а можно ли обойтись без чтения из файла, а задать числа прямо в программе? Если да, то как конкретно? Очень надо так решить, помогите!!!
Ольга
Еще раз прошу, а то мой вопрос затерялся. Помогите, люди добренькие (я заочница).
wacko.gif Подскажите, пожалуйста, а можно ли обойтись без чтения из файла, а задать числа прямо в программе? Если да, то как конкретно? Очень надо так решить, помогите!!!
volvo
Можно... Используя одномерный массив вместо двумерного (элементы заносятся сверху вниз, слева направо, например):
Const
vector: array[1 .. 15] of integer = (7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5);

Теперь можно либо немного переделать программу, чтобы она работала сразу только с одномерным массивом, либо можно из этого vector-а данные записать в матрицу (двумя циклами:
curr_pos := 1;
for i := 1 to n do
for j := 1 to i do begin
ar[i, j] := vector[curr_pos]; inc(curr_pos);
end;

)
samec
Цитата(Ольга @ 7.05.2007 18:13) *

Подскажите, пожалуйста, а можно ли обойтись без чтения из файла, а задать числа прямо в программе? Если да, то как конкретно? Очень надо так решить, помогите!!!

переделываешь процедуру


procedure readdata;
begin
write('введите n>');
readln(n);
for i:=1 to n do
for j:=1 to i do
begin
write('введите ar[',i,',',j,']>');
readln(ar[i,j]);
end;
end;



Добавлено через 14 мин.
volvo опередил smile.gif

а вот так переделываешь процедуру вывода результата на экран:

procedure writedata;
begin
for i:=1 to n do
if ar[n,i]>m then m:=ar[n,i];
writeln('наибольшая сумма равна: ',m);
end;

Ольга
Спасибо огромное за помощь, программу переделала. Только последняя просьба, можно немного пояснить: что мы этим задаем "write('введите n>');" и "write('введите ar[',i,',',j,']>');" ?

samec
n - это число строк треугольника, например для следующего треугольника:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

n=5
а ar[i,j] - это сами числа, которые составляют треугольник.
Ольга
Спасибо, с этим я разобралась. Только когда я ввожу цифры (7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5), то как я понимаю в данном примере наибольшая сумма чисел должна считаться по левой диагонали (7,3,8,2,4) и составит 24, а программа выдает 1345. Может я что-то не так поняла?
volvo
Значит, что-то неправильно сделала... Показывай полную программу...
Ольга
Вот что у меня получилось (на основании как предлагалось выше)
uses crt;
Const
vector: array[1 .. 15] of integer = (7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5);
var i,j,n,m:longint;
f,g:text;

{***********************************************************}
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;
{***********************************************************}
procedure readdata;
begin
write('введите n>');
readln(n);
for i:=1 to n do
for j:=1 to i do
begin
write('введите ar[',i,',',j,']>');
readln(vector[i]);
end;
end;

{***********************************************************}
procedure checker;
begin
for i:=2 to n do
for j:=1 to i do
if j=1 then vector[i]:=vector[i]+vector[i-1]
else
if j=i then vector[i]:=vector[i]+vector[i-1]
else vector[i]:=vector[i]+max(vector[i-1],vector[i-1]);
end;
{***********************************************************}
procedure writedata;
begin
for i:=1 to n do
if vector[i]>m then m:=vector[i];
writeln('naibolchay summa',m);
end;

{***********************************************************}
begin clrscr;
readdata;
checker;
writedata;
readkey;
end.
volvo
blink.gif Это где такое предлагалось? Я предлагал совсем другое, и если ты взяла ОДНУ часть от моего предложения, то будь добра взять и ВТОРУЮ, а не комбинировать непонятно что... Вот что я предлагал:

uses crt;
Const
n = 5;
vector: array[1 .. 15] of integer =
(7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5);
var
ar: array [1..100, 1..100] of longint;
m: longint;

{***********************************************************}
function max(x,y:longint):longint;
begin
if x>y then max:=x
else max:=y;
end;

{***********************************************************}
procedure readdata;
var i, j, curr_pos: integer;
begin
curr_pos := 1;
for i := 1 to n do
for j := 1 to i do begin
ar[i, j] := vector[curr_pos]; inc(curr_pos);
end;
end;

{***********************************************************}
procedure checker;
var i, j: integer;
begin
for i:=2 to n do
for j:=1 to i do
if j=1 then ar[i,j]:=ar[i,j]+ar[i-1,j]
else
if j=i then ar[i,j]:=ar[i,j]+ar[i-1,j-1]
else ar[i,j]:=ar[i,j]+max(ar[i-1,j-1],ar[i-1,j]);
end;

{***********************************************************}
procedure writedata;
var i: integer;
begin
for i:=1 to n do
if ar[n,i]>m then m:=ar[n,i];
writeln(m);
end;

{***********************************************************}
begin
clrscr;
readdata;
checker;
writedata;
readkey;
end.

(кстати, ответ должен быть не 24, а 30 - я написал об этом еще в посте №7)
Софа
Огромное спасибо!!!
Lapp
Софа, а ты Ольга??
Ольга
rolleyes.gif
Нет, я - Ольга, а Софа моя подруга, у нас компьютер с выходом в Интернет один на двоих (и как ты уже догадался мы обе заочницы).
Большое спасибо за помощь. Ольга.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.