Задача 35: Треугольник (VI международная
олимпиада по информатике)
Дан треугольник, составленный из чисел. Напишите программу, которая
вычисляет наибольшую сумму чисел, расположенных на пути,
начинающемся в верхней точке и заканчивающемся на основании
треугольника.
Каждый шаг на пути может осуществляться вниз по диагонали влево или
вниз по диагонали вправо.
Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.
Входные данные:
Первым числом во входном файле с именем INPUT.TXT является
количество строка в треугольнике. Пример файла исходных данных
представлен ниже.
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Выходные данные:
В выходной файл с именем OUTPUT.TXT записывается только наибольшая
сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных выше
исходных данных.
30
Пример входных данных и правильной последовательности:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Решение:
Эта задача предлагалась не только на международной олимпиаде, но и
на областной в Самаре, несколько лет назад.
Первое решение, которое приходит в голову - рекурсия - неправильное.
Здесь есть решение проще.
Для хранения треугольника заведем массив 100*100 (из элементов word,
а почему не byte вы поймете позже), часть элементов которого
останутся нулевыми. Начнем анализировать треугольник, двигаясь от
предпоследней строки к первой (такой тип движения избавит нас от
части частных случаев). Итак, смотрим на предпоследнюю строку. У нее
по диагонали снизу есть два соседа (в треугольном массиве это число
которое находится на 1 клетку ниже и число, на 1 клетку ниже и
правее данного) - выберем из них наибольший и прибавим к значению
элемента значение наибольшего из нижних соседей. Повторяя эту
операцию для каждой строки до вершины и для самой вершины, в вершине
(элемент (1;1)) получим искомую сумму. Если бы мы двигались сверху
вниз, то возникал бы случай для крайних элементов, у которых всего
один сосед.
Вот если бы нам надо было вывести маршрут, то было бы несколько
сложнее, а так задача очень проста в реализации и несложна в
понимании :)
Далее
ð
