Hallo,
bezugnehmend auf das Rätsel vom 20.12. im Adventsgewinnspiel 2015 soll dieses kleine Programm die Anzahl der möglichen Wege in einem Rechteckgitter ermitteln.
Ich starte einen Extra-Thread um den AGS 2015-Thread nicht mit einem speziellen Thema zu "belasten".
Durch
Horst_H wurde unter
www.entwickler-ecke.....php?p=697585#697585 eine sehr schöne rekursive Lösung angegeben. Für sehr große Gitter steigt die Zahl der zu durchsuchenden Möglichkeiten stark an, so dass die Rekursion sehr rechenintensiv wird.
Aus diesem Grund greife ich bei meiner Lösung auf die Theorie nach Delannoy und Schröder zurück.
Gegeben ist ein rechteckiges Gitter der Größe a x b.
Gesucht ist die Anzahl aller möglichen Wege vom Punkt (0,0) nach (a,b), wenn ausschließlich Schritte (1,0), (0,1) und (1,1) möglich sind. Nach Delannoy gilt:
D(a,b) = D(a-1,b) + D(a,b-1) + D(a-1,b-1) ; D(0,0) = 1
Fordert man zusätzlich, dass die Gerade b = a nie überschritten werden darf, so beschränken sich die Wege auf ein Dreiecksgitter. Für diese Wege wurde durch Schröder eine mathematische Lösung gegeben.
Das Problem kann durch Sperren von einzelnen Weggabelungen erweitert werden.
Im Programm kann die Größe des Rechteckgitters bis maximal 25 in jeder Richtung eingestellt werden. Weggabelungen können durch linken Mausklick auf einen Gitterpunkt gesetzt oder gelöscht werden. Ebenso kann man zwischen Delannoy-Wegen und Schröder-Wegen wählen.
Schön ist, dass die Berechnung der Wegmöglichkeiten sehr schnell erfolgt.
Beste Grüße
Mathematiker
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein