Domine
Vrsta domin je podana s seznamom parov (terk), na primer
[(3, 6), (6, 6), (6, 1), (1, 0)] ali [(3, 6), (6, 6), (2, 3)].
Napišite funkcijo domine(xs), ki prejme takšen seznam in pove, ali so domine
pravilno zložene (prva številka naslednje domine je enaka drugi številki predhodne). Za prvi seznam mora vrniti True in za drugega
False.
Rešitev
def domine(domine):
for i in range(len(domine) - 1):
if domine[i][1] != domine[i + 1][0]:
return False
return True
Grde besede
Napišite funkcijo polepsaj(s, sopomenke), ki v nizu s nadomesti vse grde besede z naključno izbrano lepo sopomenko iz podanega seznama terk, npr.:
grde_besede = [
('kreten', ['kljukec']),
('idiot', ['mentalno zaostala oseba', 'omejen clovek']),
...
]
>>> polepsaj('Joj ta Python spet se pocutim kot idiot', grde_besede)
'Joj ta Python spet se pocutim kot mentalno zaostala oseba'
Rešitev
Naloge se lahko lotimo na več načinov. Za vsako besedo lahko preverimo, ali obstaja v seznamu sopomenk. Če jo najdemo, uporabimo njeno naključno sopomenko, sicer pa kar besedo samo.
import random
def polepsaj(s, grde_besede):
r = []
for beseda in s.split():
for grda_beseda, sopomenke in grde_besede:
if beseda == grda_beseda:
r.append(random.choice(sopomenke))
break
else:
r.append(beseda)
return ' '.join(r)
V resnici bi namesto seznama terk raje uporabili slovar, da se izognemo vsakokratnemu iskanju po seznamu terk.
def polepsaj(s, grde_besede):
r = []
grde_besede = dict(grde_besede)
for beseda in s.split():
if beseda in grde_besede:
sopomenke = grde_besede[beseda]
r.append(random.choice(sopomenke))
else:
r.append(beseda)
return ' '.join(r)
Krajše:
def polepsaj(s, grde_besede):
grde_besede = dict(grde_besede)
return ' '.join(random.choice(grde_besede.get(beseda, [beseda])) for beseda in s.split())
Lahko pa naredimo obratno in se sprehodimo po seznamu grdih besed in zamenjamo vse pojavitve posamezne grde besede v nizu. Notranja zanka v naslednji rešitvi je potrebna zato, ker bi sicer isto grdo besedo vedno zamenjali z isto sopomenko.
def polepsaj(s, grde_besede):
for grda_beseda, sopomenke in grde_besede:
while grda_beseda in s:
s = s.replace(grda_beseda, random.choice(sopomenke), 1)
return s
Fibonacci
Napišite funkcijo fibonacci(n), ki vrne seznam prvih n Fibonaccijevih
števil (od $F_0$ do $F_{n-1}$).
>>> fibonacci(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
Rešitev
def fibonacci(n):
a, b = 0, 1
f = []
for i in range(n):
f.append(a)
a, b = b, a + b
return f
Skalarni produkt
Napišite funkcijo skalarni(u, v), ki izračuna skalarni produkt dveh vektorjev u in v. Vektorje predstavimo s seznami ali terkami.
Skalarni produkt vektorjev (1, 2, 3) in (4, 5, 6) je 32.
Rešitev
def skalarni(u, v):
s = 0
for x, y in zip(u,v):
s += x*y
return s
Ali krajše:
def skalarni(u, v):
return sum(x*y for x, y in zip(u,v))
Skalarni produkt 2
Napišite funkcijo skalarni2(u, v), ki vrne niz oz. izraz, ki ga je treba izračunati, če nas
zanima skalarni produkt dveh vektorjev.
Za vektorja (1, 2, 3) in (4, 5, 6) naj vaša funkcija vrne niz "1 * 4 + 2 * 5 + 3 * 6".
Rešitev
Naloge je nadležna, ker se hitro zgodi, da na koncu niza izpišemo en + preveč.
def skalarni2(u, v):
s = ''
for (x, y) in zip(u, v):
if s: s += ' + '
s += str(x) + ' * ' + str(y)
return s
Težave se lahko elegantno znebimo s pomočjo funkcije join.
def skalarni2(u, v):
return ' + '.join(str(x) + ' * ' + str(y) for (x, y) in zip(u, v))
Vsote
Podan imate seznam xs sestavljen iz n nenegativnih števil. Vaša naloga je napisati funkcijo vsota(xs, k), ki vrne največjo vsoto k zaporednih števil v tem seznamu.
>>> vsota([9, 1, 2, 3, 8, 9, 0, 4, 3, 7], k)
24
Tisti, ki se vam to zdi prelahko, lahko vaš program preizkusite na seznamu z milijon elementi. Poiskati morate pa največjo vsoto deset tisoč zaporednih števil.
Rešitev
def vsota(xs, k):
naj = sum(xs[:k])
for i in range(len(xs) - k + 1):
naj = max(naj, sum(xs[i:i+k]))
return naj
Ali krajše:
def vsota(xs, k):
return max(sum(xs[i:i+k]) for i in range(len(xs) - k + 1))
Problem počasnega programa je to, da se veliko dela ponavlja.
V vgnezdeni for zanki nas izračun nove vsote stane k seštevanj.
V izboljšani verziji dobimo novo vsoto le z enim
seštevanjem in enim odštevanjem ne glede na to, koliko števil
seštevamo. To storimo tako, da odštejemo skrajno levo število seznama
in prištejemo desno.
def vsota(xs, k):
vsota = naj = sum(xs[:k])
for zacetek, konec in zip(xs, xs[k:]):
vsota += konec - zacetek
naj = max(naj, vsota)
return naj