Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
0 / 0 / 0
Регистрация: 11.02.2010
Сообщений: 7

Вычислить сумму максимальных элементов всех строк треугольника

12.02.2010, 16:26. Показов 1563. Ответов 15
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Задача переведена на русский (если что-то неясно, спросите, попробую перевести ещё точнее)
Для Паскаля запишите решение, пожалуйста)

Дан треугольник из чисел вида
X
XX
XXX
XXXX
XXXXX
с максимальным количеством строк = 100
числа в треугольнике целые и находятся в диапазоне 0..99
программа вычисляет сумму максимальных элементов всех строк
Input
6
2 8
1 1 3

Output 17

сумма может считатся только по линии (начинается сверху и идёт вниз) которая может идти строго вниз либо отклонятся по диагонали вправо вниз

Y
X Y
Y X X
нельзя сложить игрики

Y
Y X
Y X X
можно сложить

Y
Y X
X Y X
X X Y X
X X Y X X
можно сложить
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
12.02.2010, 16:26
Ответы с готовыми решениями:

Найти сумму максимальных элементов столбцов матрицы и наименьшую из сумм элементов строк
Данна вещественная матрица А (n, m). Найти сумму максимальных элементов столбцов матрицы и...

Даны длины a,b и с сторон некоторого треугольника. Найти медианы треугольника, сторонами которого являются медианы исходного треугольника
Как сделать с процедурой

Указатели. Найти сумму максимальных элементов строк матрицы.
Найти сумму максимальных элементов строк матрицы 5х4 в ДРП.

15
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
12.02.2010, 21:05
программа вычисляет сумму максимальных элементов всех строк
Условия не ясно.
А если максимальные элементы не находятся так что их можно складывать ?
Например так:
99
1 99
99 1 1

Тогда что ?

Может условие формулируется иначе, а именно:
Найти максимально возможную сумму ?

Тогда эта задача просто решается с помощью метода динамического программирования.
Считаем динамику снизу вверх и слева направо по этому треугольнику.
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
12.02.2010, 21:15
Цитата Сообщение от odip Посмотреть сообщение
Найти максимально возможную сумму ?
Я думаю, что именно так.
0
0 / 0 / 0
Регистрация: 11.02.2010
Сообщений: 7
12.02.2010, 23:26  [ТС]
не складываются 99 в последней строчке, а вместо них в сумму идёт 1

(знаю, что условие звучит жутко...оно не по-русски составлялось сначала, а было переведено)

Добавлено через 1 час 47 минут
вобщем, имеется ввиду, что число из первой строчки идёт автоматом... а другое идёт либо то, что под ним, либо в строчке под ним, но справа...(в зависимости от того, какое из них больше)

например

2
3 4
7 6 5
8 9 8

тут мы считаем: 2+4(оно ниже справа)+6(7 мы взять не можем,тк оно слева от 4)+9(тк оно под 6 и больше 8, которое справа)

я не знаю, как ещё объяснить))))
0
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
13.02.2010, 08:26
Lily001, Это в принципе задача на поиск пути с максимальным весом, например у Вас в примере есть 2 равнозначных пути
1) 2-4-6-9
2) 2-3-7-9
На маленьком примере это можно быстро найти, а при количестве строк 100, это уже сложная задача на перебор с возвратом. Хотите понять, читайте литературу на эту тему.
0
Платежеспособный зверь
 Аватар для кот Бегемот
8966 / 4389 / 1655
Регистрация: 28.10.2009
Сообщений: 11,647
13.02.2010, 14:00
нет тут никакого перебора с возвратом, это простая задача. Она просто формулировать не умеет, так она должна звучать:
двигаясь от верхнего элемента вниз или вправо вниз найти максимально возможную сумму элементов
сейчас я напишу решение

Добавлено через 15 минут
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var
a:array[1..100,1..100]of integer;
i,j,n:integer;
begin
randomize;
writeln('vvedite kol-vo strok');
readln(n);
for i:=1 to n do
for j:=1 to i do
a[i,j]:=random(100);
writeln('treugolnik chisel:');
for i:=1 to n do
begin
for j:=1 to i do
write (a[i,j]:4);
writeln;
end;
for i:=n downto 2 do
for j:=1 to i-1 do
if a[i,j]>a[i,j+1]then a[i-1,j]:=a[i-1,j]+a[i,j]else a[i-1,j]:=a[i-1,j]+a[i,j+1];
writeln(a[1,1]);
readln;
end.
1
 Аватар для Unrealler
654 / 352 / 113
Регистрация: 11.12.2009
Сообщений: 508
13.02.2010, 14:07
Цитата Сообщение от кот Бегемот Посмотреть сообщение
Pascal
1
a:array[1..100,1..100]of byte
Нужен integer, а то получается выход за пределы byte
1
Платежеспособный зверь
 Аватар для кот Бегемот
8966 / 4389 / 1655
Регистрация: 28.10.2009
Сообщений: 11,647
13.02.2010, 14:12
уже исправил, когда проверял
1
Почетный модератор
 Аватар для Puporev
64315 / 47611 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
13.02.2010, 14:51
Именно максимально возможную, а не из подряд идущих наибольших. Выбирая рядом стоящее наибольшее из двух, мы можем пропустить стоящее впереди меньшего под ним намного большее число.
Например
2
3 5
10 6 7
Путь 2-3-10 больше пути 2-5-7
1
 Аватар для yanyk1n
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
13.02.2010, 15:32
Задача на динамическое программирование. В строке I мы знаем решения для всех строк от 1 до I-1:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
uses crt;
const maxn=100;
var t,s:array[1..maxn,1..maxn]of integer;
i,j,n,m:integer;
 
function max(a,b:integer):integer;
begin
 if a>b then max:=a else max:=b;
end;
 
begin
 clrscr;
 write('Кол-во строк -> ');
 readln(n);
 for i:=1 to n do
 begin
  write('Строка ',i:2,' -> ');
  for j:=1 to i do read(t[i,j]);
  readln;
 end;
 s[1,1]:=t[1,1];
 for i:=2 to n do
 begin
  s[i,1]:=s[i-1,1]+t[i,1];
  for j:=2 to i-1 do s[i,j]:=max(s[i-1,j],s[i-1,j-1])+t[i,j];
  s[i,i]:=s[i-1,i-1]+t[i,i];
 end;
 
 m:=-1;
 for i:=1 to n do m:=max(m,s[n,i]);
 writeln('MAX=',m);
 readln;
end.
1
0 / 0 / 0
Регистрация: 11.02.2010
Сообщений: 7
13.02.2010, 18:42  [ТС]
Цитата Сообщение от k1ry4 Посмотреть сообщение
Задача на динамическое программирование. В строке I мы знаем решения для всех строк от 1 до I-1:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
uses crt;
const maxn=100;
var t,s:array[1..maxn,1..maxn]of integer;
i,j,n,m:integer;
 
function max(a,b:integer):integer;
begin
 if a>b then max:=a else max:=b;
end;
 
begin
 clrscr;
 write('Кол-во строк -> ');
 readln(n);
 for i:=1 to n do
 begin
  write('Строка ',i:2,' -> ');
  for j:=1 to i do read(t[i,j]);
  readln;
 end;
 s[1,1]:=t[1,1];
 for i:=2 to n do
 begin
  s[i,1]:=s[i-1,1]+t[i,1];
  for j:=2 to i-1 do s[i,j]:=max(s[i-1,j],s[i-1,j-1])+t[i,j];
  s[i,i]:=s[i-1,i-1]+t[i,i];
 end;
 
 m:=-1;
 for i:=1 to n do m:=max(m,s[n,i]);
 writeln('MAX=',m);
 readln;
end.
неа, не работает как надо...

1
1 2
4 3 2
6 5 4 3

по идее должно быть: 1+2+3+5=11
а выдаёт 12
0
 Аватар для yanyk1n
4342 / 1474 / 680
Регистрация: 12.03.2009
Сообщений: 5,310
13.02.2010, 18:47
Цитата Сообщение от Lily001 Посмотреть сообщение
1
1 2
4 3 2
6 5 4 3
по идее должно быть: 1+2+3+5=11
а выдаёт 12
Давай считать вместе:
1
1 2
4 3 2
6 5 4 3
1+1+4+6=?
1
0 / 0 / 0
Регистрация: 11.02.2010
Сообщений: 7
13.02.2010, 22:19  [ТС]
Цитата Сообщение от k1ry4 Посмотреть сообщение
Давай считать вместе:
1
1 2
4 3 2
6 5 4 3
1+1+4+6=?
во второй строчке по условию мы должны взять 2, а не 1... а значит ниже 3, а не 4 (тк она слева) ...и ниже 5 по той же схеме...

Добавлено через 27 минут
Почитала тут ваши дискуссии... я всё формулировать умею) просто задача изначально не на русском языке идёт, а на румынском... и учительница мне перевела, как я вам говорю... я её переспрошу в понедельник тогда...))
спасибо всем)))
0
Платежеспособный зверь
 Аватар для кот Бегемот
8966 / 4389 / 1655
Регистрация: 28.10.2009
Сообщений: 11,647
13.02.2010, 23:40
Моё решение по-любому и правильнее, и короче, и проще.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
14.02.2010, 11:55
Цитата Сообщение от Lily001 Посмотреть сообщение
во второй строчке по условию мы должны взять 2, а не 1... а значит ниже 3, а не 4 (тк она слева) ...и ниже 5 по той же схеме...
По какому условию ?
По твоему ?
В таком виде как сейчас оно содержит противоречие.
1) Брать максимальные элементы в строке
2) В то же время двигаться только вниз и вправо.
На мой вопрос - что делать если максимальный элемент в строке не может быть взять вниз и вправо - был дан ответ - что нужно брать 1 (см пост 4).
Из этого следует что условие 1 можно не соблюдать.

Вопрос - что это за задача где можно не соблюдать условие ?
Ответ - мы имеем дело с неправильной формулировкой задачи.
Чего Lily001 понять почему-то не может.

Если переформулировать задачу
1) найти максимально возможную сумму
2) В то же время двигаться только вниз и вправо.
то задача становится корректной.

Добавлено через 4 минуты
Моё решение по-любому и правильнее, и короче, и проще.
Решение не очень хорошее - портится массив a[][].
0
Платежеспособный зверь
 Аватар для кот Бегемот
8966 / 4389 / 1655
Регистрация: 28.10.2009
Сообщений: 11,647
14.02.2010, 12:17
to odip
Решение не очень хорошее - портится массив a[][].
мы ищем сумму. мы её нашли. нужен был бы массив, переприсвоили бы значения массиву b, что очень просто.
Сначала найди решение проще и лучше, потом хай чужие решения
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
14.02.2010, 12:17
Помогаю со студенческими работами здесь

Найти сумму максимальных элементов строк матрицы 5х4 ,используя указатели.
Найти сумму максимальных элементов строк матрицы 5х4 ,используя указатели.

Найти сумму максимальных элементов строк целочисленной матрицы
найти сумму крупнейших элементов строк двумерного массива целых чисел.

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

Найти сумму максимальных элементов строк матрицы
У матрице А(7х5) найти сумму максимальных элементов ее строк

В матрице найти сумму максимальных элементов ее строк и их индексы
Программа паскаль Работа с матрицами Нужна программа без процедур и функций У матрице А(7х5)...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Новые блоги и статьи
BOINC: 22 года — и всё ещё работает
Programma_Boinc 12.03.2026
BOINC: 22 года — и всё ещё работает Дэвид Андерсон написал ретроспективу. Кратко: в 2001 году он ушёл из United Devices, где был CTO, и за несколько месяцев написал ядро BOINC — клиент, сервер,. . .
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru