Liczby Fibonacciego

Ciąg Fibonacciego to ciąg, w którym dwa pierwsze elementy mają wartość \(1\), a każdy kolejny element stanowi sumę dwóch poprzednich.

Pierwszych dziesięć kolejnych liczb Fibonacciego to: \(1, 1, 2, 3, 5, 8, 13, 21, 34, 55\).

Specification

Input

• \(n\) - liczba naturalna, \(n>0\).

Output

• \(n\)-ta liczba Fibonacciego.

Example

Input

n := 10

Output: \(55\)

Solution rekurencyjne

\[ Fib(n) = \begin{cases} 1 & n \leq 2 \\ Fib(n - 1) + Fib(n - 2) & n > 2 \\ \end{cases} \]

Pseudocode

funkcja Fib(n):
    1. Jeżeli n <= 2, to:
        2. Zwróć 1
    3. Zwróć Fib(n - 1) + Fib(n - 2)

Block diagram

%%{init: {"flowchart": {"curve": "linear"}, "theme": "neutral"} }%%
flowchart TD
    START(["Fib(n)"]) --> K1{n <= 2}
    K1 -- TRUE --> K2[/Zwróć 1/]
    K2 --> STOP([STOP])
    K1 -- FALSE --> K3[/"Zwróć Fib(n - 1) + Fib(n - 2)"/]
    K3 --> STOP

Solution iteracyjne

Pseudocode

funkcja Fib(n):
    1. f1 := 1
    2. f2 := 1
    3. Od i := 3 do n + 1, wykonuj:
        4. f3 := f1 + f2
        5. f1 := f2
        6. f2 := f3
    7. Zwróć f2

Block diagram

%%{init: {"flowchart": {"curve": "linear"}, "theme": "neutral"} }%%
flowchart TD
    START(["Fib(n)"]) --> K1["f1 := 1
    f2 := 1
    i := 3"]
    K1 --> K3{i <= n + 1}
    K3 -- TRUE --> K4["f3 := f1 + f2
    f1 := f2
    f2 := f3
    i := i +1"]
    K4 --> K3
    K3 -- FALSE --> K7[/Zwróć f2/]
    K7 --> STOP([STOP])

Implementation

C++

Python

Implementation - pozostałe

Haskell