Umíte pascalsky - 8.lekce ... |
Umíte pascalsky? 8.lekce |
Vytisknout |
||||||||||||||||||||||||||||||||||||||||||||
Tvorba efektivních programů Časově efektivnější je ten program, jehož realizace vyžaduje méně (porovnatelných) kroků - je rychlejší při řešení úloh s větší složitostí. Paměťová efektivnější je ten program, jehož realizace vyžaduje méně místa v paměti (méně proměnných..). Dále se budeme věnovat časové efektivnosti. Optimalizace se nazývá úprava programu na efektivnější tvar. Uplatňujeme při ní hlavně tyto zásady: 1. Neprovádět opakovaně v cyklu to, co se dá provést před ním - vyjmutí před cyklus. 2. Optimalizujte tělo cyklu 3. Používejte předchozí výsledky 4. Využívejte speciálních vlastnosti problému 1. Vyjmutí před cyklus Cyklus: for cislo:=1 to pocet do begin vysledek := (argument + cislo)*sin(argument); write(vysledek) end lze optimalizovat takto: pomoc:=sin(argument); for cislo:=1 to pocet do begin vysledek := (argument + cislo)*pomoc; write(vysledek) end Tím se bude sin(argument) počítat poze jednou! 2. Optimalizace těla cyklu Cyklus: for argument:=1 to pocet do begin write(1/(cislo - cos(argument)); write(1/(cislo + cos(argument)); end lze optimalizovat takto: for argument:=1 to pocet do begin pomoc := cos(argument); write(1/(cislo - pomoc)); write(1/{cislo + pomoc}} end Tím se v těle cyklu bude cos(argument) počítat poze jednou! 3. Použítí předchozích výsledků Hodnota sinx, kde x je velikost úhlu v obloukové míře (rad) se počítá podle vzorce: sinx = x - x3/3! + x5/5! - x7/7! + ... Příklad: Sestavte program Sinus pro výpočet hodnoty sinx se zadanou přesnostií (libovolně malé kladné číslo). Myšlenka (hrubý algoritmus): Nejprve se zadá argument x a nějaká přesnost výpočtu - proměnná chyba. Pak se vypočítá první člen řady (zlomek) na pravé straně, zkontroluje, zda je větší (v absolutní hodnotě, protože jsou některé členy záporné) než chyba (má vliv na výsledek), poku ano, přičte se a opakuje se dále pro druhý člen řady atd. Cyklus skončí, až vypočítaný člen bude menší než chyba. Kostra (hrubý program) tedy vypadá takto:
Ne. Stačí si všimnout, že každý další člen se dá snadno vypočítat z předhízejícího. 1) má opačné znaménko ... vynásobíme -1 2) v čitateli je o 2 větší exponent u x ... násobíme x*x 3) ve jmenovateli je faktoriál čísla o 2 větší ... jmenovatele vynásobíme číslem o 1 a o 2 větším A takto vypadá po optimalizaci celý program na výpočet hodnoty sinx:
Při hledání největšího společného dělitele (NSD) dvou přirozených čísel lze využít následující vlastnosti NSD, která je podstatou Euklidova algoritmu: Například tedy: NSD(84,36)=NSD(84-36,36)=NSD(48,36)=NSD(48-36,36)=NSD(12,36)=NSD(12,36-12)=NSD(12,24)=NSD(12,24-12)=NSD(12,12)=12 Příklad: Sestavte program Euklid pro nalezení největšího společného dělitele dvou přirozených čísel. Myšlenka (hrubý algoritmus): Opakovaně odečítáme menší číslo od většího až jsou obě čísla stejná - to je jejich NSD.
Chceme-li vypočítat hodnotu polynomu, používáme nejefektivnější algoritmus, který se nazývá Hornerovo schéma. Rozepíšeme-li si výhodně polynom např. čtvrtého stupně, dostáváme:
Myšlenka (hrubý algoritmus): Při výpočtu hodnoty polynomu tedy nepočítáme jednotlivé mocniny ale postupně (od vnitřku - první hodnotou polynomu bude a1) násobením proměnnou a přičtením dalšího koeficientu až použijeme všechny koeficienty (počet opakování udává stupeň polynomu).
Domácí úkol: Sestavte program Sito pro opakované nalezení zadaného počtu prvočísel pomocí procedury (s parametrem udávajícím počet prvočísel) Hledej a Lepsi_hlede (vznikne optimalizací Hledej) dle volby uživatele. Porovnej časy realizace. On-line účast na řešení úkolu Pomocí volby Řešit můžete (po přihlášení) odeslat vaše řešení domácího úkolu (každý úkol smíte řešit jen jednou). Volbou Hodnocení si přečtete hodnocení a komentář od vyučujícího. Dotaz nebo připomínku můžete opakovaně zasílat pomocí tlačítka Dotazy, Komunikace (na levém okraji) zobrazuje příklad možné komunikace s vyučujícím. |