Dekompozice problému, rekurze

Dekompozice problému, rekurze BI-PA1 – Programován´ı a Algoritmizace 1

Ladislav Vagner, Josef Vogel Katedra teoretick´ e informatiky a Katedra softwarov´ eho inˇzen´ yrstv´ı Fakulta informaˇ cn´ıch technologi´ı ˇ e vysok´ Cesk´ e uˇ cen´ı technick´ e v Praze [email protected], [email protected]

5. prosince 2016 a 8. prosince 2016

Pˇrehled Dekompozice problému. Rekurze. Rekurze a efektivita. Rekurze – pˇr´ıklady. Algoritmus merge sort.

ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

2/43

Dekompozice problému Návrh programu – dekompozice problému: pokus´ıme se rozloˇzit komplexn´ı problém (výsledný program) na jednoduˇsˇs´ı problémy (podproblémy), uˇzit´ım pseudok´ odu (abstraktn´ı pˇr´ıkazy) vyˇreˇs´ıme podproblémy, uˇzit´ım abstraktn´ıch pˇr´ıkaz˚ u vytvoˇr´ıme obrys celého ˇreˇsen´ı, pro implementaci abstraktn´ıch pˇr´ıkaz˚ u pouˇzijeme funkce.

Rozklad problému bude ukázán na variantˇe hry NIM: je dán celkový poˇcet zápalek (kamen˚ u, . . . ), napˇr. 15..35, hráˇc se stˇr´ıdá se strojem v odeb´ırán´ı, je moˇzno odebrat 1, 2 nebo 3 zápalky, prohraje ten, kdo odebere posledn´ı zápalku.


Rekurze, BI-PA1

3/43

Dekompozice problému Návrh programu – dekompozice problému: pokus´ıme se rozloˇzit komplexn´ı problém (výsledný program) na jednoduˇsˇs´ı problémy (podproblémy), uˇzit´ım pseudok´ odu (abstraktn´ı pˇr´ıkazy) vyˇreˇs´ıme podproblémy, uˇzit´ım abstraktn´ıch pˇr´ıkaz˚ u vytvoˇr´ıme obrys celého ˇreˇsen´ı, pro implementaci abstraktn´ıch pˇr´ıkaz˚ u pouˇzijeme funkce.

Rozklad problému bude ukázán na variantˇe hry NIM: je dán celkový poˇcet zápalek (kamen˚ u, . . . ), napˇr. 15..35, hráˇc se stˇr´ıdá se strojem v odeb´ırán´ı, je moˇzno odebrat 1, 2 nebo 3 zápalky, prohraje ten, kdo odebere posledn´ı zápalku.

Podproblémy: Inicializace – zadán´ı poˇctu zápalek, odebrán´ı zápalek hráˇcem, odebrán´ı zápalek strojem.


Rekurze, BI-PA1

3/43

Hra NIM – návrh int poˇ cetZ´ apalek; bool strojNaTahu = false; /* zat´ ım abstraktnˇ e */ zad´ an´ ı_poˇ ctu_z´ apalek do { if ( strojNaTahu ) hraje_poˇ c´ ıtaˇ c else hraje_ˇ clovˇ ek strojNaTahu = ! strojNaTahu; } while ( poˇ cetZ´ apalek > 0 ); if ( strojNaTahu ) stroj_vyhr´ al; else clovˇ ˇ ek_vyhr´ al ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

4/43

Hra NIM – implementace (kostra programu) int totalMatches; bool computerTurn = false; /* bool budeme definovat */ /* ... */ int main ( void ) { gameSetup (); do { if ( computerTurn ) computerPlayer (); else humanPlayer (); computerTurn = ! computerTurn; } while ( totalMatches > 0 ); if ( computerTurn ) printf("Vyhral jsem!\n"); else printf("Tys vyhral, gratuluji\n" ); return 0; } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

5/43

Hra NIM – implementace (zadán´ı poˇctu zápalek) void gameSetup ( void ) { printf ( "Napis pocet zapalek:\n" ); do { scanf ( "%d", &totalMatches ); /* ˇ spatnˇ e zadan´ y poˇ cet z´ apalek neˇ reˇ s´ ıme */ } while ( totalMatches < 15 || totalMatches > 35 ); }


Rekurze, BI-PA1

6/43

Hra NIM – implementace (hraje ˇclovˇek) void humanPlayer ( void ) { int taken; bool error; printf ( "%d zapalek. Kolik odeberes?\n", totalMatches ); do { scanf ( "%d", &taken ); error = false; if ( taken < 1 ) { error = true; printf ( "nejmene jedna musi byt odebrana!\n" ); } if ( taken > 3 || taken > totalMatches ) { error = true; printf ( "prilis mnoho odebrano!\n" ); } } while ( error ); totalMatches -= taken; } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

7/43

Hra NIM – implementace (hraje stroj) Poˇcet zápalek nevýhodný pro protihráˇce je 1, 5, 9, . . . , obecnˇe 4n + 1 zápalek: Kdyˇz je poˇcet zápalek 4n + 1 a hráˇc odebere a = 1, 2, 3 zápalky, tak inteligentn´ı protihráˇc odebere b = 3, 2, 1 zápalek, po dvou kolech je poˇcet zápalek zmenˇsen o 4 na 4(n − 1) + 1, tud´ıˇz poˇcet zápalek je zmenˇsen na 1 po 2n kolech a protihráˇc prohrává.

Kdyˇz zbývá p zápalek, stroj odeb´ırá x zápalek aby platilo: p − x = 4n + 1 x = (p − 1)

mod 4

Kdyˇz z formule vyjde x = 0, tak je to stav pro stroj nevýhodný. Pak stroj prohraje, pokud ˇclovˇek zná správnou strategii, Tak kdyˇz x = 0, stroj odebere x = 1 zápalku doufaje, ˇze lidský protihráˇc udˇelá chybu. ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

8/43

Hra NIM – implementace (hraje stroj) void computerPlayer ( void ) { int taken; taken = ( totalMatches - 1 ) % 4; if ( taken == 0 ) taken = 1; printf ( "%d zapalek. Stroj odebira %d.\n", totalMatches, taken ); totalMatches -= taken; }


Rekurze, BI-PA1

9/43

Hra NIM – implementace (typ bool) V jazyce C neexistuje datový typ bool. Tento typ m˚ uˇzeme definovat takto: #define bool char #define true 1 #define false 0

po této definici vˇsechny výskyty bool, true, a false jsou nahrazeny char, 1, a 0. Proto: bool computerTurn = false; /* tato deklarace je zpracov´ ana preprocesorem kompil´ atoru na: */ char computerTurn = 0; ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

10/43

Hra NIM – implementaˇcn´ı poznámka Implementace pouˇz´ıvá globáln´ı promˇennou totalMatches a computerTurn. Pouˇzit´ı globáln´ıch promˇenných nen´ı dobrá technika: je pˇr´ıˇcinou problém˚ u ve v´ıcevláknových programech, je pˇr´ıˇcinou problém˚ u s rekurzivn´ımi/reentrantn´ımi funkcemi, u ´drˇzba a integrace software je sloˇzitˇejˇs´ı.

Promˇenná computerTurn se pouˇz´ıvá jedinˇe ve funkci main a dát ji sem jako lokáln´ı je triviáln´ı u ´prava. Promˇenná totalMatches je pouˇzita pro pˇredán´ı informace mezi funkcemi. M´ısto globáln´ı promˇenné lze uˇz´ıt vstupn´ı parametr a návratovou hodnotu (nebo alternativnˇe pouˇz´ıt jako parametr referenci – in/out parametr). Funkce gameSetup vrát´ı poˇcet zápalek jako návratovou hodnotu, funkce computerPlayer a humanPlayer pouˇzij´ı poˇcet zápalek jako in/out parametr. ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

11/43

Rekurze Rekurze: viz ”Rekurze”.


Rekurze, BI-PA1

12/43

Rekurze Rekurze: viz ”Rekurze”. tato ”vtipná”definice bývá dávána do knih o programován´ı, ukazuje vˇsak sp´ıˇse na nepochopen´ı rekurze ze strany autora knihy.

Rekurze: pokud neznáte význam tohoto pojmu, pokraˇcujte pojmem ”Rekurze”.


Rekurze, BI-PA1

12/43

Rekurze Rekurze: viz ”Rekurze”. tato ”vtipná”definice bývá dávána do knih o programován´ı, ukazuje vˇsak sp´ıˇse na nepochopen´ı rekurze ze strany autora knihy.

Rekurze: pokud neznáte význam tohoto pojmu, pokraˇcujte pojmem ”Rekurze”. Nepˇr´ım´ a rekurze: pokud neznáte význam tohoto pojmu, pokraˇcujte pojmem ”Rekurzivn´ı volán´ı”. Rekurzivn´ı vol´ an´ı: pokud neznáte význam tohoto pojmu, pokraˇcujte pojmem ”Nepˇr´ımá rekurze”.


Rekurze, BI-PA1

12/43

Rekurze Rekurze je takový zp˚ usob programován´ı, kde funkce k vyˇreˇsen´ı problému volá sebe sama. Pro pouˇzit´ı rekurze mus´ı být splnˇeny dvˇe obecné podm´ınky: rekurzivn´ı volán´ı ˇreˇs´ı menˇs´ı (jednoduˇsˇs´ı) instanci p˚ uvodn´ıho problému, existuje nˇejaká triviáln´ı (jednoduchá) instance problému, kde rekurze konˇc´ı.

Pˇr´ıklad rekurzivn´ıho algoritmu – výpoˇcet faktoriálu: 0! = 1 n! = 1 pro záporné n, n! = n ∗ (n − 1)! pro kladné n.


Rekurze, BI-PA1

13/43

Rekurze – pˇr´ıklady Faktoriál iterativnˇe: int factorialIter ( int n ) { int f = 1; while ( n > 1) { f *= n; n--; } return f; } Faktoriál rekurzivnˇe: int factorialRec ( int n ) { if ( n <= 1 ) return 1; return n * factorialRec ( n - 1 ); }


Rekurze, BI-PA1

14/43

Rekurze – pˇr´ıklady Iterativn´ı algoritmus nalezen´ı nejvˇetˇs´ıho spoleˇcného dˇelitele: int gcd (int x, int y) { int remainder; while( y != 0 ) { remainder = x % y; x = y; y = remainder; } return x; } Kolik iterac´ı se provede?


Rekurze, BI-PA1

15/43

Rekurze – pˇr´ıklady Iterativn´ı algoritmus nalezen´ı nejvˇetˇs´ıho spoleˇcného dˇelitele: int gcd (int x, int y) { int remainder; while( y != 0 ) { remainder = x % y; x = y; y = remainder; } return x; } Kolik iterac´ı se provede? Necht’ x ≥ y > 0. Pak x mod y < x2 . D˚ ukaz: y ≤ x2 . Pak nerovnost plat´ı z definice. y > x2 . Pak x mod y = x − y < x2 . Proto je hodnota max(x, y ) p˚ ulena kaˇzdé dvˇe iterace, coˇz vede na 2 log2 (max(x, y )) iterac´ı. ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

15/43

Rekurze – pˇr´ıklady Rekurzivn´ı algoritmus nalezen´ı nejvˇetˇs´ıho spoleˇcného dˇelitele: int gcd ( int x, int y ) { if ( x == y ) return x; if ( x > y ) return gcd ( x % y, y ); else return gcd ( x, y % x ); }


Rekurze, BI-PA1

16/43

Rekurze a dekompozice problému Problém: pˇreˇc´ıst sekvenci celých ˇc´ısel zakonˇcenou 0, vypsat sekvenci v obráceném poˇrad´ı.

Dekompozice: obrácen´ı sekvence m˚ uˇze být dekomponováno na zpracován´ı prvn´ıho prvku a obrácen´ı zbytku sekvence: obrat’( x ) = obrat’( ) x. my pouˇzijeme abstraktn´ı pˇr´ıkaz ”obrat’”, ten obrát´ı zbytek sekvence ze vstupu, pˇr´ıkaz bude obsahovat tˇri kroky: 1 2 3


ˇcten´ı ˇc´ısla x sekvence ze vstupu, obr´ acen´ı zbytku sekvence – ”reverse”, výpis x.

Rekurze, BI-PA1

17/43

Rekurze a dekompozice problému Postup pˇri výpisu sekvence v obráceném poˇrad´ı: stack:

read x if ( ) reverse

x=1

Input:

1

7

4

9

0

Output:


Rekurze, BI-PA1

18/43



read x

x=1

if ( ) reverse

x=7

Input:

7

4

9

0

Output:


Rekurze, BI-PA1

18/43




x=1 read x

x=7

if ( ) reverse

x=4

Input:

4

9

0

Output:


Rekurze, BI-PA1

18/43




x=1 read x if ( ) reverse

x=7 read x

x=4

if ( ) reverse

x=9

Input:

9

0

Output:


Rekurze, BI-PA1

18/43





x=7 read x

x=4

if ( ) reverse

read x

x=9

if ( ) reverse

x=0

write x

Input: Output:


Rekurze, BI-PA1

0 0

18/43





x=7 read x

x=4

if ( ) reverse

read x

x=9

if ( ) reverse

x=0

write x write x

Input: Output:


Rekurze, BI-PA1

0

9

18/43





x=7 read x

x=4

if ( ) reverse

read x

x=9

if ( ) reverse

x=0

write x write x write x Input: Output:


Rekurze, BI-PA1

0

9

4

18/43





x=7 read x

x=4

if ( ) reverse

read x

x=9

if ( ) reverse

x=0

write x write x write x write x

Input: Output:


Rekurze, BI-PA1

0

9

4

7

18/43





x=7 read x

x=4

if ( ) reverse

read x

x=9

if ( ) reverse

x=0

write x write x write x write x write x


Input: Output:

Rekurze, BI-PA1

0

9

4

7

1

18/43

Rekurze a dekompozice problému #include <stdio.h> void reverse( void ) { int x; scanf ( "%d", &x ); if ( x != 0 ) reverse (); printf ( "%d ", x ); } int main( void ) { printf ( "Napis cisla zakoncena 0:\n" ); reverse (); printf ( "\n" ); return 0; } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

19/43

Rekurze a dekompozice problému – Hanojské vˇeˇze

Zlaté disky jsou na kol´ıku #1, Disky mohou být pˇresouvány jen po jednom. Disk m˚ uˇze být pˇresunut na kterýkoli prázdný kol´ık nebo na kol´ık s vˇetˇs´ım diskem (disky). Disky nemohou být um´ıstˇeny mimo kol´ıky. ´ Ulohou je pˇrem´ıstit vˇeˇz z kol´ıku #1 na kol´ık #2. ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

20/43

Rekurze a dekompozice problému – Hanojské vˇeˇze Dekompozice – definujeme abstraktn´ı pˇr´ıkaz pˇ resuˇ n vˇ eˇ z ( n, x, y, z ). Význam je tento: Pˇresun vˇeˇze výˇsky n z kol´ıku x na kol´ık y s pomoc´ı pˇrechodného uloˇzen´ı na kol´ıku z.

Pˇr´ıkaz rozloˇz´ıme na tˇri kroky: pˇ resuˇ n vˇ eˇ z ( n-1, x, z, y ), pˇresun disku z kol´ıku x na kol´ık y pˇ resuˇ n vˇ eˇ z ( n-1, z, y, x ).


Rekurze, BI-PA1

21/43

Rekurze a dekompozice problému – Hanojské vˇeˇze #include <stdio.h> void moveTower ( int h, int from, int to, int tmp ) { if ( h > 0 ) { moveTower ( h-1, from, tmp, to ); printf ( "presun disku z %d na %d\n", from, to ); moveTower ( h-1, tmp, to, from ); } } int main( void ) { int disks; printf ( "Napis pocet disku:\n" ); scanf ( "%d", &disks ); if ( disks > 0 ) moveTower ( disks, 1, 2, 3 ); else /* ... oˇ setˇ ren´ ı chyby ... */ return 0; } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

22/43

Rekurze a efektivita Rekurzivn´ı funkce jsou pˇr´ımou implementac´ı rekurzivn´ıch algoritm˚ u: rekurzivn´ı algoritmy pracuj´ı zp˚ usobem ”shora dol˚ u”, triviáln´ı instance problému je implementována pˇr´ımo, rekurzivn´ı volán´ı se pouˇzije pro ˇreˇsen´ı obecné instance problému.

Rekurzivn´ı funkce jsou obvykle krátké, pˇr´ımoˇcaré a snadno srozumitelné. Rekurzivn´ı funkce maj´ı sklon k jisté neefektivnosti. Napˇr´ıklad stejné jednoduˇsˇs´ı problémy mohou být ˇreˇseny mnohokrát. Mnohé rekurzivn´ı algoritmy mohou být nahrazeny iterativn´ımi (napˇr. faktoriál, gcd, . . . ). Iterativn´ı algoritmy obvykle pracuj´ı zp˚ usobem ”zdola nahoru”, od instance jednoduchého problému ke komplexnˇejˇs´ı instanci problému.


Rekurze, BI-PA1

23/43

Fibonacciho posloupnost Pingala (Chhandah-shastra, the Art of Prosody, 450 or 200 pˇr.n.l.) Leonardo Pisano (Leonardo z Pisy), známý jako Fibonacci (cca 1175–1250) – král´ıci. Henry E. Dudeney (1857 - 1930) – krávy. Kdyˇz má kráva prvn´ı tele ve vˇeku 2 let a pak kaˇzdý rok, kolik krav to bude ve 12 letech (ˇzádn´ı býci, ˇzádná kráva nezemˇre)? poˇcet krav = poˇcet krav vloni + novˇe narozené (tj. poˇcet krav pˇredloni) fn = fn−1 + fn−2 , f1 = 1, f2 = 1.

n 1 2 3 4 ˇ L. Vagner, J. Vogel, CVUT FIT

fn 1 1 2 3

n 5 6 7 8

fn 5 8 13 21

n 9 10 11 12

fn 34 55 89 144

Rekurze, BI-PA1

24/43

Fibonacciho posloupnost int fibonacci ( int n ) { if ( n <= 2 ) return 1; return fibonacci ( n - 1 ) + fibonacci ( n - 2 ); }

Rekurzivn´ı ˇreˇsen´ı je krátké a jednoduché. Kód pˇr´ımo koresponduje s rekurentn´ı definic´ı. Je také efektivn´ı?


Rekurze, BI-PA1

25/43

Fibonacciho posloupnost int fibonacci ( int n ) { int i, fN = 1, fN1 = 1, fN2 = 1; for ( i = 2; i <= n; i ++ ) { fN2 = fN1; fN1 = fN; fN = fN2 + fN1; } return fN; }

Iterativn´ı ˇreˇsen´ı je ponˇekud delˇs´ı. Kód poˇc´ıtá Fibonacciho ˇc´ısla ”zdola nahoru”(od f2 , f3 , . . . ). Je efektivn´ı?


Rekurze, BI-PA1

26/43

Fibonacciho posloupnost int fibonacci ( int n ) { int i, fN = 1, fN1 = 1, fN2 = 1; for ( i = 2; i <= n; i ++ ) { fN2 = fN1; fN1 = fN; fN = fN2 + fN1; } return fN; }

Iterativn´ı ˇreˇsen´ı je ponˇekud delˇs´ı. Kód poˇc´ıtá Fibonacciho ˇc´ısla ”zdola nahoru”(od f2 , f3 , . . . ). Je efektivn´ı? Kód provád´ı n iterac´ı, tj. 3 ∗ n sˇc´ıtán´ı/pˇriˇrazen´ı.


Rekurze, BI-PA1

26/43

Fibonacciho posloupnost Iterativn´ı ˇreˇsen´ı: 3 ∗ n operac´ı. Rekurzivn´ı ˇreˇsen´ı:


Rekurze, BI-PA1

27/43

Fibonacciho posloupnost Iterativn´ı ˇreˇsen´ı: 3 ∗ n operac´ı. Rekurzivn´ı ˇreˇsen´ı: f (10) f (9) f (8) f (7) ...

f (6) ...

f (7) f (6) ...

f (5) ...

f (8) f (7) f (6) ...

f (5) ...

f (6) f (5) ...

f (4) ...

Rekurzivn´ı ˇreˇsen´ı: exponenciáln´ı sloˇzitost


Rekurze, BI-PA1

27/43

Fibonacciho posloupnost Iterativn´ı ˇreˇsen´ı: 3 ∗ n operac´ı. Rekurzivn´ı ˇreˇsen´ı: pˇribliˇznˇe 2n operac´ı. Pˇr´ımý výpoˇcet (J. Kepler): Zlatý ˇrez ϕ: √ 1+ 5 ϕ= ≈ 1.6180339887498948482045868343656 2 Fibonacciho ˇc´ıslo: fn =


ϕn − (1 − ϕ)n √ 5

Rekurze, BI-PA1

28/43

Rekurze – násoben´ı /* Iterativn´ ı celoˇ c´ ıseln´ e n´ asoben´ ı, x >= 0 */ int mulIter ( int x, int y ) { int res = 0, i; for ( i = 0; i < x; i ++ ) res += y; return res; } /* Rekurzivn´ ı celoˇ c´ ıseln´ e n´ asoben´ ı, x >= 0 */ int mulRec ( int x, int y ) { if ( x == 0 ) return 0; return y + mulRec ( x - 1, y ); }


Rekurze, BI-PA1

29/43

Rekurze – faktorizace void factorizeIter ( int x ) { int d = 2; while ( d <= x ) { if ( x % d == 0 ) { printf ( "%d ", d ); x /= d; } else d ++; } }


Rekurze, BI-PA1

30/43

Rekurze – faktorizace void factorizeRec ( int x ) { int d = 2; while ( d <= x ) { if ( x % d == 0 ) { printf ( "%d ", d ); factorizeRec ( x / d ); return; } else d ++; } }


Rekurze, BI-PA1

31/43

Rekurze – faktorizace void factorizeRec ( int x ) { int d = 2; while ( d <= x ) { if ( x % d == 0 ) { printf ( "%d ", d ); factorizeRec ( x / d ); return; } else d ++; } } /* kaˇ zd´ e vol´ an´ ı zaˇ cı ń´ a od d = 2 */


Rekurze, BI-PA1

31/43

Rekurze – faktorizace void factorizeRec2 ( int x, int d ) { if ( d <= x ) { while ( d < x && x % d != 0 ) d++; printf ( "%d ",d ); factorizeRec2 ( x / d, d ); } }


Rekurze, BI-PA1

32/43

Merge sort Jednoduché ˇradic´ı algoritmy maj´ı sloˇzitost T (n) ∈ O(n2 ). Kvadratická ˇcasová sloˇzitost je zbyteˇcnˇe velká. Efektivn´ı ˇradic´ı algoritmy ˇrad´ı v ˇcase T (n) ∈ O(n log n). ˇ Razen´ ı sluˇcován´ım je takový algoritmus. Algoritmus Merge sort je zaloˇzen na operaci sluˇcován´ı. M˚ uˇze být popsán rekurzivnˇe: pole o velikosti jednoho prvku je seˇrazené, kdyˇz má pole v´ıce prvk˚ u, rozdˇel´ı se na dvˇe ˇcásti (poloviny). merge sort je uˇzit rekurzivnˇe pro seˇrazen´ı obou ˇcást´ı, obˇe ˇcásti se slouˇc´ı do vˇetˇs´ıho pole.


Rekurze, BI-PA1

33/43

Merge sort pole: rozdˇ elen´ ı: razen´ ˇ ı polovin: slouˇ cen´ ı:


15 15 11 10

32 32 15 11

74 74 32 15

11 11 74 24

80 10 80|10 80|10 27 32

40 40 24 34

27 27 27 40

Rekurze, BI-PA1

34 34 34 74

24 24 40 80

34/43

Sluˇcován´ı (merge) Problém: Necht’ a a b jsou seˇrazené sekvence. Máme vytvoˇrit seˇrazenou sekvenci c takovou, ˇze obsahuje vˇsechny prvky z a i z b. Pˇr´ıklad: a: 2 3 6 8 10 34 b: 3 7 12 13 55 c: 2 3 3 6 7 8 10 12 13 34 55

Kdyˇz a a b jsou pole, m˚ uˇzeme pˇripravit funkci, která je slouˇc´ı: void merge ( int *a, int la, int *b, int lb, int *c );

Jak slouˇcit sekvence? Zkop´ırovat a do c, pˇridat b do c a seˇradit pole c. Ne – to by bylo neefektivn´ı.


Rekurze, BI-PA1

35/43

Sluˇcován´ı – efektivnˇe pˇreˇc´ıst prvn´ı prvek obou sekvenc´ı a a b, pˇridat menˇs´ı (nebo stejnou) z prvk˚ u do c, pˇreˇc´ıst dalˇs´ı prvek sekvence, ze které bylo pˇridáno, pˇredchoz´ı kroky opakovat aˇz do vyˇcerpán´ı jedné ze sekvenc´ı, pˇridat zbytek nevyˇcerpané sekvence na konec c. void merge( int *a, int na, int * b, int nb, int *c ) { int ia = 0, ib = 0, ic = 0; while ( ia < na && ib < nb ) if ( a[ia] <= b[ib] ) c[ic++] = a[ia++]; else c[ic++] = b[ib++]; while (ia < na) c[ic++] = a[ia++]; while (ib < nb) c[ic++] = b[ib++]; } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

36/43

Merge sort void merge ( int *src, int *dst, int l, int r, int rEnd ) { int lEnd = r - 1, i = l; while ( l <= dst[i++] = while ( l <= while ( r <=

lEnd && r <= rEnd ) src[l] <= src[r] ? src[l++] : src[r++]; lEnd) dst[i++] = src[l++]; rEnd) dst[i++] = src[r++];

}

src dst l r rEnd


Rekurze, BI-PA1

37/43

Merge sort (rekurzivnˇe) void mergeSortRec( int *a, int *tmp, int l, int r ) { int i, mid; if ( l == r) return; /* 1 prvek -> seˇ razeno */ mid = ( l + r ) / 2; mergeSortRec ( a, tmp, l, mid ); mergeSortRec ( a, tmp, mid + 1, r ); merge ( a, tmp, l, mid+1, r ); for ( i = l; i <= r; i ++ ) a[i] = tmp[i]; } /* V´ ysledn´ a ˇ radic´ ı funkce */ void mergeSort ( int *a, int n ) { int *tmp = (int*)malloc ( n * sizeof( *tmp ) ); mergeSortRec( a, tmp, 0, n-1 ); free ( tmp ); } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

38/43

Merge sort (iterativnˇe) Rekurzivn´ı funkce merge sort volá sebe sama opakovanˇe, aˇz je délka seˇrazeného pole 1. Z tohoto pohledu jsou krátké rozdˇelené sekvence sluˇcovány do delˇs´ıch. Sekvence jsou slouˇceny do pomocného pole, které mus´ı být zkop´ırováno zpˇet do zdrojového pole. Iterativn´ı merge sort pracuje zdola nahoru: pole a je rozdˇeleno na sekvence délky 1, sekvence jsou slouˇceny do pole tmp (seˇrazené sekvence 2 prvk˚ u), v dalˇs´ı iteraci jsou sekvence délky 2 z pole tmp slouˇceny do sekvenc´ı v poli a (sekvence 4 seˇrazených prvk˚ u), a znova v dalˇs´ı iteraci jsou sekvence délky 4 z a slouˇceny do pole tmp (sekvence 8 seˇrazených prvk˚ u), to pokraˇcuje, aˇz je celé pole seˇrazeno, je-li poˇcet slouˇcen´ı lichý, je výsledek v poli tmp. V tomto pˇr´ıpadˇe je tˇreba jeˇstˇe dalˇs´ı krok – data mus´ı být zkop´ırována zpˇet do pole a. ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

39/43

Merge sort (iterativnˇe) a

49 62 21 70 89 99 21 76 53 40 87 70 32 70 24 93 90 65 90

tmp

49 62 21 70 89 99 21 76 40 53 70 87 32 70 24 93 65 90 90

a

21 49 62 70 21 76 89 99 40 53 70 87 24 32 70 93 65 90 90

tmp

21 21 49 62 70 76 89 99 24 32 40 53 70 70 87 93 65 90 90

a

21 21 24 32 40 49 53 62 70 70 70 76 87 89 93 99 65 90 90

tmp

21 21 24 32 40 49 53 62 65 70 70 70 76 87 89 90 90 93 99


Rekurze, BI-PA1

40/43

Merge sort (iterativnˇe) void mergeSort ( int *a, int n ) { int *tmp = (int*)malloc ( n * sizeof(*tmp) ), *src = a, *dst = tmp, *x; int len = 1, last = n-1, i; while ( len < n ) { int l = 0, r = len; while (l <= last ) { merge ( src, dst, l, min(r, n), min(r+len-1, last) ); l += 2 * len; r += 2 * len; } len *= 2; x = src; src = dst; dst = x; } if ( src != a ) for ( i = 0; i < n; i ++ ) a[i] = tmp[i]; free ( tmp ); } ˇ L. Vagner, J. Vogel, CVUT FIT

Rekurze, BI-PA1

41/43

Merge sort Analýza sloˇzitosti algoritmu Merge sort: n Vnitˇrn´ı cyklus probˇehne 2∗len krát. Ten volá funkci merge pro vytvoˇren´ı sekvence délky (nejv´ıce) len + len. Tud´ıˇz, ˇcasová n sloˇzitost je 2∗len ∗ 2 ∗ len = n, vnˇejˇs´ı cyklus iteruje, aˇz do hodnoty len == n. Hodnota len se zdvojnásob´ı v kaˇzdé iteraci, a tak je poˇcet iterac´ı k, kde 2k = n, k je tedy k = log2 (n), pˇr´ıpadný posledn´ı kop´ıruj´ıc´ı krok trvá dobu u ´mˇernou n, celkový ˇcas:

T (n) ∈ O(n log n + n) ∈ O(n log n)

Nevýhodou tohoto algoritmu je potˇreba pomocného pamˇet’ového prostoru. Jiné ˇradic´ı algoritmy (napˇr. Quick sort) toto omezen´ı nemaj´ı.


Rekurze, BI-PA1

42/43

Otázky a odpovˇedi

Otázky . . .


Rekurze, BI-PA1

43/43

Dekompozice problému, rekurze

Recommend Documents