Problem 15: Pfade über ein Gitter

Gesucht wird die Anzahl von möglichen Pfaden über ein 20 x 20 Zellen großes Gitter! [das englische Original]

Es wird davon aus gegangen, dass man immer in der oberen linken Ecke eines 2-dimensionalen Gitters startet, ausschließlich nach rechts und unten gehen kann, um letztendlich in der unteren rechten Ecke zu enden. Das angegeben Beispiel zeigt, dass man so für ein 2 x 2 Zellen großes Gitter 6 verschiedene Wege gehen kann.

Der Lösung dieses Problems kann man sich rein mathematisch nähern. Offensichtlich ist, dass man innerhalb eines Weges immer so viele Schritte braucht, wie es Zellen in der Breite plus Zellen in der Höhe gibt. Innerhalb dieses Bereiches gibt es wiederum immer dies selbe Anzahl von Schritten nach links (= die Breite des Gitters) sowie nach unten (=Höhe des Gitters). Daraus lässt sich ableiten, dass die Anzahl der Wege als eine Permutation mit Wiederholung berechenbar ist. Benutzt man die Variablen u für die Schritte nach unten und r für die Schritte nach rechts, er gibt sich diese Formel für die Permutation:


( r + u )! / ( r! * u! )

Für das Beispiel ergibt sich damit die Lösung:


  ( 2 + 2 )! / ( 2! * 2! )
= 4! / 2! / 2!
= 24 / 2 / 2
= 6

So weit, so gut! Versucht man diese Formel allerdings für den allgemeinen Fall bzw. für das gesuchte Gitter zu benutzen, gelangt man schnell in Zahlenbereiche, die nicht mehr nativ darzustellen sind. Schaut man sich allerdings die Variablen genau an, kann man folgende Vereinfachung erkennen:

Vereinfachung der Gleichung für eine Permutation mit Wiederholung
Vereinfachung der Gleichung für eine Permutation mit Wiederholung

Auf das gesuchte Gitter angewendet ergibt sich folgende Gleichung:

Vereinfachte Gleichung für die Permutation von 20 und 20 Elementen
Vereinfachte Gleichung für die Permutation von 20 und 20 Elementen

Man erkennt, dass diese Gleichung sehr einfach mit nur einer Schleife zu berechnen ist. Auch kann man sehen, dass bei unterschiedlicher Höhe und Breite des Gitters die Anzahl der Schleifendurchläufe sinkt:

Vereinfachte Gleichung für eine Permutation von 10 und 3 Elementen
Vereinfachte Gleichung für eine Permutation von 10 und 3 Elementen

Damit ergibt sich folgende triviale Lösung für das Problem 15:

@Override
public String solve() {

   int r=20, d=20;

   int min = ( r < d ) ? r : d;
   int max = ( r > d ) ? r : d;

   long res = 1;

   for( int i=0; i<min; i++ ) {
      res *= ( max + min - i );
      res /= ( 1 + i );
      IO.debugln( "res @ " + i + " => " + res );
   }

   return IO.l2s( res );
}

Den vollständigen Quellcode der Klasse für die Lösung des Problems 15 kann man sich hier anschauen!

<< Problem 14 Übersicht Problem 16 >>

Kommentar verfassen

Willkommen in Nico Dannebergs Netzwerk

%d Bloggern gefällt das: