3
|
Задача 290. Максимум в треугольникепостоянный адрес задачи: http://www.diofant.ru/problem/858/показать код для вставки на свой сайт >> |
Задачу решили:
4
всего попыток:
4
поделиться задачей:
|
|
|
Задача опубликована:
14.06.10 08:00
Прислал:
mikev
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
1
сложность:
1
класс:
11 и старше
баллы: 100
Темы:
арифметика
|
|
Лучшее решение:
Oleg
(Олег Пилипёнок)
|
В числовом треугольнике, составленном из целых чисел, мы хотим найти такой числовой треугольник меньшего размера, чтобы сумма составляющих его чисел была максимальна.
В примере на рисунке красным цветом выделен такой максимальный треугольник. Сумма составляющих его чисел равна 42.
Теперь мы хотим решить эту задачу для треугольника побольше. Наш треугольник будет состоять из 1000 строк. Чтобы его заполнить, сгенерируем 500500 псевдослучайных чисел sk в диапазоне от -219 до 219, используя следующий линейно-конгруэнтный генератор псевдослучайных чисел:
t := 0
для k от 1 до 500500:
t := (615949*t + 797807) (mod 220)
sk := t-219
Тогда получим: s1 = 273519, s2 = -153582, s3 = 450905, а исходный треугольник будет выглядеть следующим образом
s1
s2 s3
s4 s5 s6
s7 s8 s9 s10
...
Искомый треугольник может начинаться с любого числа и продолжаться сколь угодно далеко вниз, включая в себя два примыкающих элемента из следующей строки, три элемента из строки следующей за нею, и т.д. Определим сумму треугольника как сумму всех входящих в него элементов.
Найдите наибольшую сумму треугольника, для всех треугольников, которые можно построить указанным способом.
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>