IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> Треугольник из чисел
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


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

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



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

Сообщение отредактировано: Lapp -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Пионер
**

Группа: Пользователи
Сообщений: 86
Пол: Мужской

Репутация: -  0  +


у тебя хоть написано что?
чем тебе помочь-то?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Ольга @ 3.05.2007 12:57) *

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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


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

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.



--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

для матрицы

1
1 1
1 1 1

Результат 11

Это как так ?


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гость






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


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Учиться, учиться еще раз учиться
***

Группа: Пользователи
Сообщений: 158
Пол: Мужской
Реальное имя: Яшар

Репутация: -  3  +


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

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5


--------------------
Чтобы поразить цель важна не точность, а смелость
Шарль Луи Монтескё
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


Подскажите, пожалуйста, а можно ли обойтись без чтения из файла, а задать числа прямо в программе? Если да, то как конкретно? Очень надо так решить, помогите!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


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


Гость






Можно... Используя одномерный массив вместо двумерного (элементы заносятся сверху вниз, слева направо, например):
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;

)

Сообщение отредактировано: volvo -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


Цитата(Ольга @ 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;

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


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

n=5
а ar[i,j] - это сами числа, которые составляют треугольник.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


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


Гость






Значит, что-то неправильно сделала... Показывай полную программу...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 15
Пол: Женский
Реальное имя: Оля

Репутация: -  0  +


Вот что у меня получилось (на основании как предлагалось выше)
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.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Гость






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)
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20





Группа: Пользователи
Сообщений: 9
Пол: Женский
Реальное имя: Софья

Репутация: -  0  +


Огромное спасибо!!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 27.09.2020 4:18
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name