Witam,
Męczę się z tym zadaniem już trochę czasu liczę na jakieś rady:
Napisz algorytm obliczania n-ty wyraz ciągu Fibonacciego. Wejście: liczba naturalna n Wyjście: n-ty wyraz ciągu Fibonacciego.
Należy napisać algorytm, który działa w czasie O(logn). Dodatkowe wymaganie to: Program powinien wczytywać wartość n z konsoli.
Zrobiłem coś takiego, no ale są błędy w kompilacji. Liczę na pomoc.
edit: kod jest niepoprawny
To jest Fibonacci? Nie wygląda:) Żeby mieć ~logn Musisz użyć algebry, mnożenie macierzy.
https://en.wikipedia.org/wiki/Fibonacci_number
Pseudokod (Python):
https://github.com/lion137/blog/blob/master/Matrix_Exponetiation_Fibo.ipynb
When google for solution, then: Showing results for fibonacci Log N
OT
rozumiem, na rozgrzewkę albo interview zamiast fizz-buzz fibonacci O(n) albo dynamicznie z użyciem 'cache'
ale O(log n) albo zrzynasz gotowca z sieci abo co? Masz sam dojść do rozwiązania? chyba, że to akurat zadanie domowe z algebry a temat był omawiany na ćwiczeniach, ty go tylko implementujesz.
ja prosty inżynier jestem, rekurencje wypasałem ;)
Myślę że warto spojrzeć tu:
https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/
Nie wiem Panowie co jest nie tak z tym kodem. Użyłem tego algorytmu z metody 6 co wysłał Sarrus ale chyba robię coś nie tak. Mogłby ktoś mi to ładnie wyjaśnić ;/
Plus jeszcze chciałbym dodać funkcję setprecision żeby można było sobie sprawdzać nieograniczone wyrazy ciągów.
C++
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
const int MAX = 1000;
int f[MAX] = {0};
int fib(int n)
{
cout << "Podaj nr wyrazu ciagu: ";
cin>>n;
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n])
return f[n];
int k = (n & 1)? (n+1)/2 : n/2;
f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
: (2*fib(k-1) + fib(k))*fib(k);
return f[n];
}
cout<<setprecision(10000);
cout<<endl<<"wyraz nr "<<n<<": "<<fib(n);
return 0;
}
Co Ty funkcję w mainie Umieszczasz? Jakie "nieograniczone wyrazy ciągów" w trzydziestu jeden bitach (int)?
const int MAX = 1000;
int f[MAX] = {0};
int fib(int n) {
if (n == 0)
return 0;
if (n == 1 || n == 2)
return (f[n] = 1);
if (f[n])
return f[n];
int k = (n & 1)? (n+1)/2 : n/2;
f[n] = (n & 1)? (fib(k)*fib(k) + fib(k-1)*fib(k-1))
: (2*fib(k-1) + fib(k))*fib(k);
return f[n];
}
int main(int argc, char **argv){
int n;
cin >> n;
cout << "\n";
cout << fib(n);
cout << "\n";
return 0;
}
Umieściłeś ciało funkcji fib w ciele funkcji main. To się w ogóle kompiluje? Na tej stronie jest możliwość skopiowania przykładu przyciskiem. Użyj go.
Jesteś pewny że po prostu masz policzyć Fibonacciego?
A nie przypadkiem Fibonacciego modulo jakaś liczba? Albo Fibonacciego dla n tak małego, że by wynik mieścił się w typie wbudowanym?
Wygląda na to, że arytmetyka wielkich liczb jest tuż za twoim zasięgiem, a to jest potrzebne by policzyć dowolnego Fibonacciego.
Po:
#include <iostream>
using namespace std;
unsigned long long fib(unsigned n)
{
static const unsigned MAX=94;
static unsigned long long f[MAX]={0,1,1};
if(n>=MAX) return (unsigned long long)-1;
if((!n)||(f[n])) return f[n];
int k=(n+1)>>1;
return f[n]=(n&1)?(fib(k)*fib(k)+fib(k-1)*fib(k-1)):(2*fib(k-1)+fib(k))*fib(k);
}
int main()
{
for(unsigned i=0;i<200;++i) cout<<i<<": "<<fib(i)<<endl;
return 0;
}