Dichiarazione di problemi:
Ho un albero con valori di nodo (i, j) dove i, j < 1. I figli di ciascun nodo assumono i valori (i - 1, j), (i - 1, j - 1) e (i, j - 1) rispettivamente. Ora, i e j hanno vincoli dove non possono essere inferiori a zero, quindi, dato i (o j WLOG) == 0 per un nodo, il suo unico figlio diventa (0, j - 1) (assumendo j > 0).
Questi nodi rappresentano gli indici di una matrice e ciò che rappresentano i bambini sono l'indice a ovest, a nord oa nord ovest dell'indice attualmente selezionato. (L'avviso 0 rappresenta il lato ovest o il lato nord della matrice)
Ho scritto un algoritmo ricorsivo che produrrà il numero di direzioni diverse che puoi percorrere per arrivare da node_0 (i, j) all'inizio.
def backtrackrecursion( currentnode, counter ):
if currentnode.getindex() == (0 , 0):
return counter++
if currentnode.geti() > 0:
currentnode.addchild(Node(index=(i - 1, j)))
if currentnode.getj() > 0:
currentnode.addchild(Node(index=(i, j - 1)))
if currentnode.getindex() >= ( 1 , 1 ):
currentnode.addchild(Node(index=(i - 1, j - 1)))
for child in currentnode.getchildren():
counter += backtrackrecursion(child, counter)
return counter
Capisco perché funzioni. La mia ragazza ha scritto un altro algoritmo e, con mio grande stupore, funziona altrettanto bene.
def btr(cnode, cou):
if cnode.getindex() == ( 0 , 0 ):
return cou++
if cnode.getindex() != (0 , 0):
cou = btr(cnode.inddecr( -1, 0), cou) + btr(cnode.inddecr(0, -1), cou) + btr(cnode.inddrec( -1 , -1 ), cou)
return cou
ora potrei aver perso una proprietà nella sua classe che cancella tutti i bambini con indice i o j < 0, ma non dovrebbe essere una chiamata infinita? Dov'è la logica che mi manca?