Vrnimo se k prvi domači nalogi zajčjim luknjam. Kot smo se naučili, gredo bobri čez tako, da poskačejo v luknjo, dokler se ta ne napolni, tisti, ki so ostali zunaj gredo čez, potem pa se bobri, ki so v luknji, izvlečejo tako, da se primejo za repe, zgornji pa prime za rep zadnjega izmed bobrov, ki so ostali zunaj. Manever uspe, če je bobrov več, kot je velika največja luknja.

Vse funkcije, ki jih sprogramirate v tej domači nalogi, morajo biti rekurzivne. V njih ne smete uporabiti for in while, prav tako pa ne smete klicati nobene funkcije razen funkcije, ki jo programirate in, če želite, funkcije len.

Obvezna naloga

Napiši funkcije:

  • bo_slo_cez(luknje, bobrov), ki prejme seznam globin lukenj in število bobrov ter vrne True, če je bobrov več, kot je globoka najglobja lukna in False, če jih ni. Funkcija naj kliče le len (neobvezno - če želite) in samo sebe.

    Niti funkcije naj_luknja ne kličite.

  • naj_luknja(luknje), ki prejme globine lukenj in vrne globino najglobje luknje.

  • vedno_hujse(luknje), ki prejme seznam lukenj in pove (True ali False) ali je vsaka luknja globja od prejšnje (torej ali je prva globja od ničte in tako naprej).

Rešitev

Čez bo šlo, če ni lukenj, ali pa je prva luknja dovolj majhna in vse ostale tudi.

def bo_slo_cez(luknje, bobrov):
    return not luknje or luknje[0] < bobrov and bo_slo_cez(luknje[1:], bobrov)

En študent je oddal naslednjo zanimivo čudno rešitev.

def bo_slo_cez(luknje, bobrov):
    return True if not luknje else False if luknje[0] > bobrov else bo_slo_cez(luknje[1:], bobrov)

To je v bistvu čisto ista, a povedano precej bolj zavozlano in nepregledno. Funkcija vrne True, če ni lukenj, sicer vrne False, če je prva luknja pregloboka, sicer vrne rezultat glede na preostale luknje.

O naj_luknje se da povedati več zanimivega. Najprej začnimo z rešitvijo, ki jo je oddalo sumljivo veliko študentov; upam, da niso prepisovali, saj se v tem primeru delajo norca iz sebe.

def naj_luknja(luknje):  # Tole je zelo narobe!
    if luknje == []:
        return 0
    if len(luknje) == 1:
        return luknje[0]
    if luknje[0] < luknje[1]:
        del luknje[0]
    else:
        del luknje[1]
    return naj_luknja(luknje)

Tole je zelo narobe. Če napišemo program

luknje = [1, 2, 3, 4]
print(naj_luknja(luknje))
print(luknje)

Se mora seveda izpisati

4
[1, 2, 3, 4]

gornji program pa seveda izpiše

4
[4]

Enkrat za vedno se moramo zmeniti (, kar smo se poskušali že večkrat): funkcije ne smejo spreminjati podatkov, ki jih dobijo kot argument. Ta funkcija uniči slovar. Kaj bi rekli o metodi count, če bi ta iz seznama pobrisala vse elemente, razen tistih, ki jih prešteva? Ali pa o metodi get, če bi ta iz slovarja odstranila element, ki ga vrača? Da ne dela pravilno, ne? No, ta funkcija pa prav tako.

Na takšno napako žal nisem računal, zato nisem napisal testov zanjo. Pravzaprav mi je asistentka povedala, da pišete takšno rešitev, vendar si nisem takoj zapisal, da moram dodati teste.

Pač pa sem računal na naslednjo napako, a prav tako pozabil test zanjo.

def naj_luknja(luknje):
    if len(luknje) == 0:
        return 0
    else:
        if luknje[0] > naj_luknja(luknje[1:]):
            return luknje[0]
        else:
            return naj_luknja(luknje[1:])

Ta funkcija deluje in je praktično pravilna. Test je pravzaprav takšen, kot mora biti, hotel sem le dodati, da range(20) v zadnjem testu preskusno spremenite še v range(30). Sicer pa se že pri 20 vidi, da je funkcija nekam počasna.

Problem je tule. Funkcija naj_luknja dvakrat pokliče funkcijo naj_luknja (ne vedno, a če je seznam urejen, bo naslednja vedno večja od prejšnje in v tem primeru bo funkcijo res vedno poklicala dvakrat). To še ne bi bilo tako hudo, če ne bi vsak od teh dveh klicev dvakrat poklical naj_luknja. Kar ne bi bilo tako hudo, če ne bi vsak od teh štirih klicev dvakrat ... in vsak od teh osmih dvakrat ... in vsak od teh šestnajstih dvakrat ... skupaj torej 220 ali 10,485.576 klicev. Deset milijonov. Pri seznamu dolžine 30 pa 230, približno 10 milijard. Pri seznamu dolžine 40 pa deset bilijonov. Tega ne bi nikoli dočakali.

Program je potrebno le malo spremeniti:

def naj_luknja(luknje):
    if not luknje:
        return 0
    naj = naj_luknja(luknje[1:])
    if naj > luknje[0]:
        return naj
    else:
        return luknje[0]

Vedno hujše je, če imamo manj kot dve luknji ali pa je prva luknja manjša od druge in je tudi naprej vedno hujše.

def vedno_hujse(luknje):
    return len(luknje) < 2 or luknje[0] < luknje[1] and vedno_hujse(luknje[1:])

Malo sem pričakoval, da boste pisali vedno_hujse(luknje[2:]), vendar ne vem, ali ste ali ne. Pač pa ste, zanimivo, zapletali pogoj z if len(luknje) == 0 or len(luknje) == 1 ali pa if luknje == [] or len(luknje) == 1. Oboje deluje, vendar je globina lukenj vedno pozitivna (luknja z negativno globino ni zajčja luknja temveč krtov hrib) in cela, torej je 0 ali 1 isto kot < 2 ali <=1.

Dodatna naloga

Ta je lepa in jo priporočam v reševanje.

Recimo, da je bobrom v luknjah popolnoma všeč, zato ne bodo skakali ven, temveč bodo ostali v njih. Napiši funkcijo zapolnjenih(luknje, bobrov), ki prejme seznam globin lukenj in število bobrov ter vrne število lukenj, ki jih bodo bobri popolnoma napolnili.

Klic zapolnjenih([5, 3, 2, 8, 4, 1, 3], 12) vrne 3, ker bo 12 bobrov napolnilo prve tri luknje, preostala dva bobra, ki bosta skočila v četrto, pa le-te očitno na bosta napolnila.

Rešitev

Če ni lukenj, ki bi jih lahko zapolnili (not luknje), ali pa če bobri ne zadoščajo niti za prvo (bobri < luknje[0]), vrnemo 0. Sicer pa zapolnimo prvo luknjo (1 +) in se vprašamo, koliko od ostalih lukenj (luknje[1:]) lahko zapolnimo z ostalimi bobti (bobri - luknje[0]).

def zapolnjenih(luknje, bobrov):
    if not luknje or bobrov < luknje[0]:
        return 0
    else:
        return 1 + zapolnjenih(luknje[1:], bobrov - luknje[0])
Utolsó módosítás: 2020. március 31., kedd, 09:17