IB113 Radek Pelánek
2021
Rozcvička 1
0 112 1 3 3 4 3 4
Ukázka nevhodného programu
def čtverec(n):
for i in ranged, n): print("*" * i) if i == n-1:
P = 1
while n+1 > p:
print("*" * n) n = n - 1
4/67
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ě
• int - „integer", celá čísla
• float
• „floating-point number"
• čísla s plovoucí desetinnou čárkou
• reprezentace: mantisa x bázeexponent
• nepřesnosti, zaokrouhlování
• ( complex - komplexní čísla )
< □ ►   4 S1 ►   < -ž ►   < -š ►
6/67
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
7/67
Nepřesné výpočty - praktický případ
záměr chyba
12      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:
9 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í
9/67
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:
• použití knihovny: import math
• zaokrouhlování: round, math, ceil, math.flc
• absolutní hodnota: abs
• math, exp, math, log, math.sqrt
o goniometrické funkce: math, sin, math, cos, .
• konstanty: math.pi, math.e
< □ ► * gi ► 4
»> 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.
12/67
Ciferný součet
• vstup: číslo x
• výstup: ciferný součet čísla 9 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
14/67
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	
15/67
ferný součet - řešení
def digit_sum(n): result = 0 while n > 0:
result += n n = n // 10 return result
10
16/67
Ciferný součet: jednořádkové řešení
Cistě pro zajímavost:
digit_sum = lambda n: sum(map(int, str(n)))
(skrze řetězec vyrobíme seznam jednotlivých cifer, sečteme vestavěnou funkcí sum, funkci definujeme lambda abstrakcí)
17/67
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:
18/67
Volání funkce, parametry funkce
• definice funkce
• obecný zápis, jak se funkce počítá
• nezpůsobí žádný konkrétní výpočet
• volání funkce
• výpočet funkce pro konkrétní zadané hodnoty parametrů
• hodnoty parametrů funkce
• zadáváme při volání, nikoliv při definici
• (až na defaultní parametry, ale ty můžete zatím ignorovat)
•<□►   4 ^ t   <  -ž  ►   <  -š ►
19/67
ON A SCALE OF lit 10, HOW LIKELY 15 17 THAT THIS QUESTS IS USING BINARY?
htts://xkcd.com/953/
20/67
Binární soustava: počítání na prstech
https://www.khanacademy.org/math/vi-hart/v/ binary-hand-dance
Príklad: převod na binární zápis
Problém: převodník z desítkové na binární soustavu vstup: číslo v desítkové soustavě výstup: číslo v binární soustavě
• Jak převedeme „22" na binární zápis?
• Jak převedeme obecné číslo na binární zápis?
22/67
def to_binary(n): output = 1111 while n > 0:
if n °/0 2 == 0:
output = "0" + output else:
output = "1" + output n = n // 2 return output
print(to_binary(22))
Převod na binární zápis - průběh výpočtu
n =	22	output =	
n =	11	output =	0
n =	5	output =	10
n =	2	output =	110
n =	1	output =	0110
n =	0	output =	10110
24/67
Tajná posloupnost
0112122312232334122323342 3 3 4 3 4 ...
25/67
Tajná posloupnost
0112122312232334122323342 3 3 4 3 4 ...
Počet jedniček v binárním zápisu. Jak vypsat programem?
25/67
Tajná posloupnost
def count_ones(n): count = 0 while n > 0:
if n % 2 == 1: count += 1 n = n // 2 return count
def sequence(n):
for i in range(n):
print (count_ones(i), end=M 11)
26/67
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 o^oeoím stats w if you
PKX Al\JTOER, AMD It ÍTS&EN DiVlOE IT Gtf TWO AND IF \T'S ODD MULT! RY íT D/ THREE AND ADD ONE, AND VCU REPEAT THIS PROCEDURE UDNG ENOUGH, EVEOTJAUV YCOR FftlEMDS W!il STOP CAUJMG ID SEE IF YOU WAMT To H AMG OUT!
htts://xkcd.com/710/
< □ MS M I M I ►       1      O Q, O
28/67
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)
29/67
O       2     4     6     8    10    12    14   16 0        20     40     60     80     100 120
30/67
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()
31/67
def collatz_length(n): length = 1 while n != 1:
if n °/0 2 == 0: n = n // 2 else:
n = 3*n + 1 length += 1 return length
def collatz_table(count):
for i in range(l, count+1):
print(i, collatz_length(i))
32/67
Collatzova posloupnost: délka posloupnosti
o
10
15 20
25
33/67
34/67
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
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?
36/67
Naivní algoritmus I
9 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ší
37/67
• „školní" algoritmus
• najít všechny dělitele čísel a, b
9 projít dělitele, vybrat společné, vynásobit
• příklad:
• 180 = 22-32-5
• 504 = 23 • 32 • 7
• NSD = 22 • 32 = 36
38/67
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?
40/67
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
š    *0 <\ O
41/67
bez rekurze
def gcd_euclid(a, b): if a == 0:
return b while a != 0 and b if a > b:
a = a °/0 b else:
b = b °/o a return max(a, b)
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
44/67
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)
Výpočet odmocniny
• vstup: číslo x
• výstup: přibližná hodnota y^č Jak na to?
46/67
• 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í)
46/67
Výpočet odmocniny: binární půlen
spodní odhad st
i
0
0
0
o
o
0.5
0.5
0.5
0.5
0.5
ed    horní odhad
1.5
1.5
1.5
H4
1.5
m
1.5
47/67
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
\
Výpočet odmocniny - chyba
Drobný problém: Program není korektní. Kde je chyba?
•<□►   4 ^ >■   <  -ž  ►   < -E ►
49/67
Výpočet odmocniny - poznámky
• Funguje korektně jen pro čísla > 1
• Co program udělá pro čísla < 1?
• Proč?
• Jak to opravit?
50/67
\
Vsuvka: Obecný kontext
problém algoritmus program ladění
< □ ►   4^ >   4 S ►   < -E ►
51/67
Poznámka o ladění
o laděním se nebudeme (na prednáškach) 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)
53/67
9 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, ...
54/67
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"
55/67
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
• kde je problém? (identifikace funkce, číslo řádku)
• co je za problém (typ chyby)
56/67
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
• preklepy
• 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)"
58/67
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)
59/67
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**2)
• Program je zbytečně neefektivní. Proč?
• Výpis čísel, která lze zapsat jako součet čtverců
61/67
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)
63/67
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/
64/67
Kontrolní otázky
• Jaký je rozdíl mezi číselnými typy int a float?
• Jak zapisujeme operace „celočíselné dělení" a „dělení se zbytkem"?
• Co dělají funkce round, math.floor, math.ceil?
• Jaká je základní myšlenka algoritmu pro výpočet ciferného součtu?
• Jaká je základní myšlenka algoritmu pro výpočet odmocniny?
• Jaká je základní myšlenka algoritmu pro převod na binární zápis?
• Jaký je význam příkazu return? Jaký je rozdíl mezi tím, když na konci funkce zavoláme return a print?
65/67
Doporučené procvičování
https://www.umimeprogramovat.cz/porozuměni • Výpočty s čísly
https:
//www.umimeprogramovat.cz/programovani-v-pythonu
• Proměnné a číselné výrazy
• Logické výrazy
66/67
Shrnutí
• operace s čísly, náhoda
• ukázky programů
• ukázky algoritmů, efektivita
Příště: náhodná čísla a simulace, řetězce a šifry