Rekurencja ciąg Fibonacciego
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Rekurencja ciąg Fibonacciego

AutorWiadomość
Temat założony przez niniejszego użytkownika
Rekurencja ciąg Fibonacciego
» 2019-02-23 15:13:51
Hej, właśnie zaczynam swoją zabawę z rekurencją. Uznałem, że w ramach treningu napisze ciąg Fibonacciego rekurencyjnie i wymyśliłem takie coś.
C/C++
#include <iostream>
 
long long Fib( int n, long long = 1, long long = 1 );
int main()
{
            int n;
            std::cin >> n;
            std::cout << n << "-ty wyraz ciagu Fib = " << Fib( n );
}
long long Fib( int n, long long a, long long b )
{
            if( n < 3 )
                         return b;
   
            return Fib( n - 1, b, b + a );
}
I w sumie wszystko działa itd. Ale wszędzie widzę takie rozwiązanie tego problemu.
C/C++
int fib( int n )
{
    if( n < 3 )
         return 1;
   
    return fib( n - 2 ) + fib( n - 1 );
}
Jest dużo wolniejsze od mojego. I tu pytanie do was. Czy moje rozwiązanie jest niepoprawne? Czy może łamie zasady rekurencji? 

P-174062
» 2019-02-23 15:44:50
W twoim kodzie rekurencja jest zbędna, więc łamiesz zasadę rekurencji, która brzmi "nie używaj niepotrzebnie rekurencji". A rozwiązanie z internetu jest wolniejsze, bo to najgorsza możliwa implementacja™ wyznaczania wyrazu ciągu fibonacciego, która ma jakiś sens. Musiałbyś zrezygnować z sensu, żeby zaimplementować to gorzej.
P-174063
Temat założony przez niniejszego użytkownika
» 2019-02-23 16:28:00
Dziękuje za odpowiedź :) i wiem, że w sumie w tym przypadku rekurencja ma mało sensu bo można by było zrobić to chociażby tak.(Uznając, że n to min 3)
C/C++
#include <iostream>
int main()
{
    int n, a = 1, b = 1;
    std::cin >> n;
    while( n > 2 )
    {
        b = b + a;
        a = b - a;
        n--;
    }
    std::cout << b;
}
Ale czasem warto złamać pewne zasady aby nauczyć się nowego sposobu myślenia prawda? A zaczyna się od najbardziej banalnych spraw :D. I zapamiętam twoje słowa.
P-174064
« 1 »
 Strona 1 z 1