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

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

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

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

Пример: 

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

Реализация:

1. @akolosov364, JS: 1 балл

Если n < 3. То будет всего 1 решение. Рекурсивный проход от лучшего возможного верхнего до худшего возможного. Нужно учесть что верхняя граница может быть больше меньше n, например для 10: 4(остаток 6, но можно использовать только 3).

https://gist.github.com/KolosovAO/842a196e9ddb3aa4d9fd9bf26304d6ad

Test:

https://repl.it/@AlieksieiKoloso/task135

2. @kirillmotrichkin, Python: 1 балл

Будем рекурсивно строить пирамиды. Ведь любая верхняя часть пирамиды это тоже пирамида, но поменьше.

https://gist.github.com/superkiria/51231684f57cbefea0e815589ef7bdf1

3. @egormasharskii, С++: 3.1 балла (1 + 3*0.5 балла за доп.методы решения + 2*0.3 балла за 2 доп.варианта с помощью метода мемоизации)

Метод 1: Количество разложений для N блоков равно сумме количеств разложений ,где максимальная длина нижнего уровня уровня равна N-1,N-2,....

Метод 2. Оптимизация для предыдущего алгоритма. Запоминаем уже вычисленные значения (мемоизация) чтобы не вычислять одно и тоже. По моим замерам закэшировать удается до 90% значений.

Метод 3. Здесь мы считаем ту же формулу. Но на этот раз идем нет от конца к началу , а от начала к концу. За счет этого избавляемся от рекурсии, но возможно проигрываем по памяти и делаем возможно лишнюю работу поскольку не знаем какие значения понадобятся потом.

Метод 4. Определим решение немного иначе. Количество разложений для N блоков равно сумме количеств разложений двух типов: 1. на нижнем уровне лежит блок длины N. 2. на нижнем уровне лежит блок длины меньше N.

Метод 5. Мемоизация предыдущего алгоритма. Опять не вычисляем уже вычисленные значения. Для мойих тестов экономилось до 20% вычислений (См. GetStats метод).

Метод 6. Опять нерекурсивная динамика. Идем от тачала к концу (от 1 к N). За счет этого избавляемся от рекурсии, но получаем избыточность по памяти и лишние вычисления для ячеек которые возможно не будут нужны.

https://ideone.com/Xa5b9T

4. @my_diamonds_dancing, Python: 0.7 балла (алгоритм не оптимальный, поэтому уже при N = 70 программа работает больше минуты)

https://github.com/myDiamondsDancing/UniLecs-Tasks/blob/master/Task%20135.py

5. Антон, Haskell: 1 балл

Для того, чтобы найти количество пирамид, составленных из n блоков, пробуем начать пирамиду нижнем слоем из k кирпичей и надстроить сверху оставшимися n - k кирпичами. На надстройку будет ограничение — её основание не должно превышать k - 1блоков. Т. о., чтобы найти количество способов построить пирамиду из n блоков с основанием не более m блоков, надо перебрать все возможные основания от 1 до min(n, m), для каждого такого значения k найти количество способов построить пирамиду из n - k блоков с основанием не больше k - 1 (одинаковый этажи не допускаются) и просуммировать результаты. Количество способов построить пирамиду из n блоков равно, очевидно, количеству способов построить пирамиду из n блоков с основанием не больше n. Надо отметить, что один из вариантов пирамиды -- это один ряд из всех наличных кирпичей. Для корректности рекурсии определим для базового случая (количество блоков n = 0) значение равным 1.

Test:

https://rextester.com/XLHGU71026

6. @jinxonik, Python, C++: 1.1 балла

Метод принимает число блоков prev на предыдущем уровне и кол-во оставшихся (ещё не использованных) блоков. Запускаем цикл i от 2 до минимального из prev и rest (limit), не включая это значение. При этом если rest < prev, добавляем к счётчику пирамид единицу (т.е. учитываем пирамиду, которая образуется добавлением ряда из rest блоков). В цикле суммируем результаты рекурсивных вызовов метода calc_it со значениями i и rest-i, фактически добавляя к нашей пирамиде i блоков (при этом i всегда будет меньше rest) и идём строить дальше, имея в запасе ещё rest-i блоков). Для ускорения работы результаты кэшируем :) 

https://gist.github.com/jin-x/44c7840a45bf246d69ec0a092944ce25

C++ Test:

https://repl.it/@jin_x/UniLecs-135-pyramidcpp

Python Test:

https://repl.it/@jin_x/UniLecs-135-pyramidpy

7. @lPestl, C#, F#, C++, Blueprints Visual Scripting: (2 балла за 3 различных метода + 0.3 балла за 3 доп.реализации на 3х различных ЯП) = 2.3 балла

Метод 1 (рекурсия без цикла): C#, F#

C#
https://gist.github.com/lpestl/02b77da5b06282207fd3734b05eb9487

F#

https://gist.github.com/lpestl/060c7c110ab85e7de300fa76a8da9858

Метод 2 (рекурсия с циклом): C++

https://gist.github.com/lpestl/649b3fd532f86a753210387915c14fab

Метод 3 (оптимизированная рекурсия с циклом): Blueprints Visual Scripting

https://blueprintue.com/blueprint/nggukw9m/

8. @voodoo_woodpecker, Python: 1.5 балла за 2 отдельных метода решения!

Метод 1. Рекурсия. Работает, но медленно. Подход "снизу вверх" -- оставляем на нижнем уровне от n до минимально возможного.

Метод 2. На основании динамического программирования. Так как запоминает предыдущие результаты, то будет работать быстрее при повторных запусках. Если мы уже знаем сколько пирамидок можно построить, то возвращаем это число.

https://gist.github.com/MikePeleah/ca2427a403ad930fb63f637a667736ba

Test:

https://repl.it/@MikePeleah/UniLecs135