 Задача на треугольник |
Прочтите прежде чем задавать вопрос!
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
| MARSHALL MATHERS |
  15.04.2005 22:27
Сообщение
#1
|
|
Гость  |
На рисунке изображен треугольник(я напишу треугольник как он дан в массиве):
|7 | |38 | |810 | |2744 | |45265| (типа того, палочками обочначены границы конкретно этого треугольника) Написать прогу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающимся в верхней точке треугольника и заканчивющиймся на основании треугольника. Каждый шаг на пути может осуществлятся вниз по диогонали влево или по диогонали вправо. Число строк в треуголнике >1 и <=100. Треугольник составлен из целых чисел от 0 до 99...(это оригинальый текст задачи) надаюсь на ваши советы?! |
 
|
|
  |
Ответов
| Atos |
18.04.2005 9:42
Сообщение
#2
|
 Прогрессор  Группа: Модераторы Сообщений: 602 Пол: Мужской Реальное имя: Михаил Репутация:  9  |
Цитата(Oleg_Z @ 16.04.05 5:17) Не согласен! можно и графами обойтись. На вскидку - кажется можно решить задачу используя Флойда, заменив там знак для поиска максимального веса для пути. Только граф из треугольника получи и все. Получишь сложность алгоримта O(n^3). А у приведённого алгоритма O(n^2), каждая вершина рассматривается только один раз. Разве можно проще сделать? |
   |
|
Сообщений в этой теме
MARSHALL MATHERS Задача на треугольник 15.04.2005 22:27
Atos Задача на динамическое программирование. Алгоритм ... 16.04.2005 5:22 Altair
Не согласен!
можно и графами обойтись.
На в... 16.04.2005 8:17 Marshall Mathers Можно попроще для ученика 9 класса...
Я вообще сн... 16.04.2005 13:16
volvo "Вам шашечки или ехать?" (С)
это очень... 18.04.2005 8:54 xds Флейм с намёком: задача на квадрат, куб, параллеле... 18.04.2005 15:36 Marshall Mathers Пожалйста подскажите, сделайте реальную подсказку,... 18.04.2005 21:27 Altair а что были даны фантастические? :) 18.04.2005 21:36 MARSHALL MATHERS Блин мне всего 15 лет, из тех слов которые вы тут ... 18.04.2005 22:05 volvo Ну так используй то, что знаешь. Я-то как могу дог... 18.04.2005 22:07 Atos MARSHALL MATHERS, так всё-таки какое именно место ... 19.04.2005 6:44 MARSHALL MATHERS Нашел я решение в интернете, задача 1994 или 1991 ... 19.04.2005 22:18 |
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
Текстовая версия | 20.07.2025 16:53 |