Testi

Testi: testi-rekurzivni-izpis-seznamov.py

Naloga

Napiši funkcijo dump(xs, n), ki kot argument dobi seznam xs, ki vsebuje števila in sezname, ki vsebujejo števila in sezname, ki vsebujejo števila in sezname, ki ... Kot rezultat naj funkcija vrne niz, ki predstavlja vsebino seznama. Da se izognemo predolgim izpisom, dobi funkcija še en argument, n: pri vsakem seznamu izpiše le prvih n elementov; če je poleg teh še kakšen, doda tri pike.

Nekaj primerov

>>> dump([1, 2, 3, 4, 5], 100) '[1, 2, 3, 4, 5]' >>> dump([1, 2, 3, 4, 5], 3) '[1, 2, 3, ...]' >>> dump([1, 2, 3, [4, 5]], 100) '[1, 2, 3, [4, 5]]' >>> dump([1, 2, 3, [4, 5]], 2) '[1, 2, ...]' >>> dump([[1, 2, 3], [4, 5, 6], 7], 2) [[1, 2, ...], [4, 5, ...], ...] >>> dump([[[[1]], 2], 3, [4, 5]], 100) '[[[[1]], 2], 3, [4, 5]]' >>> dump([[[[1]], 2], 3, [4, 5]], 3) '[[[[1]], 2], 3, [4, 5]]' >>> dump([[[[1]], 2], 3, [4, 5]], 2) '[[[[1]], 2], 3, ...]' >>> dump([[[[[[[[[[]]]]]]]]]], 100) '[[[[[[[[[[]]]]]]]]]]' >>> dump([[[[[[[[[[]]]]]]]]]], 1) '[[[[[[[[[[]]]]]]]]]]'

Nasvet 1: Najprej napiši funkcijo, ki pravilo naredi, kar kaže prvi gornji primer in nato funkcijo, ki pravilno naredi, kar kaže drugi primer. Šele nato se loti gnezdenja - rekurzije. S pikami (omejitvijo dolžine) se lahko ukvarjaš, ko si končal vse drugo, saj jih je lahko dodati k že narejeni funkciji.

Nasvet 2: Funkcija naj pripravi seznam nizov, ki jih je potrebno izpisati, v niz ločen z vejicami pa jih postavi s pomočjo metode join, ki smo si jo ogledali, ko smo se pogovarjali o metodah nizov.

Nasvet 3: Naloge se ne loti v zadnjem trenutku.

Rešitev

Lepa rekurzivna rešitev zloži v seznam vse, kar je treba, v obliki nizov, potem pa kar v returnu to z joinom združi z vejicami in spredaj in zadaj prilepi oklepaje. Seznam pa sestavi takole: v začetku je seveda prazen. Nato vzame prvih n elementov seznama (xs [:n]) in za vsakega stori tole: če gre za seznam, pokliče dump, ki vrne seznam v obliki niza. Sicer pa s str pretvori število v niz. Ko je zanke konec, preverimo, ali ima seznam morda več kot n elementov in v tem primeru dodamo še niz s tremi pikami.

def dump(xs, n): res = [] for el in xs[:n]: if isinstance(el, list): res.append(dump(el, n)) else: res.append(str(el)) if len(xs) > n: res.append("...") return "["+", ".join(res)+"]"

Kdor ne ve za join, je obsojen na mučenje z vejicami in nalogo reši takole

def dump(xs, n): res = "" for el in xs[:n]: if res: res += ', ' if isinstance(el, list): res += dump(el, n) else: res += str(el) if len(xs) > n: if res: res += ', ' res += "..." return "["+res+"]"

Zmerno zoprno, a znosno. To vedno in povsod čaka tiste, ki ne vedo za join.

Rešitev brez rekurzije

Obstajajo problemi, ki niso narejeni za rekurzijo. Vse, kar smo počeli na predavanjih (razen Fibonaccija), so pravzaprav natanko takšni primeri; z rekurzijo smo jih reševali, ker so preprosti.

Obstajajo pa tudi "pravi rekurzivni" problemi. Tale je eden njih. Če hočeš problem, za katerega bi bilo naravno uporabiti rekurzijo, reševati brez uporabe rekurzije, moraš navadno zato res obvladati rekurzijo. Razlog je v tem, da moraš nekako napisati rekurziven program, ne da bi uporabil rekurzijo. Rekurzijo moraš na nek način nagoljufati, odsimulirati. Za to pa je potrebno več in ne manj znanja.

Spodnji program deluje tako, da ima na seznamu toDump stvari, ki jih mora še zapisati, lepo po vrsti. Kadar ima pred sabo element, ga pač zapiše. Kadar prebere, da mora "dumpati" seznam, pa to naredi tako, da na seznam stvari, ki jih je potrebno dumpati, doda oklepaj, prvih n elementov tega seznama, pike, če je treba, in zaklepaj.

Naj razume, kdor hoče. Te rešitve ne kažem zato, da bi jo razumeli, temveč zato, da bi videli, zakaj je rekurzija (ki ste jo ta vikend najbrž pošteno preklinjali) boljša kot alternativa.

def dump(xs, n): toDump = [xs] res = "" while toDump: el = toDump.pop(0) if isinstance(el, list): toDump = ['[']+el[:n]+[']' if len(el) <= n else '...]'] + toDump else: if res and res[-1] != '[' and el != ']': res += ', ' res += str(el) return res
Zadnja sprememba: četrtek, 25. marec 2021, 20.32