Volání podprogramu opětovně v jeho těle

volání podprogramu opětovně v jeho těle

• volání podprogramu opětovně v jeho těle

• v době, kdy předchozí volání ještě nebylo ukončeno

• Druhy rekurze

• přímá rekurze

• nepřímá rekurze

podprogram volá sám sebe

• podprogram volá sám sebe

• void A(…)

• {

• A();

• }

aktivují se vzájemně dva podprogramy

• aktivují se vzájemně dva podprogramy

• void A(…)

• {

• B();

• }

• void B(…)

• {

• A();

• }

pravidla tvorby rekurzivní funkce

• pravidla tvorby rekurzivní funkce

• musí být definována podmínka pro ukončení rekurze
• v algoritmu se musí ověřit, zda nenastala koncová situace
• v každém kroku musí dojít ke zjednodušení problému

Napište rekurzivní funkci pro výpočet faktoriálu

• Napište rekurzivní funkci pro výpočet faktoriálu

fakt(2)

• fakt(2)

Napište rekurzivní funkci pro výpočet Fibbonaciho posloupnosti

• Napište rekurzivní funkci pro výpočet Fibbonaciho posloupnosti

• F(0) = 0

• F(1) = 1

• F(n) = F(n-1) + F(n-2)

rekurze, je-li příliš „hluboká“, způsobí růst velikosti zásobníku

• rekurze, je-li příliš „hluboká“, způsobí růst velikosti zásobníku

• v některých případech je možné ji nahradit pouhým cyklem
• jindy se musí simulovat zásobník

• long fakt(int n)

• {

• long faktorial = 1;

• for(i=2;i<=n;i=i+1)

• faktorial = faktorial*i;

• return faktorial;

• }

Je dána celá částka v Kč. Máme k dispozici mince v hodnotách 20 Kč, 10 Kč, 5 Kč, 2Kč, 1 Kč. Napište rekurzivní proceduru, která vytiskne na obrazovku složení částky z co nejmenšího počtu mincí (vytiskne seznam mincí).

• Je dána celá částka v Kč. Máme k dispozici mince v hodnotách 20 Kč, 10 Kč, 5 Kč, 2Kč, 1 Kč. Napište rekurzivní proceduru, která vytiskne na obrazovku složení částky z co nejmenšího počtu mincí (vytiskne seznam mincí).

• Domácí úloha: Odstraňte rekurzi (přepište proceduru pomocí cyklu).

máme 3 tyče (1, 2, 3)

• máme 3 tyče (1, 2, 3)

• na první tyči je věž z n disků naskládaných na sebe, spodní disk má největší průměr

• úkol:

• přemístit věž z tyče 1 na tyč 2 pomocí třetí tyče 3 přesouváním disků za podmínek:
• v jediném kroku lze přenést jeden disk z tyče na tyč
• disk lze odložit pouze na tyč
• nelze položit disk o větším průměru na disk s menším průměrem.

triviální úloha

• triviální úloha

• přenesení věže o výšce 1, tj. přenesení disku, z tyče na tyč
• je reprezentována procedurou

• void Prenes_disk(int odkud, int kam),

• která v našem programu vypíše informaci o přesunu disku, např.: 1 -> 2

• úvaha

• chci-li přesunout věž např. o výšce 3 disky z tyče 1 na tyč 2 pomocí tyče 3, musím nejprve přesunout věž o výšce 2 (počítáno od shora) na tyč 3 pomocí 2, pak přesunout spodní největší disk z tyče 1 na tyč 2 a nakonec přesunout věž o výšce 2 z tyče 3 na tyč 2 pomocí tyče 1

void prenes_vez(int vyska, int odkud, int kam, int pomoci)

• void prenes_vez(int vyska, int odkud, int kam, int pomoci)

• {

• if (vyska == 1) prenes_disk(odkud,kam);

• else

• {

• prenes_vez(vyska-1, odkud, pomoci, kam);

• prenes_disk(odkud,kam);

• prenes_vez(vyska-1,pomoci,kam,odkud);

• }

• }

přesunutí věže o n discích se skládá z přesunutí věže o (n-1) discích, přesunutí disku a přesunutí věže zpět o (n-1) discích

• přesunutí věže o n discích se skládá z přesunutí věže o (n-1) discích, přesunutí disku a přesunutí věže zpět o (n-1) discích

• počet kroků algoritmu (počet přesunutí disků) je dán rekurentním vztahem:

• F(n) = F(n-1) + 1 + F(n-1) = 2F(n-1)+1,

• přičemž F(1) = 1

řešením rovnice je vztah

• řešením rovnice je vztah

• F(n) = 2n - 1

• tj. počet přesunů disku u věže výšky n je roven 2n - 1

• složitost algoritmu je tedy O(2n)

• exponenciální

Prohledávání s návratem (Backtracking)

• Prohledávání s návratem (Backtracking)

• používá se pro hledání všech řešení daného problému

• princip:

• řešení hledám po krocích, pokud je řešení nalezeno nebo nelze úlohu dále řešit, vrátím se o krok zpět

• úlohy:

• hledání všech cest v bludišti
• problém rozmístění 8 dam na šachovnici

úkol:

• úkol:

• umístit 8 dam na šachovnici 8x8 polí, aby se vzájemně neohrožovaly

• princip:

• umístím dámu na první řádek na první sloupec, další dámu na druhý řádek na třetí sloupec atd., pokud nemohu další dámu umístit, provedu návrat na předchozí řádek a dámu posunu

demonstrace na 4 dámách na šachovnici 4x4

• demonstrace na 4 dámách na šachovnici 4x4

Rozděl a panuj (Divide and Conquer)

• Rozděl a panuj (Divide and Conquer)

• používá se pro zjednodušení řešení složitého problému

• princip:

• rozdělím prostor řešení na dva menší (pokud možno stejně velké) podprostory
• vyřeším problém na každém podprostoru samostatně (stejnou technikou)
• spojím obě řešení

• úlohy:

• Hanojské věže
• řazení: QuickSort

algoritmus s návratem (rekurzivní)

• algoritmus s návratem (rekurzivní)

• je-li to možné, v každé místnosti zkusím „jít na všechny“ světové strany do další místnosti
• pokud jsem našel východ, vypíši cestu a vrátím se o krok zpět
• vracím se o krok zpět, nemohu-li postoupit do další mísnosti (jsem v slepé uličče)

Jak bude principiálně algoritmus vypadat?

• Jak bude principiálně algoritmus vypadat?

• Napišme jej v pseudokódu.

jdi_do_mistnosti(kam)

• jdi_do_mistnosti(kam)

• {

• if (jsem_venku) { tiskni_cestu(); return; }

• else

• {

• if (mohu_na_sever) jdi_do_mistnosti(sever);

• if (mohu_na_jih) jdi_do_mistnosti(jih);

• if (mohu_na_vychod) jdi_do_mistnosti(vychod);

• if (mohu_na_zapad) jdi_do_mistnosti(zapad);

• }

• }

Donald Knuth

• Donald Knuth

• Data + Algorithms = Programs

Kostka domina je tvořena dvěma poli. Každé z nich může být prázdné nebo může obsahovat jistý počet teček od 1 do 6. Kostky se skládají do řady tak, že vedle sebe stojící kostky musí sousedit stejnými poli; za kostkou s prázdným polem nelze dát další kostku.

• Kostka domina je tvořena dvěma poli. Každé z nich může být prázdné nebo může obsahovat jistý počet teček od 1 do 6. Kostky se skládají do řady tak, že vedle sebe stojící kostky musí sousedit stejnými poli; za kostkou s prázdným polem nelze dát další kostku.

• Vstupem vašeho programu bude soubor se seznamem kostek domina, které máte k dispozici (na každém řádku bude dvojice čísel oddělená mezerou, představující počet teček). V seznamu se může opakovat i více stejných kostek. Zjistěte jakou nejdelší řadu lze z těchto kostek sestavit. Vytiskněte tuto řadu a její délku měřenou počtem kostek. Stačí jedno řešení.