Ciąg Fibonacciego - review

0

Witam
Pytanie typowo pod rozmowę rekrutacyjną. Czy da się poniższe prościej napisać?

#include <iostream>
#include <vector>
#include <exception>

using namespace std;

void wygenerujCiag(const int n, vector<int>& ciag)
{
    if(n >= ciag.size())
       throw std::runtime_error("Invalid ciag");

    if(!n)
    {
        ciag.at(0) = 0;
        return;
    }

    wygenerujCiag(n-1, ciag);

    if(n==1)
        ciag.at(1) = 1;
    else
    {
        ciag.at(n) = ciag.at(n-1) + ciag.at(n-2);
    }
}

void wypiszCiagFibonacciego(const int& n)
{
    std::vector<int> ciag(n+1);
    try
    {
        wygenerujCiag(n, ciag);
    }
    catch(const std::runtime_error& exc)
    {
        cout << exc.what() << endl;
    }
    
    cout << ciag.at(0) << endl;
    cout << ciag.at(1) << endl;
    for(size_t i = 2; i< ciag.size(); ++i)
        cout << ciag.at(i) << " = " << ciag.at(i-1) << " + " << ciag.at(i-2) << endl;
}

int main()
{
    wypiszCiagFibonacciego(10);

    return 0;
}

Prościej mogłoby być tak:

#include <iostream>

using namespace std;

constexpr int wygenerujCiag(const int n)
{
    return n >= 2 ? wygenerujCiag(n-2) + wygenerujCiag(n-1): n;
}

int main()
{
    for(int i=0;i<10;++i)
    cout << wygenerujCiag(i) << endl;

    return 0;
}

ale wtedy liczymy dużo więcej razy ten sam wyraz ciągu z tym że w czasie kompilacji więc może to bez znaczenia?

1

Ja bym to iteracyjnie policzył, jeśli i tak chcesz całą tablicę wyników. Dużo prościej i masz jasną złożoność, w przeciwieństwie do liczenia na to, że kompilator się domyśli.

Jak tablicy wszystkich wyników nie potrzebujesz to w ogóle inaczej bym to zrobił - jakąś prostą lambdą z std::exchange na 2 ostatnich liczbach.

throw std::runtime_error("Invalid ciag");

;​D

2

Dlaczego to tak strasznie wygląda? Ten drugi, "prostszy" kod to rak w złożoności O(Fib(n)), a pierwszy to IMHO wtf jakiś - ja rozumiem, że nie piszę w C++ nic to może nie ogarniam, ale taki kod nie zachęca ani trochę, żeby zacząć.
Nie można tak (modulo nazwanie zmiennych)?

int fib(int n)
{
    if(n == 1 || n == 2)
        return 1;    

    int a1 = 1;
    int a2 = 1;
    int temp;
    for(int i = 2; i < n; i++)
    {
        temp = a1 + a2;
        a1 = a2;
        a2 = temp;
    }
    return a2;
}

Jeśli potrzebna jest tablica to można sobie tablicować wartości w trakcie, jeśli nie to wystarczy dla sensownych wartości n.

0

ok czyli jak nie zależy nam na tym by wynik był wygenerowany w czasie kompilacji to używać lepiej zwykłej iteracji. Przewaga nad rekurencją też jest taka że dla bardzo dużych n nie będzie przepełnienia stosu co przy rekurencji mogłoby teoretycznie wystąpić.

0

Jak wynik chcesz w czasie kompilacji to możesz iterować (poza C++11 i starszymi)

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