Rekurencja ciąg Fibonacciego
Ostatnio zmodyfikowano 2019-02-23 16:28
Mavannkas 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ś. #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. 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? |
|
pekfos |
» 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. |
|
Mavannkas 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) #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. |
|
| « 1 » |