Pˇr´ıklady Pˇredn´aˇska 4
26. ˇr´ıjna 2015
OBSAH 1
Funkce Lokalizace (viditelnost) jmen
2
Typ promˇenn´e: pole Pouˇzit´ı pole – pˇr´ıklady
3
Typ UKAZATEL K ˇcemu ukazatel? Pole a ukazatel
4
Typ promˇenn´e : soubor
5
Knihovna stdlib – uˇziteˇcn´e funkce Generov´an´ı ˇc´ısel Tˇr´ıdˇen´ı Vyhled´av´an´ı
6
Sloˇzitost
7
ˇ Cteme programy
Program v C
3/ 45
Program v C je mnoˇzina funkc´ı, z nichˇz pr´avˇe jedna je main.
A co dalˇs´ı?
Funkce
4/ 45
Deklarace funkce: hlaviˇ cka funkce tˇ elo funkce u) hlaviˇ cka funkce: typ jm´eno ( seznam parametr˚ typ: void, int, float ... typ n´avratov´e hodnoty seznam parametr˚ u: () nebo (void) ... ˇz´adn´e parametry (typ jmeno, typ jmeno) (int a, float b) tˇ elo funkce: { deklarace promˇenn´ych; pˇr´ıkazy; } V tˇele funkce je pˇr´ıkaz return v´ yraz ; kde hodnota v´yrazu m´a typ n´avratov´e hodnoty. Vol´ an´ı funkce: jmeno funkce (seznam argument˚ u); za parametry se dosad´ı hodnoty v zadan´em poˇrad´ı v C se parametry pˇred´avaj´ı hodnotou Uvnitˇr funkce nesm´ı b´yt deklarov´ana jin´a (lok´aln´ı) funkce.
K ˇcemu jsou funkce?
Dˇelba pr´ace ˇ Citelnost (srozumitelnost) programu ...
5/ 45
Pˇr´ıklad int nacti_cele(){ int a; scanf("%d",&a); return(a); } float nacti_float(){ float a; scanf("%f",&a); returm a;} pouˇ zit´ı: int main(){ int a,b; a=nacti_cele(); b=nacti_cele(); float p,q; p=nacti_float(); q=nacti_float(); }
6/ 45
Funkce s parametry a jednou n´avratovou hodnotou
Plocha troj´ uheln´ıku (Heron˚ uv vzorec): float plocha_heron(float a, float b, float c){ float p, o; o=(a+b+c)/2; p=sqrt(o*(o-a)*(o-b)*(o-c)); return p;} Diskriminant kvadratick´e rovnice: float diskriminant (float a, float b, float c){ return(b*b-4*a*c);}
7/ 45
V´ıce neˇz jedna n´avratov´a hodnota N´ avratov´ a hodnota je zmˇ enˇ en´ a hodnota. Parametry se pˇred´avaj´ı hodnotou: obsah vnˇ ejˇs´ı promˇenn´e se nemˇ en´ı, hodnoty se kop´ıruj´ı do lok´aln´ıch promˇenn´ych funkce.
Jak to ”obej´ıt”?
glob´aln´ı promˇenn´e pomoc´ı ukazatele
8/ 45
Oblasti viditelnosti promˇenn´ych (identifik´ator˚ u) // glob´aln´ı kontext int A[100], B; #define mojepi 3.14 secti(int A , int B ) // lok´aln´ı kontext: {return A+B;} void napln pole(int N ) // lok´aln´ı kontext: {int i; for(i=0; i
Typ promˇenn´e: Pole
10/ 45
Definice pole promˇ enn´ ych typ NAZEV_POLE[maximalnivelikost]; int A[10]; float B[20]; Index zaˇ c´ın´ a nulou, prvky tedy jsou A[0], ... , A[9] B[0],B[1], ... , B[19] Pr´ ace s prvky pole. Jako s jakoukoliv jinou promˇennou, jen s jednotliv´ymi prvky, pomoc´ı index˚ u. Indexy nejsou kontrolov´any. A[7]=5; x=A[0]+2*A[1]; i=8; A[i]=4;
Deklarace pole
11/ 45
deklarace pole: int float typ jm´eno [ poˇcet ]; typ ... poˇcet mus´ı b´yt zn´am pˇri pˇrekladu, proto ´ ˇ SPRAVN E int v[4]; #define POCET 10 float r[20]; . . . int z[POCET]; poˇcet urˇcuje, kolik prvk˚ u m´a pole, tj. (kolik pamˇeti bylo pˇridˇeleno).
Prvky pole
12/ 45
Prvky pole jsou promˇenn´e typu typ . K jednotliv´ym prvk˚ um se dostaneme pomoc´ı z´avorek [ ] Indexuj´ı se vˇzdy od 0 (tj. m´ame prvky z[0]...z[POCET-1]). NEN´I kontrola mez´ı! int v[4]; m´ame v[0]...v[3]. Pˇri v[4] ... lezeme na ciz´ı u ´zem´ı! v 6 6 6
66
v [0] v [1] v [2] v [3] v [4]
Kdy potˇrebujeme pole
13/ 45
Chceme oznaˇcit jedn´ım jm´enem ”podobn´e”hodnoty Vytvoˇrit pole 100 prvoˇc´ısel. Pr´ace s vektory. Zpracov´an´ı 50 namˇeˇren´ych hodnot stejn´e veliˇciny. Mus´ıme data zkoumat v´ıcekr´at Kolik ˇc´ısel se liˇs´ı od aritmetick´eho pr˚ umˇeru o v´ıce neˇz p %. Kolik ze zadan´ych ˇc´ısel se rovn´a posledn´ımu. Seˇradit ˇc´ısla podle velikosti.
Operace
14/ 45
Nelze prov´est operaci s cel´ym polem najednou. Zpravidla realizujeme operaci pomoc´ı cyklu, ve kter´em pracujeme s jednotliv´ymi prvky pole. Pˇr´ıklady: Naplnit pole hodnotami. Vytisknout pole. Urˇcit, kolik ze zadan´ych ˇc´ısel se liˇs´ı od aritmetick´eho pr˚ umˇeru o p. Vytvoˇrit pole prvn´ıch 100 prvoˇc´ısel. Uvaˇzujte, kde je nutn´e pouˇz´ıt pole, kde si vystaˇc´ıme s jednoduch´ymi promˇenn´ymi: D´ano 50 ˇc´ısel. Urˇcit aritmetick´y pr˚ umˇer. D´ano 50 ˇc´ısel. Kolik z nich se rovn´a posledn´ımu? D´ano 100 ˇc´ısel. Vytisknout nejprve kladn´a, potom ostatn´ı.
Naplnit pole hodnotami a vytisknout
#include<stdio.h> main() { int pole[10], i; printf("Zadej 10 celych cisel\n"); for(i=0; i<10; i++) scanf("%d",&pole[i]); printf("Pole obsahuje tato cisla:\n"); for(i=0; i<10; i++) printf("%d, ",pole[i]); }
15/ 45
Funkce pro pr´aci v poli
16/ 45
Bez ukazatele, s glob´ aln´ı promˇ ennou. Glob´aln´ı promˇenn´a: pouˇzit´ı na vlastn´ı nebezpeˇc´ı! #include<stdio.h> #define N //maximalni pocet prvku int nacti_cele(){int a; scanf("%d",&a); return a;} int G_a[N], G_b[N] void nacti_pole_int(int kolik){ //VZDY do pole G_a!!! int i; for(i=0; i
Pouˇzit´ı
17/ 45
int main(){ int pocet; pocet=nacti_cele(); nacti_pole_int(pocet); //nacteny hodnoty do G_a! tiskni_pole(2,3); //vytiskne G_b[2]: co tam je? kopiruj(0,pocet); tiskni_pole(0,pocet); }
Ukazatel
18/ 45
Co to je? typ * jmeno jmeno
ˇcteme : jmeno je ukazatel na typ -
hodnota typu typ
promˇenn´a jmeno je typu ukazatel , typ jmeno
*jmeno je typu typ
ˇcteme : jmeno je promˇ enn´ a typu typ
promˇenn´a &jmeno je typu ukazatel ,
jmeno je typu typ
Kˇ cemu ukazatel? Parametr funkce: hodnota ukazatele se nezmˇen´ı, ”obsah”ano Pole jako parametr funkce, funkce jako parametr funkce, ... Definov´an´ı abstraktn´ıch datov´ ych typ˚ u (seznamy, stromy)
Zmˇena hodnoty parametru funkce ... void vymen(int * a, int * b) { int pom; pom = *a; *a = *b; *b = pom; return ; } main() { int a,b; scanf("%d%d", &a, &b); vymen(&a, &b); printf("a=%d, b=%d", a, b); }
19/ 45
Funkce jako parametr funkce void tabl(float odk, float dok, float krok, double(∗f)(double) ) { float x; for(x=odk; x<dok; x=x+krok) printf("\n%4.2f\t%5.3lf",x,f(x)); return; } double g(double x) { float vysledek; vysledek = cos(x)+3∗sin(x); return vysledek; } main() { float x; tabl(1,2,0.01,g); tabl(0,M PI,0.1,cos); }
20/ 45
Pole a ukazatel : int * a; a b int v[3]; v p
21/ 45
float * b; hodnota typu int hodnota typu float float p[3]; hodnoty typu int hodnoty typu float -? -?
int *v1, v[3]; - ? ... v1
ROZD´IL ? pamˇet’ nepˇridˇelena!
6 6 v1+1 v1+2 v Promˇenn´a v je zaˇc´atek um´ıstˇen´ı 3 hodnot typu int. pro v[0], v[1], v[2] je pamˇet’ pˇridˇelena, pro *v1 , pro v[3]...
NEN´I!!
Pˇridˇelov´an´ı pamˇeti
22/ 45
Kaˇzd´e m´ısto, na kter´e ukazuje ukazatel mus´ı m´ıt pˇridˇelenu pamˇet’! Knihovna stdlib , funkce malloc(). typ * jmeno; ⇒ jmeno = (typ *)malloc(kolik*sizeof(typ)); int * a, *v1; a = (int *) malloc(sizeof(int)); v1 = (int *) malloc(3*sizeof(int)); (ted’ m˚ uˇzeme s polem v1 pracovat stejnˇe jako s polem v, tj v1[0], v1[1], v1[2]) Uvolnˇen´ı pamˇeti funkce free () Pomoc´ı ukazatele je moˇzn´e deklarovat pole, kter´e bude m´ıt pˇridˇelenu pamˇet’ v pr˚ ubˇ ehu pr´ ace programu.
Pole jako parametr funkce, pole jako n´avratov´a hodnota funkce
23/ 45
Funkce, kter´a ze zadan´eho pole vytvoˇr´ı nov´e, ve kter´em budou ˇc´ısla v opaˇcn´em poˇrad´ı. int * funkce (int * pole, int N) { int * vysl, i; vysl = (int *)malloc(N* sizeof(int)); for(i=0; i
Kr´atce o souborech
24/ 45
Deklarace FILE * jmeno_promenne; ”standardn´ı I/O”: stdin, stdout Operace 1
otevˇren´ı na ˇcten´ı (r) nebo na z´apis (w): jmeno promenne = fopen(”jmeno souboru”,”r”); jmeno promenne = fopen(”jmeno souboru”,”w”);
2
zavˇren´ı fclose(jmeno promenne);
3
cteni ze souboru fscanf( jmeno promenne,”format”,&kam);
4
z´apis do souboru fprintf(jmeno promenne,”format”,co);
5
testov´an´ı na konec souboru: feof(jmeno promenne)
K ˇcemu soubory?
Jeden program napoˇc´ıt´a hodnoty, druh´y program je zpracuje. (Napˇr´ıklad grafick´e zobrazen´ı hodnot.) Dat je hodnˇe – nezad´av´ame poˇr´ad z kl´avesnice ...
Jak se pouˇz´ıvaj´ı
26/ 45
FILE * vstup, *vystup; vstup=fopen("jmeno souboru","r"); vystup = fopen("jmeno souboru","w"); ... fprintf(vystup, "...", ...); fscanf(vstup, "...", ...; ... fclose(vstup); fclose(vystup); kl´avesnice a obrazovka: standardn´ı – nemus´ıme deklarovat, otev´ırat a zav´ırat fprintf(stdout, ”. . . ”, . . . ); fscanf(stdin, ”. . . ”, . . . ); lehce zmˇen´ıme: vstup=stdin;
vystup=stdout;
Pˇr´ıklad – v´ysledky mˇeˇren´ı
27/ 45
V souboru cisla.txt m´ame 100 re´aln´ych ˇc´ısel. Potˇrebujeme zjistit, kolik z nich se liˇs´ı od pr˚ umˇern´e hodnoty o m´enˇe neˇz 10% a uloˇzit je do souboru spravna.txt. Jak na to? 1
Naˇcteme ˇc´ısla do pole.
2
Pˇri naˇc´ıt´an´ı urˇc´ıme jejich souˇcet.
3
Vypoˇc´ıt´ame pr˚ umˇer. Znovu projdeme vˇsechna ˇc´ısla a
4
vyhovuj´ıc´ı spoˇc´ıt´ame a zap´ıˇseme do souboru.
Pˇr´ıklad – program
28/ 45
#include... #define N 100 main(){ FILE * f; int i, pocet=0; float s=0,p[N]; f = fopen("cisla.txt","r"); if(f== NULL){printf("PROBLEM!"); return -1;} for(i=0; i< N; i++) { fscanf(f,"%f",&p[i]); s=s+p[i]; }//celkovy soucet fclose(f); s=s/N; //prumer f = fopen("spravna.txt","w"); for(i=0; i< N; i++) //prochazime cisla jeste jednou if(fabs(p[i]-s)<0.1)//pokud se lisi "malo" {pocet=pocet+1; fprintf(f,"%5.3f\n", p[i]); } fclose(f); }
Pˇr´ıklad – poˇcty zn´amek
29/ 45
V souboru znamky.txt m´ame v´ysledky testu ve tvaru: student (identifikaˇcn´ı ˇc´ıslo) zn´amka (1,2,3,4). Potˇrebujeme zjistit, kolik bylo jedniˇcek, dvojek, trojek, ˇctyˇrek. Posledn´ı z´aznam m´a id rovn´y 0. Jak na to? Pomocn´ e pole poˇcty velikosti 5: poˇcty[0]: – nic, poˇcty[1] – jedniˇcky . . . poˇcty[4] – ˇctyˇrky. 1
Ze souboru pˇreˇcteme 2 ˇc´ısla: prvn´ı id ignorujeme, dokud nen´ı nulov´e druh´e znamka zpracujeme:
2
poˇcty[ znamka] = poˇcty[ znamka] +1.
3
Projdeme pole poˇcty a vyp´ıˇseme v´ysledky.
Zn´amky – program #include<stdio.h> main(){ FILE * f; int i, id, znamka, pocty[5]; for(i=0; i< 5; i++) pocty[i] = 0; f = fopen("znamky.txt","r"); if(f== NULL){printf("PROBLEM!"); return -1;} fscanf(f,"%d",&id); while(id!=0){ fscanf(f,"%d",&znamka); pocty[znamka] = pocty[znamka]+1; fscanf(f,"%d",&id); } fclose(f); for(i=1; i<= 4; i++) fprintf(stdout,"%5d", pocty[i]); }
30/ 45
Funkce z knihovny stdlib
31/ 45
http://www.cplusplus.com/reference/cstdlib/ Tˇr´ıdˇ en´ı : qsort tˇr´ıd´ı algoritmem quicksort souvisl´e pole libovoln´eho typu Vyhled´ av´ an´ı(v setˇr´ıdˇen´em poli) : bsearch realizuje bin´arn´ı vyhled´av´an´ı v poli libovoln´eho typu Generov´ an´ı ˇ c´ısel int rand (void); vygeneruje pseudon´ahodn´a ˇc´ısla
Pˇr´ıklad: Generov´an´ı n´ahodn´ych ˇc´ısel
32/ 45
#include <stdio.h> /* printf, scanf, NULL */ #include <stdlib.h> /* srand, rand */ #include
/* time */ main () /* uhodni cislo */ { int tajne, hadane; /* initializace generatoru nahod: */ srand (time(NULL)); /* generuje tajne cislo mezi 1 a 10: */ tajne = rand() % 10 + 1; do { printf ("\nHadej, jake cislo si myslim (1 -- 10): "); scanf ("%d",&hadane); if (tajnehadane) printf ("\nTajne cislo je vetsi" } while (tajne!=hadane); printf ("Uhadl jsi!");
Tˇr´ıdˇen´ı : quicksort
33/ 45
void qsort( void *pole, ukazatel na pole, kter´e tˇr´ıd´ıme poˇcet prvk˚ u size t N, size t prvek, velikost prvku int (*porovnej)(const void *, const void *) jak se urˇcuje poˇrad´ı ); size t is je ”obecn´y”bezznam´enkov´y typ. K tˇr´ıdˇen´ı je pouˇzita funkce na kterou ukazuje porovnej. Funkce porovnej() mus´ı vracet z´apornou hodnotu, pokud je prvn´ı argument menˇs´ı neˇz druh´y, nulovou hodnotu pokud se rovnaj´ı a kladnou hodnotu pokud je prvn´ı argument vˇetˇs´ı neˇz druh´y. qsort (poleA, 6, sizeof(int), compare);
Funkce vyhovuj´ıc´ı ˇsablonˇe
34/ 45
ˇ Sablona: int compar (void* prvni, void* druhy); dva argumenty – ukazatele, kter´ymi budou pˇred´any dvˇe hodnoty n´avratov´a hodnota: typ int – kladn´a hodnota v pˇr´ıpadˇe, ˇze prvn´ı pˇred druh´ym (>) – z´aporn´a hodnota v pˇr´ıpadˇe, ˇze prvn´ı za druh´ym ( < ) – nula v pˇr´ıpadˇe, ˇze prvn´ı == druh´y int porovnej cele(int *a, int *b) { return *a - *b; } pˇretypov´an´ı na ”sablonu”: (int (*)(const void *, const void *)) porovnej cele nebo (bez pˇretypov´an´ı): int porovnej cele (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int porovnej realne (const void * a, const void * b) { if(fabs(*(float*) a - *(float * ) b) < EPS) return 0; else return (*(float *) a - *(float *)b); } Podobnˇe – ”porovnej”podle zadan´e ˇsablony pro r˚ uzn´e typy.
Pouˇzit´ı qsort #include <stdio.h> #include <stdlib.h>
35/ 45
/* printf */ /* qsort */
int poleA[] = { 40, 10, 100, 90, 20, 25 }; int compare (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } main () { int n; qsort (poleA, 6, sizeof(int), compare); for (n=0; n<6; n++) printf ("%d ",poleA[n]); }
Bin´arn´ı vyhled´av´an´ı: bsearch
36/ 45
void* bsearch ( void* hledane, ukazatel na hledan´y prvek void* pole, ukazatel na pole, kde hled´ame poˇcet prvk˚ u size t pocet, size t prvek, velikost prvku int (*compar)(const void*,const void*) jak se urˇcuje poˇrad´ı ); Funkce vr´at´ı ukazatel na prvek v poli, pokud tam je, nebo NULL, pokud nen´ı.
Pouˇzit´ı bsearch
37/ 45
#include <stdio.h> /* printf */ #include <stdlib.h> /* qsort, bsearch, NULL */ int porovnej (const void * a, const void * b) { return ( *(int*)a - *(int*)b ); } int A[] = { 50, 20, 60, 40, 10, 30 }; main () { int * nalezeno; int hledam = 40; qsort (A, 6, sizeof (int), porovnej); nalezeno = (int*) bsearch (&hledam, A, 6, sizeof (int),porovnej); if (nalezeno!=NULL) printf ("%d je mezi hodnotami.\n",*nalezeno); else printf ("%d nenalezeno.\n", hledam); }
Sloˇzitost
Kter´e ˇreˇsen´ı je lepˇs´ı? Pamˇet’ov´a sloˇzitost ˇ Casov´ a sloˇzitost Vzhledem k ˇcemu?
Zpravidla k velikosti vstupu.
Nejhorˇs´ı pˇr´ıpad. Pr˚ umˇern´y pˇr´ıpad. Asymptotick´a sloˇzitost : Definice Asymptotick´y horn´ı odhad funkce. Mˇejme funkce f : N → R+ , g : N → R+ . f ∈ O(g ) : ∃n0 ∈ N, ∃c ∈ R+ : ∀n ≥ n0 : f (n) ≤ c · g (n)
Sloˇzitost: pˇr´ıklad
M´ame posloupnost N ˇc´ısel; hled´ame maximum. Algoritmus: Naˇ cti vstup do posl[1]...posl[N] max=posl[1] Pro i=2 aˇ z N: Jestliˇ ze posl[i]>max, tak max=posl[i] Vypiˇ s max. Maxim´alnˇe N-1 porovn´an´ı. Pamˇet’ : N, ale lze konstantn´ı.
Sloˇzitost: pˇr´ıklad
Mˇejme K , vyp´ıˇseme tabulku n´asobk˚ u ˇc´ısel 1...K Pro i= 1 aˇ z K Pro j= 1 aˇ z K Vypiˇ s i*j a mezeru Pˇ rejdi na nov´ y ˇ r´ adek Tabulka m´a velikost K 2 na kaˇzd´em pol´ıˇcku str´av´ıme konstantn´ı ˇcas. Pamˇet’...konst nebo K 2
Dˇelba koˇristi
Dva lupiˇci objevili poklad a spoleˇcnˇe vykopali velk´e mnoˇzstv´ı minc´ı. Chtˇej´ı se o nˇe rozdˇelit rovn´ym d´ılem, na coˇz si napsali program. Kaˇzd´a mince m´a svoji zadanou hodnotu (pˇrirozen´e ˇc´ıslo), seznam hodnot program dostane na vstupu, na v´ystup vyp´ıˇse, jak si je maj´ı rozdˇelit, nebo ozn´am´ı, ˇze ˇreˇsen´ı neexistuje. Napˇr´ıklad pro mince o hodnot´ach 3, 3, 5, 5 dostanou oba mince s hodnotou 3, 5; pro sadu minc´ı 3, 3, 5 ˇreˇsen´ı neexistuje. V programu je chyba a ne mal´a, nehledejte tedy zapomenut´y stˇredn´ık, chybu v pouˇzit´ı knihovn´ı funkce jako qsort nebo neoˇsetˇren´ı ˇcten´ı vstupu. Lupiˇci ˇspatnˇe vymysleli cel´y algoritmus a program by si zaslouˇzil od z´akladu pˇrepsat.
Co dˇel´a... #include <stdio.h> #include <stdlib.h> #define MAX 1000 int N; // poˇ cet minc´ ı int ceny[MAX]; // hodnoty minc´ ı int la[MAX], lb[MAX]; // co dostane kdo // Vyp´ ıˇ se zadan´ e pole o N prvc´ ıch void vystup(int *pole, int N) { for (int i=0; i0) printf(" "); printf("%d", pole[i]); } printf("\n"); }
// Porovn´ avac´ ı funkce pro qsort() int cmp(const void *a, const void *b) { return (*((int *)b) - *((int *)a)); } int main(void) { // Pˇ reˇ cteme vstup scanf("%d", &N); for (int i=0; i
int a=0, ai=0, b=0, bi=0; for (int i=0; i pˇ rid´ ame A la[ai] = ceny[i]; ai=ai+1; a = a+ceny[i]; } else { // B -> pˇ rid´ ame B lb[bi] = ceny[i]; bi=bi+1; b = b+ ceny[i]; } }
if (b == a) { // Povedlo se rozdˇ elit // Tak to vyp´ ıˇ seme vystup(la,ai); vystup(lb,bi); } else // Nepovedlo se rozdˇ elit printf("Nelze spravedlivˇ e rozdˇ elit.\n"); exit(0); } Najdeme vstup, na nˇemˇz vyp´ıˇse ˇspatn´y v´ysledek, a urˇc´ıme pro tento vstup spr´avn´y v´ysledek.
