Wege im Rechteckgitter

Mathematiker · Verfasst: Di 22.12.15 09:28

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 user profile icon

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.
wege

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

$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

Einloggen, um Attachments anzusehen!

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Di 22.12.15 11:09

Hallo,

ich habe es für Lazarus angepasst und alten Ballast wie tdw,Startpos,EndPos entfernt.
Bei Lazarus muss man den Canvas mit passender Farbe vorher füllen, sonst ist der Hintergrund 0== clBlack.
Das Zeichnen habe ich etwas angepasst, es wird ja sonst fast 40% der Linien doppelt gezeichnet.
Man sieht mal wieder , das Zeile und Spalte als Namen irgendwie passender als koordinatenkreuzmässige x,y sind.Warum sollte ich bei maximalem X oben zeichnen und nicht rechts...

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

  b := bitmap.Width;
  h := bitmap.Height;
  x := b div (maxX + 2);
  y := h div (maxY + 2);

  //Damit Lazarus nicht einen schwarzen Hintergrund == 0 nutzt
  with ziel.Brush do
  begin
    Style := bsSolid;
    color := clWindow;
  end;
  ziel.FillRect(ziel.ClipRect);
  //Linien zeichen 
  for i := 1 to maxX do
    for j := 1 to maxY do
    begin
      myLine(i, j, i + 1, j);     // horizontal
      myLine(i, j, i, j + 1);     // vertikal
      myLine(i, j, i + 1, j + 1); // diagonal
      if j = maxy then
        myLine(i, j + 1, i + 1, j + 1); //rechts vertikal
      if i = maxx then
        myLine(i + 1, j, i + 1, j + 1); //oben horizontal
     end;

Gruß Horst

Einloggen, um Attachments anzusehen!

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme