Nepadajoče govorice
Ogrevalna naloga
Napišite rekurzivno funkcijo nepadajoca(s), ki prejme
seznam (ali, morda, niz, saj je vseeno) in vrne True, če je
zaporedje v seznamu (nizu) nepadajoče. Primeri nepadajočih zaporedij so
ABCD, AEF, AAAB, ABBCE.
Namig: Zaporedje je nepadajoče, če ima manj kot dva elementa ali pa je ničti element manjši ali enak prvemu, poleg tega pa je nepadajoče tudi zaporedje od prvega elementa naprej.
Rešitev
(...) če ima manj kot dva elementa (len(s) < 2) ali
or pa je ničti element manjši ali enak prvemu
(s[0] <= s[1]), poleg tega (and) pa je nepadajoče
tudi zaporedje od prvega elementa naprej (nepadajoca(s[1:])).
Torej:
Obvezna naloga
Napišite rekurzivno funkcijo govorica(pot, znanci), ki prejme
pot govorice in množico parov ljudi, ki se poznajo. Vrniti mora
True, če je ta pot - glede na podana poznanstva - možna, in
False, če ni. Torej isto kot v nalogi Govorice, le da mora biti
funkcija rekurzivna, poleg tega pa ne prejme slovarja krožkov, temveč že kar
množico parov znancev.
Namig: Pot je možna, če ... Hm, pravzaprav ni razloga, da tega ne bi razmislili sami.
Rešitev
Pot je možna, če je krajša od 2 (len(pot) < 2) ali
or pa je možen prvi par ((pot[0], pot[1]) in znanci)
and je možen tudi ostanek poti
(govorica(pot[1:], znanci)).
Dodatna naloga
Napišite rekurzivno funkcijo sodi_lihi(s), ki za razliko od
one na predavanjih ne bo klicala druge funkcije. Na predavanjih sem obljubil,
da bomo to naredili, vendar na koncu ni bilo časa. Problem pa je ravno prav
težak za ne prehudo dodatno nalogo.
Rešitev
Trik je v tem, da moramo preveriti ali je prvi sod in, če imamo vsaj dva, tudi, če je drugi lih. Poleg tega pa, kot vedno, ostanek.
Seznam je torej sodo-lih, če je prazen, ali pa je prvi element sod ter je krajši od 2 ali pa je drugi element lih in ... je sodo-lih tudi ostanek.
Ne spreglejte, da v rekurzivnem klicu tokrat napišemo [2:] in ne
[1:], kot prej.