UniLecs #126_1. Строковые комбинации
UniLecsЗадача: вы работаете со строками, у вас есть след.символы: '1', '2', '3'. Необходимо определить кол-во всевозможных строк длины N, ктр состоят только из этих символов, но при этом не содержат подстроку "12".
Входные данные: N - длина строки от 1 до 30.
Вывод: кол-во всевозможных комбинаций строк
Пример: N = 3
Answer = 21
Реализация:
- @akolosov364, JS, Rust: 1.6 балла (1 балл за 1е решение, 0.5 за второй подход + 0.1 за использование второго языка программирования)
Строка начинается с первой возможной комбинации 1,2 или 3. Если начинается с 1, то следующей возможной цифрой может быть только 1 или 3. Если всего 1 символ в строке, то количество комбинаций равно 3, если предыдущий символ был 1, то 2 комбинации. Решение представляет собой рекурсивное уменьшение количества строк с мемоизацией.
https://gist.github.com/KolosovAO/69121c703da3db4301d1992d8c7dd21a
Test:
https://repl.it/@AlieksieiKoloso/task126
Решение с использованием итератора. (https://oeis.org/A001906 )
https://gist.github.com/KolosovAO/05300d7e51d38034f1727a0040b1c70b
Test:
https://play.rust-lang.org/?gist=05300d7e51d38034f1727a0040b1c70b
2. @PeYceBall, F#: 1 балл
Рассмотрим функции f и g, где f(n) = количеству строк с необходимым свойством, начинающихся на 1, и g(n) - аналогично для 2(или для 3, их количество одинаково). Можно вывести следующие рекурсивные формулы:
f(n+1) = f(n) + g(n) — после 1 идёт или 1, или 3
g(n+1) = f(n) + 2*g(n) — после 2(или 3) идёт 1, 2 или 3
Основа рекурсии: f(1) = 1, g(1) = 1. Искомой величиной будет сумма f(n) + 2*g(n)
https://gist.github.com/PeYceBall/2b68a825618ff5f173019bf892689d7e
Test:
https://repl.it/@PeYceBall/ClosedNativeAcrobat
3. @tvolf, PHP: 1 балл
Предположим, у нас есть итоговый набор строк для некоторого шага N. Попробуем посчитать, какое количество строк у нас будет на шаге N+1. Допустим, на шаге N мы имеет K строк, заканчивающихся на '1' и L строк, заканчиваюшихся на остальные допустимые символы ('2' и '3'). На новом шаге N+1 мы будем иметь (K + L) строк, заканчиваюшихся на '1' (мы можем добавить '1' к каждой входной строке). При этом общее количество строк будет равно K * 2 + L * 3, так как к строке, заканчивающейся на '1', мы можем добавить лишь '1' и '3' (последовательность символов '12' исключена по условию задачи), а к остальным строкам мы можем добавить все три символа ('1', '2' и '3'). PS. Интересно, что ту же самую последовательность 3, 8, 21, 55,... можно получить, если использовать последовательность чисел Фибоначчи (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...). При этом решение для строк длиной N текущей задачи будет равно: Solution(N) = Fibonacci(N * 2 + 2)
https://gist.github.com/tvolf/60a6b6f908a9845636b1606e212fa2ea
4. @jinxonik, Python: 3 варианта, смотри полный разбор в gist-файле: 2 балла (1 балл за первое решение + 2 * 0.5 за два доп.подхода)
Кол-во вариантов можно рассчитать так: 3*F(N-1) - F(N-2), т.е. для каждой начальной цифры вычисляем кол-во вариантов для оставшейся части строки (т.е. для N-1) и вычитаем из этого числа для сочетания 12 кол-во вариантов для оставшейся части строки (т.е. для N-2). Что интересно, эта формула является формулой чисел Фибоначчи, стоящих на чётных позициях (т.е. F(N) = fib(2*N)). Числа Фибоначчи можно вычислить обычным циклом без рекурсии (и без кэшей).
https://gist.github.com/jin-x/09c65edf2fc7917375c0f4459e4b71c4
Test:
https://repl.it/@jin_x/UniLecs-126-Comb123py
5. Антон, Rust, Haskell, Python: 1.2 балла (1 балл за решение + 0.2 балла за реализации на доп.языках программирования)
Назовём строку из '1', '2', '3', не содержащую подстроку "12", валидной. Как нетрудно показать, любая подстрока валидной строки сама является валидной строкой. Из этого следует, что любую непустую валидную строку можно получить, приписав её последнюю цифру к валидной строке.
Обозначим через T(n) число валидных строк длины n.
T(0) = 1 {""}; T(1) = 3 {"1", "2", "3"}
Допустим теперь, что нам известно T(n - 2) и T(n - 1). Выведем из этого значение T(n). Пусть у нас есть все валидные строки длины n - 1. Образуем строки длины n, взяв каждую из этих валидных строк и приписав 1, потом 2, потом 3. Всего получим 3⋅T(n - 1) строк. Не все из них являются валидными. Именно, некоторые из них оканчиваются на "12". Т. к. исходные строки являлись валидными, конечные "12" — единственное, что может сделать полученные строки невалидными. Подсчитаем количество таких невалидных строк. Эти строки были получены путём приписывания 2 к валидным строкам, оканчивающимся на 1. Т. к. все подобные строки можно получить, приписав 1 к валидной строке длиной на один символ меньше, получаем, что число полученных "испорченных" конечной подстрокой "12" строк длины n равно количеству валидных строк длины n -2. Т. о., получаем, что число валидных строк длины n равно утроенному количеству валидных строк длины n - 1 минус число валидных строк длины n - 2, или, короче,
T(n) = 3⋅T(n - 1) - T(n - 2)
Имеем рекуррентную формулу. Зная её и первые два члена последовательности, мы можем подсчитать член последовательности с любым наперёд заданным номером.
https://gist.github.com/AnthonyMikh/3cab7e8d6ff56eb62a66efff5023c24f
Test:
https://play.rust-lang.org/?gist=f24eb4c51304698e903257ac2b496125
Haskell:
https://gist.github.com/AnthonyMikh/6babdeae8449ba989af70a1e4690ebf6
Python:
https://gist.github.com/AnthonyMikh/fbd9c6f94b7dbaaaa1ba1c1e2fc633fb
6. @egormasharskii, C++, 3 метода решения, подробный разбор смотри по ссылке ниже: 2.1 балла (1 балл за 1е решение + 2*0.5 балла за два доп.решения + 0.1 балла за решение с использованием шаблонов на C++)
Решение с использованием "шаблонов" на C++:
7. @Zernov_A, Java: 1 балл
https://github.com/AlexZDeveloper/SubstringCombinations/blob/master/SubstringCombinations.java
Test: