Základy programování (IZP) Sedmé laboratorní cvičení Vysoké učení technické v Brně, Fakulta informačních technologií v Brně Božetěchova 2, 612 66 Brno Cvičící: Petr Veigend (
[email protected]) Gabriela Nečasová Petr Veigend 2015/2016
Obsah
• Seznámení se zadáním druhého projektu • Funkce a řetězce • Iterační výpočty
IZP cvičení 7
2
Seznámení s druhým projektem
IZP cvičení 7
3
Seznámení se zadáním druhého projektu
Iterační výpočty (max 7 bodů) • Obhajoba: • Odevzdání:
24.11.2015 29.11.2015, 23:59:59 do WISu
• Název: proj2.c • Výstup: • standardní výstup pro výpis výsledků (na wiki) • standardní chybový výstup pro výpis chyb
• V rámci projektu můžete používat pouze matematické operace +,-,* a / • Překlad: nutno využít přepínač -lm: gcc –std=c99 –Wall –pedantic –lm proj2.c –o proj2 IZP cvičení 7
4
Syntaxe spuštění ./proj2 –-log X N ./proj2 –-iter MIN MAX EPS
• --log: vypočítá přirozený logaritmus čísla X v N iteracích • A) Pomocí Taylorova polynomu • B) Pomocí zřetězených zlomků (Continued Fractions)
• --iter: hledání požadovaného počtu iterací pro dostatečně přesný výpočet logaritmu čísla z intervalu <MIN;MAX> • Minimální přesnost: EPS = 1e-12
IZP cvičení 7
5
Implementační detaily
• Zakázáno: používat funkce z math.h • Povoleno: • Funkce • Konstanty
log(), isnan(), isinf() NAN, INFINITY
• Nezapomeňte důkladně testovat na merlinovi !!!
IZP cvičení 7
6
Implementační detaily (--log) – Taylorův polynom double taylor_log(double x, unsigned int n);
• x = číslo • n = počet členů Taylorova polynomu • Pro 0 < x < 2
𝑥2 𝑥3 𝑥4 log 1 − 𝑥 = −𝑥 − − − − ⋯ 2 3 4 • Pro x > ½ ∞ 𝑥−1 𝑥 log 𝑥 = 𝑛
𝑛
𝑛=1
• Doporučená mezní hodnota mezi polynomy je 1 IZP cvičení 7
7
Implementační detaily (--log) – zřetězený zlomek double cfrac_log(double x, unsigned int n);
• x = číslo (zde z) • n = rozvoj zřetězeného zlomku
IZP cvičení 7
8
Implementační detaily (--log) – formát výpisu log(X) = LOG_X cf_log(X) = CF_LOG_X taylor_log(X) = TAYLOR_LOG_X
• • • •
X – hodnota daná argumentem (printf %g) LOG_ hodnoty log() z math.h CF_LOG_ hodnoty vypočtené zřetězeným zlomkem TAYLOR_LOG_ hodnoty vypočtené Taylorovým polynomem
IZP cvičení 7
9
Implementační detaily – hledaní počtu iterací
• Uživatel zadá interval <MIN;MAX> a přesnost EPS • Program v tomto intervalu spočítá přirozený logaritmus pomocí Taylorova polynomu a zřetězených zlomků s danou přesností EPS a vypíše následující:
IZP cvičení 7
10
Implementační detaily – hledaní počtu iterací log(MIN) = LOG_MIN log(MAX) = LOG_MAX continued fraction iterations = CF_ITER cf_log(MIN) = CF_LOG_MIN cf_log(MAX) = CF_LOG_MAX taylor polynomial iterations = TAYLOR_ITER taylor_log(MIN) = TAYLOR_LOG_MIN taylor_log(MAX) = TAYLOR_LOG_MAX
• • • •
X, MIN, MAX – hodnoty dané argumenty (printf %g) LOG_ hodnoty log() z math.h CF_LOG_ hodnoty vypočtené zřetězeným zlomkem TAYLOR_LOG_ hodnoty vypočtené Taylorovým polynomem IZP cvičení 7
11
Implementační detaily – hledaní počtu iterací log(MIN) = LOG_MIN log(MAX) = LOG_MAX continued fraction iterations = CF_ITER cf_log(MIN) = CF_LOG_MIN cf_log(MAX) = CF_LOG_MAX taylor polynomial iterations = TAYLOR_ITER taylor_log(MIN) = TAYLOR_LOG_MIN taylor_log(MAX) = TAYLOR_LOG_MAX
• Všechny *LOG_* hodnoty (printf %.12g) • CF_ITER, TAYLOR_ITER – počet iterací
IZP cvičení 7
12
Funkce a řetězce
IZP cvičení 7
13
Funkce pro práci s řetězci – string.h
• Vyhledání znaku c v řetězci s, vrací ukazatel na vyhledaný znak, jinak NULL char* strchr(char* s, int c); • Kopie řetězce src do řetězce dst, vrací ukazatel na dst char* strcpy(char* dst, char* src); • Spojení řetězců dst a src, výsledek v dst char* strcat(char* dst, char* src); • Lexikografické porovnání řetězců s1 a s2 int strcmp(char* s1, char* s2); IZP cvičení 7
14
Bodovaný úkol 1 Práce s řetězci
IZP cvičení 7
15
Bodovaný úkol 1
• Implementujte si vlastní funkci pro lexikografické porovnání dvou řetězců int strcmpMy(char* s1, char* s2); • Funkce vrací: • 0 pokud s1 == s2 • -1 pokud s1 < s2 • 1 pokud s1 > s2
IZP cvičení 7
16
Iterační výpočty
IZP cvičení 7
17
Rekurentní problémy
• Rekurentní problém: výpočet nové hodnoty závisí na hodnotě výpočtu z předcházejícího kroku • Rekurentní vztah obecně: 𝑌𝑖+1 = 𝐹(𝑌𝑖 ) • Pro výpočet hodnoty 𝑌𝑖+1 je nutné zjistit hodnotu 𝑌𝑖
IZP cvičení 7
18
Rekurentní problémy
• Musí být dána počáteční hodnota 𝑌0 • Co musí platit pro hodnoty získané posloupnosti • 𝑌𝑖+1 = 𝐹(𝑌𝑖 ) pro y ≥ 0 • 𝑌𝑖 ≠ 𝑌𝑗 pro všechna i ≠ 𝑗 • 𝑌𝑖 pro i < 𝑁 nesplňuje podmínky požadované hodnoty • 𝑌𝑁 splňuje podmínky hledané hodnoty
IZP cvičení 7
19
Rekurentní problémy
• Algoritmické schéma řešení Y = y0; // Y – proměnná, y0 – počáteční hodnota
while(¬B(Y)) // dokud není splněna koncová podmínka Y = F(Y); // budeme počítat další prvek // posloupnosti
IZP cvičení 7
20
Rekurentní problémy
• Algoritmické schéma řešení Y = y0; // Y – proměnná, y0 – počáteční hodnota
while(¬B(Y)) // dokud není splněna koncová podmínka Y = F(Y); // budeme počítat další prvek // posloupnosti
• Zápis v C může vypadat např. double y = y0; while(!b(y)) // dokud není splněna koncová podmínka y = f(y); // budeme počítat další prvek // posloupnosti return y;
IZP cvičení 7
21
Ukončovací podmínka
• Běžně se iterační výpočet ukončí, pokud |𝑌𝑖 − 𝑌𝑖−1 | ≤ 𝐸𝑃𝑆 • To se dá v C zapsat např. double y = y0; // aktuální člen double yp; // předchozí člen do { yp = y; // uložíme hodnotu předchozího členu y = f(y); // vypočítáme další člen } while (fabs(y - yp) > eps);
• Algoritmické schéma lze použít pro výpočet číselných řad (Taylorův rozvoj), kterými lze aproximovat funkce IZP cvičení 7
22
Příklad 1: Druhá odmocnina Newtonovou metodou
• Implementujte funkci, která vypočítá druhou odmocninu √𝑥 Newtonovou metodou
𝒚𝒊+𝟏
𝟏 𝒙 = ∗ + 𝒚𝒊 𝟐 𝒚𝒊
• Prototyp funkce si vhodně zvolte
IZP cvičení 7
23
Výpočet řad
• K výpočtu řad se používají částečné součty • Pro řadu 𝑡0 , 𝑡1 , 𝑡2 , 𝑡3 , … , 𝑘𝑑𝑒 𝑡𝑖 = 𝑓 𝑡𝑖−1 můžeme napsat řadu částečných součtů 𝑖
𝑠0 , 𝑠1 , 𝑠2 , 𝑠3 , … , 𝑘𝑑𝑒 𝑠𝑖 = 𝑡𝑗 𝑗=0
• Můžeme je opět řešit rekurentně: • • • •
𝑠0 = 𝑡0 𝑠1 = 𝑠0 + 𝑡1 = 𝑡0 + 𝑡1 𝑠𝑖 = 𝑠𝑖−1 + 𝑡𝑖 částečný součet pro aktuální člen je částečný součet pro předchozí člen + hodnota aktuálního členu IZP cvičení 7
24
Výpočet řad
• Algoritmické schéma T = t0; // první člen řady S = T; // součet = první člen řady while(¬B(S, T)) { T = f(T); // vypočítáme nový člen řady S = S + T; // tento člen přičteme k aktuálnímu // částečnému součtu }
• Je nutné si vždy zjistit, jak se od sebe liší jednotlivé členy řady • Pozor: Některé řady konvergují nejrychleji jen v omezeném definičním oboru funkce IZP cvičení 7
25
Bodovaný úkol 2 Částečné součty (řady)
IZP cvičení 7
26
Bodovaný úkol 2
Pomocí částečných součtů implementuje výpočet exponenciální funkce 𝒆𝒙 . (Taylorova) řada má následující tvar: 2 3 4 𝑥 𝑥 𝑥 𝑒𝑥 = 1 + 𝑥 + + + + ⋯ 2! 3! 4!
Výsledek porovnejte s matematickou knihovnou math.h a obě hodnoty vypište na standardní výstup Nemůžete použít mocninu, faktoriál a funkci exp(x) z matematické knihovny math.h. Můžete použít funkci fabs()pro výpočet absolutní hodnoty a exp(x) pro výpis IZP cvičení 7
27
Bodovaný úkol 2 (66.6…) 2 3 4 𝑥 𝑥 𝑥 𝑒𝑥 = 1 + 𝑥 + + + + ⋯ 2! 3! 4! x = 4.2; eps = 0.01; double t = t0; double s = t; int i = 1; while (fabs(t) t = f(t, i); s = s + t;
// první člen řady // součet = první člen řady // index aktuálního členu řady > eps) { // vypočítáme nový člen řady // tento člen přičteme k // aktuálnímu částečnému součtu
} return s; IZP cvičení 7
28
Zřetězené zlomky
IZP cvičení 7
29
Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:
𝜋=
4
12 1+ 22 3+ 32 5+ 42 7+ 9+⋯
IZP cvičení 7
30
Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:
𝜋=
4
12 1+ 22 3+ 32 5+ 42 7+ 9+⋯
n=4
IZP cvičení 7
31
Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:
𝜋=
n=3
4
12 1+ 22 3+ 32 5+ 42 7+ 9+⋯
n=4
IZP cvičení 7
32
Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:
𝜋= n=2
n=3
4
12 1+ 22 3+ 32 5+ 42 7+ 9+⋯
n=4
IZP cvičení 7
33
Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:
𝜋= n=1 n=2
n=3
4
12 1+ 22 3+ 32 5+ 42 7+ 9+⋯
n=4
IZP cvičení 7
34
Příklad 2: Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:
𝜋=
4
12 1+ 22 3+ 32 5+ 42 7+ 9+⋯
IZP cvičení 7
35
Příště…
• 17.11. – státní svátek CVIČENÍ ODPADÁ • Můžete přijít na libovolné jiné cvičení, ale zadání bude vhodné pro samostudium • Pozor: spousta cvičících je příští týden pryč
• Protože se už do půlsemestrálky neuvidíme, hodně štěstí IZP cvičení 7
36
Příklady k procvičení
IZP cvičení 7
37
Příklad na rozehřátí
• Implementujte funkci void getMax(int *pole, int len, int *max);
která vyhledá v poli maximální hodnotu a vrátí ji přes ukazatel
IZP cvičení 7
38
Příklad na rozehřátí
• Implementujte funkci void getMax(int *pole, int len, int *max);
která vyhledá v poli maximální hodnotu a vrátí ji přes ukazatel • Jak inicializujeme pole?
IZP cvičení 7
39
Příklad na rozehřátí
• Implementujte funkci void getMax(int *pole, int len, int *max);
která vyhledá v poli maximální hodnotu a vrátí ji přes ukazatel • Jak inicializujeme pole? int pole[10]={7,2,3,9,15,20,-1,42,100,-75};
IZP cvičení 7
40
Příklad na rozehřátí
• Implementujte funkci void getMax(int *pole, int len, int *max);
která vyhledá v poli maximální hodnotu a vrátí ji přes ukazatel • Jak inicializujeme pole? int pole[10]={7,2,3,9,15,20,-1,42,100,-75};
• Jak zavoláme funkci getMax()?
IZP cvičení 7
41
Příklad na rozehřátí
• Implementujte funkci void getMax(int *pole, int len, int *max);
která vyhledá v poli maximální hodnotu a vrátí ji přes ukazatel • Jak inicializujeme pole? int pole[10]={7,2,3,9,15,20,-1,42,100,-75};
• Jak zavoláme funkci getMax()? int maximum = 0; getMax(pole, &maximum); IZP cvičení 7
42
Příklad 3: Zřetězené zlomky
Implementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku: 4 =1+ 𝜋 2+
1 9
25 2+ 2+⋯ Čitatele se vypočítají podle vztahu (2 ∗ 𝑛 − 1)2
IZP cvičení 7
43
Děkuji Vám za pozornost!
IZP cvičení 7
44
