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

[MagicMagor]

Hm.. pseudoCode:

Code:

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)

Code:

#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]

Code:

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

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.

Code:

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

Code:

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.