Programiranje 1 (22/23)

Kolikokrat ime

Napiši funkcijo kolikokrat_ime(oseba, crka), ki pove, kolikokrat se v rodbini osebe oseba pojavijo imena, ki se začnejo z določeno črko. Če pokličemo, recimo kolikokrat_ime(adam, "A"), mora funkcija vrniti 3, saj so v Adamovi rodbini tri osebe, katerih ime se začne s črko A (Adam, Alenka in Aleksander).

def kolikokrat_ime(oseba, crka):
    if oseba[0] == crka:
        oseb = 1
    else:
        oseb = 0
    for otrok in rodbina[oseba]:
        oseb += kolikokrat_ime(otrok, crka)
    return oseb

def kolikokrat_ime(oseba, crka):
    oseb = oseba[0] == crka
    for otrok in oseba.otroci:
        oseb += kolikokrat_ime(otrok, crka)
    return oseb

Vsa rodbina določene osebe

Napiši funkcijo vsa_rodbina(oseba), ki vrne množico ( set) z vso rodbino podane osebe (vključno z njo samo).

def vsa_rodbina(oseba):
    rodbina = {oseba}
    for otrok in rodbina[oseba]:
        rodbina |= vsa_rodbina(otrok)
    return rodbina

Vse potomstvo določene osebe

Napiši funkcijo vse_potomstvo(oseba), ki vrne množico ( set) potomcev podane osebe (brez te osebe).

def vse_potomstvo(oseba):
    rodbina = set()
    for otrok in rodbina[oseba]:
        rodbina |= {otrok} | vse_potomstvo(otrok)
    return rodbina

Kako daleč je Elizabeta?

Na predavanjih smo se naučili, kako neko osebo vprašamo, ali v njegovi rodbini obstaja oseba z določenim imenom. Zdaj bi radi naredili nekaj več: napiši funkcijo kako_dalec(oseba, ime), ki pove, kako globoko v rodbini osebe oseba je oseba z imenom ime. Če, recimo, vprašamo Elizabeto, kako daleč je do Jurija, naj reče 1, saj je to njen sin. Razdalja do Jožefa (vnuka) je 2, do pravnukov Alenke, Petra in Aleksandra pa 3. Razdalja od Elizabete do Elizabete je 0.

Če vprašamo, kako daleč je od Elizabete do Tadeje, naj vrne None.

def kako_dalec(oseba, ime):
    if oseba == ime:
        return 0
    for otrok in rodbina[oseba]:
        koliko = kako_dalec(otrok, ime)
        if koliko != None:
            return 1 + koliko

Pot do Elizabete

Ta naloga je nekoliko težja ... a ne preveč.

Reši podobno nalogo, kot je prejšnja, le da naj funkcija - poimenujmo jo pot_do(oseba, ime) ne vrne razdalje do določene osebe, temveč pot do nje. Če Elizabeto vprašamo za pot do Aleksandra, naj vrne ["Elizabeta", "Jurij", "Jožef", "Aleksander"].

Spet si najprej predstavljal, kako bi igral to igro s kolegi.

def pot_do(oseba, ime):
    if oseba == ime:
        return [ime]
    for otrok in rodbina[oseba]:
        pot = pot_do(otrok, ime)
        if pot:
            return [oseba] + pot

Še malo matematike...

Gnezdena vsota

Napiši funkcijo vsota2(xs), ki sešteje elemente vgnezdenega seznama (seznama, ki vsebuje tudi podsezname). Pomagajte si s funkcijo isinstance(x, tip), ki pove, ali je podani x tipa tip

>>> isinstance([1, 2, 3], list)
True
>>> isinstance(1, list)
False
>>> vsota2([])
0
>>> vsota2([1, 2, 3, 4, 5])
15
>>> vsota2([1, [], [2, 3, [4]], 5])
15

Namig: vsota elementov seznama je enaka vsoti vsot podseznamov + vsota elementov, ki niso podseznami. Se pravi, pojdi čez elemente seznama (npr. for e in xs). Če vidiš, da gre za seznam ( isinstance(e, list)), ga vprašaj, kakšna je njegova vsota (vključno z morebitnimi podseznami v njem); to prištej k skupni vsoti, ki jo računaš. Če pa ne gre za seznam, je to številka in jo preprosto prišteješ.

Kot vse druge, je tudi ta naloga bistveno lažja, kot se zdi.

def vsota2(xs):
    vsota = 0
    for x in xs:
        if isinstance(x, list):
            vsota += vsota2(x)
        else:
            vsota += x
    return vsota

# Funkcijo vsota2 lahko napišemo tudi brez for zanke
def vsota2(xs):
    if not xs:
        return 0
    if isinstance(xs[0], list):
        return vsota2(xs[0]) + sum(xs[1:])
    return xs[0] + vsota(xs[1:])

# ali, z malo čarovnije, samo s for zanko :)
# To rešitev objavljam bolj kot zanimivost, saj zmede tudi nekatere bolj
# izkušene programerje.
def vsota2(xs):
    vsota = 0
    for x in xs:
        if isinstance(x, list):
            xs.extend(x)
        else:
            vsota += x
    return vsota


print(vsota2([]))
print(vsota2([1, 2, 3, 4, 5]))
print(vsota2([1, [], [2, 3, [4]], 5]))

Igranje s seznami

Spodnje naloge zabavajo tiste, ki jim je všeč rekurzija. Če vam je, se jih lotite. Tistim, ki je ne marajo, pa se zdijo duhamorne. Preskusite se, v katero skupino sodite! ;)

Včasih so programerji sestavljali sezname z gnezdenjem terk. Ubogi reveži, druge izbire niso imeli. Napiši funkcijo convert(xs), ki seznam xs pretvori v ta arhaični zapis.

>>> convert([])
()
>>> convert([1])
(1, ())
>>> convert([1, 2])
(1, (2, ()))
>>> convert([5, 4, 6, 7, 1])
(5, (4, (6, (7, (1, ())))))

def convert(xs):
    if not xs:
        return ()
    return xs[0], convert(xs[1:])

Napiši funkcijo length(xs), ki izračuna dolžino seznama gnezdenih terk.

>>> length(())
0
>>> length((1, ()))
1
>>> length((5, (4, (6, (7, (1, ()))))))
5

def length(xs):
    if not xs:
        return 0
    return 1 + length(xs[1])

Napiši funkcijo dup(xs), ki ponovi vsak element seznama.

>>> dup((1, (2, ())))
(1, (1, (2, (2, ()))))
>>> dup((5, (4, (6, (7, (1, ()))))))
(5, (5, (4, (4, (6, (6, (7, (7, (1, (1, ()))))))))))

def dup(xs):
    if not xs:
        return ()
    return xs[0], (xs[0], dup(xs[1]))

Napiši funkcijo reverse(xs), ki obrne seznam.

>>> reverse((5, (4, (6, (7, (1, ()))))))
(1, (7, (6, (4, (5, ())))))

def reverse(xs, ys=()):
    if xs == ():
        return ys
    return reverse(xs[1], (xs[0], ys))

Če ta take naloge zabavajo jih na internetu najdeš še veliko več.

Izpis direktorijev

Funkcija os.listdir(ime_direktorija) vrne seznam z imeni vseh datotek v podanem direktoriju. Nekatera od teh imen predstavljajo datoteke, nekatera pa, morda, direktorije. Funkcija os.path.isdir(ime) pove, ali je ime ime datoteke ali direktorija.

Napišite funkcijo izpisi_datoteke(ime_direktorija), ki izpiše imena vseh datotek v direktoriju ime_direktorija in v vseh njegovih poddirektorijih, direktorijih poddirektorijev.

Za to nalogo ni testov. Preskušajte jo na direktorijih na svojem računalniku.

Namig: to je spet isto kot rodovnik...

Nasvet: recimo, da imamo direktorij "x" in os.listdir("x") vrne (med drugim) ime "y". Da bi izvedeli, ali je "y" direktorij ali datoteka, moramo poklicati os.path.isdir(os.path.join("x", "y")) in ne le os.path.isdir("y").

import os
def izpisi_datoteke(ime_direktorija):
    datoteke = os.listdir(ime_direktorija)
    for d in datoteke:
        pot = os.path.join(ime_direktorija, d)
        if os.path.isdir(pot):
            izpisi_datoteke(pot)
        else:
            print (d)