rogramy a algoritmy pracující s čís
IBlil Úvod do programovaní skrze Python 2012
O přednášce
• některé detaily o práci s čísly v Pythonu
• ukázky jednoduchých algoritmů
• ukázky programů, ilustrace základních konstru
íselné typy
• int - celá čísla
• float
• čísla s plovoucí desetinnou čárkou
• reprezentace: báze, exponent
• nepřesnosti, zaokrouhlování
Číselné typy - poznámky
• dělení: rozdíl 3/2 a 3/2.0
• „nafukování" typu int: rozdíl C (a většina dalších jazyků)
• přetypování: int(x), float(x)
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
Ciferný součet
• vstup: číslo x
• výstup: ciferný součet čísla x
• 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
Ciferný součet - ukázka nevhodného programu
if n '/. 10 == 0:
f = 0 + f
elif n '/. 10 == 1:
f = 1 + f
elif n 1 10 == 2:
f = 2 + f
elif n '/, 10 == 3:
f = 3 + f
elif n '/. 10 == 4:
f = 4 + f
Ciferný součet - řešení
def ciferny_soucet(n): součet = 0 while n > 0:
součet += n °/0 10
n = n / 10 return součet
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
Collatzova posloupnost: výpis
def collatz_vypis(n): while n != 1: print n, if n '/. 2 == 0: n = n / 2 else:
n = 3*n + 1
print 1
Collatzova posloupnost: příklady graficky
Collatzova posloupnost: počet kroků
def collatz_kroky(n): kroku = 1 while n != 1: if n y. 2:
n = 3*n + 1 else:
n = n / 2 kroku += 1 return kroku
for i in ranged, 100):
print i, collatz_kroky(i)
Collatzova hypotéza
• platí, že pro každé počáteční číslo n, narazí posloupnost na číslo 1?
• experimentálně ověřeno pro velká n (~ 1018)
• důkaz není znám
Collatzova posloupnost: experimenty
• upravte uvedenou funkci, aby nepočítala počet kroků, ale maximální číslo, které v průběhu výpočtu posloupnosti „potkáme"
• vykreslete graf těchto maximálních čísel
Příklad: Hádanka hlavy a nohy
Farmář chová prasata a slepice. Celkem je na dvoře 20 hlav a 56 noh. Kolik má slepic a kolik prasat?
• jak vyřešit pro konkrétní zadání?
• jak vyřešit pro obecné zadání (H hlav a N noh)?
• co když farmář chová ještě osminohé pavouky?
Hlavy, nohy: řešení
dva možné přístupy:
O „inteligentně": řešení systému lineárních rovnic O „hrubou silou":
• „vyzkoušej všechny možnosti"
• cyklus přes všechny možné počty prasat
Hlavy, nohy: program
def hledej_reseni(hlavy, nohy): for prasata in range(0, hlavy+1): slepice = hlavy - prasata if prasata * 4 + slepice * 2 == nohy print "prasata =", prasata,\ "slepice =", slepice
Jak bych musel program změnit, kdybych řešil úlohu pavouky?
Největší společný dělitel
• vstup: přirozená čísla a, b
• výstup: největší společný dělitel
• příklad: 180, 504
Jak na to?
aivní algoritmus I
• projít všechny čísla od 1 do min(a,
• pro každé vyzkoušet, zda dělí a i b
• vzít nej větší
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
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
Operace modulo
• modulo = zbytek po dělení
• příklady:
• 13 mod 5 = 3
• 28 mod 4 = 0
• 14 mod 3 = 2 a 18 mod 1 = 11
• 29 mod 13 = 11
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
Euklidův algoritmus: pseudokód
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
Euklidův algoritmus: pseudokód
modulo varianta, rekurzivně
def nsd(a,b): if b == 0:
return a else:
return nsd(b, a °/0 b)
Příklady
• 160, 75
• 57, 33
< □ ►   4 (5? ► <
1 -O^O
Příklad I - řešení
krok a b
1 160 75
2 75 10
3 10 5
4 5 0
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)
Euklidův algoritmus - vizualizace
http://en.wikipedia.org/wiki/Euclidean
Výpočet odmocniny
• vstup: číslo x
• výstup: přibližná hodnota yGč Jak na to?
1 -00.0
Výpočet odmocniny
• vstup: číslo x
• výstup: přibližná hodnota yGč Jak na to?
Mnoho metod, ukázka jedné z nich (rozhodně ne nejvíce efektivní)
Výpočet odmocniny: binární půlení
spodní odhad horní odhad
1        1        1        1 1			
0 1	0.5 i	1 1.5	2 1
1 0 1	1 0.5 i	1 1.5 1     1 1	1 2 i
1 0 1	1 0.5 i	1     1 1 1 1.5 I III	1 2 i
1 0 1	1 0.5 i	I III 1 1.5 I        1 1	1 2 i
1 0	1 0.5	1        1 1 1 1.5	1 2
Výpočet odmocniny: binární půlení
def odmocnina(x, přesnost = 0.01): horni_odhad = x spodni_odhad = 0
stred = (horni_odhad + spodni_odhad) / 2.0 while abs(stred**2 - x) > přesnost: if stred**2 > x:
horni_odhad = stred if stred**2 < x:
spodni_odhad = stred stred = (horni_odhad + spodni_odhad) / 2.0 return stred
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 - knihovna random
0 random.random() - float od 0 do 1
• random.randint (a,b) - celé číslo mezi a, b
• mnoho dalších funkcí
Náhodná čísla: průměr vzorku
Vygenerujeme soubor náhodných čísel a vypočítáme průměrnou hodnotu:
def prumer_nahodnych(kolik, maximum = 100): součet =0.0 for i in range(kolik):
součet += random.randint(0, maximum) return součet / kolik
Jakou očekáváme hodnotu na výstupu? Jak velký bude rozptyl hodnot? (Názorná ukázka centrální limitní věty)
Výpočet 7T
• vr = 3.14159265359.
• Ale jak se na to přišli
• Jak vypočítat n?
Výpočet n
Příklady naivních metod: • Gregoryho-Leibnizova řada (součet je n):
(-1)*     4    4    4    4 4
2/c + l     1    3    5    7 9
ír=0
• Monte Carlo metoda - házení šipek do čtvrtdisku
Výpočet % - Gregory-Leibniz
def gregory_leibniz(n): součet =0.0 znaménko = 1.0 for k in range(l,n+l):
součet += znaménko/(2*k-l)
znaménko *= -1 return 4*soucet
Výpočet % - Monte Carlo
• obsah čtvrtdisku: n/A
• obsah čtverce: 1
Výpočet % - Monte Carlo
def monte_carlo_kruh(pocet_pokusu): zasahy = 0
for k in range(pocet_pokusu):
x = random.random()
y = random.random()
if x*x + y*y < 1: zasahy += 1 return 4.0 * zasahy / pocet_pokusu
Kámen, nůžky, papír
KNP: strategie
def strategie_rovnomerna(): r = random.randint(l,3) if r == 1:
return "K" elif r == 2:
return "N" else:
return "P"
def strategie_kamen(): return "K"
KNP: vyhodnocení tahu
def vyhodnoť(tahl, tah2): if tahl == tah2: return 0
if tahl == "K" and tah2 == "N" or \ tahl == "N" and tah2 == "P" or \ tahl == "P" and tah2 == "K": return 1
return -1
KNP: sehrání západu
def knp_hra(pocet_kol): body = 0
for i in ranged, pocet_kol+l) : print "Kolo ", i tahl = strategie_rovnomerna() tah2 = strategie_rovnomerna() print "Tahy hracu:", tahl, tah2 body += vyhodnot(tahl, tah2) print "Body hrace 1:", body
KNP: obecnější strategie
def strategie(vahaK, vahaN, vahaP):
r = random.randint(1, vahaK + vahaN + vahaP) if r <= vahaK:
return "K" elif r <= vahaK + vahaN:
return "N" else:
return "P"
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)
alší příklady
• výpočet nejmenšího společného násobku
• lze zapsat n jako součet druhých mocnin?
• další metody aproximace n
• aproximativní výpočet kořenů polynomu x3 — 3x2 + 1
• náhodnostní simulace zápasu ve volejbale, tenisu, ...
• operace s čísly detailněji (typy, funkce, náhoda, ...)
• ukázky algoritmů
• ukázky programů