Nty wyraz fibonacci

Odpowiedz Nowy wątek
2019-11-07 19:11
0

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

edytowany 2x, ostatnio: Neron101, 2019-11-07 19:31
Sformatuj kod. - lion137 2019-11-07 19:15

Pozostało 580 znaków

2019-11-07 19:21
2

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/bl[...]trix_Exponetiation_Fibo.ipynb


edytowany 1x, ostatnio: lion137, 2019-11-07 19:26
Wzory wyglądają trochę jak wariant 26 stąd: http://mathworld.wolfram.com/FibonacciNumber.html - Patryk27 2019-11-07 19:29
He, he, podali ogólną macierz relacji rekurencyjnej, a Fibonacci jest prosta: http://mathworld.wolfram.com/FibonacciQ-Matrix.html - lion137 2019-11-07 19:37
Heh, nie wiedziałem że można fib w logn policzyć. Good to know. - kq 2019-11-07 19:44
To teraz na rekrutacjach liczymy fib O(log n), nie potrafi pani, pan policzyć, to nie możemy zaproponować dolnych widełek ale 60% dolnej stawki. Jakby co, przyznaję się, też nie wiedziałem. - BraVolt 2019-11-07 19:48
Jest fib w O(1) https://gitlab.com/snippets/1879264 Niestety szybko znaczy mało dokładnie :/ (EDIT: teraz doczytałem: metoda 7 z linku Sarrusa) - Delor 2019-11-08 00:25

Pozostało 580 znaków

2019-11-07 19:44
0

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 ;)


"Ktoś sobie uświadomił, że pisał pod pseudonimem rzeczy, które lepiej żeby w firmie nie wypatrzyli :-)"

"- Ledwo na studiach 3 tydzień się kończy i już ciężko?
- Niestety prowadzący jest dziwny i robi kartkówki"

Pozostało 580 znaków

2019-11-07 20:04
2

Myślę że warto spojrzeć tu:

https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

Pozostało 580 znaków

2019-11-07 21:36
0

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.


#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;
}
edytowany 1x, ostatnio: Neron101, 2019-11-07 21:36

Pozostało 580 znaków

2019-11-07 21:54
1

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;
}

No z tym intem błąd, powinien być long double na takie duże liczby sorki, uczę się dopiero i dużo rzeczy ucieka mojej uwadze. A z mainem to już kombinowałem na różne sposoby dlatego tak - Neron101 2019-11-07 21:56
Dlaczego 'Umieszczasz' napisałeś z wielkiej litery? - Sarrus 2019-11-08 09:29
Bo w drugiej osobie. - lion137 2019-11-08 19:36
To co że w drugiej osobie? Albo coś pomieszałeś, albo jestem nie na czasie. - Sarrus 2019-11-09 15:28

Pozostało 580 znaków

2019-11-08 09:31
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.

tak kompiluje się. Całą klasę tak można napisać. Jest to dziwne i też mnie wnerwia, ale da się. - MarekR22 2019-11-08 10:50

Pozostało 580 znaków

2019-11-08 10:54
2

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.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
Właśnie, w temacie nie ma informacji, jakich typów użyć, a potem pisze o "nieograniczonych wyrazach ciągów"... - lion137 2019-11-08 11:10

Pozostało 580 znaków

2019-11-08 12:02
1

Po:

  • poprawieniu: typów, zakresów, inicjalizacji;
  • Usunięciu zbędnych warunków, załączeniu pozostałych;
  • Oraz innych niezbędnych ruchach ...
#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;
}

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0