Задача на треугольник Опции

[MARSHALL MATHERS]

На рисунке изображен треугольник(я напишу треугольник как он дан в массиве):
|7 |
|38 |
|810 |
|2744 |
|45265|
(типа того, палочками обочначены границы конкретно этого треугольника)
Написать прогу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающимся в верхней точке треугольника и заканчивющиймся на основании треугольника. Каждый шаг на пути может осуществлятся вниз по диогонали влево или по диогонали вправо. Число строк в треуголнике >1 и <=100. Треугольник составлен из целых чисел от 0 до 99...(это оригинальый текст задачи) надаюсь на ваши советы?!

[Atos]

Задача на динамическое программирование. Алгоритм решения такой: пусть у нас n строк. Определим для каждого элемента каждой строки его вес таким образом, чтобы вес первого элемента первой строки был равен нужному нам результату.
Шаг 0. Всем элементам n-й строки определим вес, равный их значению. Присвоим i:=n-1
Шаг 1. Рассмотрим i-ю строку. Предположим, что мы уже знаем часть искомого пути, протягивающуюся от первой строки до i-й, и знаем некоторое j-е число в i-й строке, которое принадлежит пути. Тогда для него надо определить, куда путь пойдёт дальше- вправо вниз или влево вниз. Поэтому определим вес j-го элемента как сумму его значения и максимального из весов элементов( i+1)-й строки, лежащих по диагонали влево и по диагонали вправо.
Но так как мы на самом деле ещё не знаем пути. то эту операцию повторяем для всех чисел i-й строки (т. е. j меняется от 1 до i).
Шаг 2. Если i>1, то уменьшаем i на единицу и возвращаемся к шагу 1, иначе КОНЕЦ РАБОТЫ

Надеюсь, понятно рассказал... Если, что, переспроси.

[Altair]

Задача на динамическое программирование

Не согласен!
можно и графами обойтись.

На вскидку - кажется можно решить задачу используя Флойда, заменив там знак для поиска максимального веса для пути.
Только граф из треугольника получи и все.

Получишь сложность алгоримта O(n^3).

[Marshall Mathers]

Можно попроще для ученика 9 класса...

Я вообще сначала думал просто по диогоналям вправо влево, сделал, мне сказали не правильно. Надо искать путь к наибольшему числу

[volvo]

Можно попроще для ученика 9 класса...

"Вам шашечки или ехать?" (С)

По диагоналям вправо-влево

это очень даже НЕпросто, потому как можно сначала право, потом влево, а можно 2 раза влево, а потом вправо. Представляешь себе полный перебор при числе строк = 100? Так что придется смотреть в сторону графов...

[Atos]

Не согласен!
можно и графами обойтись.

На вскидку - кажется можно решить задачу используя Флойда, заменив там знак для поиска максимального веса для пути.
Только граф из треугольника получи и все.

Получишь сложность алгоримта O(n^3).

А у приведённого алгоритма O(n^2), каждая вершина рассматривается только один раз.
Разве можно проще сделать?

[xds]

Флейм с намёком: задача на квадрат, куб, параллелепипед, массивы, процедуры, функции... ;)

"Треугольник из чисел"!

Добавлено:
Динамическое программирование - метод оптимизации перебора. Граф - структура данных. ;)

xds, а кнопку "Правка" что, отменили?

Сообщение отредактировано: volvo - 18.04.2005 20:02

[Marshall Mathers]

Пожалйста подскажите, сделайте реальную подсказку, я даже не могу представить как тут делать...

[Altair]

а что были даны фантастические?

[MARSHALL MATHERS]

Блин мне всего 15 лет, из тех слов которые вы тут написали мне ничего не понятно...Использовать то...это. Я "то" и "это" не знаю...

[volvo]

Ну так используй то, что знаешь. Я-то как могу догадаться, что тебе известно, а что нет? Телепатия?

[Atos]

MARSHALL MATHERS, так всё-таки какое именно место в моём объяснении непонятно?

Вот пример:
дан треугольник
3
6.....2
1.....4.....9

Каждому элементу должен быть присвоен некоторый вес. Пока он неизвестен.
3,?
6,?......2,?
1,?......4,?......9,?

Шаг 0.
3,?
6,?.......2,?
1,1.......4,4......9,9
У нас три строчки. Рассматриваем (3-1)=вторую строчку.

Шаг 1.
Смотрим на число 6. Влево вниз отнего - элемент с весом 1, вправо вниз - элемент с весом 4. Выбираем максимум. Это 4 . Складываем 4 и 6. Получившееся делаем весом рассматриваемого элемента.
3,?
6,10.......2,?
1,1........4,4........9,9
Теперь аналогичным образом рассматриваем второй элемент второй строй - это число 2. Выбираем максимум из 4 и 9 и складываем с двойкой. Получается вес 11.
3,?
6,10........2,11
1,1........4,4.......9,9
Элементы второй строки закончились. Переходим на шаг 2.

Шаг 2. Переходим на строчку выше. (Рассматриваем 2-1=первую строку).Возвращаемся к шагу 1.

Шаг 1. Смотрим на число 3. Выбираем максимум из 10 и 11, скаладываем.
3,14
6,10........2,11
1,1........4,4........9,9
Элементов в строке больше нет

Шаг 2. Строчек выше уже нет. Конец работы. Вес самого верхнего элемента=14, и есть максимальная длина пути.

Теперь понятнее?


Сообщение отредактировано: Atos - 19.04.2005 10:48

[MARSHALL MATHERS]

Нашел я решение в интернете, задача 1994 или 1991 года