1.4.5. Ciąg Fibonacciego

ZADANIE: Wypisz ciąg Fibonacciego aż do n-tego wyrazu podanego przez użytkownika. Ciąg Fibonacciego to ciąg liczb naturalnych, którego każdy wyraz poza dwoma pierwszymi jest sumą dwóch wyrazów poprzednich. Początkowe wyrazy tego ciągu to: 0 1 1 2 3 5 8 13 21. Przyjmujemy, że 0 wchodzi w skład ciągu.

POJĘCIA: funkcja, zwracanie wartości, tupla, rozpakowanie tupli, przypisanie wielokrotne.

Kod nr
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#! /usr/bin/env python3
# -*- coding: utf-8 -*-


def fib_iter1(n):  # definicja funkcji
    """
        Funkcja drukuje kolejne wyrazy ciągu Fibonacciego
        aż do wyrazu n-tego, który zwraca.
        Wersja iteracyjna z pętlą while.
    """
    pwyrazy = (0, 1)  # dwa pierwsze wyrazy ciągu zapisane w tupli
    a, b = pwyrazy  # przypisanie wielokrotne, rozpakowanie tupli
    print(a, end=" ")
    while n > 1:
        print (b, end=" ")
        a, b = b, a + b  # przypisanie wielokrotne
        n -= 1


def fib_iter2(n):
    """
        Funkcja drukuje kolejne wyrazy ciągu Fibonacciego
        aż do wyrazu n-tego, który zwraca.
        Wersja iteracyjna z pętlą for.
    """
    a, b = 0, 1
    print("wyraz", 1, a)
    print("wyraz", 2, b)
    for i in range(1, n - 1):
        # wynik = a + b
        a, b = b, a + b
        print("wyraz", i + 2, b)

    print()  # wiersz odstępu
    return b


def fib_rek(n):
    """
        Funkcja zwraca n-ty wyraz ciągu Fibonacciego.
        Wersja rekurencyjna.
    """
    if n < 1:
        return 0
    if n < 2:
        return 1
    return fib_rek(n - 1) + fib_rek(n - 2)


def main(args):
    n = int(input("Podaj nr wyrazu: "))
    fib_iter1(n)
    print()
    print("=" * 40)
    fib_iter2(n)
    print("=" * 40)
    print(fib_rek(n - 1))
    return 0


if __name__ == '__main__':
    import sys
    sys.exit(main(sys.argv))

Instrukcje realizujące jedno zadanie zazwyczaj grupujemy w funkcje, które można później wielokrotnie wywoływać. Funkcję definiujemy za pomocą słowa kluczowego def wg schematu def nazwa_funkcji(parametry):. Przy czym parametry są opcjonalne. Po dwukropku od nowego wiersza umieszczamy odpowiednio wcięte instrukcje, które tworzą ciało funkcji. Funkcja może zwrócać jakąś wartość za pomocą polecenia return wartość.

Zapis a, b = pwyrazy jest przykładem rozpakowania tupli, tzn. zmienne a i b przyjmują wartości kolejnych elementów tupli pwyrazy. Zapis równoważny, w którym nie definiujemy tupli tylko wprost podajemy wartości, to a, b = 0, 1; ten sposób przypisania wielokrotnego stosujemy w kodzie a, b = b, b + a. Jak widać, ilość zmiennych z lewej strony musi odpowiadać liczbie wartości rozpakowywanych z tupli lub liczbie wartości podawanych wprost z prawej strony.

Podane przykłady pokazują, że algorytmy iteracyjne można implementować za pomocą różnych instrukcji sterujących, w tym wypadku pętli while i for, a także z wykorzystaniem podejścia rekurencyjnego. W tym ostatnim wypadku zwróć uwagę na argument wywołania funkcji.

1.4.5.1. Zadania dodatkowe

Zmień funkcje tak, aby zwracały poprawne wartości przy założeniu, że dwa pierwsze wyrazy ciągu równe są 1 (bez zera).


Licencja Creative Commons Materiały Python 101 udostępniane przez Centrum Edukacji Obywatelskiej na licencji Creative Commons Uznanie autorstwa-Na tych samych warunkach 4.0 Międzynarodowa.

Utworzony:2018-04-12 o 19:31 w Sphinx 1.5.3
Autorzy:Patrz plik “Autorzy”