На рисунке изображен треугольник из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке треугольника и заканчивающемся на основании треугольника.
Код
7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
- Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо. - Число строк в треугольнике > 1 и <100. - Треугольник составлен из целых чисел от 0 до 99.
Renbo
4.05.2007 23:40
у тебя хоть написано что? чем тебе помочь-то?
мисс_граффити
5.05.2007 0:19
задание случайно не на деревья?
Lapp
5.05.2007 11:08
Цитата(Ольга @ 3.05.2007 12:57)
На рисунке изображен треугольник из чисел.
Этот треугольник представляет собой обычную матрицу, поеврнутую на 45 градусов. Ходить в такой матрице можно только направо или вниз. Реализуй ее как массив, а дальше - полный перебор.. Можно рекурсией попробовать, но стек может не выдержать..
Добавлено через 5 мин. Вот как получится, если твой пример записать таким массивом:
Код
7 8 0 4 5 3 1 4 6 8 7 2 2 5 4
Матрица всегда будет треугольная.
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
да нет же мой алгоритм абсолютно верен просто мой ввод из файла таков:
Код
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
Ольга
7.05.2007 18:13
Подскажите, пожалуйста, а можно ли обойтись без чтения из файла, а задать числа прямо в программе? Если да, то как конкретно? Очень надо так решить, помогите!!!
Ольга
10.05.2007 12:33
Еще раз прошу, а то мой вопрос затерялся. Помогите, люди добренькие (я заочница). Подскажите, пожалуйста, а можно ли обойтись без чтения из файла, а задать числа прямо в программе? Если да, то как конкретно? Очень надо так решить, помогите!!!
volvo
10.05.2007 12:45
Можно... Используя одномерный массив вместо двумерного (элементы заносятся сверху вниз, слева направо, например):
Теперь можно либо немного переделать программу, чтобы она работала сразу только с одномерным массивом, либо можно из этого 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
Цитата(Ольга @ 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 опередил
а вот так переделываешь процедуру вывода результата на экран:
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
Нет, я - Ольга, а Софа моя подруга, у нас компьютер с выходом в Интернет один на двоих (и как ты уже догадался мы обе заочницы). Большое спасибо за помощь. Ольга.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.