Расчет мод м для больших чисел Фибоначчи - PullRequest
Новая
       26

Расчет мод м для больших чисел Фибоначчи

1 голос
/ 24 июня 2019

Я получаю два предупреждения (сужение преобразования && control может достигнуть конца не пустой функции) со следующим кодом. Однако код компилируется, когда я его запускаю, он выдает следующее сообщение: Process finished with exit code 139 (interrupted by signal 11: SIGSEGV)

Код скомпилирован с использованием CLion на Ubuntu 

// calculate F(n) mod m   

#include <iostream>
#include <cmath>

long long Fiobonacci(long long n) { // Fast calculation of Fibonacci number using 'fast doubling'

    if (n == 0)
        return 0;
    else if (n % 2 == 0)
        return Fiobonacci(n / 2) * (2 * Fiobonacci(n / 2 + 1) - Fiobonacci(n / 2));
    else
        return std::pow(Fiobonacci((n + 1) / 2), 2) + std::pow(Fiobonacci((n - 1) / 2), 2);
}

long long GetPissanoPeriod(long long m){
    for (long long i = 0; i <= 6 * m ; ++i){
        if (Fiobonacci(i) % m == 0){ // if an element is zero it might be followed by a 1
            if(Fiobonacci(i+1) % m == 1)
                return i+1;
        }
    }
}

int main() {
    long long n, m;
    std::cin >> n >> m;
    long long period = GetPissanoPeriod(m);
    long long res = Fiobonacci(n % period) % m;
    std::cout << res << 'n';
}

1 Ответ

1 голос
/ 24 июня 2019

См. Модифицированный код ниже. 

 #include <iostream>
 #include <cmath>
 using namespace std;
 long long pow2(long long x)
 {
     return x * x;
  }
 long long Fibonacci(long long n) { // Fast calculation of Fibonacci number using 'fast doubling'

         if (n == 0)
                 return 0;
         else if(n <= 2)
                 return 1;
         else if (n % 2 == 0)
                 return Fibonacci(n / 2) * (2 * Fibonacci(n / 2 + 1) - Fibonacci(n / 2));
        else
                 return pow2(Fibonacci((n/2 + 1) / 2), 2) + pow2(Fibonacci((n / 2)), 2);
}

 long long GetPisanoPeriod(long long m){
         for (long long i = 2; i <= m * m ; ++i){
                 if (Fibonacci(i) % m == 0){ // if an element is zero it might be followed by a 1
                         if(Fibonacci(i+1) % m == 1){
                                return i - 1;
                         }
                 }
         }
 return 1;
 }
 int main() {
         long long n, m;
         std::cin >> n >> m;
         long long period = GetPisanoPeriod(m);
         long long res = Fibonacci(n % period) % m;
         std::cout << "res" << res<<endl;
 }

элемент управления может достигать конца ошибки неунифицированной функции из-за не возврата значения из GetPisanoPeriod. как указано @ JaMiT

Ошибка сегментации произошла из-за неверного условия завершения функции Фибоначчи. Ряд Фибоначчи определяется следующим образом. 

  Fn = Fn-1 + Fn-2

с начальными значениями 

  F0 = 0 and F1 = 1

То есть должно быть условие завершения для n = 0 и n = 1. Для n = 2 Вы не должны вызывать рекурсию, можете просто вернуть 1.

Кроме этого, в формуле вычисления Фибоначчи были исправления, как вы можете видеть. В GetPisanoPeriod элемент управления должен начинаться с 2. в противном случае он всегда будет возвращать 0.

...