Liczby Fibonacciego
Limit pamięci: 32 MB
Liczby Fibonacciego definiuje się w następujący sposób:
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 ();;