Calculating Different Paths on a Grid
In der abgebildeten Rastersituation fragen wir uns, wie viele unterschiedliche Wege Alice von Punkt A nach Punkt B nehmen kann, wenn sie sich nur nach rechts oder nach unten bewegen darf. Um dies zu lösen, verwenden wir die gegebene Regel, dass die Anzahl der Wege zu einem Kreuzungspunkt die Summe der Wege der vorigen Kreuzungspunkte ist.
Beginnen wir damit, die Pfade zu Punkt A mit 1 zu kennzeichnen, weil es nur einen Weg gibt, an diesen Punkt zu gelangen (indem man einfach dort startet). Dann gehen wir systematisch durch jedes Gitterfeld und addieren die Anzahl der Wege, die zu diesem Punkt führen. Das machen wir so, weil Alice entweder von links oder von oben zu jedem Punkt auf dem Gitter gelangen kann.
So erhalten die Punkte direkt rechts von A und direkt unter A jeweils den Wert 1, da man zu diesen Punkten nur auf eine Art gelangen kann.
Schritt für Schritt füllen wir die Tabelle aus, bis wir zu Punkt B kommen. Jedes Feld in einer Zeile oder Spalte erhöht sich um die Summe der Felder oberhalb und links von diesem Feld. Die letzte Zeile und Spalte vor B wird somit die Anzahl der Wege von A zu den Punkten direkt links und oberhalb von B repräsentieren.
Nachdem wir alle Werte hinzugefügt haben, wird das Feld direkt bei B die Gesamtzahl der verschiedenen Pfade von A nach B zeigen.
Ich kann die genauen Zahlen nicht sehen und dir deshalb nicht den genauen Wert für B geben. Aber wenn du der Methode folgst, die ich beschrieben habe, und die Zahlen von links nach rechts und von oben nach unten aufsummierst, wirst du zuerst die Werte in den Gitterpunkten entlang des ersten rechten und unteren Pfades berechnen, bis zu den Schnittpunkten, die B umgeben, und letztendlich wirst du die Anzahl der Wege zu B herausfinden.
Es ist wichtig, dass du mit der ersten Zeile und der ersten Spalte beginnst und schrittweise weitermachst und dabei die Anzahl der Pfade an jedem Punkt aufsummierst. Wenn du dies getan hast, sollte der letzte Wert, den du erhältst – der Wert im Feld an Punkt B – dir sagen, wie viele unterschiedliche Wege Alice nehmen kann.
