Bagaimana menemukan fibonacci dalam jumlah besar? [duplikat]
Saya memecahkan masalah CSES di mana saya harus menemukan jumlah pertama angka Fibonacci 'n'. Kode:
#pragma GCC optimize("Ofast")
#include <iostream>
using namespace std;
int main()
{
unsigned long long int n;
scanf("%llu", &n);
unsigned long long int seq[n];
seq[0] = 0;
seq[1] = 1;
unsigned long long int mod = 1000000000 + 7;
for (unsigned long long int i = 2; i < n + 1; i++) {
seq[i] = (seq[i - 1] + seq[i - 2]) % mod;
}
cout << seq[n];
}
Masalahnya menetapkan bahwa nilai n bisa mencapai 10 ^ 18 dan oleh karena itu saya telah menggunakan unsigned long long int
untuk menginisialisasi n. Soal juga menginstruksikan untuk memberikan jawaban modulo 7. Kode berfungsi dengan baik untuk nilai n hingga 4 digit tetapi rusak ketika nilai n naik ke langit-langit atas 10 ^ 18. Ini memberikan (0xC00000FD)
kesalahan dan tidak mengembalikan apa pun. Tolong bantu saya memahami masalah di sini dan bagaimana mengatasinya. Saran lain juga akan kami hargai.
Jawaban
Dalam masalah ini
F [i] -> i bilangan Fibonacci. MOD = 1e9 + 7. n <1e18
F [n]% MOD =?
F [n] = F [n-1] + F [n-2] jika Anda menghitung ini dengan perulangan Anda mendapatkan TL
dengan cara itulah Anda dapat mengoptimalkan solusi ini
sekarang Anda menghitung F [n] dengan rekursi
F [2 * n] = - F [n] * F [n] + 2 * F [n] * F [n + 1]
F [2 * n + 1] = F [n] * F [n] + F [n + 1] * F [n + 1]
inilah solusi saya
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
void fib(ll n ,ll &a , ll &b){
if(n == 0){
a = 0;
b = 1;
return;
}
ll x, y;
if(n%2==1){
fib(n-1 ,x,y);
a = y;
b = (x+y)%MOD;
return;
}
fib(n/2 , x , y);
a = (x*(2*y +MOD -x)%MOD)%MOD;
b = ((x*x)%MOD+(y*y)%MOD)%MOD;
return;
}
int main(){
ll N , a, b;
cin >> N;
fib(N , a, b);
cout << a;
}
Saat melakukan penambahan modular, Anda perlu menerapkan mod Anda ke setiap nilai yang Anda tambahkan.
Misalnya, (a + b)% c = (a% c + b% c)% c.
Artinya dalam kode Anda:
seq[i] = (seq[i - 1] % mod + seq[i - 2] % mod) % mod;
Jika tidak, penambahan seq[i - 1]
dan seq[i - 2]
akan mengakibatkan luapan.
Baca lebih lanjut tentang aritmatika modular di sini .
Saya pikir masalah dengan kode ini adalah Anda membuat larik seq[n]
ukuran n
, yang dapat menyebabkan SEGFAULT
di Linux dan STATUS_STACK_OVERFLOW (0xc00000fd)
di Windows untuk jumlah besar, yang mengacu pada kelelahan tumpukan.
Di bawah ini saya memberikan versi yang lebih baik dari algoritme Anda, yang menggunakan ukuran memori tetap, dan untuk penambahan modulo, saya menggunakan sum_by_modulo
fungsi, untuk menghindari overflow dalam (a + b) % m
operasi, yang prinsipnya dijelaskan di sini .
#pragma GCC optimize("Ofast")
#include <iostream>
typedef unsigned long long int ullong;
ullong sum_by_modulo(ullong a, ullong b, ullong m){
ullong sum;
a %= m;
b %= m;
ullong c = m - a;
if (b==c)
sum = 0;
if (b<c)
sum = a + b;
if (b > c)
sum = b-c;
return sum;
}
int main()
{
ullong n;
ullong t1 = 0, t2 = 1, nextTerm = 0;
ullong modulo = 1000000000 + 7;
std::cout << "Enter the number of term: ";
std::cin >> n;
for (ullong i = 1; i <= n; ++i)
{
if(i == 1)
continue;
if(i == 2)
continue;
nextTerm = sum_by_modulo(t1, t2, modulo);
t1 = t2;
t2 = nextTerm;
}
std::cout << nextTerm << " ";
return 0;
}