'Taxigeometrie' Rekursiv lösen. [Anzahl kürzester Strecken zwischen zwei Punkten]

[FF]

WIr machen in Info grade Rekursive Programmierung.

Dabei haben wir folgende Aufgabe:
Ein Programm, das die Anzahl der kürzesten Wege zwischen zwei Punkten auf einem Schachbrettförmigen Raster.
http://upload.wikimedia.org/wikipedia/commons/thumb/0/08/Manhattan_distance.svg/300px-Manhattan_distance.svg.png
also praktisch bei sowas. (die grüne Linie ignorieren. die anderen 3 sind mögliche wege. Ermittelt soll die Anzahl von solchen möglichen wegen.)

Dies soll Rekursiv gelöst werden.

Allerdings habe ich nicht den leisesten Schimmer wie das geht.
Wäre euch sehr verbunden, wenn ihr mir nen Ansatz oder besser Die Lösung hier bis heute Abend posten könntet, brauch das für Morgen :D


[ich hab ne lösung, wie man das !rekursiv löst. dabei werden alle möglichen wegen bruteforced, und als 'code' aufgezeichnet, alle die sich unterscheiden, werden gezählt. aber es soll ja eben rekursiv sein........]

[MagicMagor]

Hm.. pseudoCode:


laufeWeg(int startX, int startY) {
if startX != zielX {
laufeWeg(startX+1);
}
if startY != zielY {
laufeWeg(startY+1);
}
if startX == zielX && startY == zielY {
anzahlWege++;
}
}

Das ganze startest du dann mit dem Punkt unten rechts (0,0). Das läuft dann jeden Knoten durch und geht nacheinander alle Möglichkeiten ab. Jedes mal wenn er am Ziel ankommt (und damit den aktuellen Durchlauf beendet) zählt er einen neugefunden Weg dazu.
Da du nur die Koordinaten hochzählst erhälst du automatisch alle kürzesten Wege.

[DFYX]

Anderer Ansatz (In der Zwischenzeit getestet und komplett reineditiert)

#include <cstdlib>
#include <iostream>

using namespace std;

int max_x, max_y;

int anzahlWege(int x, int y)
{
if(x == max_x && y == max_y)
{
return 1;
}

int ret = 0;
if(x < max_x)
{
ret += anzahlWege(x + 1, y);
}
if(y < max_y)
{
ret += anzahlWege(x, y + 1);
}
return ret;
}

int main(int argc, char *argv[])
{
max_x = max_y = 6;
cout << "Anzahl Wege: " << anzahlWege(0, 0) << endl;
return EXIT_SUCCESS;
}

[FF]

unit Unit1;

interface

uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;

type
TForm1 = class(TForm)
Edit1: TEdit;
Button1: TButton;
procedure Button1Click(Sender: TObject);
function AnzahlWege(x,y,end_x,end_y:integer):integer;
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
begin
edit1.text:=inttoStr(anzahlwege(0,0,5,5));
end;

function TForm1.AnzahlWege(x,y,end_x,end_y:integer):integer;
var zahl:integer;
begin
if (x = end_x) and (y = end_y) then
result:=1; // wenn nur 1x1 kästchen
zahl:=0;
if (x < end_x) then
zahl := zahl + anzahlWege(x+1,y,end_x,end_y);
if (y < end_y) then
zahl := zahl + anzahlWege(x,y+1,end_x,end_y);

result:=zahl;
end;

end.


mein delphigeblubber.
leider ist result immer 0.
immer.

[FF]

ok, die lösung war so einfach wie doof.
ich hab den c++ in delphi code umgeschrieben, und demensprechend angepasst.
das return wurde zu result.
was ich nicht wusste, ist, das result die funktion nicht beendet :<
insofern wurde mein zähler immer wieder auf 0 gesetzt.
delphi suckt.

[Crash-Override]

ich hab den c++ in delphi code umgeschrieben
Das war vernünftig :A


delphi suckt.
O.O nein, es ist äußerst praktisch das result nicht beendet (wäre auch insofern dämlich, da es ja nur eine Variablezuweisung ist, nicht wie in C eine funktion. So kann man in Delphi immer schön platz sparen z.B.


function x: Integer;
begin
result := 0;
if x then
result := 1;
end;

oder so. Jedenfalls wenn du nach Result beenden willst schau dir mal den "exit"-Befehl an.

[FF]

function x: Integer;
begin
result := 0;
if x then
result := 1;
end;


wäre woander


function x: Integer;
{
if x
return 1;
else
return 0;
}


oder so in der art.


aber egal, danke nochmal an dfyx und magor, funzt ja jetzt.