Computer Programming 2019/20 fall

14. kodutöö

1. Tasemed

Kirjuta rekursiivne funktsioon tasemed, mis võtab argumendiks mitmemõõtmelise järjendi ning tagastab kahemõõtmelise järjendi, mille sisemised järjendid koosnevad algse järjendi elementidest tasemete kaupa, samas järjekorras (vt näidet). Tulemuse esimeses reas on kõik elemendid, mis asuvad etteantud järjendis esimesel tasemel, teises reas kõik elemendid, mis asuvad teisel tasemel jne. Proovi lahendada ülesanne globaalseid muutujaid kasutamata!

Näide funktsiooni kasutamisest:

>>> tasemed([1, [2, [3], [[4], 3], 2], 1, []])
[[1, 1], [2, 2], [3, 3], [4]]

>>> tasemed([8, [6, 7, [-1], [4, [[10]]], 2], 1])
[[8, 1], [6, 7, 2], [-1, 4], [], [10]]

VIHJE. Tõenäoliselt on vajalik iga rekursiivse väljakutse puhul kaasa anda tase, millel asud, ning järjend, mida muudetakse. Samas peaks funktsioon esmasel väljakutsel nõudma sisendiks ainsa parameetrina vaid algset järjendit. Seda võib teha vaikeparameetritega (default parameters) või abifunktsiooniga, nagu järgmistes näidetes.

Näide 1. Rekursiivne põhifunktsioon vaikeparameetritega.

def tasemed(järjend, tase = 0, tulemus = []):

    ...   

    tasemed(järjend, tase + 1, tulemus)        # Rekursiivne väljakutse

tasemed([1, 2, [3]])                           # Programmis kasutamine
                                               # Tagastab [[1, 2], [3]]

Näide 2. Rekursiivne abifunktsioon tasemedAbi, mida põhifunktsioon välja kutsub.

def tasemed(järjend):
    return tasemedAbi(järjend, 0, [])

def tasemedAbi(järjend, tase, tulemus)

    ...     

    tasemedAbi(järjend, tase + 1, tulemus)     # Rekursiivne väljakutse

tasemed([1, 2, [3]])                           # Programmis kasutamine
                                               # Tagastab [[1, 2], [3]]

2. Väljasta liin

Kirjuta rekursiivne funktsioon väljasta_liin, mis võtab argumentideks eellase nime, järglase nime ja sugupuu sõnastiku ning väljastab ekraanile põlvnemiste ahela eellasest järglaseni, kui selline ahel leidub. Kui ahelat ei leidu, siis tuleks väljastada tekst "ei leidu". Sõnastikus on võtmeks sõnena nimi ning väärtuseks ennikuna (või listina) isa nimi indeksil 0 ja ema nimi indeksil 1. Funktsioon võib tagastada vabalt valitud väärtusi, aga ekraanile tuleb väljastada nõutud nimed.

Näide programmi tööst (sõnastiku väljund on ilustatud):

>>> sõnastik
{
  'Kalle': ('Teet', 'Maris'), 
  'Maris': ('Konstantin', 'Mari'), 
  'Rita': ('Teet', 'Maris'), 
  'Siim': ('Teet', 'Maris'), 
  'Mari': ('Karl', 'Leeni'), 
  'Teet': ('Joosep', 'Adele'), 
  'Adele': ('Johannes', 'Leida'), 
  'Konstantin': ('Viktor', 'Jelena'), 
  'Joosep': ('August', 'Emma'), 
  'Viktor': ('Nikolai', 'Maria')
}

>>> väljasta_liin('Leida', 'Kalle', sõnastik)
Leida
Adele
Teet
Kalle

>>>> väljasta_liin('Mari', 'Adele', sõnastik)
ei leidu