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

[MARSHALL MATHERS]

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

[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 6:48