Версия для печати темы

Автор: Ольга 3.05.2007 15:57

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

- Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
- Число строк в треугольнике > 1 и <100.
- Треугольник составлен из целых чисел от 0 до 99.

Автор: Renbo 4.05.2007 23:40

у тебя хоть написано что?
чем тебе помочь-то?

Автор: мисс_граффити 5.05.2007 0:19

задание случайно не на деревья?

Автор: Lapp 5.05.2007 11:08

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

Добавлено через 5 мин.
Вот как получится, если твой пример записать таким массивом:

Матрица всегда будет треугольная.

Автор: Bard 5.05.2007 18:01

а вот тебе и прога этой задачи:

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 5.05.2007 19:56

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

для матрицы

1
1 1
1 1 1

Результат 11

Это как так ?

Автор: volvo 5.05.2007 20:23

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

Автор: klem4 5.05.2007 21:20

Да, проблема в неверном чтении из файла

Автор: Bard 5.05.2007 23:27

да нет же мой алгоритм абсолютно верен просто мой ввод из файла таков:

Автор: Ольга 7.05.2007 18:13

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

Автор: Ольга 10.05.2007 12:33

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

Автор: volvo 10.05.2007 12:45

Можно... Используя одномерный массив вместо двумерного (элементы заносятся сверху вниз, слева направо, например):

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 10.05.2007 12:48

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

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 опередил

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

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

Автор: Ольга 10.05.2007 14:43

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

Автор: samec 11.05.2007 8:15

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

n=5
а ar[i,j] - это сами числа, которые составляют треугольник.

Автор: Ольга 11.05.2007 12:36

Спасибо, с этим я разобралась. Только когда я ввожу цифры (7, 3, 8, 8, 1, 0, 2, 7, 4, 4, 4, 5, 2, 6, 5), то как я понимаю в данном примере наибольшая сумма чисел должна считаться по левой диагонали (7,3,8,2,4) и составит 24, а программа выдает 1345. Может я что-то не так поняла?

Автор: volvo 11.05.2007 12:43

Значит, что-то неправильно сделала... Показывай полную программу...

Автор: Ольга 11.05.2007 12:55

Вот что у меня получилось (на основании как предлагалось выше)
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 11.05.2007 13:03

Это где такое предлагалось? Я предлагал совсем другое, и если ты взяла ОДНУ часть от моего предложения, то будь добра взять и ВТОРУЮ, а не комбинировать непонятно что... Вот что я предлагал:

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)

Автор: Софа 11.05.2007 13:21

Огромное спасибо!!!

Автор: Lapp 11.05.2007 14:45

Софа, а ты Ольга??

Автор: Ольга 11.05.2007 14:54

Нет, я - Ольга, а Софа моя подруга, у нас компьютер с выходом в Интернет один на двоих (и как ты уже догадался мы обе заочницы).
Большое спасибо за помощь. Ольга.