Algoritmizace a programování

Algoritmizace a programování

Procedurální programování Rekurze Jazyk C

České vysoké učení technické Fakulta elektrotechnická Ver.1.10

J. Zděnek 2015

Procedurální programování - zásady •

Postupný návrh programu rozkladem řešeného problému na podproblémy • zadaný problém rozložíme na podproblémy • pro řešení podproblémů zavedeme abstraktní příkazy • pomocí abstraktních příkazů sestavíme hrubé řešení • abstraktní příkazy realizujeme pomocí metod (funkcí, procedur) • Navržené metody propojíme pomocí předávání parametrů

•

Rozklad problému na podproblémy ukážeme na jednoduchých příkladech

A8B14ADP Jazyk C - procedurální programovaní

2

Rozklad problému na podproblémy funkceA( ) Vstup dat od uživatele main() Začátek programu

Řešený problém

funkceA ( ) funkceB ( ) funkceC ( ) funkceD ( ) Konec programu

Výstupní Parametr(y)

Vstupní parametry funkceD( ) Výstup výsledku pro uživatele


Vstupní parametry funkceB( ) Dílčí výpočet 1

funkceC( ) Dílčí výpočet 2

3

Příklad 1 – Výpočet s volbou metody (1) • • • •

Navrhněte řešení programu, který vypočítá buď obsah obdélníku nebo kruhu. Druh výpočtu lze volit z klávesnice z nabídkového menu (volba čísly) Výpočet lze spouštět z klávesnice opakovaně pro různé parametry Výsledky výpočtu se zobrazují na obrazovce

•

Dílčí podproblémy (pro identifikované části zvolíme název budoucí funkce): • Nabídkové menu s volbou obsluhy (1) ctiPrikaz • Vykonání příkazu obsluhy (2) cmdObdelnik (3) cmdKruh • Vlastní matematický výpočet (4) obsahObdelniku (5) obsahKruhu • Pomocné metody • Zjištění parametrů pro výpočet (6) prectiKladnyDouble • Tisk nápovědy, pokynů a výsledků (7) tiskNaObrazovku • Řídicí program celého řešení,zapíšeme v: (8) main Identifikovali jsme 8 dílčích bloků, ty zapíšeme pomocí funkcí

•

A0B36PRI A8B14ADP „PROGRAMOVÁNÍ“ Jazyk C - procedurální 06 programovaní

44

Příklad 1 – Výpočet s volbou metody (2) • Hrubé řešení (zapsané pseudojazykem – ten si volíme) Opakuj { switch (ctiPrikaz) pocitat-obdelnik: cmdObdelnik // napoveda tiskNaObrazovku prectiKladnyDouble // cti parametry vypoctu obsahObdelniku // vlastni vypocet tiskNaObrazovku // zobraz vysledek break pocitat-kruh: cmdKruh // napoveda tiskNaObrazovku prectiKladnyDouble // cti parametry vypoctu obsahKruhu // vlastni vypocet tiskNaObrazovku // zobraz vysledek break konec-programu: return } A8B14ADP Jazyk C - procedurální programovaní

5

Příklad 1 – Vstup a vyhodnocení příkazu (3) int ctiPrikaz(void){ int cmd; while(true){ tiskNaObrazovku ("\nObsah-obdelniku=1,Obsah-kruhu=2,Konec=3","\n“,-1); tiskNaObrazovku("Prikaz = ","“,-1); switch(scanf("%d", &cmd)){ case CMD_KRUH:…; case CMD_OBDELNIK:..; case CMD_KONEC: return (cmd); default: tiskNaObrazovku("Neznamy prikaz","\n“,-1); break; } } }


6

Příklad 1 – Příkaz pro výpočet obsahu obdélníku (4) void cmdObdelnik(void){ // Akce "Obdelnik" double a,b,p; tiskNaObrazovku("Vypocet obsahu OBDELNIKU","\n“,-1); // Vstup dat a = prectiKladnyDouble("a ="); b = prectiKladnyDouble("b ="); // Vypocet p = obsahObdelniku(a, b); // Vystup dat tiskNaObrazovku("Obsah Obdelniku = ","",p); }


7

Příklad 1 – Příkaz pro výpočet obsahu kruhu (5) void cmdKruh(void){ // Akce "Kruh“ double r,p; tiskNaObrazovku("Vypocet obsahu KRUHU","\n“,-1); // Vstup dat r = prectiKladnyDouble("r ="); // Vypocet p = obsahKruhu(r); // Vystup dat tiskNaObrazovku("Obsah KRUHU = ","",p); }


8

Příklad 1 – Vlastní výpočet obsahů obrazců (6) double obsahObdelniku(double a, double b){ // Vypocet double obsahObdelniku; obsahObdelniku = a * b; return(obsahObdelniku); } double obsahKruhu (double r) { // Vypocet double obsahKruhu; obsahKruhu = 2 * 3.14 * r; return (obsahKruhu); }


9

Příklad 1 – Zjištění parametrů výpočtu (7) double prectiKladnyDouble(char napis[]){ // Vstup dat (kladne racionalni cislo) double dIn; while(true){ tiskNaObrazovku("Zadej kladne cislo","\n“,-1); tiskNaObrazovku(napis,"“,-1); scanf("%d", &dIn); if (dIn >= 0) return(d); tiskNaObrazovku("Chyba","\n“,-1); } }


10

Příklad 1 – Tisk nápovědy a výsledků (8) void tiskNaObrazovku(char s[],char lf[],double d){ if(d < 0){ printf("%s %s", s, lf); }else{ printf("%s%3.2f %s", s, d, lf); } }


11

Příklad 1 – Řídicí program celého řešení (9) #include <stdio.h> #include <stdlib.h> enum {CMD_KRUH,CMD_OBDELNIK,CMD_KONEC}; int main(int argc, char** argv) { while(true){ switch(ctiPrikaz()){ case CMD_KRUH: cmdKruh();break; case CMD_OBDELNIK: cmdObdelnik();break; case CMD_KONEC: tiskNaObrazovku("KONEC","\n“,-1);return; } } } A8B14ADP Jazyk C - procedurální programovaní

12 12

Příklad 2 – Hra NIM (1) [1] •

Navrhněte řešení programu pro hru NIM „počítač-člověk“

•

Pravidla hry NIM: • hráč zadá počet zápalek (např. od 15 do 35) • pak se střídá se strojem v odebírání; odebrat lze 1, 2 nebo 3 zápalky, • prohraje ten, kdo odebere poslední zápalku.

•

Dílčí podproblémy: • zadání počtu zápalek • odebrání zápalek hráčem • odebrání zápalek strojem


13

Příklad 2 – Hra NIM (2) •

Pravidla pro odebírání zápalek strojem, která vedou k vítězství (je-li to možné): • počet zápalek nevýhodných pro protihráče je 1, 5, 9, atd., obecně 4n+1, kde n >0, • stroj musí z počtu p zápalek odebrat x zápalek tak, aby platilo p – x = 4n + 1 • z tohoto vztahu po úpravě a s ohledem na omezení pro x dostaneme x = (p – 1) mod 4 • vyjde-li x=0, znamená to, že okamžitý počet zápalek je pro stroj nevýhodný a bude-li protihráč postupovat správně, stroj prohraje.


14

Příklad 2 – Hra NIM (3) •

Hrubé řešení: typedef unsigned Tboolean; int pocet; Tboolean stroj = FALSE; // zadání počtu zápalek do{ if (stroj) “odebrání zápalek strojem“ else “odebrání zápalek hráčem“ stroj = !stroj; }while (pocet > 0); if (stroj) “vyhrál stroj“ else “vyhrál hráč“

•

Podproblémy „zadání počtu zápalek“, „odebrání zápalek strojem“ a „odebrání zápalek hráčem“ budeme realizovat funkcemi, proměnné pocet a stroj pro ně budou statickými proměnnými


15

Příklad 2 – Hra NIM (3) #define TRUE 1 #define FALSE 0 int main(int argc, char** argv){ int pocet, stroj=FALSE; pocet = zadaniPoctu(); do { if (stroj) pocet = bereStroj(pocet); else pocet = bereHrac(pocet); stroj = !stroj; }while(pocet > 0); printf("Vsechny zapalky odebrany \n"); if(!stroj) printf("Vyhral jsem \n\n"); else printf("\nVyhral jste, gratuluji \n\n"); return (EXIT_SUCCESS); } A8B14ADP Jazyk C - procedurální programovaní

16

Příklad 2 – Hra NIM (4) int zadaniPoctu(void){ int pocet = 0; do { printf("Zadejte pocet zapalek (od 15 do 35) = "); scanf("%d", &pocet); } while (pocet < 15 || pocet > 30); return (pocet); }


17

Příklad 2 – Hra NIM (5) int bereHrac(int pocet) { int x, chyba; do { chyba = FALSE; printf("Pocet zapalek = %d \n\n", pocet); printf("Kolik odeberete (1..3) ? "); scanf("%d", &x); if (x < 1) { printf("Prilis malo \n"); chyba = TRUE; } else if (x > 3 || x > pocet) { printf("Prilis mnoho \n"); chyba = TRUE; } } while (chyba); pocet -= x; return (pocet); } A8B14ADP Jazyk C - procedurální programovaní

18

Příklad 2 – Hra NIM int bereStroj(int pocet) { int x; printf("Pocet zapalek = %d \n\n", pocet); x = (pocet-1) % 4; if(x == 0) x = 1; printf("Odebiram %d \n", x); pocet -= x; return(pocet); }


19

Rekurze • Definice ze slovníku (pozor vtip) Rekurze viz „Rekurze“ • ….nekonečná rekurze, lépe: pokud neznáte význam tohoto pojmu, pokračujte pojmem „Rekurze“ • Rekurze - algoritmus, který volá v průběhu svého běhu sama sebe Příklad: výpočet faktoriálu: n! 0! = 1, 1! = 1, pro záporné číslo x budiž x! = 1 pro n>1, n! = n(n-1)! A8B14ADP Jazyk C - procedurální programovaní

20

Rekurze [1] • •

• •

Rekurzivní funkce (procedury) jsou přímou realizací rekurzivních algoritmů Rekurzivní algoritmus předepisuje výpočet „shora dolů“ v závislosti na velikosti (složitosti) vstupních dat: • pro nejmenší (nejjednodušší) data je výpočet předepsán přímo • pro obecná data je výpočet předepsán s využitím téhož algoritmu pro menší (jednodušší) data Výhodou rekurzivních funkcí (procedur) je jednoduchost a přehlednost Nevýhodou může být časová náročnost způsobená např. zbytečným opakováním výpočtu

•

Řadu rekurzívních algoritmů lze nahradit iteračními, které počítají výsledek „zdola nahoru“, tj, od menších (jednodušších) dat k větším (složitějším)

•

Pokud algoritmus výpočtu „zdola nahoru“ nenajdeme (např. při řešení problému Hanojských věží), lze rekurzivitu odstranit pomocí tzv. zásobníku


21

Rekurzivní algoritmus • Rekurzivní algoritmus v některém kroku volá sám sebe • Rekurzivní metoda v některém příkazu volá sama sebe ( i nepřímo ) • Příklad – faktoriál : • Rekurse n! = 1 pro n≤1 n! = n*(n-1)! pro n>1 • Iterace n! = n*(n-1)*(n-2)*…*2*1


22

Faktoriál pomocí rekurze a iterace Rekurze n! = 1 pro n≤1 n! = n*(n-1)! pro n>1 Iterace n! = n*(n-1)*(n-2)*…*2*1 int fakt(int n) { int fakt(int n) { int fakt(int n) { if (n<=1) return 1; if (n<=1) return 1; int f = 1; else return n*fakt(n-1); return n*fakt(n-1); while (n>1){ } } f *= n; n--; } int fakt(int return n) { f; return n<=1?1:n*fakt(n-1); // ternární operátor } } A8B14ADP Jazyk C - procedurální programovaní

23

Rekurze a rozklad problému na podproblémy •

Program, který přečte posloupnost čísel zakončenou nulou a vypíše ji obráceně

•

Rozklad problému: • zavedeme abstraktní příkaz přečti,vypiš a obrať posloupnost • příkaz rozložíme do tří kroků: „obrať posloupnost“: • přečti číslo (a ulož ho) • if (přečtené číslo není nula) „obrať posloupnost“ (zbytek) • vypiš číslo (uložené)


24

Příklad 3 - Rekurze „Obrať posloupnost“ [1] „obrať posloupnost“ • přečti číslo • if (přečtené číslo není nula) „obrať posloupnost, tj. zbytek“ • vypiš číslo 2 cti x 4 if()… cti x 6 if()… cti x 8 if()… cti x 24680 if()…

08642

2

piš x

piš x

cti x 8

6

4

piš x

0

if()… piš x 0

piš x A8B14ADP Jazyk C - procedurální programovaní

25

Příklad 3 - Rekurze – obrat() posloupnost •

Řešení:

int main(int argc, char** argv){ printf(„Zadejte posloupnost zakončenou nulou"); obrat(); return (EXIT_SUCCESS); } static void obrat() { int x; scanf("%d", &x); if(x!=0) obrat(); printf(("%d ", x); }


// načtení // otočení zbytku // vypsani cisla

26

Příklad 4 - Rekurze - Hanojské věže [1] 1

•

•

2

3

Zavedeme abstraktní příkaz • přenes_věž(n,1,2,3) který interpretujeme jako "přenes n disků z jehly 1 na jehlu 2 s použitím jehly 3". Pro n > 0 lze příkaz rozložit na tři jednodušší příkazy • přenes_věž(n-1,1,3,2) • "přenes disk z jehly 1 na jehlu 2", • přenes_věž(n-1,3,2,1)


27

Příklad 4 - Rekurze - Hanojské věže void main(String[] args) { printf(“Zadejte výšku věže"); int pocetDisku; scanf("%d", &pocetDisku); prenesVez(pocetDisku, 1, 2, 3); }

3 přenes disk z 1 na 2 přenes disk z 1 na 3 přenes disk z 2 na 3 přenes disk z 1 na 2 přenes disk z 3 na 1 přenes disk z 3 na 2 přenes disk z 1 na 2

void prenesVez(int vyska,int odkud,int kam,int pomoci){ if(vyska>0) { prenesVez(vyska-1,odkud,pomoci,kam); printf(“Přenes disk z %d na %d“,odkud,kam); prenesVez(vyska-1,pomoci,kam,odkud); } } A8B14ADP Jazyk C - procedurální programovaní

28

Příklad rekurze - Hanojské věže prenesVez(3, 1, 2, 3); (1, 2);

prenesVez(2, 1, 3, 2);

prenesVez(2, 3, 2, 1);

prenesVez(1, 1, 2, 3); (1, 3); prenesVez(1, 2, 3, 1); | prenesVez(1, 3, 1, 2); (3, 2); prenesVez(1, 1, 2, 3); (1, 2);

(2, 3);

(3, 1);

(1, 2);

prenesVez(int vyska, int odkud, int kam, int pomoci) { if(vyska > 0){ 3 prenesVez(vyska-1,odkud,pomoci,kam); printf(“Přenes disk z %d na %d“,odkud,kam); přenes disk z 1 na 2 přenes disk z 1 na 3 prenesVez(vyska-1,pomoci,kam,odkud); přenes disk z 2 na 3 } přenes disk z 1 na 2 }


přenes disk z 3 na 1 přenes disk z 3 na 2 29 přenes disk z 1 na 2 29

Obecně k rekurzivitě • •

• •

Rekurzivní metody jsou přímou realizací rekurzivních algoritmů Rekurzivní algoritmus předepisuje výpočet „shora dolů“ v závislosti na velikosti (složitosti) vstupních dat: • pro nejmenší ( nejjednodušší ) data je výpočet předepsán přímo • pro obecná data je výpočet předepsán s využitím téhož algoritmu pro menší ( jednodušší ) data Výhodou rekurzivních metod je jednoduchost a přehlednost Nevýhodou může být časová náročnost způsobená např. zbytečným opakováním výpočtu


30

Fibonacciho posloupnost – historie [1] • Maatraameru (Chhandah-shāstra, the Art of Prosody, 450 or 200 BC) • Leonardo Pisano (Leonardo z Pisy), známý také jako Fibonacci (cca 1175–1250) - králíci • Henry E. Dudeney (1857 - 1930) - krávy • „Jestliže každá kráva vyprodukuje své první tele (jalovici) ve věku dvou let a poté každý rok jednu další jalovici, kolik budete mít krav za 12 let, jestliže Vám žádná nezemře?“ • • • • • • •

Rok - počet krav (jalovic) •….. 1 1 •12 144 2 1 •….. 3 2 •50 20 365 011 074 (20 miliard) 4 3 5 5 Počet krav = počet krav vloni + 6 8 počet narozených (odpovídá počtu krav předloni)

fn = fn-1 + fn-2


31

Fibonacciho posloupnost - rekurzivně •

Platí:

f0 = 1 f1 = 1 fn = fn-1 + fn-2

pro n > 1

Rekurzivní funkce: int fib(int i) { if (i < 2) return 1; return fib(i-1)+fib(i-2); }

Rekurze je hezká - zápis „odpovídá“ rekurentní definici. Je ale i efektivní?


32

Složitost výpočtu Fibonacciho čísla - rekurzivně fib(10)

Příklad pro fib(10): fib(9) fib(8) + fib(7) fib(7)+ fib(6)

fib(6)+ fib(5)

+

fib(8) fib(7) + fib(6)

fib(6) + fib(5)

fib(5)+ fib(4)

f50 20 365 011 074 (20 miliard) Složitost je exponenciální!!!! int fib(int i) { if (i < 2) return 1; return fib(i-1)+fib(i-2); A8B14ADP } Jazyk C - procedurální programovaní

33

Fibonacciho posloupnost - iteračně •

Platí: f0 = 1 f1 = 1 fn = fn-1 + fn-2 , pro n > 1

Iteračně: int fibonacci(int n){ int i,fN_2 = 1; int fN_1 = 1, fN = 1; for (i = 2;i <= n; i++){ fN_2 = fN_1; fN_1 = fN; fN = fN_1 + fN_2; } return fN; }


fN_2

fN_1

1

fN

1

1

i

1

+

1

2

2

1

+

2

3

3

2

+

3

5

4

3

+

5

8

5

Složitost: 3*n

34

Reference •

[1] Jelinek,I.- Zděnek, J.: Presentace k přednáškám A0B36PRI, 2012


35

Algoritmizace a programování

Procedurální programování Rekurze KONEC

České vysoké učení technické Fakulta elektrotechnická

Algoritmizace a programování

Recommend Documents