Во время подготовки к олимпиадам по информатике мне попалась довольно-таки интересная задача. После двухчасового размышления над ней на уроке литературы, светлых идей мне в голову не пришло. Однако, вернувшись к ней через месяц, я смог относительно легко придумать решение за полчаса, и демонстрирую его вам.
Задача:
Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.
Требуется написать программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только "маленькие" треугольники, а вообще все треугольники — в частности, треугольник, выделенный жирным, а также вся фигура, являются интересующими нас треугольниками). На вход программе подаётся N - высота главного треугольника.
Путей решения данной задачи существует великое множество. Так как я не силен в комбинаторике, то именно динамика сразу пришла мне в голову.
Можно заметить, что в каждый следующий треугольник, начиная с треугольника высоты 3, входит ровно три треугольника высоты N - 1. Соответственно, мы можем использовать вычисленное для них значение треугольников. Однако, т.к. часть треугольников накладывается друг на друга, нам необходимо это учесть
Можно также заметить, что при наложении получается три треугольника величины N-2. Соответственно, значения для данных треугольников надо вычесть трижды. Тогда мы потеряем треугольник в центре высоты N-3, в котором все наложения сходятся. Чтобы этого не случилось, добавляем кол-во треугольников для треугольника высоты N-3 в решение.
Внимательный читатель также может заметить, что в нашей модели не учтен большой треугольник, а также то, что при четных N в центре появляется дополнительный треугольничек, повернутый вниз. Добавив соответствующие правки, получим готовую формулу!
Итоговый код решения на питоне:
Заключение: никогда не сдавайтесь! То, что не получилось сегодня, получится позже, если вы будете активно работать
UPD: ссылка на задачу