Úvod do programování 10. hodina

Úvod do programování 10. hodina RNDr. Jan Lánský, Ph.D. Katedra informatiky a matematiky Fakulta ekonomických studií Vysoká škola finanční a správní 2015

Umíme z minulé hodiny 

Syntax  

Dvojrozměrné pole Pole polí 



String.Split()

Algoritmy   

 

Násobení řádku matice konstantou Prohození dvou řádků matice Součet matic Součin matic ASCII Art

Jan Lánský

Úvod do programování 10. hodina

2

Cíle hodiny 

Rekurze  

  

Faktoriál Přetečení, nekonečná rekurze Převod z desítkové do dvojkové soustavy Vztah rekurze a cyklu Fibonacciho čísla 

  

Verze s dynamickým programováním

Binární vyhledávání Hanojské věže Kochova vločka

Jan Lánský


3

Rekurze: Motivace 

Volání funkce sama sebou 



Kratší a přehlednější zdrojové kódy než v případě zápisu bez pomocí rekurze 



jednotlivá volání jsou nazývána zanoření

Vystihnutí hlavní myšlenky algoritmu

Oproti zápisu bez pomocí rekurze pomalejší běh programu (desítky procent) 

Při špatném použití i zhoršení časové složitosti řádově

Jan Lánský


4

Pravidla použití rekurze 

Problém lze rozdělit na menší podproblémy, které vyřeší téže rekurzivní funkce 



 

nebo převést problém na menší podproblém

Parametr(y) rekurzivní funkce se musí v každém zanoření přibližovat testované hodnotě v ukončovací podmínce Rekurze musí být ukončena podmínkou testující parametr(y) rekurzivní funkce Nepoužívat rekurzi pro kritické systémy (elektrárny, letadla)

Jan Lánský


5

Rekurze: faktoriál Faktoriál n! = 1*2*…*(n-1)*n

Nerekurzivní řešení: V cyklu násobíme 1 až n

Ukončení rekurze Rekurzivní volání funkce sama sebe se sníženou hodnotou parametru.

n! = n * (n-1)! Zanoření funkce Jan Lánský


6

Faktoriál: formálně 

Faktoriál n je součin čísel od 1 do čísla n 



Faktoriál n-1 je součin čísel od 1 do čísla n - 1 



n! = 1 * 2 * 3 * … * (n-2) * (n-1) * n (n-1)! = 1 * 2 * 3 * … * (n-2) * (n-1)

Faktoriál n vyjádříme pomocí faktoriálu n-1  



n! = (n-1)! * n pro n > 1 n! = 1 pro n = 1 a pro n = 0 Tento zápis je rekurzivní

Jan Lánský


7

Rekurze: ladění

Funkce je zanořena, breakpoint byl aktivován opakovaně

Breakpoint

Světlý podklad značí, že tato funkce je vykonávána Jan Lánský


8

Rekurze: Call stack Aktuálně se volá faktoriál s hodnotou parametru 4

Zásobník volání funkcí

Funkce Main Kliknutím na řádek aktivujeme libovolnou funkci a můžeme prohlížet její proměnné Jan Lánský


9

Faktoriál s výpisy

Aby šel provést závěrečný výpis, museli jsem zavést proměnnou na výsledek Jan Lánský

Na začátku funkce napíšeme s jakými parametry je volána

Na konci funkce napíšeme, jaká je její výsledná hodnota


10

Faktoriál s výpisy

Postupně jsme se zanořovali od 8 do 1

Pro 1 se ukončí rekurze

Postupně jsme se vynořovali od 1 do 8 Faktoriál pomocí cyklu počítá obdobně jako vynořování z rekurze Jan Lánský


11

Součet čísel 1 až n Obdoba faktoriálu Faktoriál je součin čísel od 1 do n.

Faktoriál roste velmi rychle, došlo by k přetečení datového typu. Proto ukazujeme součet

Kolik je 1+2+ …+ 10000 ?

Nemuseli jsme nic počítat Sn = n*(n + 1)/2 Jan Lánský


12

Přetečení zásobníku volání

Došla paměť, přetečení zásobníku

Jan Lánský


13

Přetečení zásobníku volání 

Pokud voláme rekurzivní funkci je nám povolen jen omezený počet zanoření (dle velikosti zásobníku volání)  



V případě SoucetOd1DoN to bylo 1446 Pro rozumné použití rekurze dostatečně Nejčastěji dojde paměť při nekonečné rekurzi (chybí ukončující podmínka rekurze)

Jan Lánský


14

Konečnost rekurze 



Nepřímá rekurze Občas se zapomene ukončit, pak vznikne nekonečná rekurze

Rekurzivní funkce musí být vždy zakončena  Rejstřík podmínkou pro  Cyklus nekonečný testování hodnoty  Viz Nekonečný cyklus parametru funkce  Nekonečný cyklus Parametr funkce se  viz Cyklus nekonečný musí v jednotlivých voláních blížit testované hodnotě Faktorial (n) = n * Faktorial (n-1) Faktorial (1) = 1

Jan Lánský


15

Převod z desítkové do dvojkové soustavy (little endian)

Little endian: Postupně vypisujeme zbytky po dělení číslem dvě. Big endian: Obtížnější, museli bychom mít pomocné pole 13 = 6 * 2 + 1 6=3*2+0 Jan Lánský

3=1*2+1 1=0*2+1

Little endian: Postupně vypisujeme zbytky po dělení číslem dvě. Big endián: Stačí prohodit výpis a rekurzivní volání 1310  10112 (little endian) 1310  11012 (big endian)


16

Nepoužívat: Uvádíme jen pro ilustraci. Cyklus se vyhodnotí rychleji

Převod cyklu na rekurzi Konec rekurze při nesplnění podmínky

Voláme rekurzivní funkci s novou hodnotu x Místo cyklu vložíme volání rekurzivní funkce

Jan Lánský


17

Náhrada rekurze 

Rekurze je silnější prostředek než cyklus 



Převod rekurze na cyklus (cykly) 







náhradu nelze provést automaticky

Podmínka ukončující rekurzi odpovídá podmínce cyklu Problematický vyšší počet rekurzivních volání (stromová rekurze) Velmi často je nutno použít datovou strukturu zásobník (bude probírána později)

Odstranění rekurze použitím jiného algoritmu 

bude za chvíli Fibonacci

Jan Lánský


18

Odstrašující příklad na rekurzi

Řádu 2

Fibonacciho čísla 

   

Stromová rekurze: Rekurzivní volání je dvakrát

F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) pro n>1 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … Zlatý řez limnoo F(n) / F(n-1)  

= (1+ 5) / 2 = 1.618 Vyskytuje se často v přírodě (listy, ulita)

Jan Lánský


19

Fibonacciho čísla F(0) = 0 F(1) = 1

Fibonacci(20); Fibonacci(30); Fibonacci(50);

Jan Lánský

F(n) = F(n-1) + F(n-2) Proč je tak pomalé ? Stromová rekurze Časová složitost O(2N) Úvod do programování 10. hodina

20

Opakovaně počítáme ty samé hodnoty. Exponenciální časová složitost

Fibonacciho čísla 5

Kolikrát počítáme F(0) 3x F(1) 5x F(2) 3x F(3) 2x F(4) 1x F(5) 1x

3

2

1

Jan Lánský

3

4

2

1

1

2

0

1

1

0

0 Úvod do programování 10. hodina

21

Fibonacciho čísla lineárně Časová složitost O(N)

Technika „Dynamické programování“: Rozklad problému na podproblémy a jejich řešení je uloženo pro další použití Postupně počítáme F(0), F(1), F(2) až F(n). Stačí si nám pamatovat dva poslední členy posloupnosti F(n-1) a F(n-2)

Jan Lánský


22

Fibonacciho čísla lineárně Př: červená barva kružnice F(1) a F(2) Červená barva pole F(3) = F(1) + F(2)

F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8) F(9) 0

1

F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(1) F(2) F(3) F(4) F(5) F(6) F(7) F(8)

0

1

1

Jan Lánský

2

3

5

8

13


21

34

23

Binární vyhledávání 

Hledání prvku v setříděném poli. 





V 5. přednášce byla probrána nerekurzivní verze

Rozpůlíme pole na dvě poloviny, podle hodnoty dělícího prvku se rozhodneme, ve které polovině by se měl prvek nacházet Rekurzivní verze má také O(log(N)) Časová složitost O(log(N)) Jan Lánský


24

Pole setříděné vzestupně

Binární vyhledávání Lineární rekurze, nikdy se neprohledá levá i pravá část najednou

Prvek nenalezen, konec rekurze

Rekurzivně prohledáme levou nebo pravou část pole – dle hodnoty středového prvku

Prvek nalezen, konec rekurze

Pro rekurzivní verzi potřebujeme znát jakou část pole prohledáváme (začátek, konec) Jan Lánský

Volání z nerekurzivní funkce: častý trik


25

Binární vyhledávání Hledáme hodnotu 5 v poli p 0

4

9

5 4 5 4 5 6 7 9

0 1 1 2 3 4 5 6 7 9 Jan Lánský

BVNajdi (p, 6, 6, 5) stred = 6, p[stred] == x BVNajdi (p, 5, 6, 5) stred = 5, p[stred] < x BVNajdi (p, 5, 9, 5) stred = 7, p[stred] > x BVNajdi (p, 0, 9, 5) stred = 4, p[stred] < x


26

Hanojské věže 

Přemístit všechny disky z věže 1 na věž 3 

 

Édouard Lucas, 1883

Lze využít věž 2

Větší disk nesmí být nikdy umístěn na menší disk V každém tahu lze přemísťovat jen jeden nejvrchnější disk Počet tahů k vyřešení 2n - 1, kde n > 1 je počet disků

1 2 3 4 5 6 

https://www.mathsisfun.com/games/towerofhanoi.html Jan Lánský


27

Hanojské věže

1) Přemístíme n-1 disků z původní věže na pomocnou věž s využitím cílové věže jako odkladiště 2) Přesun největší disk

3) Přesuneme n-1 disků z pomocné věže na cílovou věž s využitím původní věže jako odkladiště Rozšíření funkce o pomocné proměnné: z – původní věž, kam – cílová věž, prez – pomocná věž jako odkladiště Jan Lánský


28

Hanojské věže pro n = 4 Největší disk 4 Nejmenší disk 1

Vyzkoušejme tento postup v online hře

Jan Lánský


29

Druh fraktálu

Kochova vločka 



 

Helge von Koch, 1904

Začínáme s trojúhelníkem V každém zanoření z každé hrany odstraníme prostřední třetinu a nahradíme ji dvěma hranami rovnostranného trojúhelníku směřujícími z vločky směrem ven Končíme po zvoleném počtu zanoření http://mathworld.wolfram.com/KochSnowflake.html

Zanoření 0 až 3. Vločku tvoří křivka, nikoliv plocha Jan Lánský


30

Přímá a nepřímá rekurze 

Přímá – rekurzivní volání v těle funkce 



Všechny probrané příklady

Nepřímá – rekurzivní volání ve vnořené funkci 

 

Př.: Fce1 () { Fce2(); } Fce2 () { Fce1(); } Příklad Rejstřík – nekonečná rekurze Smysluplný příklad bude v LS

Jan Lánský


31

Lineární a stromová rekurze 

Lineární - obvykle jedna větev rekurzivního volání nebo více větví, které se volají s parametrem odpovídajícímu n vydělenému počtem větví.  



Př.: faktoriál – jedna větev [n-1], Př.: binární vyhledávání – dvě větve [n/2], ale navíc se vykoná jen jedna

Stromová – více větví rekurzivních volání, které se volají s parametrem odpovídajícímu původnímu parametru (zmenšenému o konstantou)  

Př.: Fibonacciho čísla – dvě větve [n-1] a [n-2] Př.: Hanojské věže – dvě větve [n-1]

Jan Lánský


32

Časová složitost 







Rekurze je vždy pomalejší než nerekurzivní řešení (desítky procent) Někdy nerekurzivní řešení může mít i lepší asymptotickou složitost (Fibonacci) Lineární rekurze – obvykle převod na cyklus – O(N), případně O(log(N)) Stromová rekurze – hrozí O(2N), pokud se volá alespoň dvakrát o délce N

Jan Lánský


33

Zpětná vazba 

Objevili jste ve slajdech chyby? 



Nechápete nějaký slajd? 





Je příliš obtížný, nesrozumitelný?

Máte nějaký nápad na vylepšení? Anonymní formulář 



Včetně pravopisných

Odeslání za pár vteřin

http://goo.gl/forms/WxkZqBsZLs

Jan Lánský


34

Úvod do programování 10. hodina

Recommend Documents