На главную > Программисту> Задачи > Треугольник или Обезьяна и бананы

Треугольник или Обезьяна и бананы

В вершине треугольника находится число. Под ним находятся два числа, в следующем нижнем ряду три и т.д. В основании n-этажного треугольника, получается, находится n чисел.

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

Другая формулировка.
Обезьяна спускается с дерева по правилам, указанным выше. На каждой ветке она может взять определенное количество бананов. Выбрать маршрут, при котором количество бананов будет максимальным.

  • Жадные алгоритмы.
  • Даулеткулов А.Б.
    Олимиады по информатике. Учебно-методическое пособие.
    Алматы., ИНТ, 2005. – 242с.
    См. с.177.

Интернет-конкурс Золотой сайт