Základy programování (IZP)

Základy programování (IZP) Bonusové 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 2014/2015

Obsah

• Zopakování zadání druhého projektu • Zopakování problematiky iteračních výpočtů • Obecný úvod • Taylorova řada (minule e^x) • Zřetězené zlomky

IZP doplňkové cvičení

2

Seznámení se zadáním druhého projektu

Iterační výpočty • obhajoba: 24.11.2014 • odevzdání: 30.11.2014 do WISu • dokumentace: 05.12.2014

• 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 / • Součástí projektu je i dokumentace • Zakázáno: použití math.h (až na isnan(), isinf(), tan() a konstanty NAN a INF) IZP doplňkové cvičení

3

Porovnání metod (--tan)

• Budete počítat funkci tangens dvěma iteračními výpočty: • Taylorova řada (Taylor series)

𝑥 3 2𝑥 5 17𝑥 7 62𝑥 9 tan 𝑥 = 𝑥 + + + + +⋯ 3 15 315 2835

• Budete potřebovat 13 čitatelů a jmenovatelů (viz zadání)

• Zřetězené zlomky (Continued Fractions) • Není omezena úroveň zanoření

tan 𝑥 =

𝑥

𝑥2 1− 𝑥2 3− 𝑥2 5− 7−⋯ IZP doplňkové cvičení

4

Porovnání metod (--tan)

• Vaše výsledky porovnáte s výsledky knihovní funkce tan() • Pozor na správný formát výstupu Zkratka I

Význam počet iterací

Formát %d

M

tan() z math.h

%e

T

taylor_tan()

%e

TE

%e

C

absolutní chyba (Taylor) cfrac_tan()

CE

absolutní chyba (zlomky)

%e

%e

• Při porovnávání metod NEBUDETE • uvažovat přesnost 1e-10 a • odvozovat počet iterací tak, aby byla přesnost dosažena IZP doplňkové cvičení

5

Vzdálenost a výška měřeného objektu (-m) • Pomocí metody zřetězených zlomků budete pomocí tangens úhlů 𝛼 a 𝛽 počítat proměnné d a v (pokud bude zadán i úhel 𝛽) na následujícím obrázku:

• Proměnná c je implicitně nastavena, ale pomocí argumentu příkazového řádku se může měnit • Při výpočtech BUDETE • uvažovat přesnost 1e-10 a • odvozovat počet iterací tak, aby byla přesnost dosažena

• Pozor: výpis ve formátu %.10e IZP doplňkové cvičení

6

Další informace o implementaci

Při implementaci věnujte pozornost: • Nejdříve správnému algoritmickému schématu zápisu iteračního výpočtu, • poté přesnosti (tj. počtu iterací), • a až nakonec urychlování a optimalizaci (při hodnocení na to bude brán zřetel) • Všechny úhly budou v radiánech a v prvním 𝜋 kvadrantu [0, ) 2

• Desetinná čísla budou typu double


7

Překlad programu

• Pokud používáme funkce z math.h, je nutné při překladu použít přepínač -lm: gcc –std=c99 –Wall –pedantic –g –lm proj2.c –o proj2


8

Rekurentní problémy [1]

• 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 𝑌𝑖


9


• 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


10


• 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


11


• 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;


12

Ukončovací podmínka [1]

• 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 doplňkové cvičení

13

Výpočet řad [1]

• 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 + 𝑡𝑖 •  částečný součet pro aktuální člen je částečný součet pro předchozí člen + hodnota aktuálního členu


14

Výpočet řad [1]

• 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 doplňkové cvičení

15

Iterační výpočty – součtové řady 2 3 4 𝑥 𝑥 𝑥 𝑒𝑥 = 1 + 𝑥 + + + + ⋯ 2! 3! 4!

Jak postupovat???

IZP cvičení 3

16

Iterační výpočty – součtové řady 2 3 4 𝑥 𝑥 𝑥 𝑒𝑥 = 1 + 𝑥 + + + + ⋯ 2! 3! 4!

Jak postupovat???

// x je v zadání // přesnost (eps) je v zadání // Základní proměnné: // částečný součet // současný a předchozí člen // Určete rozdíl mezi jednotlivými členy řady cyklus(ukončovací podmínka) { // výpočet nového členu řady // výsledek += nový člen řady } IZP cvičení 3

17

Zřetězené zlomky

• V následujícím příkladu budeme počítat číslo 𝜋 pomocí zřetězeného zlomku • Úroveň rozvoje zřetězeného zlomku (n) je zvolena na 4


18

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


19

Zřetězené zlomky


𝜋=

n=3

4

12 1+ 22 3+ 32 5+ 42 7+ 9+⋯

n=4


20

Zřetězené zlomky


𝜋= n=2

n=3

4

12 1+ 22 3+ 32 5+ 42 7+ 9+⋯

n=4


21

Zřetězené zlomky


𝜋= n=1 n=2

n=3

4

12 1+ 22 3+ 32 5+ 42 7+ 9+⋯

n=4


22

Zřetězené zlomky

• Jak bylo řečeno, při výpočtu funkce tangens pomocí zřetězeného zlomku budete uvažovat přesnost 1e-10 a upravovat počet členů • Postup výpočtu: // inicializace prvních dvou úrovní zanoření while (fabs(aktuální – předchozí) > eps) { // provedení iteračního výpočtu // zavolání funkce pro výpočet, uložení nové // hodnoty };


23

Zřetězené zlomky – inicializace

• Pro n=1mplementujte výpočet čísla 𝜋 pomocí zřetězeného zlomku:

4 𝜋= 1


24

Zřetězené zlomky – inicializace

• Pro n = 2výpočet čísla 𝜋 pomocí zřetězeného zlomku:

𝜋= • Atd.

4 12 1+ 3


25

Poznámka

• Nepoužívejte zvláštní funkce pro výpočet • Mocniny • Faktoriálu apod.

• Vždy dopočítávejte pouze rozdíly mezi jednotlivými členy


26

Děkuji Vám za pozornost!


27

Použitá literatura

[1] Materiály ke třetímu demonstračnímu cvičení. FIT VUT


28

Základy programování (IZP)

Recommend Documents