2 lata, 3 miesiące temu
autor: Manveru

1

• Bezpośrednie łącze
• Komentarze (1)
• Oznacz jako niewłaściwe

Powyższe rozwiązanie sypnie się na rekurencji przy większych liczbach. Warto pomyśleć nad optymalizacją.

int f(int n)
{
  static int t[46] = {-1};
  if (t[n] > 0)
    return t[n];
  else
  {
    if (n < 2) 
    {
      t[n] = 1;
      return 1;
    }
    else
    {
      int i;
      for(i = 2; i <= n; ++i)
        t[i] = f(i-1) + f(i-2);
      return t[n];
    }
  }
}

2 lata, 3 miesiące temu
autor: rtb

1

• Bezpośrednie łącze
• Dodaj komentarz
• Oznacz jako niewłaściwe

Tutaj chyba nawet trzeba pomyśleć o optymalizacji (np. przez spamiętywanie) - to jest przecież akademicki przykład na to, jak zastosowanie prostej rekurencji (wynikającej wprost ze wzoru) zwiększy złożoność funkcji z liniowej względem indeksu poszukiwanego elementu do wykładniczej.

2 lata, 3 miesiące temu
autor: newton

1

• Bezpośrednie łącze
• Komentarze (1)
• Oznacz jako niewłaściwe

Ciąg Fibonacciego to funkcja definiowana rekurencyjnie, więc przy jej obliczaniu rekurencja jest rozwiązaniem, które samo się narzuca. Niestety, jest to rozwiązanie najgorsze - tak pod względem zużycia pamięci jak i czasu. Metoda z zapisywaniem wszystkich dotychczas obliczonych elementów nieco je ulepsza, ale jest wprowadzona trochę na siłę. Skoro i tak mamy korzystać z poprzednio obliczonych elementów, to po co zapisywać je wszystkie? Wystarczą przecież dwa ostatnie. Dwie funkcje - w Pascalu i w C.

function Fib (n : Integer) : Integer;
  var prev_fib, tmp, i : Integer;
  begin
    if n = 0 then Fib := 0
    else begin
      prev_fib := 0;
      Fib := 1;
      for i := 2 to n do begin
        tmp := Fib;
        Fib := prev_fib + Fib;
        prev_fib := tmp;
      end;
    end;
  end;

int fib(n)
{
        int prev_fib = 0, fib = 1, tmp, i;
        if(n == 0)
                return 0;
        for(i = 2 ; i <= n ; i++)
        {
                tmp = fib;
                fib = prev_fib + fib;
                prev_fib = tmp;
        }
        return fib;
}

Nie jest to rozwiązanie rekurencyjne, ale działa o wiele szybciej (w czasie liniowym, jak zauważyli przedmówcy) i dla obliczenia dowolnego elementu ciągu wymaga tyle samo pamięci (czyli ma stałą złożoność pamięciową).

2 lata, 3 miesiące temu
autor: Wujek_Staszek

0

• Bezpośrednie łącze
• Komentarze (1)
• Oznacz jako niewłaściwe

Kiedyś pisałem coś takiego na zaliczenie. Funkcja obliczająca wyrazy ciągu wygląda następująco:

function Fibo (n : Integer) : Integer;
    begin
        if n < 2 then Fibo := n
        else Fibo := Fibo(n-1) + Fibo(n-2);
    end;

Interfejs dopisz sobie sam.