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

• 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

• Napište program, který vypočítá rozdíl dvou časů zadaných ve formátu: HH:MM:SS

• 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

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í

while podmínka:
  blok instrukcí

• 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čí

n = int(input())
while n > 1:
  if n % 2 == 0:
    n = n // 2
  else:
    n = 3 * n + 1

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í

for proměnná in seznam:
  blok instrukcí

for i in "abcd":
  print(i)

for i in (1, 10, 2, 8):
  print(i)

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

for i in "abcd":
  if i == "c":
    break
  print(i)

• Výstup:

a
b

for i in "abcd":
  if i == "c":
    continue
  print(i)

• Výstup:

a
b
d

• 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

• 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

• 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):

print('.', end="")

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

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)

• 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

• 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

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

• Newtonova (Babylónská) metoda tečen $x_{i+1}= x_{i}-\frac{f(x_i)}{f'(x_i)}$ pro třetí odmocninu z čísla $y$ je opět $f(x)=x^3-y$ a tím $f'(x)=3x^2$, pak 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$

• 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}$.

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.

* Napište program root.py který metodou půlení intervalu spočítá kořen polynomu 5-tého stupně $a_5\cdot x^5+a_4\cdot x^4+a_3\cdot x^3+a_2\cdot x^2+a_1\cdot x+a_0$

• Vstup: šest řádek, obsahující postupně koeficienty $a_5$ až $a_0$. Koeficient $a_5$ je na první řádce, $a_0$ na poslední řádce.
• Výstup: jedno reálné číslo, které je kořenem zadaného polynomu.

• 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 mezí víte že:
  • kořen $x \in (-100,100 )$
• Použití jakékoliv knihovní funkce (např. math apod.) není dovoleno, program volající cizí funkce nebude hodnocen.

• Napište program rational.py, který převede reálné číslo v desítkové soustavě na reálné číslo v soustavě o zadaném základu
  • Vstup: dvě řádky standardního vstupu, první řádka obsahuje celé číslo od 2 do 36, základ soustavy, druhá řádka obsahuje reálné číslo pro převod
  • Výstup: reálné číslo v zadané soustavě na 10 míst za tečkou.

• Pro vstup reálného čísla můžete použít konverzi float(input())
• Správný formát výstupního čísla:
  • číslo začíná nenulovým znakem, nebo znakem - a nenulovým znakem
  • Pro soustavy o základu menším nebo rovno 10, obsahuje desetinné číslo pouze znaky od 0 .. (základ soustavy - 1) a znak .
  • Pro soustavy o základu větším než 10, obsahuje desetinné číslo na výstupu znaky 0,..,9 a malá písmena 'a', .. , $chr(ord('a') + zaklad\_soustavy-11)$.
  • “trailing zeros” - číslo vypište vždy s 6 místy za tečkou, i kdyby bylo číslo již převedeno přesně
    • příklad trailing zeros: “0.25” převedeno na dvojkovou soustavu “0.010000”

• Příklady:

  Vstup:
  2
  111.1
  Výstup:
  1101111.000110

  Vstup:
  26
  0.1
  Výstup:
  0.2fffff

  Vstup:
  5
  -125.12345
  Výstup:
  -1000.030203

  Vstup:
  36
  1068.5385991730136
  Výstup:
  to.je0vse