Rekurzivni nim - Rim

Napisali boste nekaj funkcij, ki ste jih pisali za nalogo Nim - le da bodo tokrat rekurzivne.

Testi

Testi: testi-rim.py

Obvezna naloga

Napiši naslednje funkcije:

• vsota(s) vrne vsoto števil v podanem seznamu. To seveda že poznamo s predavanj, vendar vseeno sprogramiraj še enkrat. Sam(a). Vsoto, vemo, izračunamo tako, da k prvemu elementu prištejemo vsoto ostalih.

• vsebuje(s, x) vrne True, če seznam s vsebuje element x in False, če ga ne. Stvar je preprosta: prazen seznam očitno ne vsebuje x. Sicer pa preverimo, ali je prvi element enak x, ali pa je x vsebovan v preostanku seznama.

• najvecja_potenca(n) vrne največjo potenco števila 2, ki je manjša ali enaka podanemu števila n. Klic najvecja_potenca(22) vrne 16, saj bi bilo 32 že preveč. Klic najvecja_potenca(32) pa vrne 32. Predpostaviti smeš, da je n pozitivno celo število.

  Kako to narediti rekurzivno? Preprosto: največja potenca, ki gre v n, je dvakrat večja od največje potence, ki gre v n polovic (če uporabljamo celoštevilsko deljenje).

  Je to res?

  • največja potenca, ki gre v 22 je dvakrat večja od največje potence, ki gre v 11;
  • največja potenca, ki gre v 11, je dvakrat večja od največje potence, ki gre v 5;
  • največja potenca, ki gre v 5, je dvakrat večja od največje potence, ki gre v 2;
  • največja, potenca, ki gre v 2, je dvakrat večja od največje potence, ki gre v 1;
  • največja potenca, ki gre v 1, je 1; (... torej je največja potenca, ki gre v 2, 2; torej gre v 5 4, torej gre v 11 8, torej gre v 22 16).

Rešitev

Vsota števil v seznamu je enaka vrednosti prvega elementa, ki ji prištejemo vsoto ostalih elementov. Reč se ustavi, ko je seznam prazen; vsota elementov v njem je 0.

def vsota(s):
    if not s:
        return 0
    else:
        return s[0] + vsota(s[1:])

Rokohitrsko, zavedajoč se, da je False isto kot 0:

def vsota(s):
    return s != [] and s[0] + vsota(s[1:])

Seznam s vsebuje x, če ni prazen in je x prvi element ali pa ostanek vsebuje x. Reč se ustavi, ko je seznam prazen in Python ne gre preverjat ostanka pogoja.

def vsebuje(s, x):
    return s != [] and (s[0] == x or vsebuje(s[1:], x))

Z največjo potenco pa opravimo, kot svetuje naloga: "največja potenca, ki gre v n, je dvakrat večja od največje potence, ki gre v n polovic (če uporabljamo celoštevilsko deljenje)." Reč se ustavi, če je n enak 1; tedaj je največja potenca enaka 1.

def najvecja_potenca(n):
    if n == 1:
        return 1
    return 2 * najvecja_potenca(n // 2)

Dodatna naloga

• razbij(n) vrne seznam potenc števila 2, ki se seštejejo v podano število n; vsaka potenca lahko nastopa le enkrat. Klic razbij(22) vrne [16, 4, 2]. Števila naj bodo urejena v padajočem vrstnem redu. Nalogo reši tako, da najprej s prejšnjo funkcijo poiščeš največjo potenco. Nato poiščeš seznam, ki predstavlja razbitje ostanka, in mu (spredaj) dodaš to potenco.

• brez(s, x) prejme nek seznam s in vrne nov seznam, ki je enak podanemu seznamu, a brez x-ov. Klic brez([5, 4, 1, 2, 1, 1, 3], 1) vrne [5, 4, 2, 3]. Te funkcije ni bilo v originalni nalogi Nim, a ti lahko pride prav pri naslednjem paketku nalog.

Rešitev

Spet naredimo natančno tako, kot pravi namig v nalogi: poiščemo največjo potenco (p), ki gre v n in potem razbijemo, kar ostane od n-ja. Končamo, ko je n nič in ni česa razbijati, tako da vrnemo prazen seznam.

def razbij(n):
    if n == 0:
        return []
    p = najvecja_potenca(n)
    return [p] + razbij(n - p)

Funkcijo brez bomo razpisali lepo počasi. Če je s prazen, vrnemo prazen seznam. Sicer pa imamo dve možnosti: če je prvi element ravno x, vrnemo ostanek brez x-a. Če je prvi elemement kaj drugega, pa vrnemo prvi element in ostanek brez x-a.

def brez(s, x):
    if not s:
        return []
    prvi, ostali = s[0], s[1:]
    if prvi == x:
        return brez(ostali, x)
    else:
        return [prvi] + brez(ostali, x)

Čisto dodatne naloge, v vaše veselje

• razlika(s, t) prejme dva seznama in vrne nov seznam, ki vsebuje elemente, ki se pojavijo v enem od podanih seznamov, ne pa v obeh. Klic razlika([16, 4, 2], [4, 1]) vrne [16, 2, 1] (v tem ali poljubnem drugem vrstnem redu), saj so to števila, ki se pojavijo le v prvem ali v drugem seznamu. Vsak element seznama s (ali t) se v tem seznamu pojavi le enkrat. Pri reševanju se ti morda (a ne nujno) splača uporabiti funkcijo, ki si jo sprogramiral prejle.

• razbij_seznam(s) prejme seznam števil in vrne seznam seznamov njihovih razbitij. Klic razbij([22, 5, 13]) vrne [[16, 4, 2], [4, 1], [8, 4, 1]].

• zdruzi_sezname(s) prejme seznam seznamov (takšen, kot ga vrača funkcija razbij_seznam) in vrne vse elemente, ki se pojavijo lihokrat.

Rešitev

razlika je ena lepših. Rekurzija bo tekla po s-ju: v vsakem klicu se bomo znebili prvega elementa s-ja.

Ustavila se bo, ko je t prazen. V tem primeru je razlika med s in t očitno s.

Če s ni prazen, moramo ločiti dva primera. Če je prvi element t-ja v s-ju (uporabili bomo rekurzivno funkcijo vsebuje), bomo vrnili razliko med s-jem brez tega elementa (ker ga je potrebno odstraniti od tam) in t-jem brez prvega elementa.

Če prvega elementa t-ja ni v s-ju, pa mora rezultat vsebovati ta element in še razliko med s in ostankom t-ja.

def razlika(s, t):
    if not t:
        return s
    prvi, ostali = t[0], t[1:]
    if vsebuje(s, prvi):
        return razlika(brez(s, prvi), ostali)
    else:
        return [prvi] + razlika(s, ostali)

Ostali dve čisto dodatni funkciji sta v primerjavi z njo trivialni.

def razbij_seznam(s):
    if not s:
        return []
    return [razbij(s[0])] + razbij_seznam(s[1:])

def zdruzi_sezname(ss):
    if not ss:
        return []
    return razlika(ss[0], zdruzi_sezname(ss[1:]))