Algoritmy a programování - Úvod

Algoritmy a programování

Organizace předmětu

  • Přednášky:
    • Účast je nepovinná, ale doporučená
  • Cvičení:
    • samostatná práce pod vedením cvičícího
    • automatické ověření správnosti řešení
    • 50% váhy zkoušky
    • nerozumíte-li, ptejte se
    • pokročilí - chtějte další úlohy

Proč se učit programování

  • číst, psát, počítat, programovat
  • počítače jsou všude
  • počítač je nástroj, program je nástroj
  • programování učí logicky a strukturovaně myslet

Co se máme naučit

Řešení problémů

  • formulace problém
  • analýza možných řešení a návrh algoritmu
  • implementace v programovacím jazyce
  • testování, ověření funkčnost
  • optimalizace
  • oprava chyb, implementace nových požadavků, údržba
  • dokumentace

Algoritmus a program

  • Co je to algoritmus?
    • přesný, detailní a úplný postup (obvykle řešení problému)
  • Co je to program?
    • zápis algoritmu v konkrétním programovacím jazyce

Python

Guido van Rossum

Proč Python?

  • jazyk vysoké úrovně, pro všeobecné použití
  • dobře čitelný, multiparadigmatický
  • mnoho knihoven
  • velmi populární (5. místo)
  • dynamický, interpretovaný (byte-code)
  • s automatickou alokací paměti
Budeme používat Python 3.
Toto není kurz jazyka Python. Detaily najdete v [dokumentaci](https://docs.python.org/3/).

Jak Python spustíme?

Napíšeme do příkazové řádky python3:

In [ ]:
!python3

Python 3.4.3 (default, Oct 14 2015, 20:28:29) 
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

(nebo spustíme IDE prostředí jako idle, nebo Jupyter notebook... Možností je mnoho)

Python jako kalkulačka

>python3
Python 3.4.3 (default, Oct 14 2015, 20:28:29) 
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 3+8
11
>>> 11*(5+3)
88
>>> 128./16.
8.0
>>> 2**16
65536

Python jako kalkulačka (2)

totéž, hezky vysázeno

In [1]:
3+8
Out[1]:
11
In [2]:
11*(5+3)
Out[2]:
88
In [1]:
128./16.
Out[1]:
8.0
In [4]:
2**16
Out[4]:
65536

Výrazy

  • Výrazy (expressions) obsahují

    • Celá čísla: 3, 8, ...
    • Reálná čísla: 128., 11.5,...
    • Operátory: +, -, /, *, ...
    • Oddělovače: (, )

Co se děje v zákulisí (REPL)

  • Spustili jsme program python3, interpret Pythonu
    • tisk výzvy (prompt) >>>
    • přečtení uživatelského vstupu (read)
    • vyhodnocení výrazu (evaluate)
    • tisk výsledku (print)
  • Opakované vykonávání (smyčka, loop)
  • REPL (read-eval-print-loop)

Program jako transformace (filtr)

Transformace vstupu na výstup

Toky dat (data flow)

Proměnné a přiřazení

Hodnotu výrazu lze uložit pro pozdější použití

identifikátor = výraz

Příklad:

In [16]:
a=3
b=3+a

Jaká je hodnota proměnné b?

In [17]:
b
Out[17]:
6

Příklad: Proměnné

In [18]:
boys=15
girls=17
total=boys+girls
difference=girls-boys
ratio=boys/total
In [20]:
total
Out[20]:
32
In [21]:
difference
Out[21]:
2
In [19]:
ratio
Out[19]:
0.46875
**Učte se anglicky.** Počítače mluví anglicky, programy jsou anglicky, informace jsou anglicky. Z důvodů přenositelnosti je bezpečnější se omezit na znaky anglické abecedy.

Hodnoty proměnných lze měnit

In [24]:
a=10
a=a-2
a=a*2

Jaká je hodnota a?

In [25]:
a
Out[25]:
16
Není-li pro to dobrý důvod, hodnoty proměnných neměňte.

Proč používat proměnné

  • DRY = Do not repeat yourself.
  • Šetřme si práci, neopakujme se
  • Zlepšení
    • Srozumitelnosti - smysluplná jména proměnných
    • Údržby - jedna změna jen na jednom místě
    • Efektivity - využijeme předchozích výpočtů

Začínáme programovat

První program - Hello world

In [5]:
# Vypíše pozdravení
print("Hello world")
  • vytvoříme v textovém editoru
  • uložíme do souboru hello_world.py
  • spustíme (z příkazové řádky, opakovaně) 
>python3 hello_world.py
In [6]:
!python3 hello_world.py

Hello world
První řádka je komentář - každý program má být komentován.

Editory, integrovaná prostředí (IDE)

  • Editory: Emacs, gEdit, joe, ...

  • spouštění

    • z příkazové řádky
    • z integrovaného prostředí
    • z Jupyter notebooku

  • Integrované prostředí: IDLE, PyCharm, Eclipse, ...

Na konkrétním editoru, případně IDE, zase tolik nezáleží.

Editace a interpretace programu

Editace a interpretace programu

Příklad: Převod stupňů Fahrenheita na stupně Celsia

Kolik ${}^\circ C$ je $75^\circ F$?

In [12]:
f=75
c=(f-32)*5./9.
print(c)

23.88888888888889

Trochu hezčí výpis (pro pokročilé):

In [14]:
print(f,"stupňů Fahrenheita je",c,"stupňů Celsia.")

75 stupňů Fahrenheita je 23.88888888888889 stupňů Celsia.
In [3]:
print("%f stupňů Fahrenheita je %f stupňů Celsia." % (f,c))

75.000000 stupňů Fahrenheita je 23.888889 stupňů Celsia.
  • funkce print vytiskne své argumenty
  • argumentem funkce print může být číslo nebo řetězec
  • %f do řetězce doplní reálná čísla z dalších argumentů
  • Omezíme počet desetinných míst (pro pokročilé):
In [4]:
print("%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia." % 
      (f,c))

75.0 stupňů Fahrenheita je 23.9 stupňů Celsia.
**Všimněte si:** uzávorkovaný výraz můžeme rozdělit na víc řádků

Program = automatizace

Co když chceme převést hodnot více? Kolik ${}^\circ C$ je $30^\circ F$?

  • Šetřme si práci, neopakujme se
  • DRY = Do not repeat yourself
  • Vytvoříme program, který budeme moci opakovaně spouštět

Program = soubor

Do souboru convert1.py uložíme jednotlivé příkazy:

# Program pro převod stupňů Fahrenheita na stupně Celsia
f=75
c=(f-32)*5./9.
print("%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia." % (f,c))

a spustíme z příkazové řádky (i opakovaně)

>python3 convert1.py
In [16]:
!python3 convert1.py

75.0 stupňů Fahrenheita je 23.9 stupňů Celsia.

Čtení parametru z příkazové řádky

Náš program počítá pořád to samé... není flexibilní.

Vylepšená verze (convert2.py):

# Program convert2.py pro převod stupňů Fahrenheita na stupně Celsia
import sys

f=int(sys.argv[1]) # první argument 
c=(f-32)*5./9.
print("%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia." % (f,c))

Argument (stupně Fahrenheita) zadáme pří spouštění:

In [25]:
!python3 convert2.py 60

60.0 stupňů Fahrenheita je 15.6 stupňů Celsia.
In [26]:
!python3 convert2.py 90

90.0 stupňů Fahrenheita je 32.2 stupňů Celsia.
In [27]:
!python3 convert2.py -20

-20.0 stupňů Fahrenheita je -28.9 stupňů Celsia.

Gratuluji, tohle je náš první užitečný program!

Poznámky:

  • Příkaz import sys zpřístupní knihovnu sys - vysvětlíme později.
  • sys.argv[1] je první argument, sys.argv[2] druhý, atd.
  • Znak "!" ignorujte

Základní části textu programů

  • Komentáře:
    # Program convert2.py pro převod stupňů Fahrenheita na stupně Celsia
  • Klíčová slova: import
In [10]:
import keyword
print(keyword.kwlist)

['False', 'None', 'True', 'and', 'as', 'assert', 'break', 'class', 'continue', 'def', 'del', 'elif', 'else', 'except', 'finally', 'for', 'from', 'global', 'if', 'import', 'in', 'is', 'lambda', 'nonlocal', 'not', 'or', 'pass', 'raise', 'return', 'try', 'while', 'with', 'yield']
  • Identifikátory: (jména proměnných a funkcí) f, c, print, ... Písmena, čísla, podtržítka, nezačíná číslem,není klíčové slovo
  • Operátory: +,-,*,/,=,...
  • Literály:
    • Celá čísla: 32,-20,...
    • Reálná čísla: 5., 9., 32.3, 1.3e-6 ($1.3\cdot 10^{-6}$)...
    • Řetězce: "Hello world", 'xyz',"%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia."...

Chyby

(neúplný přehled)

  • Syntaktické chyby (syntax errors)- nejedná se o korektně zapsaný program v Pythonu, např:
In [9]:
c=(f-32*5./9.

  File "<ipython-input-9-6c154279ea5c>", line 1
    c=(f-32*5./9.
                 ^
SyntaxError: unexpected EOF while parsing
  • nedefinované jméno funkce nebo proměnné
In [8]:
prnt("%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia." % (f,c))

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-8-2e2cdc5aa55f> in <module>()
----> 1 prnt("%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia." % (f,c))

NameError: name 'prnt' is not defined
  • Chybám se nevyhnete.
  • Možných chyb je velmi mnoho...
  • Chybová hlášení nám pomáhají chybu najít.
  • Postupně se naučíme, jak dělat chyb méně.
  • chybný vstup
In [10]:
!python3 convert2.py 20c

Traceback (most recent call last):
  File "convert2.py", line 4, in <module>
    f=int(sys.argv[1]) # první argument 
ValueError: invalid literal for int() with base 10: '20c'

Program skončil chybou = "spadnul" (crashed)

  • Dobrý program vstupy kontroluje.
  • Dobrý program umí s chybnými daty pracovat, reaguje na chyby srozumitelnou informací uživateli.
  • To se naučíte postupně.
  • Jako začátečníci předpokládejte, že vstupy jsou správné.
  • logická/významová chyba (bug) - program běží, ale dává špatné výsledky
In [15]:
c=(f-32)+5./9.
In [16]:
print("%0.1f stupňů Fahrenheita je %0.1f stupňů Celsia." % 
      (f,c))

75.0 stupňů Fahrenheita je 43.6 stupňů Celsia.
Odstranit tento druh chyb je nejnáročnější.

Řídící struktury (control structures)

Porovnávání (čísel)

In [1]:
8>3
Out[1]:
True
In [2]:
10<=10
Out[2]:
True
In [4]:
1==0
Out[4]:
False
In [6]:
2!=3
Out[6]:
True
In [7]:
a=4
b=6
a<b
Out[7]:
True

Operátory >,<,==,>=,<=,!=. Vracejí True nebo False (typ bool).

Podmíněný příkaz (if)

# Program conditionals.py pro demonstraci podmíněných příkazů
import sys
n=int(sys.argv[1]) # první argument - celé číslo
if n>0:
    print(n,"je kladné číslo")
print("Konec programu.")
In [20]:
!python3 conditionals.py 10

10 je kladné číslo
Konec programu.
In [21]:
!python3 conditionals.py -1

Konec programu.
Bloky kódu jsou v Pythonu určené odsazením.

Bloky kódu = základ strukturovaného programování.

Větvení (if-else)

# Program conditionals2.py pro demonstraci podmíněných příkazů
import sys
n=int(sys.argv[1]) # první argument 
if n>0:
    print(n,"je kladné číslo")
else:
    print(n,"není kladné číslo")
In [26]:
!python3 conditionals2.py 14

14 je kladné číslo
In [27]:
!python3 conditionals2.py -3

-3 není kladné číslo

Vnořené větvení

# Program conditionals3.py pro demonstraci podmíněných příkazů
import sys
n=int(sys.argv[1]) # první argument 
if n>0:
    print(n,"je kladné číslo")
else:
  if n==0:
     print(n,"je nula")
  else:
     print(n,"je záporné číslo")
In [32]:
!python3 conditionals3.py 14

14 je kladné číslo
In [31]:
!python3 conditionals3.py -3

-3 je záporné číslo
In [30]:
!python3 conditionals3.py 0

0 je nula

Zřetězené podmínky (if-elif-else)

# Program conditionals4.py pro demonstraci podmíněných příkazů
import sys
n=int(sys.argv[1]) # první argument
if n>0:
    print(n,"je kladné číslo")
elif n==0:
    print(n,"je nula")
else:
    print(n,"je záporné číslo")
In [34]:
!python3 conditionals4.py 14

14 je kladné číslo
In [35]:
!python3 conditionals4.py -3

-3 je záporné číslo
In [36]:
!python3 conditionals4.py 0

0 je nula

(Příklad:) Maximum tří čísel

Vytiskněte maximum tří vstupních čísel.

# maximum.py - Vytiskne maximum tří zadaných čísel 
import sys
a=int(sys.argv[1])
b=int(sys.argv[2])
c=int(sys.argv[3])

if a>b: # maximum je a nebo c
  if a>c: # a>b, a>c
    print(a)
  else:   # c >= a > b 
    print(c)
else:     # b >= a
  if b>c: # b > c, b >= a
    print(b)
  else:   # c >= b >= a,
    print(c)
In [49]:
!python3 maximum.py 10 29 3

29

Takové funkce už v Pythonu samozřejmě jsou...

In [52]:
max(10,29,3)
Out[52]:
29

(Příklad:) Kontrola prázdného vstupu

In [38]:
!python3 conditionals4.py

Traceback (most recent call last):
  File "conditionals4.py", line 3, in <module>
    n=int(sys.argv[1]) # první argument
IndexError: list index out of range
  • Zkontrolujeme počet vstupních argumentů
  • sys.argv - seznam vstupních parametrů
  • len(sys.argv) - počet prvků seznamu = počet parametrů ₊ 1
  • sys.argv[0] - nultý parametr = jméno programu (např. "conditionals4.py")
  • sys.argv[1] - první parametr = první uživatelský argument
# Program conditionals5.py pro demonstraci podmíněných příkazů
import sys
if len(sys.argv)!=2:
  print("Zadej cele cislo")
else:
  n=int(sys.argv[1]) # první argument
  if n>0:
  # zde následuje původní kód
    print(n,"je kladné číslo")
  elif n==0:
    print(n,"je nula")
  else:
    print(n,"je záporné číslo")
In [46]:
!python3 conditionals5.py 1

1 je kladné číslo
In [44]:
!python3 conditionals5.py

Zadej cele cislo

Předčasný návrat

# Program conditionals6.py pro demonstraci podmíněných příkazů
import sys
if len(sys.argv)<=1:
  print("Zadej jedno cele cislo")
  sys.exit() # ukončí program

# zde následuje původní program
n=int(sys.argv[1]) # první argument
if n>0:
  print(n,"je kladné číslo")
elif n==0:
  print(n,"je nula")
else:
  print(n,"je záporné číslo")

Funguje stejně jako conditionals5.py.

`sys.exit()` ukončí celý program. Jak ukončit funkce a cykly se naučíme později.

Cykly (smyčky) (loops)

  • Smyčka slouží k opakování části (bloku) programu
    • daný počet opakování (for)
    • pro všechny elementy z dané sekvence (for)
    • dokud platí podmínka (while)
In [54]:
for i in range(10):
    print("Budu se pilně učit.")

Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
In [55]:
for i in range(10):
    print("Budu se pilně učit.")

Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.
Budu se pilně učit.

for cyklus

Proměnná v příkazu

for <promenna> in range(n):
   <blok>

nabírá postupně hodnoty $0\dots n-1$:

In [56]:
for i in range(5):
    print("i=",i)

i= 0
i= 1
i= 2
i= 3
i= 4

Funkce range může mít i parametry start a step.

help(range)

Funkce `help` ukáže nápovědu k dané funkci či příkazu. Zkuste si `help()`.

Nastavení počáteční hodnoty cyklu:

In [59]:
for i in range(1,5):
    print("i=",i)

i= 1
i= 2
i= 3
i= 4

Nastavení kroku 3, počáteční číslo 1, horní hranice 10:

In [63]:
for i in range(1,10,3):
    print("i=",i)

i= 1
i= 4
i= 7

Můžeme počítat i sestupně (počáteční hodnota 5, krok 1, spodní hranice 0):

In [71]:
for i in range(5,0,-1):
    print("i=",i)

i= 5
i= 4
i= 3
i= 2
i= 1

Příklad: Tabulka Fahrenheit - Celsius

In [66]:
for f in range(0,110,10):
    c=(f-32)*5./9.
    print("%5.1fF = %5.1fC" % (f,c))

  0.0F = -17.8C
 10.0F = -12.2C
 20.0F =  -6.7C
 30.0F =  -1.1C
 40.0F =   4.4C
 50.0F =  10.0C
 60.0F =  15.6C
 70.0F =  21.1C
 80.0F =  26.7C
 90.0F =  32.2C
100.0F =  37.8C
  • Soubor tabulka_fahrenheit.py
  • Napříště už uložení do souboru a spuštění zdůrazňovat nebudeme.

Příklad: Součet čísel

Vypočítejte $\sum_{i=1}^{10} i$:

In [87]:
s=0
for i in range(1,101):
    s=s+i
print("Soucet je ",s)

Soucet je  5050

Kontrola:

$$\sum_{i=1}^{n} i = \frac{n (n+1)}{2}$$

Vnořené bloky a cykly

Blok kódu může obsahovat další (vnořené) bloky.

Příklad: násobilka (soubor nasobilka.py)

In [93]:
n=5
for i in range(1,n+1):
    for j in range(1,n+1):
        print("%2d * %2d = %2d" % (i,j,i*j))
 

 1 *  1 =  1
 1 *  2 =  2
 1 *  3 =  3
 1 *  4 =  4
 1 *  5 =  5
 2 *  1 =  2
 2 *  2 =  4
 2 *  3 =  6
 2 *  4 =  8
 2 *  5 = 10
 3 *  1 =  3
 3 *  2 =  6
 3 *  3 =  9
 3 *  4 = 12
 3 *  5 = 15
 4 *  1 =  4
 4 *  2 =  8
 4 *  3 = 12
 4 *  4 = 16
 4 *  5 = 20
 5 *  1 =  5
 5 *  2 = 10
 5 *  3 = 15
 5 *  4 = 20
 5 *  5 = 25
In [94]:
!python3 nasobilka.py

 1 *  1 =  1
 1 *  2 =  2
 1 *  3 =  3
 1 *  4 =  4
 1 *  5 =  5
 2 *  1 =  2
 2 *  2 =  4
 2 *  3 =  6
 2 *  4 =  8
 2 *  5 = 10
 3 *  1 =  3
 3 *  2 =  6
 3 *  3 =  9
 3 *  4 = 12
 3 *  5 = 15
 4 *  1 =  4
 4 *  2 =  8
 4 *  3 = 12
 4 *  4 = 16
 4 *  5 = 20
 5 *  1 =  5
 5 *  2 = 10
 5 *  3 = 15
 5 *  4 = 20
 5 *  5 = 25

Smyčka while

Iteruje, dokud je podminka splněná

while <podminka>:
    <blok>
In [72]:
i=5
while i>0:
    print("i=",i)
    i=i-1

i= 5
i= 4
i= 3
i= 2
i= 1

Cyklus while může nahradit cyklus for, ale nikoliv naopak

Odbočka: Operátor celočíselného dělení a modulo

In [75]:
10/3
Out[75]:
3.3333333333333335
In [76]:
10//3
Out[76]:
3

a zbytek po dělení (operace modulo)

In [77]:
10%3
Out[77]:
1

Vždy platí: (n//k)*k+(n%k)=n

In [79]:
(100//7)*7+(100%7)
Out[79]:
100

Příklad: Kolik číslic má dané přirozené číslo?

Myšlenka: Spočítáme, kolikrát lze dělit deseti, než se dostaneme k nule.

c=1 # počet číslic
while n>10:
  n=n//10 # celočíselné dělení
  c=c+1
print("Počet číslic=%d" % c)

Celý program včetně kontroly vstupů:

In [ ]:
# %load pocet_cislic.py
# Spočítej, kolik číslic má dané přirozené číslo
import sys

if len(sys.argv)!=2:
  print("Chyba: zadej jedno přirozené číslo.")
  sys.exit()

n=int(sys.argv[1])

if n<1:
  print("Chyba:",n,"není přirozené číslo!")
  sys.exit()

print("Bylo zadáno číslo", n)
  
# tady začíná vlastní výpočet  
c=1 # počet číslic
while n>10:
  n=n//10 # celočíselné dělení
  c=c+1
print("Počet číslic=%d" % c)
Pro přehlednost budeme kontroly v přednáškách občas vynechávat. Ve skutečných programech je používejte.

Zkrácené přiřazení

Místo c=c+1 píšeme c+=1. Totéž funguje i pro další operátory. Místo:

c=1 # počet číslic
while n>10:
  n=n//10 # celočíselné dělení
  c=c+1
print("Počet číslic=%d" % c)

napíšeme (soubor pocet_cislic2.py)

c=1 # počet číslic
while n>10:
  n//=10 # celočíselné dělení
  c+=1
print("Počet číslic=%d" % c)

Nekonečný cyklus

Vinou chyby program nikdy neskončí.

In [ ]:
n=982
c=1 # počet číslic
while n>10:
  n//10 # celočíselné dělení
  c+=1
print("Počet číslic=%d" % c)
  • Nekonečný cyklus může být i záměrný.
  • Snažme se dokázat, že program skončí.

Přerušení cyklu (break, continue)

V těle cyklu for nebo while:

  • break ukončí celý cyklus
  • continue přeruší aktuální iteraci a začne následující
In [83]:
for i in range(5):
    if i==3: 
        break        
    print(i)    

0
1
2
In [84]:
for i in range(5):
    if i==3: 
        continue        
    print(i)

0
1
2
4

Příklad: Test prvočíselnosti

prvočíslo $n>1$ je dělitelné pouze 1 a $n$.

$2,3,5,7,11,13,17,19,23,29,\dots$

Test dělitelnosti v Pythonu:

In [85]:
10 % 3 == 0
Out[85]:
False
In [86]:
10 % 5 == 0
Out[86]:
True

Úkol 1: Napište program, který zjistí, zda je zadané číslo prvočíslo.

Zkusím dělit zadané číslo $n$ čísly $p \in 2\dots n-1$, jestli $p\mid n$. (soubor prvocislo1.py)

# Test prvočiselnosti zadaného čísla
import sys
n=int(sys.argv[1]) # číslo, které testujeme
p=2
while p<n:
    if n % p == 0:
        break
    p+=1
if p<n:
    print(n, "není prvočíslo, je dělitelné", p)
else:
    print(n, "je prvočíslo")
In [102]:
!python3 prvocislo1.py 17

17 je prvočíslo
In [103]:
!python3 prvocislo1.py 15

15 není prvočíslo, je dělitelné 3

Otázka: Je 1 prvočíslo?

Úkol 2: Napište program, vypíše všechna prvočísla menší než $m$. (soubor prvocislo2.py)

# Vypíše prvočísla menší než zadaný limit
import sys
m=int(sys.argv[1]) 
for n in range(2,m): # cyklus 2..m-1
  p=2 # začátek testu
  while p<n:
    if n % p == 0:
        break
    p+=1
  if p==n: # n je prvočíslo
    print(n,end=", ")
print(n) #  závěrečný konec řádky

Poznámka: print(n) místo print(n,end=", ") by psalo každé číslo na vlastní řádku

In [107]:
!python3 prvocislo2.py 1000

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,

Optimalizace - nešlo by to rychleji?

  • Hledáme algoritmus, který je správný.
  • Hledáme algoritmus, který je rychlý.

Myšlenka: Stačí testovat pro $p\le\sqrt{n}$, neboť pokud $n=a b$, pak buď $a\le\sqrt{n}$ nebo $b\le\sqrt{n}$.

# prvocislo3.py - Vypíše prvočísla menší než zadaný limit
import sys
m=int(sys.argv[1]) 
for n in range(2,m): # cyklus 2..m-1
  p=2 # začátek testu
  while p*p<=n:
    if n % p == 0:
        break
    p+=1
  if p*p > n: # n je prvočíslo
    print(n,end=", ")  
print() # závěrečný konec řádky
In [123]:
!python3 prvocislo3.py 1000

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,

Změříme čas pro $m=10000$. (Pro přehlednost potlačíme výstup)

In [111]:
!time python3 prvocislo2.py 10000 >/dev/null

4.11user 0.01system 0:04.13elapsed 99%CPU (0avgtext+0avgdata 5848maxresident)k
0inputs+0outputs (0major+1649minor)pagefaults 0swaps
In [112]:
!time python3 prvocislo3.py 10000 >/dev/null

0.17user 0.00system 0:00.17elapsed 98%CPU (0avgtext+0avgdata 5852maxresident)k
0inputs+0outputs (0major+1650minor)pagefaults 0swaps

Vylepšená verze je $24\times$ lepší!

Závěr

Co jsme se naučili

  • Proč se učit programovat
  • Program, algoritmus, programovací jazyk
  • Python, jak ho spustit
  • Jak spustit program ze souboru
  • Čísla, výrazy, proměnné
  • Vstupní argumenty, výstup
  • Podmíněné příkazy (if,else)
  • Smyčky (for, while, break, continue)
  • Chyby
  • Optimalizace