====== Cvičení 2: Cykly a reálná aritmetika ======


==== Opakování ====

=== Celočíselné operace - práce s časem ===
  * Napište program, který načte celé číslo udávající časový interval ve vteřinách a vypíše kolik je to dní, hodin, minut a vteřin.
  * Tedy pokud bude vstup ''100000'' pak vypíše: ''den 1 hodin 3 minut 46 vterin 40''

=== Rozdíl dvou časových údajů ===
  * Napište program, který vypočítá rozdíl dvou časů zadaných ve formátu: ''HH:MM:SS''

=== For cykly ===

  * Napište program, který pomocí konstrukce ''for i in range(od, do, krok):''
      * vytiskne čísla 10 až 500 po deseti
      * vytiskne čísla -20 až -600 po dvaceti

==== Cykly ====
  
Základní druhy cyklů
  * for cyklus - procházení seznamu hodnot
  * while cyklus - opakuj cyklus dokud platí podmínka

While cyklus
  * while cyklus je založen na podmínce, která se vždy na začátku cyklu testuje a pokud je splněna vykoná se zadaný blok instrukcí
  
<code python>
while podmínka:
  blok instrukcí
</code>

  * Zajímavost
     * Lze dokázat, že nelze sestrojit program, který by rozhodl, zda jiný program skončí či nikoliv.
     * Člověk může dokázat, že daný while cyklus skončí
     * Pokud důkaz chybí, není jisté, zda program s while cyklem skončí
<code python>
n = int(input())
while n > 1:
  if n % 2 == 0:
    n = n // 2
  else:
    n = 3 * n + 1
</code>

For cyklus
  * for cyklus standardně prochází zadaný seznam hodnot
  * for cyklus je založen na proměnné, která prochází seznam hodnot a pro každou hodnotu ze seznamu provede blok instrukcí
  
<code python>
for proměnná in seznam:
  blok instrukcí
</code>

<code python>
for i in "abcd":
  print(i)
</code>

<code python>
for i in (1, 10, 2, 8):
  print(i)
</code>

  * Pro standardní procházení nějakého rozmezí:
    * ''range(start, cíl, krok)'', 
    * ''range(cíl)'', kdy start je automaticky 0 a krok je nastaven na 1, 
    * ''range(start, cíl)'', kdy krok je 1.
  * Lze vytvořit i for cyklus, který má dynamicky měnící se seznam hodnot, případně vrací nekonečně krát stejné/rozdílné hodnoty. V tomto případě se pak jedná spíše o while cyklus a vám doporučujeme vzhledem k přehlednosti implementovat takový program jako while cyklus.
  
Instrukce ''break'' a ''continue''
  * Uvnitř bloku instrukcí mohou být příkazy ''break'' a ''continue''.
  * Příkaz ''break'' znamená, že se okamžitě ukončí vykonávání bloku instrukcí a ukončí se i cyklus, který tento blok instrukcí obsahuje.
  * Příkaz ''continue'' znamená, že 
    * se ukončí provádění bloku instrukcí a provede se vyhodnocení podmínky (u while cyklu)
    * se přejde na novou hodnotu (u for cyklu) a pokud je to možné pokračuje se v provádění bloku instrukcí.
  * POZOR u vnořených cyklů nemají příkazy ''break''/''continue'' vliv na vnější cyklus.

<code python>
for i in "abcd":
  if i == "c":
    break
  print(i)
</code>
  * Výstup:
<code>
a
b
</code>

<code python>
for i in "abcd":
  if i == "c":
    continue
  print(i)
</code>
  * Výstup: 
<code>
a
b
d
</code>

==== Úkol 1 While cykly ====
  * Napište program, který udělá to samé co opakování for cyklů pomocí ''while'' cyklu:
      * vytiskněte čísla 10 až 500 po deseti
      * vytiskněte čísla -20 až -600 po dvaceti


==== Úkol 2 Break loop ====
  * Napište program, který načte číslo $n$ a najde jeho nejmenšího dělitele většího než 1.
  * Je vhodné použít konstrukci ''break'', cyklus můžete použít ''while'' i ''for''.
  * Otestujte svůj program na čísle 999962000357

  
  
==== Úkol 3 Tisk šachovnice ====
  * Napište program, který vytiskne čtvercovou šachovnici ze znaků 'O' a '*' o velikosti zadané uživatelem, jako vstup Vašeho programu.
  * Pro tisk znaku bez konce řádky použijte následující konstrukci (//end// definuje zakončení řetězce a je standardně nastaveno na nový řádek):
<code python>
print('.', end="")
</code>
==== Úkol 4 Odlaďte syntaktické chyby v programu ====
  * Zkopírujte si následující kód do souboru
  * V programu odstraňte syntaktické chyby
  * Program spusťte a zjistěte co dělá

<code python>
step = 0.1
sum = 0
for is in range(1, 11):
    sum += step
    if suma == is / 10:
        print("Plati", sum, "rovno", is / 10)
     else:
       print("Neplati", sum, "nerovno", is / 10)
</code>

==== Úkol 5 Výpočet třetí odmocniny přičítáním ====
  * Vypočtěte třetí odmocninu kladného čísla $y$, zadaného jako vstup Vašeho programu následujícím postupem:
     * Přičítejte k proměnné $v$ číslo 1 dokud je třetí mocnina této proměnné menší než $y$
     * Přičítejte k proměnné $v$ číslo 0.1 dokud je třetí mocnina této proměnné menší než $y$
     * Přičítejte k proměnné $v$ číslo 0.01 dokud je třetí mocnina této proměnné menší než $y$
     * Proměnná $v$ obsahuje odmocninu čísla $y$ s přesností na dvě desetinná čísla

==== Úkol 6 Výpočet třetí odmocniny přičítáním se zadanou přesností ====
  * Upravte předchozí program tak, aby pracoval se zadanou přesností
  * Program načte číslo $y$ a $n$ a nalezne třetí odmocninu z čísla $y$ na $n$ desetinných míst
  * Upravte algoritmus, aby uměl spočítat i třetí odmocniny ze záporných čísel


==== Úkol 7 Půlení intervalu ====
  * Metoda půlení intervalu hledá řešení obecné rovnice $f(x)=0$, kdy známe dva body $x_1$ a $x_2$ takové, že $f(x_1)<0$ a $f(x_2)>0$. 
     * Algoritmus rozpůlí interval mezi body $x_1$ a $x_2$, tedy nalezne bod $x' = \frac{x_1+x_2}{2}$ a pokud je $f(x')<0$ pak nahradí bod $x_1$ bodem $x'$, jinak nahradí bod $x_2$ bodem $x'$.
     * Výše uvedený krok se opakuje dokud není $|x_1-x_2|<\epsilon$, kde $\epsilon$ je požadovaná přesnost.
  * V případě hledání třetí odmocniny z čísla //y//:
      * $f(x)=x^3-y$
      * Pokud $f(x)=0$, tak $x^3-y=0$, což lze zapsat jako $x^3=y$ a tedy $x=\sqrt[3]{y}$
  * Napište program, který nalezne třetí odmocninu zadaného čísla $y$ na 8 desetinných míst 
      * (výpočet ukončíte pokud $|x_1-x_2|<0.000000001$). 
      * Na počátku zvolte $x_1=0$ a $x_2=y$ pro kladná $y>1$, $x_1=y$ a $x_2=0$ pro záporná $y< -1$, a $x_1=-1$ a $x_2=1$ v ostatních případech.
==== Úkol 8 Výpočet třetí odmocniny Newtonovou metodou ====
  * Newtonova (Babylónská) metoda tečen $x_{i+1}=\frac{f(x_i)}{f'(x_i)}$ pro třetí odmocninu z čísla $y$ dostáváme $$x_{i+1}=\frac{1}{3}\left( 2x_i + \frac{y}{x_i^2} \right)$$
  * Řada $x_i$ konverguje k třetí odmocnině z čísla $y$
  * $x_0$ můžete nastavit na libovolnou hodnotu různou od 0, např $x_0=1$, případně na lepší odhad.
  * Čím lepší odhad nalezneme, tím rychleji řada konverguje.
  * Výpočet lze ukončit
      * např. podle rozdílu $|x_{i+1}-x_i| < \epsilon$
      * nebo lze testovat $|x_i^3 - n| < \epsilon$ 

==== Úkol 9 Výpočet třetí odmocniny - porovnání ====
  * Spusťte všechny úlohy 6 - 8 pro stejné hodnoty čísla $y$ a zjistěte, které řešení potřebuje nejmenší počet kroků (změna hodnoty $x$) k nalezení řešení s přesností na 8-desetinných míst $\epsilon=10^{-8}$.
 

===== Domácí příprava =====

Procvičte si znalosti z tohoto cvičení na následujících příkladech:
   * Algoritmus pro výpis čísel -100,-99,-80,-79,-60,-59, $\ldots$ -20,-19,0,1,20,21, $\ldots$, 100.
   * Výpis hodnot sin(x) v intervalu $<0,2\pi)$ se zadaným krokem $\delta$. Např. pro $\delta=0.1$ program vypíše sin(0), sin(0.1), sin(0.2) atd. 

===== Domácí úkol =====

==== Lehká varianta ====
  * Napište program **root.py** který metodou půlení intervalu spočítá kořen zadaného polynomu 5. stupně na intervalu $< -1,1>$
    * **Vstup:**  je šest řádek ze standardního vstupu, každá řádka obsahuje jedno reálné číslo. Označme je postupně $a, b, c, d, e, f$.
    * **Výstup:** jedno číslo, které je řešením rovnice $a\cdot x^5 + b\cdot x^4 + c\cdot x^3 + d\cdot x^2 + e\cdot x + f=0$ pro $x$ v intervalu $< -1,1>$

  * Pro výpočet použijte metodu půlení intervalu.
  * Výsledek nalezněte s přesností na 8 desetinných míst (výpočet ukončíte pokud $|x_1-x_2|<0.000000001$).
  * Pro prvotní nastavení krajních použijte meze intervalu $-1$ a $1$
  * Použití jakékoliv knihovní funkce (např. ''math.log'') není dovoleno, program volající cizí funkce nebude hodnocen.
 
**Příklady**
<code>Vstup:
1.0
-86.57953
2211.04584
-14290.33697
-68290.75634
36557.68411
Výstup
0.489</code>
Polynom:  $x^5 - 86.57953 \cdot x^4 + 2211.04584 \cdot x^3 - 14290.33697 \cdot x^2 - 68290.75634 \cdot x + 36557.68411$

<code>
Vstup:
0.0
1.0
-24.56866
-630.51769
2795.40059
1895.26625
Výstup
-0.599</code>
Polynom:  $1. \cdot x^4 -24.56866 \cdot x^3 -630.51769 \cdot x^2 + 2795.40059 \cdot x + 1895.26625$.
==== Těžká varianta ====
  * Napište program **base.py**, který od sebe odečte čísla v zadané číselné soustavě
    * **Vstup:** čtyř řádky standardního vstupu, první řádka definuje základ číselné soustavy, druhá, třetí a čtvrtá obsahují tři desetinná čísla v zadané číselné soustavě
    * **Výstup:** číslo v zadané soustavě, které je součtem prvních dvou čísel od kterých je odečteno číslo třetí nebo ''ERROR''

  * Např. desetinné binární číslo $101.0101 = 1*2^2+0*2^1+1*2^0+0*2^{-1}+1*2^{-2}+0*2^{-3}+1*2^{-4} = 5.3125$.
  * Základ výstupní soustavy je v rozmezí 2 .. 36, správnost základu soustavy (první vstup) nemusíte testovat.
  * Pokud je na vstupu špatně zadané číslo (obsahuje jiné znaky než takové, které jsou přípustné pro zadanou soustavu a znak '.', případně obsahuje znak '.' vícekrát), pak program vytiskne na výstup ''ERROR''
    * Pro soustavy o základu menším nebo rovno 10, obsahuje desetinné číslo pouze čísla od 0 .. základ soustavy - 1 a znak ''.''
    * Pro soustavy o základu větším než 10, obsahuje desetinné číslo na výstupu čísla 0,..,9 a malá písmena 'a', .. , 'z' taková, že hodnota $ord(znak)-ord('a')< zaklad\_soustavy-10$.
  * **Řešení vypisujte bez tzv. leading/trailing zeros**
    * příklad leading zeros: "00.1" (správně má být "0.1"), "-010.1" (má být "-10.1")
    * příklad trailing zeros: "0.00100" (správně je "0.001"), "-0.620" (správně je "-0.62")
 
**Příklady**
Jednoduchý příklad, základ soustavy 3:
<code>
Vstup:
3
1.2222
1.0121
2.12
Výstup:
0.122
</code>
Jednoduchý příklad, základ soustavy 33:
<code>
Vstup:
33
pm.ttnp1
l.e12w
n.m6hqnq
Výstup:
pk.lo8ua7
</code>
Složitější příklad, záporný výsledek, základ soustavy 2:
<code>
Vstup:
2
1.10011
10.011
1101.0011
Výstup:
-1001.00111
</code>
Chybné zadání, soustava 4:
<code>
Vstup:
4
10.1313
11.2302214
23021.331
Výstup:
ERROR
</code>