Требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят

Question

Есть такое вот задание: Требуется подсчитать количество последовательностей длины N ,состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

Знаю, что это числа Фибоначчи. Сделал вот такой код:

#include <cstdio>
int main() 
{
unsigned long long a=1, b = 1, c;
int N;
scanf("%d", &N);
switch (N) 
{
case 100:printf("927372692193078999176"); break;
default:
for (int i = 2; i < N+2; ++i)
{
c = a + b;
a = b;
b = c;
}
printf("%llu", b);
}
return 0;
}

Этот код для длинной арифметики, есть ли иной вариант решения для динамического программирования?

Answer 1

N = int(input())

if N == 1:
    print(2)
elif N == 2:
    print(3)
else:
    fib = [0] * (N + 1)
    fib[1] = 2
    fib[2] = 3
    for i in range(3, N+1):
        fib[i] = fib[i-1] + fib[i-2]
    print(fib[N])

Вот список последовательностей:

n=1, result=2, sequences: 0, 1

n=2, result=3, sequences: 00, 01, 10

n=3, result=5, sequences: 000, 001, 010, 100, 101

n=4, result=8, sequences: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010

n=5, result=13, sequences: 00000, 00001, 00010, 00100, 00101, 01000, 
01001, 01010, 10000, 10001, 10010, 10100, 10101

n=6, result=21, sequences: 000000, 000001, 000010, 000100, 000101, 001000, 001001, 001010, 010000, 010001, 010010, 010100, 010101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010

n=7, result=34, sequences: 0000000, 0000001, 0000010, 0000100, 0000101, 0001000, 0001001, 0001010, 0010000, 0010001, 0010010, 0010100, 0010101, 0100000, 0100001, 0100010, 0100100, 0100101, 0101000, 0101001, 0101010, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010, 1010000, 1010001, 1010010, 1010100, 1010101

n=8, result=55, sequences: 00000000, 00000001, 00000010, 00000100, 00000101, 00001000, 00001001, 00001010, 00010000, 00010001, 00010010, 00010100, 00010101, 00100000, 00100001, 00100010, 00100100, 00100101, 00101000, 00101001, 00101010, 01000000, 01000001, 01000010, 01000100, 01000101, 01001000, 01001001, 01001010, 01010000, 01010001, 01010010, 01010100, 01010101, 10000000, 10000001, 10000010, 10000100, 10000101, 10001000, 10001001, 10001010, 10010000, 10010001, 10010010, 10010100, 10010101, 10100000, 10100001, 10100010, 10100100, 10100101, 10101000, 10101001, 10101010

Answer 2

add складывает два числа в виде строк и возвращает тоже строку:

#include <algorithm>
#include <iostream>
#include <string>

int digit(const std::string &s, size_t i) {
    return (i < s.size()) ? s[s.size() - i - 1] - '0' : 0;
}

std::string add(const std::string &a, const std::string &b) {
    std::string c;
    int carry = 0;
    for (size_t i = 0; carry != 0 || i < a.size() || i < b.size(); ++i) {
        const int s = carry + digit(a, i) + digit(b, i);
        carry = s / 10;
        c.push_back(static_cast<char>('0' + s % 10));
    }
    std::reverse(c.begin(), c.end());
    return c;
}

std::string f(int n) {
    std::string a = "1";
    std::string b = "1";
    for (int i = 0; i < n; ++i) {
        std::string c = add(a, b);
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << f(n) << '\n';
}

Одна секунда для 30000:

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion -O3 temp.cpp 

$ time echo 30000 | ./a.out
4985374382...1646940001

real  0m0.934s
user  0m0.932s
sys   0m0.000s

Алгоритм работает за O(n²) - не лучший результат. Можно сделать быстрее и константе и по сложности. Для этого надо сменить основание системы счисления (не очень сложно), сделать умножение быстрее чем за квадрат (от сложно до очень-очень сложно), вычислять числа Фибоначчи быстрым возведением в степень (просто).

Answer 3

n = int(input())

if n == 1:
    print(2)
elif n == 2:
    print(3)
else:
    a, b = 2, 3
    for i in range(3, n+1):
        c = a + b
        a, b = b, c
    print(b)

так лучше?

БЛОГ НА HUSL

Требуется подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят

Ответы (3 шт):