Programy a algoritmy pracující s čísly
IBlll Základy programovaní
Radek Pelánek
2018
Dnešní prednáška
• práce s čísly v Pythonu
• ukázky programů, ilustrace použití základních konstrukcí
• upozornění na záludnosti, ladění
• ukázky jednoduchých algoritmů, ilustrace rozdílu v efektivitě
v
Číselné typy
• int - „integer", celá čísla
• float
• „floating-point number"
• čísla s plovoucí desetinnou čárkou
• reprezentace: mantisa x bázeexponent
• nepresnosti, zaokrouhlování
• ( complex - komplexní čísla )
4/70
Přesná matematika:
((l + i)-l)-x=l
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
Nepřesné výpočty - praktický případ
záměr
chyba
1
2 3
1
step =0.1
while value <= bound: # draw line ... value += step
Číselné typy - poznámky
• explicitní pretypovaní: 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čeni )
v Python2.7 děleni: rozdíl 3/2 a 3/2.0
v Python3 dělení intuitivní
7/70
Kvízové otázky
Co udělá program? n = 1
while n > 0:
print(n)
n = n / 10 print("done")
Co když použijeme „n = n * 10"? A co „n = n * 10.0"?
Co udělají analogické programy v jiných programovacích jazycích?
Pokročilejší operace s čísly
Některé operace v knihovně math:
o 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
9/70
»> round(2.5) 2
»> round(3.5) 4
»> round(2.675, 2) 2.67
https://docs.python.org/3/library/functions.html#round
The behavior of round() for floats can be surprising: for example, round(2.675, 2) gives 2.67 instead of the expected 2.68. This is not a bug: it's a result of the fact that most decimal fractions can't be represented exactly as a float.
10/70
Ciferný součet
• vstup: číslo x
• výstup: ciferný součet čísla
• příklady:
• 8^8
• 15 6
• 297 18
• 11211 6
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
12/70
Ciferný součet - nevhodná pasáž
if n 7. 10 ==	= 0	• •
f = 0 +	f	
elif n 7. 10	——	1:
f = 1 +	f	
elif n 7. 10	——	2:
f = 2 +	f	
elif n 7. 10	——	3:
f = 3 +	f	
elif n 7. 10	——	4:
f = 4 +	f	
13/70
ferný součet - řešení
def digit_sum(n):
result = 0
while n > 0:
result += n °/0 10 n = n // 10
return result
14/70
Ciferný součet: pokročilé řešení
Pro zajímavost:
def digit_sum(n):
return sum(map(int, str(n)))
<  □  ►   4 ^ >■   <        ►   <  -Ž ►
15/70
Return vs. print
připomenutí:
• print = výpis
• return = návratová hodnota, se kterou můžeme dále pracovat
výpis všech čísel menších jak 1000 s ciferným součtem 13
• blízký vztah k matematickým funkcím
příklad:
16/70
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
the: couatz COllJEaUSE stats w if you
PKX Al\JTOER, AMD It VTS&EN DiVlOE IT Gtf TWO AND IF \T'S ODD Ml^TlRY fT W THREE AND ADD ONE, ANC? TCO REPEAT THIS PF5XED0RE U^Q ENOUGH, EVEOTJAUV YOUR FftiEMDS W3U. STOP OUWG TD SEE IF YOU VA*JT To HAMG OUT
htts://xkcd.com/710/
18/70
Collatzova posloupnost: výpis
def collatz_sequence(n): while n != 1:
print(n3 end=M, 11) if n % 2 == 0:
n = n // 2 else:
n = 3*n + 1
print(1)
19/70
Collatzova posloupnost: příklady graficky
začínající číslem 7 60
začínající číslem 27 10 000
10   12   14 16
80     100 120
20/70
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 °/0 2 == 0: n = n // 2 else:
n = 3*n + 1 sequence.append(1) return sequence pylab.plot(collatz(27)) pylab.show()
<<□► < if? ► •<.=.► •<-=.►    -e   -o q, o
21/70
Collatzova posloupnost
nosti
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(l5 count+1):
print(i, collatz_length(i))
•<□►    4 ^ >■    4  S  ►    <  .5 ►
22/70
Collatzova posloupnost: délka posloupnosti
o
10
15 20
25
< [3 ►    <  -=.  ►    <  -=. ►
23/70
Collatzova posloupnost: délka posloupnosti
300
250 -
200 -
150 -
100
1 000 2 000 3 000 4 000 5 000 6 000 7 000 8 000
< S ►   < -=. ►   < -š ►
24/70
Collatzova hypotéza
• Hypotéza: Pro každé počáteční číslo n, pošlou narazí na číslo 1.
• experimentálně ověřeno pro velká n 1018)
• důkaz není znám
4 □ ►   < [S ►
Největší společný dělitel
• vstup: přirozená čísla a, b
• výstup: největší společný dělitel a, b
• príklad: 180, 504
Jak na to?
26/70
Naivní algoritmus I
o 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ší
27/70
• „š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
28/70
Euklidův algoritmus: základ
základní myšlenka: pokud a > b, pak:
NSD(a, b) = NSD(a -
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
Neefektivita
• uvedená verze je neefektivní
• může být pomalejší než naivní algoritmus I
• kdy?
30/70
Euklidův algoritmus: vylepšení
vylepšená základní myšlenka: pokud a > b, pak:
NSD(a, b) = NSD(a mod b, b)
krok
1
2
3
4
a
504 180 144 36
b 180 144 36
0
< ^ >■   < -š ►   < -=. ►
31/70
Euklidův algoritmus: program
bez rekurze
def gcd_euclid(a, b): if a == 0:
return b while b != 0: if a > b:
a = a % b else:
b = b % a
return a
Euklidův algoritmus: program
modulo varianta, rekurzivně
def gcd(a, b): if b == 0:
return a else:
return gcd(b, a °/0 b)
http://en.wikipedia.org/wiki/Euclidean_algorithm
34/70
Efektivita algoritmu
• 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)
36/70
Kahoot program A
i = 1
while i < 3:
print("x", end=
i = i + 1 print(i)
_ it ii
)
37/70
Kahoot program
def increase(x) return x +
a = 5
increase(a) print(a)
Výpočet odmocniny
• vstup: číslo x
• výstup: přibližná hodnota y^č Jak na to?
39/70
• vstup: číslo x
• výstup: přibližná hodnota y^č Jak na to?
Mnoho metod, ukázka jedné z nich (rozhodně ne nejvíce efektivní)
4 ^ >■   4 ± k   <  -Ž ►
39/70
Výpočet odmocniny: binární půlen
spodní odhad st
0
0
0
o
o
0.5
0.5
0.5
0.5
0.5
ed    horní odhad
1.5
1.5
1.5
f-H
1.5
m
1.5
40/70
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 print(lower, upper, sep=M\tM) if middle**2 > x:
upper = middle if middle**2 < x:
lower = middle middle = (upper + lower) / 2 return middle
4 □ ►   < [S ►
\
Výpočet odmocniny - chyba
Drobný problém: Program není korektn Kde je chyba?
Výpočet odmocniny - poznámky
• Funguje korektně jen pro čísla > 1
• Co program udělá pro čísla < 1?
• Proč?
• Jak to opravit?
< [f? ►  < -E ►  < -ž ►     -š     -O Q, O
43/70
\
Vsuvka: Obecný kontext
problém algoritmus program ladění
44/70
Poznámka o ladění
9 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)
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)
46/70
o ladící výpisy
o 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, ...
47/70
Ladění a funkce
• dobrá dekompozice na funkce usnadňuje ladění
• „hledání chyby v celém programu" vs. „hledání chyby v dílčí funkci"
• „unit testing", „test driven development"
48/70
Ctení chybových hláse
Traceback (most recent call last):
File "sorting.py", line 63, in <module>
test_sorts() File "sorting.py", line 59, in test_sorts sort(a)
File "sorting.py", line 52, in insert_sort a[j] = curent NameError: name }curent} is not defined
9 kde je problém? (identifikace funkce, číslo řádku) • co je za problém (typ chyby)
49/70
Základní typy chyb
• SyntaxError
• invalid syntax: zapomenutá dvojtečka či závorka, záměna = a ==, .. .
• EOL while scanning string literal: zapomenutá uvozovka
• NameError - špatné jméno proměnné (překlep v názvu, chybějící inicializace)
• IndentationError - špatné odsazení
• TypeError - nepovolená operace (sčítání čísla a řetězce, přiřazení do řetězce, ...)
• IndexError - chyba při indexování řetězce, seznamu a podobně („out of range")
Caste chyby
projeví se „rychle" (program spadne hned):
• zapomenutá dvojtečka, závorka, uvozovka
• překlepy
• použití = tam, kde mělo být ==
• špatný počet argumentů při volání funkce
• zapomenuté len v "for i in range(alist)"
4 ^ >■    4  ±  k    <  -Š ►
51/70
v
Caste chyby
nemusí se projevit rychle / vždy: • použití == tam, kde mělo být =
• "True" místo True
• záměna print a return
• dělení nulou
• chybné indexování (řetězce, seznamy)
52/70
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?
Součet druhých mocnin: řešení I
def sum_of_squares_test(n): for i in range(n+l):
for j in range(n+l):
if i**2 + j**2 == n:
print(n, "=", i**2, "+", j**
a Program je zbytečně neefektivní. Proč?
• Výpis čísel, která lze zapsat jako součet čtverců
Testování druhé mocniny: nevhodný i
def is_square(n):
square_root = int(n**0.5) if square_root**2 == n:
return True else:
return False
< □ ► <
Součet druhých mocnin: řešení
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=M, 11)
56/70
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/
57/70
Náhodná čísla
• přesněji: pseudo-náhodná čísla
• opravdová náhodná čísla: https://www.random.org/
• bohaté využití v programování: výpočty, simulace, hry,
• Python
• import random
• random.random() - float od O do 1
• random.randint (a, b) - celé číslo mezi a, b
• mnoho dalších funkcí
58/70
Náhodná čŕsla: xkcd
iní get R<*n dom N vrti ber ()
í
i
return 4,' //chosen by fair dice, roll // guaranteed to be rano/om.
THIS m RANDOM NUMBER
GocmiDR voľ uttmcw/m
TO BE miř> BUTTHEOUlPlřTío BIASED CERffllM MUrIBEľRS.
/  (JOl, ř?#rf$E THOSE I   NUM6ER5 ARE JUST /rm/NStCALLYBETTER/
htts://xkcd.com/221/ htts://xkcd.com/1277/
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 hodnot? (Názorná ukázka centrální limitní věty)
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
Simulace volebního průzkumu
def survey(size, prefl, pref2, pref3): count1 = 0 count2 = 0 count3 = 0
for i in range(size):
r = random.randint(1, 100) if r <= prefl: count1 += 1 elif r <= prefl + pref2: count2 += 1 elif r <= prefl + pref2 + pref3: count3 print ("Party 1:11, 100 * count 1 / size) print("Party 2:", 100 * count2 / size) print("Party 3:", 100 * count3 / size)
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ů
men, nůžky, papír
Zdroj: Wikipedia
64/70
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"
65/70
KNP: vyhodnocení tahu
def evaluate(symbol1, symbol2): if symboll == symbol2:
return 0 if symboll == MRM and symbol2 symboll == MSM and symbol2 symboll == MPM and symbol2 return 1 return -1
KNP: sehrání západu
def rsp_game(rounds): points = 0
for i in ranged, rounds+1) : print ("Round ", i) symbol1 = strategy_uniform() symbol2 = strategy_uniform() print("Symbols:", symboll, symbol2) points += evaluate(symboll, symbol2) print("Player 1 points:", points)
4 ^ >■    4  ±  k    4  S ►
67/70
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"
68/70
KNP: rozšiřující náměty
• turnaj různých strategií
• strategie pracující s historií
9 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)
69/70
• operace s čísly, náhoda
• ukázky programů
• ukázky algoritmů, efektivita
Příště: Seznamy, řetězce a trocha šifer
70/70