Entwickler-Ecke

Open Source Projekte - Wege im Rechteckgitter


Mathematiker - Di 22.12.15 09:28
Titel: Wege im Rechteckgitter
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 iconHorst_H wurde unter http://www.entwickler-ecke.de/viewtopic.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

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


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


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


Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!