Programiranje 1 (23/24)

V tej domači nalogi vadimo pisanje rekurzivnih funkcij. Obe funkciji vam bi bilo lažje napisati iterativno; tako bi bilo za te nalogi tudi bolj naravno. Vendar potrebujemo takšne, preproste primere kot pripravo na težje, pri katerih brez rekurzije (skoraj) ne bo šlo.

Tako kot na predavanjih je smiselno najprej ločeno obravnavati prazen seznam potem pa prvi element in ostanek (ali pa ostanek in prvi element, kakor bo naneslo).

Naloga se navezuje na nalogo Zemljevid ovir.

Obvezni del

1. Napiši rekurzivno funkcijo ovirica(ovire), ki prejme seznam ovir, podanih s trojkami (x0, x1, y), in vrne True, če seznam vsebuje kakšno oviro širine 1 -- torej takšno, kjer je x0 == x1.

2. Napiši rekurzivno funkcijo najsirsa(ovire), ki prejme seznam ovir in vrne širino najširše ovire. Če je seznam prazen, funckija vrne 0.

   Klic najsirsa([(1, 1, 4), (3, 5, 3), (2, 8, 1), (8, 10, 2)]) vrne 7, saj je najdaljša ovira, (2, 8, 1), dolga 7.

Dodatni, neobvezni izziv

Napiši rekurzivno funkcijo urejene(s), ki vrne True, če so ovire urejene po y in znotraj tega po x0.

Klic urejene([(1, 1, 4), (3, 5, 3), (2, 8, 1), (8, 10, 2)]) vrne False; kršitev je že na drugem mestu, saj je prva ovira v vrstici 4, druga v vrstici 3.

Klic urejene([(2, 8, 1), (8, 10, 2), (13, 15, 2), (1, 1, 4)]) vrne True: ovire so urejene po vrsticah (element z indeksom 2 --- 1, 2, 2, in 4) in znotraj tega po stolpcih (oviri v vrstici 2 sta shranjeni od leve proti desni -- najprej 8 in potem 13).

Če je naloga pretežka, za začetek poskusi napisati rekurzivno funkcijo, ki prejme seznam števil in pove, ali so urejena po velikosti (True) ali ne (False).

Testi