алгоритм — число Фибоначчи, переполнение стека

У меня есть следующая проблема:
Я должен вычислить число Фибоначчи от другого заданного числа. Я знаю о периоде Пизано, и я пытаюсь осуществить это здесь. Это код:

#include <iostream>
#include <cstdlib>
long long get_fibonaccihuge(long long n, long long m) {
long long period = 0;
if (m % 2 == 0) {
if(m / 2 > 1)
period = 8 * (m / 2) + 4;
else
period = 3;
}
else{
if(((m + 1) / 2) > 1)
period = 4 * ((m + 1) / 2);
else
period = 1;
}

long long final_period = n % period;long long array_fib[final_period];
array_fib[0] = 1;
array_fib[1] = 1;
for (long long i = 2; i < final_period; ++i) {
array_fib[i] = (array_fib[i-1] + array_fib[i-2]) % m;
}

return array_fib[final_period - 1];
}

int main() {
long long n, m;
std::cin >> n >> m;
std::cout << get_fibonaccihuge(n, m) << '\n';
}

Он хорошо работает для небольших тестов, но проблема в том, что он не проходит следующий тест:

281621358815590 30524

Я не знаю почему. Любые предложения по поводу алгоритма я упоминал этот стр. Когда я его строил.

Я получаю ошибку: неправильный результат.

Ожидаемый результат: 11963 Мой результат: 28651

6

Решение

Если ваша задача не состоит в том, чтобы использовать периоды Пизано, я бы предложил вам использовать более распространенный известный способ вычисления n-го числа Фибоначчи с шагом log2 (n) (путем вычисления степеней матрицы 2 * 2: https://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form).

Есть две причины:

  1. Это более простой алгоритм, и это означает, что будет легче отлаживать программу
  2. Для чисел, которые вы упомянули в качестве примера, оно должно быть быстрее (log2 (n) где-то около 50, а m / 2 значительно больше).
2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]