UniLecs #135. Пирамида

Задача: представьте, что вы строите правую сторону пирамиды (см.на рисунке ниже) из N блоков (на плоскости). В пирамиде на каждом верхнем уровне блоков меньше, чем на нижнем. Необходимо определить, сколько различных пирамид можно построить из N блоков.

Входные данные: N - натуральное число от 1 до 100.

Вывод: кол-во всевозможных пирамид из N блоков

Пример: 

1. N = 3; Answer = 2
2. N = 5; Answer = 3
3. N = 6; Answer = 4

Идея: для наглядности давайте разберем 3й пример для N = 6 (смотри рисунок ниже). Если у нас есть 6 блоков, то мы можем построить след.пирамиды:

1. Пирамида из 1го уровня - все 6 блоков на 1м уровне.
2. Пирамида из 2х уровней: на второй уровень мы можем отправить 1 или 2 блока. 3 блока уже нельзя, т.к. блоков на каждом верхнем уровне должно быть меньше чем на нижнем.
3. Пирамида из 3х уровней, 3 блока на первом, 3 блока отправляем на след.уровень и уже для этого кол-ва строим новую пирамиду. Получаем 2 блока на 2м уровне и 1 блок идет на 3й. 

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

Детали реализации смотрите в коде!

Реализация:

https://gist.github.com/unilecs/4b83f5252a54c51d75b666b4f41a763c

Test:

https://dotnetfiddle.net/siMWtZ