Naloge - algoritmične (težje)
Štetje cifer
Napiši funkcijo count(n), ki sešteje vse cifre v številu n. Postopek
ponavljaj dokler ima rezultat več kot eno cifro.
>>> count(12345) # 1 + 2 + 3 + 4 + 5 = 15, 1 + 5 = 6
6
>>> count(999999999) # 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 + 9 = 81, 8 + 1 = 9
9
>>> count(213413512)
4
>>> count(2147483647)
1
Rešitev
Rešitev z while zanko.
def count(n):
while n > 9:
sum = 0
for i in str(n):
sum += int(i)
n = sum
return n
Malo bolj napredna rešitev z while zanko.
def count(n):
while n > 9:
n = sum(map(int, str(n)))
return n
Poštnina
Po pošti bi radi poslal n steklenih kock dimenzij 1 x 1 x 1 tako, da
jih zapakiramo v škatlo velikosti a x b x c. Cena poštnine je
a + b + c. Ker so kocke steklene jih moramo zapakirati tako, da v
škatli ni praznih prostorov, saj bi se sicer kocke lahko premikale in
razbile. Napiši funkcijo postnina(n), ki vrne ceno najcenejše
poštnine.
>>> postnina(1) # 1 x 1 x 1
3
>>> postnina(6) # 2 x 3 x 1
6
>>> postnina(7) # 7 x 1 x 1
9
>>> postnina(200) # 5 x 5 x 8
18
Rešitev
Najbolj preprosta rešitev pregleda vse možne a x b x c (1 <= a, b, c <= n).
def postnina(n):
cene = []
for a in range(1, n + 1):
for b in range(1, n + 1):
for c in range(1, n + 1):
if a * b * c == n:
cene.append(a + b + c)
return min(cene)
V resnici je dovolj, če napišemo zanki le za a in b. Izraz x // y vrne celi del pri deljenju x z y.
def postnina(n):
cene = []
for a in range(1, n + 1):
for b in range(1, n + 1):
c = n // (a * b)
if a * b * c == n:
cene.append(a + b + c)
return min(cene)
Program lahko pohitrimo tako da upoštevamo, da so a, b in c delitelji števila n.
def postnina(n):
delitelji = []
for i in range(1, n + 1):
if n % i == 0:
delitelji.append(i)
cene = []
for a in delitelji:
for b in delitelji:
c = n // (a * b)
if a * b * c == n:
cene.append(a + b + c)
return min(cene)
01
Seznam xs lahko vsebuje le cifri 0 in 1. Spremenimo ga lahko tako,
da katerikoli element 0 zamenjamo z 1 in obratno. Na koncu želimo,
da so vsi elementi 0 na levi strani seznama, vsi elementi 1 pa na
desni. Seznam [0, 0, 1, 0, 1] lahko z eno spremembo pretvorimo v
seznam [0, 0, 1, 1, 1], seznam [0, 1, 0, 1, 0] pa z dvema
spremembama postane [0, 1, 1, 1, 1] ali [0, 0, 0, 0, 0]. Napiši
funkcijo nic_ena(xs), ki vrne najmanjše število potrebnih sprememb.
>>> nic_ena([0, 0, 1, 0, 1])
1
>>> nic_ena([0, 0, 1, 1, 1])
0
>>> nic_ena([0, 1, 0, 1, 0])
2
>>> nic_ena([1, 1, 1, 1, 0, 0, 0])
3
>>> nic_ena([1, 0, 0, 0, 1, 1, 1, 0])
2
>>> nic_ena([0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0])
9
Rešitev
V končnem seznamu bo na nekem mestu meja med ničlami in enicami. Število potrebnih sprememb lahko za določeno mejo hitro izračunamo tako, da seštejemo število enic levo in število ničel desno od meje. Postopek ponovimo za vsako mejo.
def nic_ena(xs):
ones_left = 0
zeros_right = xs.count(0)
count = [zeros_right]
for x in xs:
if x == 0:
zeros_right -= 1
else:
ones_left += 1
count.append(ones_left + zeros_right)
return min(count)
Mask
Napiši funkcijo mask(n), ki vrne vseh $2^n$ različnih seznamov ničel in
enic dolžine n.
>>> mask(0)
[[]]
>>> mask(1)
[[0], [1]]
>>> mask(2)
[[0, 0], [0, 1], [1, 0], [1, 1]]
>>> mask(3)
[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]
>>> len(mask(10))
1024
Rešitev
Iterativna rešitev.
def mask(n):
s = [[]]
for i in range(n):
t = []
for x in s:
t.append(x + [0])
t.append(x + [1])
s = t
return s
Rekurzivna rešitev.
def mask(n):
if n == 0:
return [[]]
xss = []
for xs in mask(n - 1):
xss.append(xs + [0])
xss.append(xs + [1])
return xss
Potenčna množica
Napiši funkcijo potencna(xs), ki vrne seznam vseh podseznamov seznama
xs. Uporabi funkcijo mask iz prejšnje naloge.
>>> potencna([])
[[]]
>>> potencna([1, 5])
[[], [1], [5], [1, 5]]
>>> potencna([1, 5, 7])
[[], [1], [5], [1, 5], [7], [1, 7], [5, 7], [1, 5, 7]]
>>> len(potencna([0, 1, 2, 3, 4, 5, 6, 7, 8, 9]))
1024
Rešitev
Uporabimo funkcijo mask, ki nam pove, kateri element vključimo in katerega ne.
def potencna(xs):
rezultat = []
for mask_bits in mask(len(xs)):
xs_masked = []
for mask_bit, x in zip(mask_bits, xs):
if mask_bit:
xs_masked.append(x)
rezultat.append(xs_masked)
return rezultat
Lahko pa dopolnimo rešitev iz prejšnje naloge.
def potencna(xs):
if not xs:
return [[]]
yss = []
for ys in potencna(xs[1:]):
yss.append(ys)
yss.append(xs[:1] + ys)
return yss
Knjige
Franc in Anton izdelujeta seminarsko nalogo, za katero je treba prebrati
veliko knjig. Odločita se, da si bosta knjige razdelila pošteno. Napiši funkcijo knjige(xs), ki sprejme seznam knjig in
vrne True, če si Franc in Anton knjige lahko razdelita tako, da bosta
oba prebrala enako število strani. Seznam xs vsebuje število strani
posamezne knjige.
>>> knjige([10, 20, 30]) # Anton dobi prvo in drugo knjigo, Franc pa tretjo.
True
>>> knjige([10, 20, 30, 40]) # Anton dobi drugo in tretjo knjigo, Franc pa prvo in zadnjo.
True
>>> knjige([10, 20, 30, 40, 50])
False
>>> knjige([23, 51, 51, 153, 25, 51, 59, 39, 35, 91])
False
>>> knjige([23, 51, 51, 153, 20, 25, 51, 59, 39, 35, 91])
True
Rešitev
def knjige(xs):
cilj = sum(xs) / 2
for ys in potencna(xs):
if sum(ys) == cilj:
return True
return False