Naloge (dodatne)

n!

Napiši rekurzivno funkcijo faktoriela(n), ki izračuna n!. Funkcija je definirana z enačbama 0! = 1 in n! = n * (n - 1)!. Rešitev ne sme vsebovati zanke for ali zanke while.

>>> faktoriela(0)
1
>>> faktoriela(1)
1
>>> faktoriela(5)
120
>>> faktoriela(20)
2432902008176640000

def faktoriela(n):
    if n == 0:
        return 1
    return n * faktoriela(n - 1)

Rodovnik Celjskih grofov

Rodovnik celjskih grofov je predstavljen s slovarjem rodovnik, ki ste ga spoznali na predavanjih:

rodovnik = {'Ulrik I.': ['Viljem'], 'Margareta': [], 'Herman I.':
    ['Herman II.', 'Hans'], 'Elizabeta II.': [], 'Viljem': ['Ana Poljska'],
    'Elizabeta I.': [], 'Ana Poljska': [], 'Herman III.': ['Margareta'],
    'Ana Ortenburška': [], 'Barbara': [], 'Herman IV.': [], 'Katarina': [],
    'Friderik III.': [], 'Herman II.': ['Ludvik', 'Friderik II.', 'Herman III.',
    'Elizabeta I.', 'Barbara'], 'Ulrik II.': ['Herman IV.', 'Jurij',
    'Elizabeta II.'], 'Hans': [], 'Ludvik': [], 'Friderik I.': ['Ulrik I.',
    'Katarina', 'Herman I.', 'Ana Ortenburška'], 'Friderik II.': ['Friderik III.',
    'Ulrik II.'], 'Jurij': []}

Pogostost imena

Napiši funkcijo kolikokrat_ime(rodovnik, oseba, ime), ki pove, kolikokrat se v rodbini osebe oseba pojavi ime ime. Pri tem ime nima dodatnih oznak (številk ipd.).

>>> kolikokrat_ime(rodovnik, "Friderik I.", "Friderik")
3
>>> kolikokrat_ime(rodovnik, "Friderik II.", "Friderik")
2
>>> kolikokrat_ime(rodovnik, "Barbara", "Friderik")
0

def kolikokrat_ime(rodovnik, oseba, ime):
    n = 0
    if oseba.split()[0] == ime.split()[0]:
        n = 1
    for otrok in rodovnik[oseba]:
        n += kolikokrat_ime(rodovnik, otrok, ime)
    return n

Število žensk v rodbini

Napiši funkcijo zensk_v_rodbini(rodovnik, oseba), ki vrne število žensk v rodbini osebe oseba. Predpostavi, da je oseba ženska, če se njeno ime (to je, prvi del, pred raznimi številkami in krajevnimi nadimki) konča s črko "a".

>>> zensk_v_rodbini(rodovnik, "Ludvik")
0
>>> zensk_v_rodbini(rodovnik, "Friderik I.")
7
>>> zensk_v_rodbini(rodovnik, "Katarina")
1

def zensk_v_rodbini(rodovnik, oseba):
    n = 0
    if oseba.split()[0][-1] == 'a':
        n = 1
    for otrok in rodovnik[oseba]:
        n += zensk_v_rodbini(rodovnik, otrok)
    return n

Največja družina

Napiši funkcijo najvec_otrok(rodovnik, oseba), ki pove, kolikšno je največje število otrok pri kateremkoli članu rodbine določene osebe.

>>> najvec_otrok(rodovnik, 'Friderik I.')
5
>>> najvec_otrok(rodovnik, 'Friderik II.')
3

def najvec_otrok(rodovnik, oseba):
    if oseba is None:
        return 0
    naj_otrok = len(rodovnik[oseba])
    for otrok in rodovnik[oseba]:
        st_otrok = najvec_otrok(rodovnik, otrok)
        if st_otrok > naj_otrok:
            naj_otrok = st_otrok
    return naj_otrok

Potomstvo

Napiši funkcijo potomstvo(rodovnik, oseba), ki vrne množico (set) potomcev podane osebe.

>>> potomstvo("Ulrik I.")
{"Viljem", "Ana Poljska"}
>>> potomstvo("Ludvik")
set()

def potomstvo(rodovnik, oseba):
    n = set(rodovnik[oseba])
    for o in rodovnik[oseba]:
        n |= potomstvo(rodovnik, o)
    return n

Trgovina

Napiši funkcijo preberi_izdelke(ime_datoteke), ki prebere datoteko ime_datoteke oblike:

1;0;Racunalniki
2;0;Monitorji
3;0;Programska oprema
4;1;Prenosniki
5;1;Namizni racunalniki
6;1;Strezniki
7;3;Operacijski sistemi
8;3;Solske licence
9;3;Antivirusni programi
10;4;Prenosniki
11;4;Netbooki

V prvem stolpcu je zapisan id vrstice, v drugem id starša, v tretjem stolpcu pa najdete ime izdelka. Korenski izdelki imajo id starša enak 0. Funkcija naj vrne slovar podizdelkov. Ključi v slovarju so id-ji izdelkov, vrednosti pa seznami parov id-ja podizdelka in njegovega imena.

{'0': {('1', 'Racunalniki'), ('2', 'Monitorji'), ('3', 'Programska oprema')}, 
 '1': {('4', 'Prenosniki'), ('5', 'Namizni racunalniki'), ('6', 'Strezniki')}, 
 '3': {('7', 'Operacijski sistemi'), ('8', 'Solske licence'), ('9', 'Antivirusni programi')}, 
 '4': {('10', 'Prenosniki'), ('11', 'Netbooki')}}

Če vam ni jasno, kaj želimo s tem doseči, poskusite rešiti kar naslednjo nalogo.

import collections

def preberi_izdelke(ime_datoteke):
    db = collections.defaultdict(set)
    for line in open(ime_datoteke, 'r'):
        id, pid, name = line.strip().split(';')
        db[pid].add((id, name))
    return dict(db)

Napiši funkcijo seznam_izdelkov(slovar_izdelkov), ki bo vrnila urejen seznam vseh izdelkov.

   ['Monitorji',
    'Programska oprema',
    'Programska oprema / Antivirusni programi',
    'Programska oprema / Operacijski sistemi',
    'Programska oprema / Solske licence',
    'Racunalniki',
    'Racunalniki / Namizni racunalniki',
    'Racunalniki / Prenosniki',
    'Racunalniki / Prenosniki / Netbooki',
    'Racunalniki / Prenosniki / Prenosniki',
    'Racunalniki / Strezniki']

def seznam_izdelkov(db, pid='0', prefix=''):
    s = []
    for id, name in db[pid]:
        s.append(prefix + name)
        if id in db:
            s += seznam_izdelkov(db, id, prefix + name + ' / ')
    return sorted(s)

Napiši funkcijo seznam_koncnih(slovar_izdelkov), ki bo vrnila urejen seznam samo končnih izdelkov (to so tisti, ki nimajo podizdelkov).

   ['Monitorji',
    'Programska oprema / Antivirusni programi',
    'Programska oprema / Operacijski sistemi',
    'Programska oprema / Solske licence',
    'Racunalniki / Namizni racunalniki',
    'Racunalniki / Prenosniki / Netbooki',
    'Racunalniki / Prenosniki / Prenosniki',
    'Racunalniki / Strezniki']

def seznam_koncnih(db, pid='0', prefix=''):
    s = []
    for id, name in db[pid]:
        if id in db:
            s += seznam_koncnih(db, id, prefix + name + ' / ')
        else:
            s.append(prefix + name)
    return sorted(s)