Starting in the top left corner of a 2x2 grid, there are 6 routes (without backtracking) to the bottom right corner.

2x2 tabela

How many routes are there through a 20x20 grid?

Prevod:

V 2x2 tabeli obstaja 6 poti iz zgornjega levega oglišča do spodnjega desnega oglišča. Ne dopušča se »hoje« nazaj (premikamo se lahko le desno in navzdol).
Koliko je takih poti v 20x20 veliki tabeli?

Ena od idej je, da poiščemo vsako možno pot posebej in jih preštejemo. Ta metoda je preveč »požrešna«, saj je pri velikih dimenzijah teh poti preveč.

Druga ideja je, da ko enkrat izračunamo, koliko je možnih poti od neke točke do konca tabele, si to zapomnimo in kasneje to uporabimo.
Mi se bomo osredotočili na to zadnjo idejo.

Vsaki »točki« v tabeli bo pripadal element seznama.

• Točka (0,0) bo pripadala elementu seznam[0][0].
• Točka (0,1) bo pripadala elementu seznam[0][0]

Če računamo poti za tabelo velikosti n x n, vemo, da ima ta tabela (n+1) x (n+1) točk. Torej bomo mi potrebovali (n+1) x (n+1) velik seznam. Vsaki točki tabele pripada element seznam.

Seznam in tabela

Ko govorimo o tabeli, mislimo na tabelo, za katero računamo število možnih poti. V našem primeru tabela velikosti 20x20.
Ko govorimo o seznamu, mislimo na objekt v katerega bomo shranjevali število poti iz določene točke.

Če se nahajamo na »običajni točki« (točki, ki ne leži na desnem ali spodnjem robu) imamo natančno dve možne poti. Lahko dostopamo do točke pod nami in do točke desno od nas.

• Na vsaki točki, ki se nahaja na desnem robu, imamo natanko eno pot oz. lahko dostopamo samo do ene točke. To je točka pod trenutno točko.
• Na vsaki točki, ki se nahaja na spodnjem robu, imamo natančno eno pot oz. eno možnost do naslednje točke. Lahko dostopamo le do točke desno od trenutne točke.

Iz zgornjih ugotovitev je očitno, da so v našem seznamu v desnem stolpcu same enice, prav tako so same enice v zadnji vrstici. V bistvu je v spodnjem desnem kotu ničla, saj ta element seznama predstavlja končno točko. Mi bomo pustili kar enico, ker tega elementa v seznamu ne bomo potrebovali.

Problem bomo razbili na dve funkcije:

• Funkcija, ki nam bo ustvarila seznam z ničlami in enicami.
• Rekurzivna funkcija, ki bo preštela poti za dan seznam in pozicijo.

Naša funkcija bo sprejela parameter n. Tabela bo tako dimenzije n x n.
Kot smo že prej omenili, bo potem naš seznam dimenzije (n+1) x (n+1).
Na začetku preverimo, ali je n enak 1. Če je, vrnemo 2.
Če je n različen od nič ustvarimo seznam s samimi ničlami:

• Ustvarimo prazen seznam

• Pomagamo si s for zanko, ki teče od 1 do n. Vsakič dodamo seznamu nov seznam dolžine n s samimi ničlami:

  • sez.append((n+1)*[0])

Sedaj imamo seznam s samimi ničlami.
Zadnji stolpec napolnimo z enicami. To naredimo tako, da gremo z enojno for zanko čez seznam. Vsakemu n-temu elementu i-te vrstice dodelimo vrednost 1.
Spremenimo samo še zadnjo vrstico. Do zadnje vrstice dostopamo s sez[n]:

• sez[n] =(n+1)*[1]

Funkcija bo vračala rezultat, ki ga bomo dobili s pomočjo klica funkcije stPoti(sez, 0, 0).

Ta funkcija bo rekurzivno preverila koliko je možnih poti od lokacije (vr, st) do konca tabele.

Na začetku funkcije najprej preverimo kakšno vrednost ima element seznama podane lokacije (sez[vr][st]).
Če je vrednost različna od nič, vemo, da je od te lokacije naprej točno toliko poti, kot je vrednost tega elementa.
Če pa je element enak od nič, seštejemo poti elementa pod nami in elementa desno od nas. Poti elementa pod nami dobimo z rekurzivnim klicem stPoti(sez, vr-1, st), poti elementa desno od nas pa z rekurzivnim klicem stPoti(sez,vr, st+1).

Vrnemo vrednost elementa sez[vr,st].

V tabeli 20x20 je 137846528820 možnih poti.

Python datoteka

Testne primere bomo pisali v svojo .py datoteko.
V to datoteko na začetku uvozimo funkcije iz datoteke Poti.py.

• import Poti

  Testni primeri:

  Preverimo, če deluje za n=1 in n=2. Pomagamo si z assert stavki. Če pogoj znotraj asserta ne bo držal, bo program sprožil napako, ki jo podamo v nizu.

• n=1… obstajata dve poti:

  • assert pot(1)==2, »Napaka!«

• n=2… obstaja 6 poti:

  • assert pot(2)==6, »Napaka!«

Preverimo, če za napačen parameter sproži napako. Tukaj si bomo pomagali s try and except.

• pot(»8«)