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:

  readln(x,chyba);
  [vypocti clen]
  while [clen] > chyba do
    begin
      rada := rada + [clen];
      [vypocti clen];
    end;

{Načte argument a chybu}
{Vypočte první člen za x}
{Otestuje jeho velikost}

{Přičte}
{Vypočte další člen}



Jak ale počítat každý další člen? Užít funkce pro faktoriál a mocninu?
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:

program Sinus;
  var rada, chyba, clen, x :real;
        delim : integer;
{Deklarace globálních proměnných}

Begin
  writeln('Zadejte argument x (rad) a presnost');
  readln(x,chyba);
  rada := 0;
  clen := x;
  delim := 1;
  while abs(clen) > chyba do
    begin

{Tisk výzvy k zadání}
{Načte argument a chybu}
{Na začátku řada prázdná}
{První člen je x}
{Ve jmenovateli má 1}
{Otestuje velikost členu}

      delim := delim+2;
      rada := rada + clen;
      clen := -clen*x*x/((delim-1)*delim);
{Příště dělí faktoriálem o 2 větším}
{Přičte člen k řadě}
{Vypočte další člen}

    end;
  writeln('Hodnota sin(',x:6:4,') = ',rada:10:8);
End.
{vytiskne výsledek}


4. Využití speciálních vlastností problému

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:
NSD

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.

program Euklid;
  var cislo1_puv, cislo2_puv, cislo1, cislo2 :integer; {Deklarace globálních proměnných}
 
Begin
  writeln('Zadejte dve prirozena cisla:');
  readln(cislo1_puv,cislo2_puv);   
  cislo1 := cislo1_puv; cislo2 := cislo2_puv;
  while cislo1<>cislo2 do
      if cislo1>cislo2 then cislo1:=cislo1-cislo2
                                  else cislo2:=cislo2-cislo1;
  writeln('Nejvetsi spolecny delitel cisel ',cislo1_puv,' a ',cislo2_puv,' je ',cislo1)
End.

{Načte čísla}

{Uchování původních čísel pro tisk}
{Opakuje, dokud si nejsou čísla rovna}

{Odčítá od většího menší}
{Vytiskne výsledek}


Příklad: Sestavte program Horner pro nalezení hodnoty polynomu zadaného stupně a hodnoty proměnné.

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:
a1x4 + a2x3 + a3x2 + a4x + a5 = (((a1x + a2)x + a3)x+a4)x + a5


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).

program Horner;
  var stupen, pocet : integer;
          promenna, polynom, koeficient : real;
{Deklarace globálních proměnných}
 
Begin
  writeln('Zadejte stupen a promennou:');
  readln(stupen,promenna);   
  writeln('Zadejte první koeficient');
  readln(koeficient);   
  polynom := koeficient;
  for pocet := 1 to stupen do
    begin
      writeln('Zadejte dalsí koeficient');
      readln(koeficient);
      polynom := polynom*promenna + koeficient;
    end;
  writeln('Hodnota polynomu je ',polynom:10:2);
End.

{Načte stupeň,proměnnou}

{Načte první koeficient}
{Výchozí hodnotou polynomu bude první koeficient}
{Opakuj tolikrát, kolik je stupeň}

{Zadej další koeficient}
{Vynásob starý polynom proměnnou a přičti nový koeficient}

{Tisk výsledné hodnoty 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

Řešit úkol Prohlídka hodnocení úkolu Dotazy,připomínky

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.