1.5.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.
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 python
# -*- 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,
while n > 1:
print b,
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(raw_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))
|
Definicja funkcji w Pythonie polega na użyciu słowa kluczowego def
,
podaniu nazwy funkcji i w nawiasach okrągłych ewentualnej listy parametrów.
Definicję kończymy znakiem dwukropka, po którym wpisujemy w następnych liniach,
pamiętając o wcięciach, ciało funkcji. Funkcja może, ale nie musi zwracać wartości.
Jeżeli chcemy zwrócić jakąś wartość używamy 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.5.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).
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: | 2017-09-08 o 19:38 w Sphinx 1.4.5 |
---|---|
Autorzy: | Patrz plik “Autorzy” |