Programy a algoritmy pracující s čísly
IB111 Úvod do programování
Radek Pelánek
2017
1 / 59
Rozcvička
12
+ 22
+ 32
+ · · · + 992
+ 1002
2 / 59
Dnešní přednáška
práce s čísly v Pythonu
ukázky programů, ilustrace použití základních konstrukcí
ukázky jednoduchých algoritmů, ilustrace rozdílu v
efektivitě
3 / 59
Číselné typy
int – celá čísla
float
čísla s plovoucí desetinnou čárkou
reprezentace: báze, exponent
nepřesnosti, zaokrouhlování
( complex – komplexní čísla )
4 / 59
Nepřesnosti
Přesná matematika:
((1 +
1
x
) − 1) · x = 1
Nepřesné počítače:
>>> x = 2**50
>>> ((1 + 1 / x) - 1) * x
1.0
>>> x = 2**100
>>> ((1 + 1 / x) - 1) * x
0.0
5 / 59
Nepřesné výpočty – praktický případ
1 2 3 1 2
záměr chyba
6 / 59
Číselné typy – poznámky
explicitní přetypování: int(x), float(x)
automatické „nafukování typu int:
viz např. 2**100
pomalejší, ale korektní
rozdíl od většiny jiných prog. jazyků (běžné je
„přetečení )
v Python2.7 dělení: rozdíl 3/2 a 3/2.0
v Python3 dělení intuitivní
7 / 59
Pokročilejší operace s čísly
Některé operace v knihovně math:
použití knihovny: import math
zaokrouhlování: round, math.ceil, math.floor
absolutní hodnota: abs
math.exp, math.log, math.sqrt
goniometrické funkce: math.sin, math.cos, . . .
konstanty: math.pi, math.e
8 / 59
Ciferný součet
vstup: číslo x
výstup: ciferný součet čísla x
příklady:
8 → 8
15 → 6
297 → 18
11211 → 6
9 / 59
Ciferný součet: základní princip
opakovaně provádíme:
dělení 10 se zbytkem – hodnota poslední cifry
celočíselné dělení – „okrajování čísla
10 / 59
Ciferný součet – nevhodná pasáž
if n % 10 == 0:
f = 0 + f
elif n % 10 == 1:
f = 1 + f
elif n % 10 == 2:
f = 2 + f
elif n % 10 == 3:
f = 3 + f
elif n % 10 == 4:
f = 4 + f
...
11 / 59
Ciferný součet – řešení
def digit_sum(n):
result = 0
while n > 0:
result += n % 10
n = n // 10
return result
12 / 59
Return vs. print
připomenutí:
print = výpis
return = návratová hodnota, se kterou můžeme dále
pracovat
blízký vztah k matematickým funkcím
příklad:
výpis všech čísel menších jak 1000 s ciferným součtem 13
13 / 59
Collatzova posloupnost
vezmi přirozené číslo:
pokud je sudé, vyděl jej dvěma
pokud je liché, vynásob jej třemi a přičti jedničku
tento postup opakuj, dokud nedostaneš číslo jedna
14 / 59
htts://xkcd.com/710/
15 / 59
Collatzova posloupnost: výpis
def collatz_sequence(n):
while n != 1:
print(n, end=", ")
if n % 2 == 0:
n = n // 2
else:
n = 3*n + 1
print(1)
16 / 59
Collatzova posloupnost: příklady graficky
17 / 59
Bonus: Vykreslení grafu v Pythonu
Využívá seznamy a knihovnu pylab
import pylab
def collatz(n):
sequence = []
while n != 1:
sequence.append(n)
if n % 2 == 0:
n = n // 2
else:
n = 3*n + 1
sequence.append(1)
return sequence
pylab.plot(collatz(27))
pylab.show()
18 / 59
Collatzova posloupnost: délka posloupnosti
def collatz_length(n):
length = 1
while n != 1:
if n % 2 == 0:
n = n // 2
else:
n = 3*n + 1
length += 1
return length
def collatz_table(count):
for i in range(1, count+1):
print(i, collatz_length(i))
19 / 59
Collatzova posloupnost: délka posloupnosti I
20 / 59
Collatzova posloupnost: délka posloupnosti II
21 / 59
Collatzova hypotéza
Hypotéza: Pro každé počáteční číslo n, posloupnost
narazí na číslo 1.
experimentálně ověřeno pro velká n (∼ 1018
)
důkaz není znám
22 / 59
Největší společný dělitel
vstup: přirozená čísla a, b
výstup: největší společný dělitel a, b
příklad: 180, 504
Jak na to?
23 / 59
Naivní algoritmus I
projít všechny čísla od 1 do min(a, b)
pro každé vyzkoušet, zda dělí a i b
vzít největší
24 / 59
Naivní algoritmus II
„školní algoritmus
najít všechny dělitele čísel a, b
projít dělitele, vybrat společné, vynásobit
příklad:
180 = 22 · 32 · 5
504 = 23 · 32 · 7
NSD = 22 · 32 = 36
25 / 59
Euklidův algoritmus: základ
základní myšlenka: pokud a > b, pak:
NSD(a, b) = NSD(a − b, b)
příklad:
krok a b
1 504 180
2 324 180
3 180 144
4 144 36
5 108 36
6 72 36
7 36 36
8 36 0
26 / 59
Neefektivita
uvedená verze je neefektivní
může být pomalejší než naivní algoritmus I
kdy?
27 / 59
Euklidův algoritmus: vylepšení
vylepšená základní myšlenka: pokud a > b, pak:
NSD(a, b) = NSD(a mod b, b)
krok a b
1 504 180
2 180 144
3 144 36
4 36 0
28 / 59
Euklidův algoritmus: program
varianta s odčítáním, bez rekurze
def nsd(a,b):
if a == 0:
return b
while b != 0:
if a > b:
a = a - b
else:
b = b - a
return a
29 / 59
Euklidův algoritmus: program
modulo varianta, rekurzivně
def nsd(a,b):
if b == 0:
return a
else:
return nsd(b, a % b)
30 / 59
Euklidův algoritmus – vizualizace
http://en.wikipedia.org/wiki/Euclidean_algorithm
31 / 59
Efektivita algoritmů
proč byly první dva algoritmy označeny jako „naivní ?
časová náročnost algoritmu:
naivní: exponenciální vůči počtu cifer
Euklidův: lineární vůči počtu cifer
různé algoritmy se mohou výrazně lišit svou efektivností
často rozdíl použitelné vs nepoužitelné
více později (a v dalších předmětech)
32 / 59
Výpočet odmocniny
vstup: číslo x
výstup: přibližná hodnota
√
x
Jak na to?
33 / 59
Výpočet odmocniny
vstup: číslo x
výstup: přibližná hodnota
√
x
Jak na to?
Mnoho metod, ukázka jedné z nich (rozhodně ne nejvíce
efektivní)
33 / 59
Výpočet odmocniny: binární půlení
horní odhadspodní odhad
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
0 1 20.5 1.5
střed
34 / 59
Výpočet odmocniny: binární půlení
def square_root(x, precision=0.01):
upper = x
lower = 0
middle = (upper + lower) / 2
while abs(middle**2 - x) > precision:
if middle**2 > x:
upper = middle
if middle**2 < x:
lower = middle
middle = (upper + lower) / 2
return middle
35 / 59
Výpočet odmocniny – chyba
Drobný problém: Program není korektní.
Kde je chyba?
36 / 59
Výpočet odmocniny – poznámky
Funguje korektně jen pro čísla ≥ 1.
Co program udělá pro čísla < 1?
Proč?
Jak to opravit?
37 / 59
Vsuvka: Obecný kontext
problém
⇓
algoritmus
⇓
program
⇓
ladění
38 / 59
Poznámka o ladění
laděním se nebudeme (na přednáškách) příliš zabývat
to ale neznamená, že není důležité...
Ladění je dvakrát tak náročné, jak psaní vlastního kódu. Takže
pokud napíšete program tak chytře, jak jen umíte, nebudete
schopni jej odladit. (Brian W. Kernighan)
39 / 59
Postřeh k ladění
Do průšvihu nás nikdy nedostane to, co nevíme. Dostane nás
tam to, co víme příliš jistě a ono to tak prostě není. (Y. Berry)
40 / 59
Ladění
ladící výpisy
např. v každé iteraci cyklu vypisujeme stav proměnných
doporučeno vyzkoušet na ukázkových programech ze
slidů
použití debuggeru
dostupný přímo v IDLE
sledování hodnot proměnných, spuštěných příkazů,
breakpointy, ...
41 / 59
Součet druhých mocnin
Lze zapsat zadané číslo jako součet druhých mocnin?
Příklad: 13 = 22
+ 32
Která čísla lze zapsat jako součet druhých mocnin?
42 / 59
Součet druhých mocnin: řešení I
def sum_of_squares_test(n):
for i in range(n+1):
for j in range(n+1):
if i**2 + j**2 == n:
print(n, "=", i**2, "+", j**2)
Program je zbytečně neefektivní. Proč?
Výpis čísel, která lze zapsat jako součet čtverců
43 / 59
Testování druhé mocniny: nevhodný if
def is_square(n):
square_root = int(n**0.5)
if square_root**2 == n:
return True
else:
return False
44 / 59
Součet druhých mocnin: řešení II
def is_square(n):
square_root = int(n**0.5)
return square_root**2 == n
def is_sum_of_squares(n):
for i in range(int(n**0.5) + 1):
rest = n - i**2
if is_square(rest):
return True
return False
def print_sums_of_squares(count):
for i in range(count):
if is_sum_of_squares(i):
print(i, end=", ")
45 / 59
Podobné náměty
variace: součet tří druhých mocnin, součet dvou třetích
mocnin, ...
další náměty na posloupnosti: The On-Line Encyclopedia
of Integer Sequences, http://oeis.org/
46 / 59
Náhodná čísla
přesněji: pseudo-náhodná čísla
opravdová náhodná čísla: http://www.random.org/
bohaté využití v programování: výpočty, simulace, hry, ...
Python
import random
random.random() – float od 0 do 1
random.randint(a,b) – celé číslo mezi a, b
mnoho dalších funkcí
47 / 59
Náhodná čísla: xkcd
htts://xkcd.com/221/
htts://xkcd.com/1277/
48 / 59
Náhodná čísla: průměr vzorku
Vygenerujeme náhodná čísla a vypočítáme průměrnou
hodnotu:
def random_average(count, maximum=100):
total = 0
for i in range(count):
total += random.randint(0, maximum)
return total / count
Jakou očekáváme hodnotu na výstupu? Jak velký bude rozptyl
hodnot? (Názorná ukázka centrální limitní věty)
49 / 59
Simulace volebního průzkumu
volební průzkumy se často liší; jaká je jejich přesnost?
přístup 1: matematické modely, statistika
přístup 2: simulace
program:
vstup: preference stran, velikost vzorku
výstup: preference zjištěné v náhodně vybraném vzorku
50 / 59
Simulace volebního průzkumu
def survey(size, pref1, pref2, pref3):
count1 = 0
count2 = 0
count3 = 0
for i in range(size):
r = random.randint(1,100)
if r <= pref1: count1 += 1
elif r <= pref1 + pref2: count2 += 1
elif r <= pref1 + pref2 + pref3: count3 += 1
print("Party 1:", 100.0 * count1 / size)
print("Party 2:", 100.0 * count2 / size)
print("Party 3:", 100.0 * count3 / size)
51 / 59
Poznámky ke zdrojovému kódu
uvedené řešení není dobré:
„copy & paste kód
funguje jen pro 3 strany
lepší řešení – využití seznamů
52 / 59
Kámen, nůžky, papír
http://cs.wikipedia.org/wiki/Kámen,_nůžky,_papír
53 / 59
KNP: strategie
def strategy_uniform():
r = random.randint(1,3)
if r == 1:
return "R"
elif r == 2:
return "S"
else:
return "P"
def strategy_rock():
return "R"
54 / 59
KNP: vyhodnocení tahu
def evaluate(symbol1, symbol2):
if symbol1 == symbol2:
return 0
if symbol1 == "R" and symbol2 == "S" or \
symbol1 == "S" and symbol2 == "P" or \
symbol1 == "P" and symbol2 == "R":
return 1
return -1
55 / 59
KNP: sehrání západu
def rsp_game(rounds):
points = 0
for i in range(1, rounds+1):
print("Round ", i)
symbol1 = strategy_uniform()
symbol2 = strategy_uniform()
print("Symbols:", symbol1, symbol2)
points += evaluate(symbol1, symbol2)
print("Player 1 points:", points)
56 / 59
KNP: obecnější strategie
def strategy(weightR, weightS, weightP):
r = random.randint(1, weightR + weightS + weightP)
if r <= weightR:
return "R"
elif r <= weightR + weightS:
return "S"
else:
return "P"
57 / 59
KNP: rozšiřující náměty
turnaj různých strategií
strategie pracující s historií
kopírování posledního tahu soupeře
analýza historie soupeře (hraje vždy kámen? → hraj
papír)
rozšíření na více symbolů (Kámen, nůžky, papír, ještěr,
Spock)
58 / 59
Shrnutí
operace s čísly, náhoda
ukázky programů
ukázky algoritmů, efektivita
Příště: Seznamy, řetězce a trocha šifer
59 / 59