Учитывая целое число N больше нуля. Сколько существует последовательности из 1 и 2 таких, что сумма чисел в последовательности = N? (не обязательно, чтобы каждая последовательность должна содержать как 1, так и 2) пример: для N = 2; 11,2 => ans = 2 последовательности 1 и 2 для N = 3; 11,12,21 => ans = 3 последовательности 1 и 2'sУчитывая целое число N, большее нуля. Сколько последовательностей 1 и 2 есть
Можно вспомнить рекурсивную формулу, например, характеризуя последние цифры. Например, последовательность N + 1 может быть получена путем конкатенации последовательности N и a 1 или последовательности N-1 и a 2. Таким образом, она дает:
R (N + 1) = R (N) + R (N-1)
Итак, у нас есть последовательность типа Фибоначчи с R (1) = 1 и R (2) = 2.
См https://en.wikipedia.org/wiki/Fibonacci_number
Это дает
где и
.
Таким образом, вы можете запрограммировать ответ, используя постоянное количество операций.
Это так http://math.stackexchange.com/, если вы спросите меня. – frenzykryger
Можете ли вы предоставить мне свое решение, пожалуйста? –
Все еще есть очевидный способ перечислить их всех - вы начинаете с последовательности из N, затем заменяете 11 на 2 раза во всех возможных местах, затем заменяете 11 на 2 раза во всех возможных местах и так далее, пока не закончите последовательность 2s или последовательность 2s только одна 1 (во всех возможных положениях) – frenzykryger