Liczby Fibonacciego

Limit pamięci: 32 MB

Liczby Fibonacciego definiuje się w następujący sposób:

• 
• 
• dla

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę ,
• obliczy -tą liczbę Fibonacciego (),
• zapisze ją na standardowym wyjściu.

Wejście

Pierwszy i jedyny wiersz standardowego wejścia zawiera jedną liczbę całkowitą , .

Wyjście

Program powinien zapisać na standardowym wyjściu jedną liczbę całkowitą równą .

Przykład

Dla danych wejściowych:

10

poprawną odpowiedzią jest:

55

Autor zadania: W pewnym sensie Fibonacci.

Przykładowe rozwiązania

Poniżej przedstawione są przykładowe rozwiązania tego zadania w czterech językach programowania. Niestety dla dużych wartości (np. = 40) przedstawione programy działają stosunkowo wolno i stąd mogą nie zaliczyć niektórych testów.

Pascal (fib.pas)

function fib(x : integer) : longint;
begin
  if x < 2 then
    fib := x
  else
    fib := fib(x - 1) + fib(x - 2);
end;

var
   n : integer;
begin
   readln(n);
   writeln(fib(n));
end.

C (fib.c)

#include <stdio.h>

long fib(int x) {
  if (x < 2) return x;
  return (fib(x - 1) + fib(x - 2));
}

int main() {
  int n;

  scanf("%d", &n;);
  printf("%ld\n", fib(n));

  return 0; // ta linia jest wazna!
  // gdy program zwraca kod wyjscia <> 0,
  // to traktowane jest to jako blad wykonania
}

C++ (fib.cpp)

#include <iostream>

using namespace std;

long fib(int x) {
  if (x < 2) return x;
  return (fib(x - 1) + fib(x - 2));
}

int main() {
  int n;

  cin >> n;
  cout << fib(n) << "\n";
}

OCaml (fib.ml)

let rec fib n =
  if n < 2 then
    n
  else
    fib (n - 1) + fib (n - 2);;

print_int (fib (read_int ()));;
print_newline ();;