Temat 8 i 9: Rekurencja i ciąg Fibonacciego – programowanie w języku Python

Cele lekcji:

Uczniowie:

• Wiedzą na czym polega rekurencja.

• Wiedzą jak się oblicza kolejne liczby ciągu Fibonacciego.

• Znają algorytmy obliczania:

  • silni

  • potęgi

  • sumy cyfr liczby

  • ciągu Fibonacciego

• Potrafią porównać algorytm iteracyjny i rekurencyjny.

• Znają zalety i wady rekurencji.

Materiały do lekcji: 

• Podręcznik INFORMATYKA 3 str. 104-113

• Serwisy do programowania online:

  • https://ideone.com/

  • https://www.onlinegdb.com/online_c++_compiler

• Film w serwisie Informatyka w praktyce: Programowanie w C++. Rekurencja i ciąg Fibonacciego

• Film: Tajemniczy ciąg Fibonacciego. Złota liczba. Boska proporcja

Rekurencja polega na wywołaniu przez funkcję samej siebie.

Rozwiązanie problemu za pomocą rekurencji polega na rozkładzie na takie same, ale mniejsze problemy, z których moĹźna zbudować rozwiązanie problemu wyjściowego i które prowadzą w końcu do problemów z rozwiązaniem bezpośrednim.

Zaletą rekurencji jest prosty zapis funkcji. Często wystarczy odwzorował definicję rekurencyjną w zapisie funkcji.

 Wady rekurencji moĹźna zauwaĹźyć dla większych danych – są związane z brakiem pamięci na przechowywanie wywołań rekurencyjnych lub duplikowaniem obliczeń. MoĹźna to zaobserwował w przypadku ciągu Fibonacciego. Rozwiązanie rekurencyjne nie sprawdza się dla większych wartości parametru n, poniewaĹź funkcja wielokrotnie wywołuje podproblemy i nie korzysta z raz obliczonego wyniku, tylko kaĹźde wywołanie oblicza niezaleĹźnie. Lepiej sprawdza się tutaj iteracja. 

Choć niewątpliwie rekurencja podnosi zwięzłość zapisu funkcji i niejednokrotnie pozwala na rozwiązanie problemów w sposób łatwiejszy niĹź iteracja, bywa nieefektywna czasowo i potrzebuje więcej zasobów pamięciowych.

SprawdĹş w  podręczniku lub Wikipedii
Ciąg Fibonacciego – ciąg liczb naturalnych określony rekurencyjnie w sposób następujący: Pierwszy wyraz jest równy 0, drugi jest równy 1, kaĹźdy następny jest sumą dwóch poprzednich 1 1 2 3 5 8 13 21 34 55 89…
Stosunek do siebie kolejnych liczb Fibonacciego to tzw.  złoty podział np. 89/55= ok. 1.618 (złote proporcje)

Silnia - liczby naturalnej n jest to iloczyn wszystkich liczb naturalnych dodatnich nie większych niż n. 4!=1*2*3*4=24

Definicja rekurencyjna silni ma postać:

Ćwiczenia do lekcji: 

Wykonaj na ocenę ćwiczenia z podręcznika:

• Ćwiczenie 1 str. 105-106 (Silnia rekurencyjnie) 

• Ćwiczenie 2 str. 107 (Silnia iteracyjnie)

• Ćwiczenie 3 str. 108 (Potęga rekurencyjnie)

• Ćwiczenie 5 str. 109 (Suma cyfr)

• Ćwiczenie 7 str. 110 (Ciąg Fibonacciego rekurencyjnie)

• Ćwiczenie 8 str. 112 (Ciąg Fibonacciego iteracyjnie)

• Ćwiczenie uzupełniające:

  • Ćwiczenie 4 ze strony 108-109 (Rekurencyjny ciąg liczb)

• Zadanie dodatkowe:

  • Zadanie 2 ze strony 113 (Złota proporcja)

Pliki do ćwiczeń pobierz z klekcji na informatyka.wsip.pl Wskazówki do wykonania ćwiczeń (wraz z gotowymi funkcjami do wykorzystania) znajdują się w podręczniku na stronach od 105 do 113. Prace naleĹźy zapisać na e-dysku .