Lekcja 16,17,18,19
Embedded Files
Cele lekcji:
Dowiesz się czym jest rekurencja, oraz zrozumiesz istotę rekurencyjnego rozwiązywania problemów.
Poznasz przykład prostego fraktala w postaci drzewa binarnego.
Nauczysz się zapisywać funkcje rekurencyjne w języku Python.
Poznasz ograniczenia, jakie ma stosowanie techniki rekurencyjnej.
Nauczysz się na przykładach, jak rekurencje zastąpić iteracją i na odwrót.
Zagadnienia:
Rekurencja w programowaniu oznacza odwołanie się w wybranym kroku algorytmu rozwiązania problemu do tego samego problemu ale dla mniejszego rozmiaru danych. Algorytm, w którym stosuje się takie podejście nazywamy algorytmem rekurencyjnym.
(źródło podręcznik)Rekurencja to metoda rozwiązywania problemów która polega na rozbijaniu dużego problemu, na co raz to mniejsze części podproblemy. Robimy to aż do momentu, w którym otrzymamy problem tak prosty że jesteśmy wstanie sobie z nim poradzić.
(źródło Internet)Rekurencja w programowaniu to taka sytuacja gdy dana funkcja wywołuje samą siebie aż do momentu napotkania warunku podstawowego dla którego funkcja może zrzucić wynik.
(źródło Internet)
Fraktal to figura geometryczna, której podstawową cechą jest samopodobieństwo (podobieństwo wewnętrzne, powtarzalność). Oznacza to że we fraktalu można wydzielić fragmenty podobne do całej figury.
Drzewo binarne (jako prosty fraktal)
Drzewo pitagorejskie
Ćwiczenie 1 [163]
Tabliczka czekolady składa się z 16 kawałków (4rzędy po 4 kawałki). Zapisz rekurencyjny algorytm łamania czekolady na 16 pojedynczych kostek.
Ćwiczenie 2
Postaraj się uzyskać podobny rysunek drzewa binarnego jak na rysunku poniżej (wykorzystaj kod Z grafiki żółwia przycisk po prawej). Zmodyfikuj program aby uzyskać inne wymiary gałęzi i kąty rozwidleń.
Zmodyfikowałem współczynnik skrócenia kolejnych rozwidleń (1.2) oraz kąt rozwidleń (20st.) i 10 poziomów.
Zmodyfikowałem współczynnik skrócenia kolejnych rozwidleń (1.1) oraz kąt rozwidleń (15st.) i 7 poziomów.
Ciekawostki:
Efekt Droste ;-)
Zagadnienia:
Ciąg geometryczny rosnący. Ciąg liczbowy, w którym iloraz dwóch kolejnych wyrazów jest stały nazywamy ciągiem geometrycznym.
Program ciąg rekurencyjnie
Program ciąg iteracyjnie
Ćwiczenia wykonane w arkuszu kalkulacyjnym.
Ćwiczenie 2 [166]
a. W pliku otrzymanym od nauczyciela (L17.py) znajduje się fragment kodu źródłowego zawierający funkcję CiąRek. Dopisz kod który pozwoli wczytać liczbę n z klawiatury oraz wywołać funkcję CiągRek. Sprawdź działanie programu.
b. Napisz program który obliczy wartość n-tego wyrazu ciągu an danego wzorem:
patrz białe pole po prawej
Sprawdź działanie programu i podaj wynik dla 12.
Ćwiczenie 3 [166]
Zapisz kod źródłowy programu Ciąg iteracyjnie. Uruchom program dla różnych wartości.
Zagadnienia:
Ciąg Fibonacciego [167]
Liczby Fibonaciego
Złota Liczba 1,618033...
Złota Spirala
Film 1 [5:34]
Film 2[24:52]
Ćwiczenie 4 [170]
Napisz program L18a.py wg. powyższej specyfikacji z wykorzystaniem funkcji FIBRek (patrz Jamboard) lub L18.py
Sprawdź działanie programu dla liczb n=5, 10 i 35, (wyniki przedstaw w polu tekstowym).
Zagadnienia:
Wyznaczanie NWD (Największego wspólnego dzielnika) link do materiałów z klasy 2 LO iteracyjna wersja algorytmu.
Rekurencyjny algorytm Euklidesa.
Do tej pory poznaliśmy iteracyjną wersje algorytmu Euklidesa.
Jego wersja z dzieleniem opiera się na równości:
NWD(a,b) = NWD(b mod a,a) dla a=<b
gdzie b mod a oznacza resztę z dzielenia b przez liczbę a .
Działanie algorytmu sprowadza się do naprzemiennego wykonywania operacji wyznaczania reszty z dzielenia a mod b dla a>b oraz b mod a dla b>a, dopóki reszta z dzielenia nie jest równa 0
Ćwiczenie 6 [173]
Zapisz w tabeli przebieg algorytmu Euklidesa z dzieleniem dla liczb 192 i 42. (wyjaśnienia powyżej)
Ćwiczenie 7 173]
a. W funkcji NWDRek (patrz Jamboard L19) wskaż warunek początkowy oraz instrukcje wywołania rekurencyjnego.
b. Zapisz kod programu L19a.py, w którym użyjesz funkcji rekurencyjnej NWDRek. Uruchom program dla różnych a i b.
c. Wyjaśnij dlaczego program działa poprawnie również wtedy gdy początkowa wartość a jest większa od b.
Przypomnienie:
Żeby wyznaczyć NWD dwóch liczb rozkładaliśmy każdą liczbę na liczby pierwsze. Następnie te liczby pierwsze które powtarzały się w obu rozkładach mnożyliśmy. Iloraz tych liczb jest NWD.
W metodzie Euklidesa (reszta z dzielenia większej liczby przez mniejszą) całkowity wynik z dzielenia dzielimy przez resztę z dzielenia tak długo aż otrzymamy resztę z dzielenia = 0 . Ostatnia niezerowa reszta z dzielenia jest NWD.
Podsumowanie:
Podsumowanie:
Rekurencja w informatyce to odwołanie się w rozwiązywaniu problemu do tego samego problemu, ale dla mniejszego rozmiaru danych.
Funkcja rekurencyjna musi zawierać dwa warianty kodu: dla warunku początkowego, gdy funkcja zwraca konkretną wartość , oraz dla wywołania rekurencyjnego, w którym złożony przypadek zostaje zredukowany do prostszego.
Proces rekurencyjnego rozwiązywania problemu składa się z dwóch faz: redukowanie rozmiaru problemu (aż do takiego który można rozwiązać bezpośrednio) oraz zbieranie i łączenia wyników częściowych w rozwiązanie wyjściowego problemu.
Bardzo duża ilość wywołań rekurencyjnych może do niewydajnego działania programu. Jeśli dostępna pamięć przydzielona programowi przez system operacyjny zostanie przekroczona, program przesranie działać.
Pomoc na YT:
Pomoc na YT:
[4:53] Rekurencja wprowadzenie.
[16:49] Funkcje i rekurencja.
Do zastanowienia:
zdanie do poprawy i analizy
zdanie do poprawy i analizy
from time import sleep
print("Program obliczający sume liczb nieparzystych")
def liczb_n(m):
if m == 1:
return 1
return liczb_n(m-1)+2 # wywołanie rekurencyjnae z redukcją parametru
licznik = 0
suma=0
n=int(input("Podaj ilość liczb =>"))
while licznik < n:
suma = suma + liczb_n(n)
n=n-1
licznik=licznik+1
print(suma)
print("suma liczb nieparzystych wynosi: ", suma)
sleep(5)
Page updated
Report abuse