Transakcije

V začetku je imela Ana štiri zlatnike, Berta 8 in Cilka 10, torej [('Ana', 4), ('Berta', 8), ('Cilka', 10)].
Nato je dala Cilka Ani 3 zlatnike; potem je dala Cilka Ani še 2; na koncu je dala Ana Berti 2, kar zapišemo [('Cilka', 'Ana', 3), ('Cilka', 'Ana', 2), ('Ana', 'Berta', 2)].

Kdo ima na koncu največ? Napišite funkcijo transakcije(zacetek, dajatve), ki dobi zgornja seznama in vrne ime najbogatejše osebe po koncu transakcij. Če je na koncu več enako bogatih najbogatejših oseb, naj vrne poljubno izmed njih.

Najboljše bo, da se naloge lotite takole:

  1. pretvorite seznam v slovar - v gornjem primeru, recimo v {'Ana': 4, 'Berta': 8, 'Cilka': 10} - in ga izpišite, da boste videli, da ste naredili prav.
  2. napišite del funkcije, ki "izvede" transakcije in izpišite rezultat, da boste videli, da ste naredili prav. V gornjem primeru se mora izpisati {'Ana': 7, 'Berta': 10, 'Cilka': 5}
  3. v slovarju poiščete najbogatejšo osebo - torej ključ, pri katerem je vrednost največja.

Primer klica:


>>> transakcije([('Ana', 4), ('Berta', 8), ('Cilka', 10)],
                [('Cilka', 'Ana', 3), ('Cilka', 'Ana', 2), ('Ana', 'Berta', 2)])
Berta


def transakcije(zacetek, dajatve):
    stanje = {}
    for ime, vrednost in zaceket:
        stanje[ime] = vrednost
    for kdo, komu, koliko in dajatve:
        stanje[kdo] -= koliko
        stanje[komu] += koliko
    najvec = None # lahko bi napisali -1, a morda so vsi v dolgovih...
    for kdo, koliko in stanje.items():
        if najvec is None or koliko > najvec:
            najvec, kdo_naj = koliko, kdo
    return kdo_naj

Natakar

Ko je prišel natakar, so naročile:

  • Ana je naročila torto,
  • Berta je naročila krof,
  • Cilka je naročila kavo,
  • Ana je naročila še kavo,
  • Berta je rekla, da ne bo krofa,
  • Cilka je rekla, da ne bo torte (no, saj je niti ni naročila; to natakar mirno ignorira),
  • Berta je naročila torto. Vse skupaj zapišemo takole:

[("Ana", "torta"), ("Berta", "krof"), ("Cilka", "kava"), ("Ana", "kava"), ("Berta", "-krof"), ("Cilka", "-torta"), ("Berta", "torta")].

Seznam torej vsebuje pare nizov (oseba, jed), pri čemer se jed včasih začne z "-", kar pomeni, da stranka prekliče naročilo te jedi oz. pijače. Napiši funkcijo narocila(s), ki prejme takšen seznam in vrne slovar, katerega ključi so imena strank, vrednost pri vsakem ključu pa je seznam vsega, kar mora stranka na koncu dobiti.

Primer:


>>> narocila([('Ana', 'torta'), ('Berta', 'krof'), ('Cilka', 'kava'), ('Ana', 'kava'), ('Berta', '-krof'), ('Cilka', '-torta'), ('Berta', 'torta')])
{'Cilka': ['kava'], 'Berta': ['torta'], 'Ana': ['torta', 'kava']}
>>> narocila([('Ana', 'torta'), ('Ana', '-torta')])
{'Ana': []}
>>> narocila([('Ana', '-torta')])
{'Ana': []} # Tu sme funkcija vrniti tudi prazen slovar, {}


def narocila(s):
    po_strankah = {}
    for ime, jed in s:
        if jed[0] == "-":
            if ime in po_strankah and jed[1:] in po_strankah[ime]:
                po_strankah[ime].remove(jed[1:])
        else:
            if ime not in po_strankah:
                po_strankah[ime] = []
            po_strankah[ime].append(jed)
    return po_strankah

Najpogostejše

Napišite funkcijo najpogostejse(s), ki vrne besedo in znak, ki se v podanem nizu največkrat pojavita. V nizu 'in to in ono in to smo mi' se največkrat pojavita beseda 'in' in znak ' ' (presledek).

Primer:

>>> najpogostejse('aa bb aa')
('aa', 'a')
>>> najpogostejse('in to in ono in to smo mi')
('in', ' ')

Prvo nalogo bomo reševali po korakih, da dobite občutek, kako se pristopi k taki nalogi in kako se dela s slovarji. Zraven boste dobili še malo prakse pri delu s funkcijami in razumeli (vsaj upam), zakaj so koristne.

Korak 1: Frekvence

Napišite funkcijo frekvence(sez), ki sprejme seznam sez in vrne slovar. Ključi slovarja naj bodo elementi seznama, vrednosti pa njihove frekvence v seznamu. S psevdokodo bi naša funkcija izgledala nekako takole:

  1. Pripravim prazen slovar.
  2. Z zanko se sprehodim preko seznama.
    1. Če je element seznama že v slovarju, mu prištejem vrednost za 1.
    2. Če elementa še ni, ga dodam in nastavim ustrezno frekvenco.
  4. Vrnem slovar.

Korak 2: Maks element

Napišite funkcijo maks_element(sez), ki sprejme seznam sez in vrne element seznama, ki se najpogosteje pojavlja. Postopek si lahko razdelimo na dva koraka:

  1. Izračunamo frekvence elementov v seznamu in jih shranimo v slovar.
  2. Izberemo tisti ključ, ki ima največjo frekvenco. Če vemo, da se s for zanko sprehodimo preko ključev slovarja, je ta problem zelo podoben nalogi, kjer smo iskali najmanjši pozitivni element v seznamu.

Korak 3: Najpogostejše

Napišite funkcijo najpogostejse(s). Namig: niz lahko razbijete na seznam besed z metodo split(). Npr.:


s = "kaj to naredi?"
besede = s.split()

Če pa želite niz razbiti na seznam znakov, potem lahko napišete list(niz). Ali je to za našo nalogo sploh potrebno?

# Preštejemo število ponovitev elementov seznama xs.
def frekvence(xs):
    hist = {}
    for x in xs:
        if x not in hist:
            hist[x] = 0
        hist[x] += 1
    return hist

# Poiščemo element z največjo frekvenco.
def maks_element(f):
    max_freq = 0
    max_item = None
    for item, item_freq in f.items():
        if item_freq > max_freq:
            max_freq = item_freq
            max_item = item
    return max_item

def najpogostejse(s):
    return maks_element(frekvence(s.split())), maks_element(frekvence(s))

* Najpogostejše urejene

Ta naloga je malo težja za tiste s hitrimi prsti. Napišite funkcijo najpogostejse_urejene, ki vrne vse besede in črke, ki se v podanem nizu pojavijo, urejene po številu pojavitev (besede in črke z enakim številom pojavitev uredite po abecednem vrstnem redu).

>>> najpogostejse_urejene('aa bb aa')
(['aa', 'bb'], ['a', ' ', 'b'])
>>> najpogostejse_urejene('in to in ono in to smo mi')
(['in', 'to', 'mi', 'ono', 'smo'], [' ', 'o', 'i', 'n', 'm', 't', 's'])



def max_sorted(f):
    xs = []
    for k, v in f.items():
        xs.append((-v, k))
    xs.sort()

    ys = []
    for k, v in xs:
        ys.append(v)
    return ys

def najpogostejse_urejene(s):
    return max_sorted(frekvence(s.split())), max_sorted(frekvence(s))

Družinsko drevo

V datoteki family.txt je spravljeno družinsko drevo. V vsaki vrstici sta zapisani dve imeni: ime starša in ime otroka. Tako nam vrstica 'bob mary' pove, da je Bob Maryjin oče, vrstica 'bob tom' pa, da je Bob Tomov oče, itd...

Kako dostopamo do datoteke? Če želimo datoteko prebrati po vrsticah, potem enostavno napišemo:

f = open("family.txt", "rt")
for vrstica in f:
     print(vrstica)

Naloga: Napišite funkcijo family_tree(file), ki sprejeme datoteko, odprto za branje, v kateri je shranjeno družinsko drevo in vrne slovar v katerem je za vsakega starša spravljen seznam vseh njegovih otrok.

>>> family_tree(open('family.txt'))
{'renee': ['rob', 'bob'], 'ken': ['suzan'], 'rob': ['jim'], 'sid': ['rob', 'bob'], ... , 'bob': ['mary', 'tom', 'judy']}

def family_tree(fname): 
    tree = {}
    for line in open('family.txt'):
        parent, child = line.split()
        if parent not in tree:
            tree[parent] = []
        tree[parent].append(child)
    return tree

# Spoznajmo še metodo setdefault...
def family_tree(fname): 
    tree = {}
    for line in open('family.txt'):
        parent, child = line.split()
        tree.setdefault(parent, []).append(child)
    return tree

#  ...in collections.defaultdict.
import collections

def family_tree(fname): 
    tree = collections.defaultdict(list)
    for line in open('family.txt'):
        parent, child = line.split()
        tree[parent].append(child)
    return tree

Naloga: Napišite funkcijo children(tree, name), ki v družinskem drevesu tree vrne seznam vseh otrok osebe. V primeru, da oseba nima otrok vrnite prazen seznam.

>>> tree = family_tree(open('family.txt'))
>>> children(tree, 'alice')
['mary', 'tom', 'judy']
>>> children(tree, 'mary')
[]

def children(tree, name):
    if name in tree:
        return tree[name]
    return []

# Z metodo get smo lahko malo krajši.
def children(tree, name):
    return tree.get(name, [])

Naloga: Napišite funkcijo grandchildren(tree, name), ki vrne seznam vseh vnukov in vnukinj osebe.

>>> grandchildren(tree, 'renee')
['jim', 'mary', 'tom', 'judy']

def grandchildren(tree, name):
    names = []
    for child in children(tree, name):
        for grandchild in children(tree, child):
            names.append(grandchild)
    return names

# Program lahko skrajšamo, če uporabimo metodo extend.
def grandchildren(tree, name):
    names = []
    for child in children(tree, name):
        names.extend(children(tree, child))
    return names

Naloga: Naslednja funkcija je malo zahtevnejša od ostalih, zato jo lahko preskočite. Napišite funkcijo successors(tree, name), ki vrne seznam vseh naslednikov osebe.

>>> successors(tree, 'tom')
['ken', 'suzan']
>>> successors(tree, 'sid')
['rob', 'bob', 'jim', 'mary', 'tom', 'judy', 'ken', 'suzan']

# Nalogo lahko rešimo rekurzivno
def successors(tree, name):
    names = []
    for child in children(tree, name):
        names.append(child)
        names.extend(successors(tree, child))
    return names

# ali iterativno.
def successors(tree, name):
    names = []
    todo = [name]
    while todo:
        cs = children(tree, todo.pop())
        names.extend(cs)
        todo.extend(cs)
    return names

# Zanimivo iterativno rešitevi dobimo, če naslednike dodajamo kar v seznam čez katerega iteriramo.
def successors(tree, name):
    names = [name]
    for n in names:
        names.extend(children(tree, n))
    return names[1:]

Naključno generirano besedilo

Napisati želimo program, ki bo naključno generiral besedilo. Seveda ni dobro, da si samo naključno izbiramo besede in jih lepimo skupaj, saj bi tako dobili nekaj povsem neberljivega. Naloge se bomo lotili malo pametneje. Recimo, da ima program na voljo nek tekst ('in to in ono smo mi'), iz katerega se lahko uči. Naš naključni tekst bomo začeli s poljubno besedo, recimo to. Nadaljujemo tako, da se vprašamo katere besede se v učnem tekstu pojavijo za besedo to. V našem primeru je to samo beseda in. Postopek nato ponovimo z besedo in. Če kakšni besedi v učnem tekstu sledi več kot samo ena beseda, izberemo naključno. Naloge se bomo lotili po korakih:

Napišite funkcijo nasledniki(txt), ki za vsako besedo b v nizu txt zgradi seznam besed, ki v tekstu nastopijo za besedo b. Nekaj primerov:

>>> nasledniki('in in in in')
{'in': ['in', 'in', 'in']}

Za besedo in se na treh mestih pojavi beseda in.

>>> nasledniki('in to in ono in to smo mi')
{'smo': ['mi'], 'to': ['in', 'smo'], 'ono': ['in'], 'in': ['to', 'ono', 'to']}

Za besedo smo se pojavi samo beseda mi, medtem ko se recimo za besedo to pojavita tako beseda smo kot tudi beseda in.

import collections

def nasledniki(txt):
    words = txt.split()
    freq = collections.defaultdict(list)
    for word, next_word in zip(words, words[1:]):
        freq[word].append(next_word)
    return freq

Sedaj pa napišite še funkcijo tekst(nasl, num_besed), ki sprejme slovar, ki ga ustvari funkcija nasledniki in generira naključno besedilo dolgo num_besed besed.

Vaš program lahko testirate na Orwellovi noveli.

>>> import urllib.request
>>> txt = urllib.request.urlopen('http://squeeb1134.tripod.com/1984.txt').read().decode('utf8')
>>> tekst(nasledniki(txt), 20)
'Big Brother had been drained out of the hands of me for his heart banged, seeming to grow less. Always'

Zaradi naključnosti je nalogo tekst težko preveriti z unittesti. Priložen test preveri le najbolj osnovne lastnosti.

import random

def tekst(freq, besed):
    words = []
    all_words = list(freq.keys())
    word = random.choice(all_words)
    for i in range(besed):
        words.append(word)
        word = random.choice(freq.get(word, all_words))
    return ' '.join(words)
Last modified: Tuesday, 24 February 2026, 5:53 PM