Witam wszystkich. Otóż na laboratoriach z programowania dostałem zadanie, aby policzyć ilość możliwych dróg w kratce wymiaru m x n. Wiem, że można to policzyć z odpowiedniego wzoru kombinatorycznego, ale prowadzący ćwiczenia powiedział, że nie o to mu chodziło i że chciałby, żeby to było innym sposobem zrobione, tylko sęk w tym, że nie powiedział jakim. Dodam również, że jestem po prostu z tego kiepski i żadne pomysły nie przychodzą mi do głowy. Wszelka pomoc mile widziana, z góry dzięki.
0
1
Pewnie chodzi o to żeby puścić BFSa / DFSa na tych kratkach jako grafie.
0
Pewnie chodzi o to żeby puścić BFSa / DFSa na tych kratkach jako grafie.
A coś więcej? :)
0
Zadaj konkretne pytanie. Co to jest dla ciebie "ilość dróg"? Dowolnej długości? Od punktu X do punktu Y? Z cyklami?
0
Ale dróg z punktu do punktu? Z strony do strony. Teoretycznie nieskończona jeżeli mozesz się cofać.
2
wujnia napisał(a):
Ale dróg z punktu do punktu? Z strony do strony. Teoretycznie nieskończona jeżeli mozesz się cofać.
Droga to lista różnych wierzchołków po jakich należy przejść z wierzchołka początkowego do końcowego. Jedynym przypadkiem jest możliwość tożsamości początku z końcem - taka droga jest nazywana cyklem. Jest skończona ilość dróg w grafie i można je wyznaczyć.
//btw chyba urlop mi się skończył ;)