Почему он исчисляет неправильный период Пизано

Question

    long long fibonacci_fast(long long n) {

    long long a[n]{0};
    a[0]=0;
    a[1]=1;
    for(int i=2;i<=n;i++)
        a[i]=a[i-1]+a[i-2];

    return a[n];
}

и функция для вычисления периода Пизано равна

long long get_pisano_period(long long n,long long m){
    vector<long long> vec{0,1};

    for(int i=2;i<=n;i++){
        vec.push_back(fibonacci_fast(i)%m);


    long c{2};

    for(int i=2;i<=n;i++){
    if((vec[i]!=0) && (vec[i+1]!=1)){
    c++;
    }}
    return c;
}

В основной функции я просто выводю вывод get_pisano_period (n, m)

Answer 1

Код пытается оценить период Пизано (период, с которым последовательность чисел Фибоначчи по модулю n повторяется) по модулю и тому, что выглядит как предел, но существует несколько проблем.

• В fibonacci_fast, a объявлен как массив переменной длины, нестандартное расширение компилятора в C ++. Он также инициализируется, что потребует другого расширения компилятора даже с использованием C99. В этих случаях следует использовать std::vector.

• В той же функции к a также обращаются вне границ, в l oop (последняя итерация) и когда возвращается a[n].

• В get_pisano_period есть еще один источник неопределенного поведения, внутренний l oop traverse vec до n + 1, в то время как его размер is i + 2.

Логические ошибки тоже серьезны.

• fibonacci_fast вычисляет числа Фибоначчи без применяя модуль по модулю, чтобы эти значения были неограниченными.

• Модуль применяется только перед тем, как вставить значения, возвращенные fibonacci_fast в vec внутри функции get_pisano_period, но это генерирует неправильную последовательность.

• Учитывая, как это используется в get_pisano_period, часть _fast имени fibonacci_fast является своего рода al ie, так как эта функция вызывается во внешнем l oop и каждый раз, когда он генерирует (и удаляет) все числа до возрастающего i.

• * 105 3 * Более того, следующее l oop проверяет каждую пару последующих значений (давайте оставим уже упомянутый UB) и подсчитывает пары, которые не являются {0, 1}, тогда как функция должна проверять последние два значения и вырвать из l oop, как только он найдет повторяющуюся последовательность.

Если нам нужен только период и последовательность не должна быть сохранена для дальнейшего использования, мы можем сохранять и обновлять только два последних числа без использования вектора.

long long pisano_period(long long m, long long limit = 2048)
{
    long long fib_prev{0}, fib{1};

    if ( m < 2 )
        return 1;

    for (long long count{2}; count < limit; ++count)
    {
        // Evaluate the next Fibonacci number modulo m without any array or function call
        long long fib_next{
            (fib_prev + fib) % m
        };

        // If the sequence is repeating, the loop should stop.
        if ( fib == 0  &&  fib_next == 1 )
            return count - 1;

        // It stores only the two last values, so it has to update them.
        fib_prev = fib;
        fib = fib_next;
    }
    std::cerr << "Warning: limit reached.\n";
    return limit;
}

Testable здесь .