UniLecs #144_1. Super Mario

Задача: Вспоминаем легендарную игру Супер Марио. Надеюсь, все помнят правила: чтобы спасти принцессу, Супер Марио нужно преодолеть N ступенек. Также известно, что Марио прыжком может преодолеть не более K ступенек. 

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

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

Вывод: кол-во всевозможных способов добраться до принцессы.

Пример: 

1. N = 10; K = 1

Answer = 1

2. N = 4; K = 3

Answer = 7; 

1 + 1 + 1 + 1;  1 + 1 + 2;  1 + 2 + 1; 

2 + 1 + 1;  2 + 2; 

1 + 3;  3 + 1

Реализация:

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

Для решения задачи стоит использовать рекурсию, но так как для больших значений n будет слишком большая глубина стека, то лучше её мемоизировать. На каждом шаге марио может пройти от 1 до k шагов, соотвественно k никогда не меняется, а меняется только n. Когда у марио не осталось шагов или остался 1 шаг можно сделать вывод что у него остался только 1 возможный вариант.

https://gist.github.com/KolosovAO/bf3d077c67f79d7af99a6d84f25a2218

Test: https://repl.it/@AlieksieiKoloso/task144?language=nodejs

Визуализация: (#N,K - параметры)

https://kolosovao.github.io/mario.html#25,3

2. @kirillmotrichkin, Java, Python: 1.1 балла

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

https://gist.github.com/superkiria/6f89e8653565ff4b5dd63b70b306ccdc

Test Java: https://repl.it/@superkiria/unilecs144-java

Test Python: https://repl.it/@superkiria/unilecs144-py

3. @egormasharskii, C++, Python (1 + 0.3 балла за метод 2 + 4*0.5 за 4 доп.метода + 0.1 балла за решение на Python) = 3.4 балла

Метод 1. Рекурсивное решение в лоб. Для ступеньки i, количество способов в нее попасть равно сумме количества способов попасть в k предыдуих клеток.

Метод 2. Мемоизация предыдущего решения. Если мы посещаем какую-то ячейку, то запоминаем значение и если будет еще обращение то достанем сохраненное.

Метод 3. Переписанные первые два решения на прямой ход динамики. Не используем рекурсивные функции и мемоизацию. Все промежуточные результаты лежат просто в массиве. Для каждого номера ступеньки смотрим предыдущие k ступенек.

Метод 4. Предыдуще алгоритмы имели сложность O(n*k) в лучшем случае. Можно быстрее - (O(n)). Для этого будем идти по ступеньками от 1 до n и поддерживать переменную sum равную сумме предыдущих k элементов массива. Итого мы проидем по всем элементам массива обновляя значения окна за O(1).

Метод 5. Все тоже самое, но здесь при проходе по массиву мы "смотрим" не назад, а вперед. Это похоже на симуляцию всех возможных прыжков Марио с помощью BFS (поиск в ширину).

Метод 6. Все тоже самое, но здесь при проходе по массиву мы "смотрим" не назад, а вперед. Это похоже на симуляцию всех возможных прыжков Марио с помощью DFS (поиск в глубину).

https://gist.github.com/myegor/7c9096bf6d15e38e9e5abf851e7dab8c

Python: https://gist.github.com/myegor/8310bd0133d907ee54d894ef61052aec

Test C++: http://cpp.sh/8lthv

4. @LostInKadath, С++: 1 балл

Решение основано на рекурсивном подходе. Мы заводим массив слагаемых `numbers` - очевидно, он будет иметь размерность N (N единиц-слагаемых максимум). Далее работаем с этим массивом, начиная с первого слагаемого, следующим образом: - мы заполняем текущую ячейку единицей и рекурсивно решаем задачу для входных данных (N-1) и K; - после получения решения для единицы ставим на ее место двойку и рекурсивно решаем задачу для (N-2) и K; - ...Условием выхода из рекурсии служит условие `N <= 0`. Так как на каждой итерации рекурсии мы уменьшаем рассматриваемое число, то рано или поздно наступит момент, когда слагаемые закончатся. В этот момент мы увеличиваем счетчик способов на 1, печатаем содержимое массива слагаемых и возвращаемся на шаг рекурсии назад.

https://gist.github.com/LostInKadath/bd6aee24bd2c77eedd437d5cd874df06

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

Если ступенек нет (n = 0), то количество путей равно 1. Иначе количество способов добраться до i-ой ступеньки равно сумме k предшествующих элементов. На отрезке n <= k количество способов добраться до n-ой ступеньки равно:

1, если n = 1,

2^n - 1, если n ≠ 1.

Это несложно доказать методом математической индукции.

Haskell: https://gist.github.com/AnthonyMikh/dc6ef4b8ecc45ca787fbc354c5b576ff

Rust: https://gist.github.com/AnthonyMikh/b9d792f3f8a0399d0334af2959d4b82a

Test Haskell: https://rextester.com/GVUCLA64569

Test Rust: https://play.rust-lang.org/?gist=72f58e3f8bd16e73ab4d0032b281d8c4

6. @VVildVVolf, Go, F#: 1.1 балла

Go: https://gist.github.com/VVildVVolf/55e39deb1b640dac51df82746144ca54

Test Go: https://play.golang.org/p/2dCtkmxUfXo

F#: https://gist.github.com/VVildVVolf/5dd558c5469968cdc6204bce46788882

Test F#: https://dotnetfiddle.net/LMfhvi

7. @jinxonik, Python, Ruby (1 + 0.3 балла за оптимизацию + 0.1 балла за доп.ЯП) = 1.4 балла

Метод 1. Перебираем все варианты прыжков (i): от 1 до минимума из n и k. Вызываем себя рекурсивно, передав кол-во оставшихся ступеней (n-i). Если ступеней больше нет (т.е. вы нашли один из вариантов), возвращаем 1. n - кол-во ступеней, k - максимальная величина прыжка (1 k <= n <= 100).

Метод 2. Оптимизированный вариант, использующий кэширование результатов. Детали смотрите в реализации.

https://gist.github.com/jin-x/71b05ad55924ea5c2251c6b22da38d80

Test Python: https://repl.it/@jin_x/UniLecs-144-mariopy

Test Ruby: https://repl.it/@jin_x/UniLecs-144-mariorb