www.mikrocontroller.net

Forum: PC-Programmierung Fragen zur Rekursion


Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Leute!

Ich hab heute ein Programm geschrieben, dass mir die Fakultät für 
unterschiedliche Werte mittles Rekursion berechnet. Hier der Code:
#include<iostream>
using namespace std;



int fakultaet(int n)
{
  if(n == 1)
  {
    return 1;
  }
  else
  {
    return n * fakultaet(n-1);
  }
}



int main()
{
  int n;
  cin >> n;

  cout << fakultaet(n) << endl;



system("pause");
return 0;
}

Der Code funktioniert zwar, aber ich weiß an einer Stelle nicht so genau 
warum.

Der Benutzer gibt in "n" z.B. die Zahl 4 ein. Dann springt das Programm 
zur Funktion "fakultaet". Jetzt gehts weiter in die if-Abfrage. Da n=4 
ist wird wohl während der Prüfung von n == 1 ein "falsch" rauskommen. Es 
geht weiter in den else-Zweig. Dort wird dann 4*fakultaet(4-1) 
zurückgegeben. Hier taucht nun schon meine erste Frage auf:

An welche Stelle im Code wird das "4*fakultaet(3)" zurückgegeben?

Da ich mich ja in der Funktion fakultaet befinde, wird der return-Wert, 
also 4*fakultaet(3), wieder in den main-Teil zurückgegeben, oder?

Tja, ab hier weiß ich dann schon nicht mehr so genau weiter. 
Normalerweise müsste sich doch die Funktion fakultaet wieder aufrufen. 
Nun aber doch mit einem n=n-1=4-1=3, oder? Aber wo wird da n-1 
berechnet? Wenn ich nach dem ersten return-Wert die Zeile in der cout 
steht näher anschaue, dann steht doch dann: cout << 
fakultaet(fakultaet(n-1)). Spätestens ab hier verlassen mich dann 
wirklich alle guten Geister!

Könnt ihr mir das erklären?

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Probier's mal anders herum:

Für n=1 kann man leicht sehen, dass die Funktion den richtigen Wert
zurückgibt, es wird nämlich nur der if-Zweig ausgeführt.

Was passiert bei n=2? Jetzt wird der else-Zweig ausgeführt und
n*fakultaet(n-1), also 2*fakultaet(1) zurückgegeben. Dass fakultaet(1)
richtig berechnet wird, haben wir ja oben schon gesehen.

Was passiert bei n=3? Jetzt wird 3*fakultaet(2) zurückgegeben. Dass
fakultaet(2) richtig berechnet wird, haben wir ja oben schon gesehen.

...

Ich würde übrigens if(n == 1) durch if(n == 0) ersetzen. Dann liefert
die Funktion auch für n=0 das richtige Ergebnis, das nach Definition 1
ist.

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Normalerweise müsste sich doch die Funktion fakultaet wieder aufrufen.

Das tut sie auch. Nämlich genau hier.
return n * fakultaet(n-1);

Das kennzeichnende ist, dass im Rumpf einer Funktion wieder ein Aufruf 
dieser Funktion erfolgt. Schreibt man einen Ausdruck mit einem 
Funktionsnamen und einer Parameterliste, so ist das ein Aufruf dieser 
Funktion. Insofern ist da kein Unterschied zu
 cout << fakultaet(n) << endl;

in main.

>Aber wo wird da n-1 berechnet?

Auch genau hier:
return n * fakultaet(n-1);

Bevor die Funktion aufgerufen wird, werden die Ausdrücke berechnet die 
sich in der Parameterliste befinden.

Autor: andz (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Das ist das wunder der Rekursion...zeichnes dir mal genau schritt für 
schritt auf was passiert, erst vorwärts bis n==1, dann wieder rückwärts 
mit den ganzen rückgabewerten, dann wirds dir vlt klar

gruß

andz

Autor: eskimo (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
andz schrieb:
> Das ist das wunder der Rekursion...

Um Rekursion zu verstehen, muss man zunächst Rekursion verstehen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Hi Leute!
>
> Ich hab heute ein Programm geschrieben, dass mir die Fakultät für
> unterschiedliche Werte mittles Rekursion berechnet. Hier der Code:

>
> Der Code funktioniert zwar, aber ich weiß an einer Stelle nicht so genau
> warum.

Dann hast du es nicht selbst geschrieben :-)

2 Möglichkeiten:
* lass Rekursion noch links liegen.
  Das ist noch nichts für deinen Level

* Schreib dein Programm um, so dass es Ausgaben macht.
  So zb
#include<iostream>
using namespace std;

void doIndent( int n )
{
  for( int i = 0; i < n; ++i )
    cout << ' ';
}

int fakultaet(int n, int indent)
{
  doIndent( indent );
  cout << "Gesucht die Fakultaet von " << n << endl;

  if(n == 1)
  {
    doIndent( indent );
    cout << "das ist einfach, die ist 1" << endl;
    return 1;
  }

  else
  {
    doIndent( indent );
    cout << "dazu berechne ich die Fakultaet von " << n-1 << endl;

    int tmp = fakultaet(n-1, indent + 2);;

    doIndent( indent );
    cout << "also: Die Fakultaet von " << n-1 << " ist gleich " << tmp << endl;
    doIndent( indent );
    cout << "daher ist die Fakultaet von " << n << " gleich " << n << "*" << tmp << endl;

    tmp = n * tmp;

    doIndent( indent );
    cout << "das ergibt " << tmp << endl;

    return tmp;
  }
}



int main()
{
  int n;
  cin >> n;

  cout << fakultaet(n, 0) << endl;

system("pause");
return 0;
}

Jetzt erzählt dir das Programm, wann es was warum berechnet. Jede 
Einrückstufe im Output entspricht einem Aufruf der Funktion fakultaet

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Doch, doch, das Programm ist meins. Man kann auch durch sukzessives 
Ausprobieren auf die Lösung solch, ja eigentlich einfacher "Probleme" 
kommen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:

> Normalerweise müsste sich doch die Funktion fakultaet wieder aufrufen.
> Nun aber doch mit einem n=n-1=4-1=3, oder? Aber wo wird da n-1
> berechnet? Wenn ich nach dem ersten return-Wert die Zeile in der cout
> steht näher anschaue, dann steht doch dann: cout <<
> fakultaet(fakultaet(n-1)). Spätestens ab hier verlassen mich dann
> wirklich alle guten Geister!

Du hast den Mechanismus eines Funktionsaufrufs immer noch nicht 
verstanden.

wenn da steht

  return n * fakultaet(n-1);


dann wird n-1 AUSGEWERTET
n ist bei dir 4, also kommt da 3 raus.
Mit diesen 3 wird die Funktion fakultaet aufgerufen. Die Funktion 
rechnet dann was aus und liefert einen Wert.
Damit ist der Teil hier

  return n * fakultaet(n-1);
             **************

erledit. Was auch immer die Funktion für 3 zurück geliefert hat, es wird 
mit 4 (weil n ja 4 war) multipliziert und dieses Ergebnis, der 
Zahlenwert ist dann der Wert den dieser Funktionsaufruf zurückliefert.

Das was du dir hier zusammenreimst

> dann steht doch dann: cout << fakultaet(fakultaet(n-1)).

das findet nie statt!

Funktionen werden aufgerufen, indem die Werte für die Argumente bestimmt 
werden, mit diesen Werten wird dann die Funktion aufgerufen. Punkt.
Da gibt es keine Substitution, so wie das dein "dann steht doch da..." 
vermuten lässt.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Doch, doch, das Programm ist meins. Man kann auch durch sukzessives
> Ausprobieren auf die Lösung solch, ja eigentlich einfacher "Probleme"
> kommen.

Dann bist du ein Wunderkind. Was ich ehrlich bezweifle. Denn im 
Regelfall kriegen 99% aller Neulinge eine Rekursion durch ausprobieren 
nicht hin.

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Man kann auch durch sukzessives Ausprobieren auf die Lösung solch, ja
> eigentlich einfacher "Probleme" kommen.

Nun ja. Eigentlich ist das kein "Problem".

Das eine ist, dass man wissen muss, das Ausdrücke auch Funktionsaufrufe 
enthalten können. Ob das eine Funktion sich selbst aufruft ist dann ein 
weiterer Aspekt der aus dem ersten folgt.

Dann, die Frage, wie mit Ausdrücken in Parameterklammern umgegangen 
wird. Die verhalten sich im Prinzip genaus wie Ausdrücke in main, nur 
das dann das Ergebnis an die Funktion übergeben wird.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@kbuchegg:

"Die Funktion rechnet dann was aus und liefert einen Wert."

Macht das Programm dann folgendes:

fak(4)=4*fak(3)=4*3*fak2)=4*3*2*fak(1)=4*3*2*1 = 24

Irgendwie muss ja dann aus fak(3)=3 folgen, damit im nächsten Schritt 
dann 4*3*fak(2) stehen kann, oder?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vielleicht hilft dieser Einwurf noch zum besseren Verständnis:

Ein Funktionsaufruf hat einen Satz Parameter (meist), sowie
einen Rückgabewert, sowie einen Satz seiner lokalen (automatischen,
nicht static) Variablen.

Dies zusammengenommen (Parameter, Rückgabewert, lokale Variablen)
gehört jetzt aber nicht statisch zu einer Funktion, sondern
existiert genau dann, wenn die Funktion aktiv ist, also aufgerufen
wurde und sich noch nicht beendet hat.
Ohne Funktionsaufruf keine Parameter, keine lokalen Variablen,
kein Rückgabewert.

Ruft sich eine Funktion jetzt aber selbst wieder auf, dann
existiert dieser ganze Satz mehrfach:
Ab dem ersten Aufruf von fakultaet() in main() einmal,
beim rekursiven Aufruf von fakultaet() aus in ein weiteres
fakultaet() existiert der Satz ein zweites Mal, bei einem
weiteren Aufruf eind drittes Mal usw..
Mit jedem Aufruf kommt ein solcher Satz dazu, mit jedem
return verschwindet wieder einer.

Ein solcher Satz heißt gelegentlich auch "Instanz einer
Funktion" oder "stack frame".
(Genau genommen gehört noch etwas mehr dazu, wie bspw.
die Rücksprungadresse und ein framepointer, aber die sieht
man nicht von C aus.)

Wirklich genutzt wird immer nur der letzte Satz, die
anderen liegen etwas abseits, bis die aktuelle
Funktion (-sintanz) sich beendet.

Mit dieser Vorstellung bewaffnet kann man sich tatsächlich
mit einem Blatt Papier und einem Stift durch fakultaet(4)
zeilenweise durcharbeiten und alle Parameter, Variablen
und Rückgabewerte aufzeichnen.
Sehr lehrreich!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> @kbuchegg:
>
> "Die Funktion rechnet dann was aus und liefert einen Wert."
>
> Macht das Programm dann folgendes:
>
> fak(4)=4*fak(3)=4*3*fak2)=4*3*2*fak(1)=4*3*2*1 = 24

Darauf läuft es raus.
Aber so wird das nicht ausgerechnet.

Lass das Programm laufen, dass ich dir gepimpt habe. Das erzählt dir, 
wie es arbeitet

>
> Irgendwie muss ja dann aus fak(3)=3 folgen, damit im nächsten Schritt
> dann 4*3*fak(2) stehen kann, oder?

Du gehst wie ein Mathematiker ran, der Ausdrücke substituiert.
Genau das passiert NICHT!


+--- fak(4) = 4*fak(3)
|
|    +--- Neuer Funktionsaufruf für fak(3)
|    +--- fak(3) = 3*fak(2)
|    |
|    |   +--- Neuer Funktionsaufruf für fak(2)
|    |   +--- fak(2) = 2*fak(1)
|    |   |
|    |   |   +---     Neuer Funtionsaufruf für fak(1)
|    |   |   +---     fak(1) = 1
|    |   |
|    |   +--- zurück beim Problem fak(2). fak(1) ist jetzt bekannt,
|    |   +--- nämlich 1
|    |   +--- daher
|    |   +--- fak(2) = 2*fak(1) = 2 * 1 = 2
|    |
|    +--- zurück beim Problem fak(3)
|    +--- fak(3) = 3*fak(2), fak(2) ist bekannt, nämlich 2
|    +--- daher fak(3) = 3*fak(2) = 3 * 2 = 6
|
+---   zurück beim Problem fak(4)
+---   fak(4) = 4*fak(3), fak(3) ist bekannt, nämlich 6
+---   daher fak(4) = 4*fak(3) = 4 * 6 = 24

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hab jetzt mal dein gepimptes Programm ausgeführt. Ich hab mir das 
jetzt angeschaut und hab dazu noch eine Frage: Woher weiß dein bzw. ja 
auch mein Programm, dass, die Fakultät(1)=1 ist? Kommt das durch die 
if-Abfrage? Ist an der Stelle dann n=1?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ja

Wobei die Frage jetzt kein klares Zeichen dafür ist, daß du es beim 
Schreiben verstanden hattest :-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Noch ein anderer Ansatz

Stell dir vor du könntest dich Klonen. Beliebig oft.

Ihr alle stellt euch nebeneinaner auf.

Und da ihr alle Klone seid, verfügt ihr alle über dasselbe Wissen.
Nämlich:
* Die Fakultät von 1 sei gleich 1
* Um die Fakultät einer Zahl n zu berechnen, muss die Fakultät von
  n-1 bekannt sein. Die wird dann mit n multipliziert.

Nur wie kriegt man die Fakultät von n-1?
Ganz einfach. Du hast einen Klon neben dir stehen, den fragst du ganz 
einfach.

Ich frage also den ersten in der Kette:
Was ist die Fakultät von 4?
Der erste Tbias denkt ein wenig nach und entscheidet, dass er dazu die 
Fakultät von 3 kennen müsste. Die weiß er nicht, aber er weiß wen er 
fragen kann. Nämlich den Tobias rechts neben ihm.
Also fragt er ihn (Tobias#2): Was ist die Fakultät von 3?
Der denkt wieder nach und beschliesst, den Tobias neben sich, Tobias#3 
um die Fakultät von 2 zu fragen
Tobias#3 hält sich wieder an die Regel, dass er die Fakultät nur 
berechnen kann, wenn er die Fakultät von 1 kennen würde. Also fragt er 
Tabias#4 darum: Was ist die Fakultät von 1?

Tobias#4 kramt in seinen Regeln und findet raus, dass fak(1) gleich 1 
ist. Heureka, er hat eine Lösung!
Die teilt er auch sofort Tobias#3 mit, den der hatte ihn ja nach fak(1) 
gefragt.
Tobias#3 hatte die Aufgabe fak(2) zu berechnen und dazu brauchte er 
fak(1). Den Wert hat er mitlerweile von Tobias#4 bekommen. Nälich 1. 
Hoch erfreut kann er jetzt mit seiner Regel die fak(2) ausrechnen und 
das Ergebnis nach links weiterflüstern. Denn Tobias#2 hatte ihn ja um 
diese Fakultät gefragt.

Tobias#2 bekommt jetzt also die Information, dass die Fakultät von 2 
gleich 2 sei. Das passt ihm gut, den damit kann er seine Aufgabe lösen, 
fak(3) zu berechnen. 2*3 gleich 6 und das wiederrum gibt er an seinen 
linken Nachbarn weiter, Tobas, der ihn ja darum gefragt hatte.

Der erste Tobias in der Kette, kennt jetzt die Fakultät von 3 und kann 
damit die Fakultät von 4 berechnen. 4 * 6 gleich 24

Laut und stolz verkündert der daher das Ergebnis: 24

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Ich hab jetzt mal dein gepimptes Programm ausgeführt. Ich hab mir das
> jetzt angeschaut und hab dazu noch eine Frage: Woher weiß dein bzw. ja
> auch mein Programm, dass, die Fakultät(1)=1 ist? Kommt das durch die
> if-Abfrage? Ist an der Stelle dann n=1?

Wie würdest du umgangssprachlich

  if(n == 1)
  {
    return 1;
  }

interpretieren, wenn n den Wert innerhalb einer Funktion enthält, für 
den die Funktion die Fakultät berechnen soll?

Heck. Das steht doch genauso auch in deinem Programm. Ich hab doch 
nichts anderes gemacht, als in dein Programm noch ein paar 
Ausgabeanweiszungen einzubauen.
ok dazu musste ich das

    return n*fakultaet(n-1);

in einzelne Schritte zerlegen, damit ich zwischen die Schritte 
Textausgaben reinpflanzen kann. Aber im Grunde ist es immer noch dein 
Programm, so wie du das geschrieben hast!

Ob ich schreibe

   return n*fakultaet(n-1);

oder
   int tmp = n*fakultaet(n-1);
   return tmp;

das ändert doch nichts!

Und wenn ich letzters dann auch noch auseinandernehme

   int fak = fakultaet(n-1);
   int tmp = n * fak;
   return tmp;

dann ist das immer noch dasselbe. Nur dass ich jetzt Ausgabeanweisungen 
dazwischen reinklenmmen kann.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also, ich muss euch wirklich bewundern, dass ihr mit so belä******* 
Leuten wie z.B. so lange gedult habt. Eure Beispiele sind echt super. 
Ich denke auch, dass ich das jetzt für die Fakultät auch verstanden 
habe, aber ich weiß, wenn jetzt ein anderes Problem zur Rekursion kommt, 
dann kack ich wieder genauso ab wie bei den ganzen anderen Aufgabe die 
ich hier schon gestellt habe...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Also, ich muss euch wirklich bewundern, dass ihr mit so belä*******
> Leuten wie z.B. so lange gedult habt. Eure Beispiele sind echt super.
> Ich denke auch, dass ich das jetzt für die Fakultät auch verstanden
> habe, aber ich weiß, wenn jetzt ein anderes Problem zur Rekursion kommt,
> dann kack ich wieder genauso ab wie bei den ganzen anderen Aufgabe die
> ich hier schon gestellt habe...

Na dann, musst du üben.

Die Fibonacci Zahlen definieren sich so
Fib(0) = 0
Fib(1) = 1
Fib(n) = Fib(n-1) + Fib(n-2)    ; für n > 1

Schreiben sie ein rekursives Programm zum Berechnen von Fibonacci Zahlen 
und berechnen sie Fib(6). Es genügt wenn das Programm die Zahlen einfach 
nur berechnet. Optimierungen sind nicht notwendig.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für dein Beispiel.

Ich werds gleich mal probieren, ok?

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hm, also das hab ich jetzt ziemlich gut gelöst bekommen:

Mein Code:
#include<iostream>
using namespace std;


int fib(int n)
{
  if(n == 0)
  {
    return 0;
  }

  if(n == 1)
  {
    return 1;
  }
  else
  {
  return fib(n-1) + fib(n-2);
  }
}


int main()
{
  int n;
  cin >> n;

  cout << fib(n);


system("pause");
return 0;
}


Hast du noch ein Beispiel? Vielleicht in der Art nur etwas schwieriger?

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Hast du noch ein Beispiel? Vielleicht in der Art nur etwas schwieriger?

Grösster gemeinsamer Teiler?

ggt(a,0) = a
ggt(a,b) = ggt(b, a mod b) für b != 0

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So, ich denke, der Code sollte den GgT Berechnen:
#include<iostream>
using namespace std;


int ggt(int a, int b)
{
  if(b == 0)
  {
    return a;
  }
  else
  {
  return ggt(b, (a % b));
  }
}


int main()
{
  int a, b;
  cin >> a;
  cin >> b;

  cout << ggt(a,b);


system("pause");
return 0;
}


Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich hab noch eine Aufgabe selber gefunden:

Ich soll nun durch Rekursive Programmierung mit dem Grundsatz "Teile und 
Herrsche" eine Min-Max-Suche durchführen. Ich darf ein short Array mit 
fest definierter Länge selbst mit unterschiedlichen Zahlen belegen. Aus 
diesem Array soll ich dann den kleinsten und größten Wert herausfinden. 
Den Min-Wert und den Max-Wert soll ich dann in einem Long ausgeben. In 
diesem Long soll in den oberen 16Bit der Max-Wert und in den unteren 
16Bit soll der Min-Wert stehen. Ich hab hier mal angefangen zu 
programmieren:
#include<iostream>
using namespace std;



//minmax
long minmax(short array[], int len)
{
  short teil1[3], teil2[3];
  
  cout << "Teil1: ";

  for(int i=0; i<3; i=i+1)
  {
    teil1[i] = array[i];
    cout << teil1[i];
  }

  cout << endl << "Teil2: ";

  for(int j=3; j<6; j=j+1)
  {
    teil2[j-3] = array[j];
    cout << teil2[j-3];
  }

  minmax(teil1, teil2);
}




int main()
{
    short array[6] = {4,3,7,2,1,6};
    int len = 6;
    long ergebnis;
    

    minmax(array, len);



system("pause");
return 0;
}

Das Problem ist nur, dass ich jetzt nicht mehr weiter weiß, wie ich 
meine Funktion (besser gesagt, die for-Schleifen) so "flexibel" mache, 
dass sie mir dann auch noch "teilen" wenn die Größe des array nur noch 
bei 3 ist...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Hm, also das hab ich jetzt ziemlich gut gelöst bekommen:

OK.

> Hast du noch ein Beispiel? Vielleicht in der Art nur etwas schwieriger?

Es gibt noch jede Menge. Das Problem ist nur: es darf auch nicht zu 
schwer sein.

Aber da du ja mit Arrays auf Kriegsfuss stehst :-) wie wärs damit:

Es gibt da ein 2D Array mit einem Labyrinth. Jedes Element im Labyrinth 
wird durch einen Code gekennzeichnet

#  ist eine Mauer
M  ist die Maus
K  ist der Käse


richte dir ein 2D char Array [10][10] ein mit diesem Inhalt


[code]
    0123456789
 0  ##########
 1  # #  #K  #
 2  # # #### #
 3  #   #    #
 4  # # # ####
 5  ### # ## #
 6  #   #    #
 7  ## ##### #
 8  #        #
 9  ##########
[code]

Die Maus steht an Position [1][1], also hier
   0123456789
 0  ##########
 1  #M#  #K  #
 2  # # #### #
 3  #   #    #
 4  # # # ####
 5  ### # ## #
 6  #   #    #
 7  ## ##### #
 8  #        #
 9  ##########
[code]

schreiben sie ein rekursives Programm, das die Frage beantwortet: Wie 
kommt die Maus zum Käse?

Die Maus geht nach einer einfachen Strategie vor

   * an einem Feld mit einer Mauer kann ich nicht sein
   * bin ich am Feld mit dem Käse, Hurra! ich melde den
     Erfolg an die aufrufende Funktion
   * probiere es nach links, rechts, oben, unten
     Führt ein Schritt in diese Richtung nicht zum Erfolg
     dann wird die jeweils nächste Richtung probiert.
     Gibt es keine Richtung mehr, dann melde der aufrufenden
     Funktion, dass ich kein Glück hatte.

Die rekursive Funktion hat diese Signatur

   int  SchrittNach( int x, int y )
   {
      ....
   }

Der Return Wert ist die Rückmeldung, ob dieser Schritt zum Käse führt.
0 ... kein Erfolg, so gehts nicht zum Käse
1 ... Erfolg, Käse gefunden!

Als Ausgabe genügt es, die Feldnummern der betretenen Felder auszugeben, 
wobei es keine Rolle spielt, wenn diese Feldnummern in umgekehrter 
Reihenfolge ausgegeben werden in der die Maus eigentlich gehen müsste.

Wenn im obigen die Ausgabe lautet

[code]
    0123456789
 0  ##########
 1  #M#  #K  #
 2  # # #### #
 3  #   #    #
 4  # # # ####
 5  ### # ## #
 6  #   #    #
 7  ## ##### #
 8  #        #
 9  ##########
[code]

 1 7
 1 8
 2 8
 3 8
 3 7
 3 6
 3 5
 4 5
 5 5
 6 5
 6 6
 6 7
 6 8
 7 8
 8 8
 8 7
 8 6
 8 5
 8 4
 8 3
 7 3
 6 3
 6 4
 5 4
 4 4
 4 3
 3 3
 3 2
 3 1
 2 1
 1 1

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also ich werd dann mal die Maus machen:

Ich mach jetzt mal das hier:

"richte dir ein 2D char Array [10][10] ein mit diesem Inhalt"

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:

> Das Problem ist nur, dass ich jetzt nicht mehr weiter weiß, wie ich
> meine Funktion (besser gesagt, die for-Schleifen) so "flexibel" mache,
> dass sie mir dann auch noch "teilen" wenn die Größe des array nur noch
> bei 3 ist...

Du hast dir kein rekursives Prinzip für deine Aufgabe überlegt.

Bei dieser Art Aufgaben lautet der Ansatz immer:

Wann ist das Problem besonders einfach?
Wie kann ich mit der Kentnis der Lösung eines etwas einfacheren Problems 
mein etwas schwierigere Problem lösen?

Nun in einem Array den kleinsten/größten Wert zu finden ist dann 
besonders einfach, wenn das Array nur 1 Element groß ist. Denn dann ist 
dieses 1 Element offensichtlich gleichzeitig sowohl das kleinste als 
auch das größte Element in diesem Array (mit Länge 1)

Das ist der sog. "Trivialfall"

Der schwierigere Fall sieht so aus:
Gegeben 1 Array mit Länge n
Dieses Array kann ich in 2 Teile teilen, zb in der Mitte
Ich hab also 2 Teilarrays von 0 bis n/2 (m Elemente) und von n/2 +1 bis 
n (k Elemente)
    |<--------- n ------->|
 
    * * * * * * * * * * * *

    |<--- m -->|<-- k --->|

Wenn ich nun Minimum und Maximum von m
als auch Minimum und Maximum von k kennen würde

DANN kann ich auch ganz leicht Minimum und Maximum von n ausrechnen.
Denn min(n)  = min( min(m), min(k) )
und  max(n)  = max( max(m), max(k) )

mit anderen Worten das Minimum von n ist der kleinere der beiden Werte: 
Minimum von m  und  Minimum von k
und das Maximum von n ist der größere der beiden Werte: Maximum von m 
und Maximum von k

Der Charm rekursiver Lösungen besteht darin, dass meistens nicht viel 
gerechnet wird :-) Man kennt eine triviale Lösung und ein Rezept, wie 
man den 'Schwierigkeitsgrad' sukzessive zurückdrehen kann sowie ein 
Rezept wie man das schwierigere Problem mithilfe des leichteren Problems 
lösen kann.

Bei der Fakultät war der Trivialfall
"Die Fakultät von 1 ist 1"

das Rezept um das schwierige Problem zu vereinfachen, ist nicht die 
Fakultät von n zu berechnen sondern die Fakultät von n-1.
Kennt man die Lösung für n-1 dann kann man damit das 'schwierigere' 
Problem, die Fakultät von n zu berechnen, lösen.

"Die Fakultät von n ist n mal die Fakultät von n-1"

Und da das rekursiv passiert, wird dadurch sukzessive das Problem immer 
einfacher, bis man irgendwann beim Trivialfall angelangt ist. Dann geht 
alles rückwärts und mit dem zweiten Teil des Rezepts baut sich dann aus 
den einfachen Lösungen rückwärts die schwierigere Lösung auf.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst du mir sagen was an diesem Code falsch ist?
#include<iostream>
using namespace std;



int main()
{


  int i, j;
    char labyrinth[10][10];
  
  labyrinth[10][10] = {{"##########"},{"# #  #K  #"},{"# # #### #"},{"#   #    #"},{"# # # ####"},{"### # ## #"},{"#   #    #"},{"## ##### #"},{"#        #"},{"##########"}};


  for(i=0; i<10; i=i+1)
  {
    cout << endl;
    for(j=0; j<10; j=j+1)
    {
      cout << labyrinth[i][j];
    }
  }


system("pause");
return 0;
}

Autor: Martin (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Ich denke auch, dass ich das jetzt für die Fakultät auch verstanden
> habe, aber ich weiß, wenn jetzt ein anderes Problem zur Rekursion kommt,
> dann kack ich wieder genauso ab wie bei den ganzen anderen Aufgabe die
> ich hier schon gestellt habe...Beitrag melden | Bearbeiten | Löschen |

Hallo,

ich habe noch von einer anderen rekursive Rechenvorschrift gehört, die 
heißt 'Ackermann-Funktion'. Dabei kackt allerdings der Computer ab, 
sobald man etwas größere Zahlen einsetzt ...

Gruß,
Martin


ack (0,m) = m + 1
ack (n, 0) = ack (n-1, 1)
ack (n, m) = ack (n-1, ack (n, m-1))

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kannst Du vielleicht erstmal schreiben, wie Du darauf kommst, dass an 
dem Code was falsch ist?

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Weil mir beim compilieren Vs 2010 das hier ausspuckt:

Fehler  1  error C2059: Syntaxfehler: '{'  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  1  aufgabe2
Fehler  2  error C2143: Syntaxfehler: Es fehlt ';' vor '{' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  1 
aufgabe2
Fehler  3  error C2143: Syntaxfehler: Es fehlt ';' vor '}' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  1 
aufgabe2
Fehler  4  error C2143: Syntaxfehler: Es fehlt ';' vor ',' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  1 
aufgabe2
Fehler  5  error C2143: Syntaxfehler: Es fehlt ';' vor ',' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  1 
aufgabe2
Fehler  6  error C2059: Syntaxfehler: ','  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  1  aufgabe2
Fehler  7  error C2059: Syntaxfehler: 'for'  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1  aufgabe2
Fehler  8  error C2143: Syntaxfehler: Es fehlt ')' vor ';' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1 
aufgabe2
Fehler  9  error C2143: Syntaxfehler: Es fehlt ';' vor '<' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1 
aufgabe2
Fehler  10  error C4430: Fehlender Typspezifizierer - int wird 
angenommen. Hinweis: "default-int" wird von C++ nicht unterstützt. 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1 
aufgabe2
Fehler  11  error C4430: Fehlender Typspezifizierer - int wird 
angenommen. Hinweis: "default-int" wird von C++ nicht unterstützt. 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1 
aufgabe2
Fehler  12  error C2086: 'int i': Neudefinition  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1  aufgabe2
Fehler  13  error C2059: Syntaxfehler: ')'  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  15  1  aufgabe2
Fehler  14  error C2143: Syntaxfehler: Es fehlt ';' vor '{' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  16  1 
aufgabe2
Fehler  15  error C2447: '{': Funktionsheader fehlt - Parameterliste im 
alten Stil?  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  16  1  aufgabe2
Fehler  16  error C4430: Fehlender Typspezifizierer - int wird 
angenommen. Hinweis: "default-int" wird von C++ nicht unterstützt. 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  25  1 
aufgabe2
Fehler  17  error C2365: "system": Erneute Definition; vorherige 
Definition war "Funktion".  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  25  1  aufgabe2
Fehler  18  error C2440: 'Initialisierung': 'const char [6]' kann nicht 
in 'int' konvertiert werden  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  25  1  aufgabe2
Fehler  19  error C2059: Syntaxfehler: 'return'  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  26  1  aufgabe2
Fehler  20  error C2059: Syntaxfehler: '}'  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  27  1  aufgabe2
Fehler  21  error C2143: Syntaxfehler: Es fehlt ';' vor '}' 
c:\users\tobias mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  27  1 
aufgabe2
Fehler  22  error C2059: Syntaxfehler: '}'  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  27  1  aufgabe2
  23  IntelliSense: Es wurde ein Ausdruck erwartet.  c:\users\tobias 
mehrl\desktop\aufgabe2\aufgabe2\aufgabe2.cpp  12  23  aufgabe2

Autor: Rolf Magnus (rmagnus)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Kannst du mir sagen was an diesem Code falsch ist?
> labyrinth[10][10] = {{"##########"},{"# #  #K  #"},{"# # #### #"},{"#   #    #"},{"# # # ####"},{"### # ## #"},{"#   #    #"},{"## ##### #"},{"#        #"},{"##########"}};

Seufz

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich will eine 10x10 Feld. Also schreib ich bei der Deklaration:

char labyrinth[10][10];

Das ist doch nicht falsch, oder etwa schon wieder?

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rolf Magnus schrieb:
> /Seufz/
Ja.

@Tobias Mehrl (bandchef)
Wolltest du dir nicht ein C-Buch kaufen? So langsam wird das wirklich 
nervig mit deinen ewigen Grundlagenfragen welche in jedem Buch 
beantwortet werden!!! Jetzt postet du schon wieder eine solche Anfrage 
obwohl die letzte ( Beitrag "Array als Parameter in einer Funktion" ) 
noch nicht geklärt ist.

WIR SIND NICHT DAZU DA DIR DIE GRUNDLAGEN VON C ZU ERKLÄREN!!!

Und unterschätz die Sache mit dem Arbeitgeber nicht die ich im 
Array-Thread ansprach, das Internet vergisst nichts!

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Aber warum funktioniert dann das hier?
#include<iostream>

using namespace std;

int main()
{
  char maze[20][21] = {
    "####################",
    "# # # # ###   # #  #",
    "# # # # #   # # # ##",
    "#   # # # ### # #  #",
    "### # # #   #   ## #",
    "#   # #   # # #    #",
    "# ### # ##### # # ##",
    "# #   # # # ### #  #",
    "# # ###   #  #  ## #",
    "#   # ### ## # #   #",
    "### # # # #  ### # #",
    "# # ###      # # # #",
    "#   # # ###### # # #",
    "# ###     #    # # #",
    "# #   ### # ## ### #",
    "#   # # # # #    # #",
    "### # # ### # #### #",
    "#     # # #        #",
    "# #####  F  # #### #",
    "####################"
  };
 
    return 0;
 }
 

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nun. Die Fehlermeldung bezieht sich ja nicht auf die Deklaration, oder?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Aber warum funktioniert dann das hier?

Tobias Mehrl schrieb:
> Ich will eine 10x10 Feld. Also schreib ich bei der Deklaration:
>
> char labyrinth[10][10];
>
> Das ist doch nicht falsch, oder etwa schon wieder?

Das ist richtig.

Aber:

Arrays kann man nicht zuweisen.
Das hier
labyrinth[10][10] = {{"##########"},{"# #  #K  #"},{"# # #### #"},{"#   #    #"},{"# # # ####"},{"### # ## #"},{"#   #    #"},{"## ##### #"},{"#        #"},{"##########"}};

ist der Versuch einer Zuweisung, wenn ich mir die [10][10] mal großzügig 
wegdenke.

Arrays können initialisiert werden!
#include<iostream>
using namespace std;

int main()
{
  int i, j;
  char labyrinth[10][10] = {
       {"##########"},
       {"# #  #K  #"},
       {"# # #### #"},
       {"#   #    #"},
       {"# # # ####"},
       {"### # ## #"},
       {"#   #    #"},
       {"## ##### #"},
       {"#        #"},
       {"##########"}
  };


  for(i=0; i<10; i=i+1)
  {
    cout << endl;
    for(j=0; j<10; j=j+1)
    {
      cout << labyrinth[i][j];
    }
  }


system("pause");
return 0;
}

Siehst du. Und genau aus dem Grund bin ich ehrlich gesagt unglücklich 
damit, dass du dich an Rekursionen versuchst.
Du hast noch so viel, was viel wichtiger wäre. Rekursionen sind etwas, 
wenn man nach dem ersten Jahr eine gewisse Grundsicherheit erlangt hat.
Dazu gehört auch der Unterschied zwischen Initialisierung und Zuweisung.
Dazugehört noch jede Menge anderes Zeug. Massenhaft.
zb Parameter passing
zb Strukturen
zb komplexere Datenstrukturen
zb File Handling
zb dynamisches Speichermanagement

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Genau. Kannst drei Worte Japanisch und willst schon Haikus schreiben. So 
geht das nicht.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Es gibt da ein 2D Array mit einem Labyrinth.

Ich hatte mal an der Uni (ca. 1984 oder 1985) eine ähnliche Aufgabe:
Gegeben ist ein Labyrinth von der Standardeingabe mit Leerzeichen,
man durch kann, und * für Mauern.
Am oberen und unteren Ende ist je eine Öffnung, und gesucht ist ein
Weg, als Zusatzaufgabe der kürzeste Weg.

Dafür habe ich den Lösungsquelltext noch hier liegen, siehe
http://mfgkw.dyndns.org/lab.jpg

Was die Sache etwas spannender macht ist die Tatsache, daß es
da ohne Rekursion gehen musste :-)

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Also gut Leute. Nochmal von vorne:

Der Code funktioniert nicht:
#include<iostream>
using namespace std;

int main()
{
  int i, j;
  char labyrinth[10][10] = {
       "##########",
       "# #  #K  #",
       "# # #### #",
       "#   #    #",
       "# # # ####",
       "### # ## #",
       "#   #    #",
       "## ##### #",
       "#        #",
       "##########"
  };


system("pause");
return 0;
}


system("pause");
return 0;
}


Warum geht dann aber das hier?
#include<iostream>
using namespace std;

int main()
{
  char labyrinth[20][21] = {
    "####################",
    "# # # # ###   # #  #",
    "# # # # #   # # # ##",
    "#   # # # ### # #  #",
    "### # # #   #   ## #",
    "#   # #   # # #    #",
    "# ### # ##### # # ##",
    "# #   # # # ### #  #",
    "# # ###   #  #  ## #",
    "#   # ### ## # #   #",
    "### # # # #  ### # #",
    "# # ###      # # # #",
    "#   # # ###### # # #",
    "# ###     #    # # #",
    "# #   ### # ## ### #",
    "#   # # # # #    # #",
    "### # # ### # #### #",
    "#     # # #        #",
    "# #####  F  # #### #",
    "####################"
  };


system("pause");
return 0;
}


Aber warum geht dann das hier? da ist doch verdammt nochmal nix anders 
wie bei meinem code mit dem kleineren array!

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:

> Aber warum geht dann das hier? da ist doch verdammt nochmal nix anders
> wie bei meinem code mit dem kleineren array!

Schau dir deinen Code noch einmal genau an!

zb wieviele
  system("pause");
zählst du in deinem Code?

Wieviele Klammern { gehen auf und wieviele } gehen zu ?

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Dazugehört noch jede Menge anderes Zeug. Massenhaft.
> zb Parameter passing
> zb Strukturen
> zb komplexere Datenstrukturen
> zb File Handling
> zb dynamisches Speichermanagement

und Wissen rund um Strings wie der letzte Codeschnipsel beweist.

Oh, wenn bloss alle Leute soviel Geduld wie der Herr Moderator hätten, 
die Welt würde viel gewinnen. Respekt!

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die 2 system...

sind durch copy&paste reingekommen

Autor: Rolf Magnus (rmagnus)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
In C++ paßt "##########" nicht in ein Array aus 10 char. Du brauchst 11, 
weil ein String immer mit einem '\0' abgeschlossen wird.
In C könntest du so ein Array trotzdem mit "##########" initialisieren. 
Dann würde das \0 einfach weggelassen werden. In C++ ist das aber nicht 
erlaubt, und du hast ja hier C++.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Die 2 system...
>
> sind durch copy&paste reingekommen

Grrr

  char labyrinth[20][21] = {
    "####################",

Zähl doch mal, wieviele # hier in einem String sind und dann vergleichst 
du mit der Arraydeklaration. Vielleicht klingelts dann.

Ich kann mir aber ehrlich gesagt nicht wirklich vorstellen, dass in so 
einem Fall die Fehlermeldung des Compilers wahnsinnig kryptisch am 
eigentlichen Problem vorbeiredet.

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Meine Güte. Jetzt reichts aber. Du kannst ja nicht mal den Unterschied 
zwischen zwei Texten erkennen.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Oh, wenn bloss alle Leute soviel Geduld wie der Herr Moderator hätten,
> die Welt würde viel gewinnen. Respekt!

Nein, innerhalb einer Generation würde die Welt untergehen, weil
keiner mehr etwas selber macht.
Weil nicht jeder so geduldig ist, dauert es etwas länger.

Also, wenn die Welt untergeht, weiß ich welcher Moderator hier schuld
ist :-)

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, ihr habt recht. Ich weiß jetzt woran ich wieder gescheiter bin.

Ich hab einmal ein 10x10 und einmal 20x20 Feld. Da nun in C++ 10 bzw. 20 
chars nicht in ein 20 Elemente array reinpasst muss man eben schreiben:

array[10][11]

bzw.

array[20][21]

Ich bin dann off. Mir reichts für heute. Bis morgen dann, dann kann ich 
euch wieder nerven... :-)

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> Dafür habe ich den Lösungsquelltext noch hier liegen, siehe
> http://mfgkw.dyndns.org/lab.jpg

Jetzt machst du's Tobias aber sehr leicht. Er braucht deinen geposteten
Code ja nur noch durch den Fortran-nach-C++-Konverter zu schicken, der
sicher auch automatisch erkennt, dass man den Algorithmus rekursiv
darstellen kann.

;-) SCNR

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nicht auf allen Karten ist der oben aufgedruckte Text lesbar,
bei einigen müsste man sich die Löcher anschauen und den Text
rekonstruieren.
Er hat also doch noch etwas zu kodieren...

Autor: Zwölf Mal Acht (hacky)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Toll, diese Rekursionen... kann denn jemand die Fakultaet einer reelen, 
resp komplexen Zahl rechnen ?

Duck und weg

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Gammafunktion, gar kein Thema...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:

> Dafür habe ich den Lösungsquelltext noch hier liegen, siehe
> http://mfgkw.dyndns.org/lab.jpg

Ja, ja
      IMPLICIT INTEGER (A-Z)

und auch ein
      COMMON ....

immer wieder ein Quell der Freude in Fortran :-)

Könnte mich in den A... beissen, dass ich all meine Lochkarten vor 
Jahren entsorgt habe. Eine einzige ist übrig geblieben und von der weiß 
ich nicht genau wo sie ist.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi Leute!

Zitat von kbuchegg:

"Die Maus geht nach einer einfachen Strategie vor

   * an einem Feld mit einer Mauer kann ich nicht sein
   * bin ich am Feld mit dem Käse, Hurra! ich melde den
     Erfolg an die aufrufende Funktion
   * probiere es nach links, rechts, oben, unten
     Führt ein Schritt in diese Richtung nicht zum Erfolg
     dann wird die jeweils nächste Richtung probiert.
     Gibt es keine Richtung mehr, dann melde der aufrufenden
     Funktion, dass ich kein Glück hatte.

Die rekursive Funktion hat diese Signatur

   int  SchrittNach( int x, int y )
   {
      ....
   }

Der Return Wert ist die Rückmeldung, ob dieser Schritt zum Käse führt.
0 ... kein Erfolg, so gehts nicht zum Käse
1 ... Erfolg, Käse gefunden!"


Ich bin jetzt soweit, dass ich das Array ja mittlerweile richtig mit dem 
Labyrinth intialisiert habe. Die oben schon gezeigt Funktion hab ich 
schon mal so Lückenhaft in meinen Code implementiert. Jetzt hab doch 
noch einige Probleme damit. Ich weiß jetzt irgendwie nicht, wie bzw. mit 
welchen Parametern ich die Funktion aufrufen soll...

Ich stell mir grad das so vor. Die Funktion soll prüfen, ob über, links, 
rechts bzw. unten ein # ist. Soweit ist das doch richtig?

Ich hab mir jetzt mal die Variablen x bzw. y mit jeweils einer 1 
initialisert weil ja die Maus bei 1,1 startet. Die Funktion soll nun 
rekursiv die weiter oben genannten Fälle überprüfen, nicht wahr?

Mein Code sieht jetzt schon mal so aus:
#include<iostream>
using namespace std;



int SchrittNach(int x, int y)
{
  if(((x-1) == '#') || ((y-1) == '#'))
  {
    SchrittNach(x+1, y+1);
  }
  else
  {
    if(((x+1) == '#') || ((y+1) == '#'))
    {
      SchrittNach(x-1, y-1);
    }
  }
return 1;
}




int main()
{
  int x, y;
  char labyrinth[10][11] = {
       "##########",
       "# #  #K  #",
       "# # #### #",
       "#   #    #",
       "# # # ####",
       "### # ## #",
       "#   #    #",
       "## ##### #",
       "#        #",
       "##########"
  };


  x = 1;
  y = 1;

  cout << SchrittNach(x, y);


system("pause");
return 0;
}

Aber irgendwie weiß ich jetzt da schon mal wieder nicht mehr weiter, wie 
ich da jetzt das else formulieren soll. Außerdem bin ich mir auch nicht 
sicher, ob das schon alle möglichen Fäll abdeckt, aber wahrscheinlich 
nicht.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hm, ich hab mir jetzt nochmal meine obige Funktion durchgeschaut und 
dabei festgestellt, dass das was ich da geschrieben hab vielleicht doch 
nicht so intellegient war. Hier mal noch mein neuer Versuch (diesmal 
aber nur die Funktion an sich; die Ausgabe is ja dann wieder was 
anderes):
int SchrittNach(int x, int y)
{
  if((x-1) == '#')
  {
    SchrittNach(x+1, y);
  }
  else
  {
    if((x+1) == '#')
    {
      SchrittNach(x-1, y);
    }
  }
  return 1;

  if((y-1) == '#')
  {
    SchrittNach(x, y+1);
  }
  else
  {
    if((y+1) == '#')
    {
      SchrittNach(x, y-1);
    }
  }
  return 1;
}

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Anstatt zu prüfen wo eine Wand ist und dann blind in die andere Richtung 
(möglicherweise gegen eine andere) zu laufen. würde es wohl helfen wenn 
du schaust wo noch frei ist!

Ansonsten wie wäre es mit ausprobieren?
Auch müsste man meiner Meinung nach eine Art "besucht" Flag mitführen um 
nicht eine endlosrekursion zu erzeugen (so etwas ist dann auch keine 
Rekursion mehr sonder nennt sich Backtracking, bei einer Rekursion hat 
man idR eine Funktion die idealerweise beweisbar (streng) monoton ist)

Autor: Daniel -------- (root)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> DANN kann ich auch ganz leicht Minimum und Maximum von n ausrechnen.
> Denn min(n)  = min( min(m), min(k) )
> und  max(n)  = max( max(m), max(k) )
>
> mit anderen Worten das Minimum von n ist der kleinere der beiden Werte:
> Minimum von m  und  Minimum von k
> und das Maximum von n ist der größere der beiden Werte: Maximum von m
> und Maximum von k
>
> Der Charm rekursiver Lösungen besteht darin, dass meistens nicht viel
> gerechnet wird :-) Man kennt eine triviale Lösung und ein Rezept, wie
> man den 'Schwierigkeitsgrad' sukzessive zurückdrehen kann sowie ein
> Rezept wie man das schwierigere Problem mithilfe des leichteren Problems
> lösen kann.

hört sich wie das Optimalitätskriterium von Bellman an.
Und da heute nahezu jeder 4 Kerne CPUs besitzt (hust ... :-)
bietet sich OpenMP task pragma für die weitere Programmverfeinerung an.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es sieht zwar auf den ersten Blick ungewohnt aus, aber ich würde es so 
angehen:

Die Funktion SchrittNach soll als Returnwert eine Aussage darüber 
liefern, ob dieser Schritt zum Ziel führt.

Gut.

Wann führt er nicht zum Ziel?

Wenn der Schritt in eine Mauer führen würde oder wenn keiner der von 
dieser Position weiter erreichbaren Schritte zum Ziel führt.

Und genauso würde ich das auch programmieren
int SchrittNach(int x, int y)
{
  // Hurra! Da liegt er ja
  //
  if( labyrinth[x][y] == 'K' )
    return TRUE;

  // Käse nicht da, aber laufen wir in eine Mauer? Wenn ja
  // dann kann dieser Schritt nicht Teil der Lösung sein
  if( labyrinth[x][y] = '#' )
    return FALSE;

  // OK. Die Maus steht im freien Feld und der Käse ist auch nicht da
  // Das bedeutet: dieser SChritt könnte Teil der Lösung sein, wenn
  // es in einer Richtung zum Käse geht
  //
  // allerdings hinterlässt sich die Maus eine Markierung, dass sie schon
  // mal hier war, damit sie dasselbe Feld nicht noch einmal besucht. Wenn
  // sie schon mal hier war, dann gehts hier auch nicht zum Käse
  if( labyrinth[x][y] == '.' )
    return FALSE;

  labyrinth[x][y] = '.';

  //
  // probiers nach rechts
  if( SchrittNach[x+1][y] )
    return TRUE;

  // rechts wahr wohl nichts, probiers nach links
  if( SchrittNach[x-1][y] )
    return TRUE;

  // rechts links war nichts, nach oben
  if( SchrittNach[x][y-1] )
    return TRUE;

  // bleibt nur noch nach unten
  if( SchrittNach[x][y+1] )
    return TRUE;

  // in keiner der 4 Richtungen gehts zum Käse
  // Schade. Damit steht auch fest, dass dieses Feld nicht auf
  // dem Lösungsweg liegen kann. Mach die Markierung wieder weg

  labyrinth[x][y] = ' ';

  return FALSE;
}

sollte nicht so weit daneben sein.
Nebeneffekt: Die hinterlassenen Markierungen zeigen auch gleich den Weg 
an :-)

Aber ich merke, dass die Aufgabe gemein war. Das ist eine Sonderform 
einer Rekursion, die man 'Backtracking' nennt. Das Prinzip: Eine Lösung 
finden, indem man geordnet alle Möglichkeiten durchprobiert. Und genau 
das tut die Maus, sie probiert alle 4 Richtungen aus, welche davon zum 
Ziel führt.

Wie schon gesagt: leg das ad acta. Das ist alles viel zu schwer für 
deinen momentanen Stand. Das hat alles noch keinen Sinn. Da gibt es 
wichtigere Dinge

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
if( SchrittNach[x+1][y] )
soll wohl eher heißen
if( SchrittNach(x+1, y) )
oder kann man in C jetzt auch schon Funktionen als Array ansprechen? o.O

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Danke für die Korrektur.
Sitz hier im Dunkeln auf einem fremden Rechner mit einer flachen 
$#+$§"?# Tastatur und vertipp mich dauernd. Da hab ich nicht drauf 
geachtet :-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Tobias

Aber wenn du mit Arrays üben willst :-)


Wir haben eine Kammer, in der sind Elementarteilchen. Die Kammer ist 10 
mal 10 Felder groß

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
0  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
1  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
2  |   |   | T |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
3  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
4  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
5  |   |   |   |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+
6  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
7  |   | T |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
8  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
9  |   |   |   |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+

UM rauszukriegen, wo die Teilchen sitzen, schickt man ein Testteilchen 
an einer (vom Benutzer vorgegebenen) Stelle am Rand in dieses Array.
Dieses Test-Teilchen wandert immer geradlinig.
Allerdings gilt:

* trifft es frontal auf ein T so wird er dort reflektiert, dreht also
  seine Richtung um.

  Ein in die Zeile 2 eingespeistes Teilchen legt also diesen Weg zurück 
...

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
0  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
1  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
2  | * | * | * | T |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
3  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
4  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
5  |   |   |   |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+
6  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
7  |   | T |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
8  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
9  |   |   |   |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+

  .. und kommt wieder in Zeile 2/links wieder heraus.

* Ein Test-Teilchen welches neben (über/unter/rechts/links) einem
  Teilchen ankommt, wird um 90° abgelenkt.
  Ein in die Zeile 1 eingespeistes Teilchen legt also diesen Weg
  zurück

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
0  |   |   | * |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
1  | > | * | * |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
2  |   |   |   | T |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
3  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
4  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
5  |   |   |   |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+
6  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
7  |   | T |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
8  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
9  |   |   |   |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+

wenn es auf seinem weiteren Weg wieder auf andere Teilchen trifft, dann 
geht das Spiel natürlich weiter. zb in Zeile 3

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
0  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
1  |   |   |   |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
2  |   |   |   | T |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
3  | > | * | * |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
4  |   |   | * |   |   |   |   |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
5  |   |   | * |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+
6  |   |   | * | * | * | * | * |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
7  |   | T |   |   |   |   | * |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
8  |   |   | * | * | * | * | * |   |   |   |
   +---+---+---+---+---+---+---+---+---+---+
9  |   |   | v |   |   |   |   | T |   |   |
   +---+---+---+---+---+---+---+---+---+---+

Das Teilchen kommt also in Spalte 2/unten wieder raus.

* trifft ein Teilchen auf eine Lücke zwischen den Teilchen, dann geht es 
einfach durch die Lücke durch und wird nicht abgelenkt

     0   1   2   3   4   5   6   7   8   9
   +---+---+---+---+---+---+---+---+---+---+
0  |   |   |   |   |   |   |   | * |   |   |
   +---+---+---+---+---+---+---+---+---+---+
1  |   |   |   |   |   |   |   | * |   |   |
   +---+---+---+---+---+---+---+---+---+---+
2  |   |   | T |   |   |   |   | * |   |   |
   +---+---+---+---+---+---+---+---+---+---+
3  | > | * | * | * | * | * | * | * |   |   |
   +---+---+---+---+---+---+---+---+---+---+
4  |   |   | T |   |   |   |   |   | T |   |
   +---+---+---+---+---+---+---+---+---+---+
5  |   |   |   |   |   |   |   |   |   |   |

Hier kommt also das Teilchen, welche in Zeile 3/links eingespeist wurde, 
in der Spalte 7/oben wieder raus.

Zu schreiben ist ein Programm, welches dieses Verhalten simuliert und 
bestimmt, wo ein Testteilchen wieder rauskommt, wenn man es an einer 
bestimmten Zeile/Spalte oben/unten Links/rechts einspeist.
Die Art der Benutzereingabe ist dem Programmierer überlassen. Der 
Benutzer muss nur die Möglichkeit haben festzulegen, wo genau er sein 
Testteilchen einspeisen will. Dazu genügt zb eine Systematik

   u4    u für 'unten' (muss daher eine Spalte sein) und zwar die 4.
   o3    o wie oben
   r6    rechts, 6. Zeile
   l7    links, 7. Zeile

Fürs erst genügt es, wenn das Programm eine 'Grafik' ausgibt, in der der 
Weg des Testteilchens eingezeichnet ist und zwar für jeden einzelnen 
'Schritt' des Testteilchens. Die Verteilung der T in der Matrix kann als 
fix angenommen werden und wird vom Programmierer festgelegt (braucht 
also nicht eingebbar sein)

Eine 'schöne' Ausgabe mit Trennlinien, ähnlich obiger ASCII Grafik, ist 
anzustreben. Eintritt und Austrittspunkt sind mit frei zu wählenden 
Sonderzeichen zu markieren. Nach dem Austritt soll das Programm auch 
noch das Endergebnis ("Austritt bei .....") bekannt geben.


Sonderpunkte: Wie könnte man aus dieser Grundidee ein Spiel entwickeln?


Besonderes Augenmerk ist auf eine korrekte Behandlung der Randfelder zu 
legen. Ich werde mir das Programm dann sehr genau ansehen, ob das 
Programm irgendwo 'Out of Bounds' auf das Array zugreift.

Autor: jungspund (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Karl heinz:

Hast du schonmal daran gedacht, eine Homepage zu machen mit solchen 
Programmier-Tutorials und -Aufgaben mit Lösungen und Erklärungen? =)
Würde ja schon fast reichen, wenn du das, was du hier schreibst sammeln 
würdest.
Finde das sehr interessant und lehrreich! Und deine Aufgaben sind immer 
interessant und klug ausgewählt!

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zitat:

"Wie schon gesagt: leg das ad acta. Das ist alles viel zu schwer für
deinen momentanen Stand. Das hat alles noch keinen Sinn. Da gibt es
wichtigere Dinge."


Ich hab mir gestern nach meinem letzten Eintrag nach fast ne Stunden 
darüber den Kopf zerbrechen, und war heute, ja schon fast, überglücklich 
als ich deine Lösung gesehen. Ich hab nämlich so von der Grundüberlegung 
her, das gleich im Kopf bzw. in Visual Studio gehabt wie du gepostet 
hast. Ich zeig euch hier mal meinen neuen Code bei dem ich noch ein 
Problem hab (natürlich sieht der jetzt ähnlich mit dem von kabuchegg 
aus, da ich ihn daran angepasst hab):
#include<iostream>
using namespace std;



int SchrittNach(int x, int y)
{
  char Labyrinth[10][11];

  if(Labyrinth[x][y] == 'K')
  return 1;

  if(Labyrinth[x][y] == '#')
  return 0;

  if(Labyrinth[x][y] == '.')
  return 0;



  if(SchrittNach(x-1, y))
    return 1;

  if(SchrittNach(x+1, y))
    return 1;

  if(SchrittNach(x, y-1))
    return 1;

  if(SchrittNach(x, y+1))
    return 1;



  if(Labyrinth[x][y] == ' ')
    return 0;
}



int main()
{
  int x, y;
  char Labyrinth[10][11] = {
       "##########",
       "# #  #K  #",
       "# # #### #",
       "#   #    #",
       "# # # ####",
       "### # ## #",
       "#   #    #",
       "## ##### #",
       "#        #",
       "##########"
  };


  x = 1;
  y = 1;


  SchrittNach(x, y);


system("pause");
return 0;
}

Ich hab jetzt nur noch das Problem, dass mir VS2010 folgende 
Fehlermeldung in Zeile 37 zurückgibt: "SchrittNach": Nicht alle 
Steuerelementpfade geben einen Wert zurück. Zeile 37 ist die Zeile mit 
der schließenden Klammer der Funktion. Ich verstehe die Fehlermeldung 
nicht. Ich hab bei der jeder if-Abfrage ein return. Warum gibt dann 
nicht alle Steuerelementpfade was zurück?

Wie kann ich das jetzt eigentlich ausgeben? Ich mein, ich möchte ja nun 
auch noch sehen, wie die Maus ihren Punkt hinterlässt und das M zum K 
wandert...

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Warum gibt dann nicht alle Steuerelementpfade was zurück?
Wenn keine der Bedingungen in den ifs erfüllt ist gibt es keinen 
Rückgabewert. Programmlogik hab ich nicht geprüft.

Wär übrigens nett wenn du im "Array-als-Funktionsparameter"-Thread 
nochmal eine Rückmeldung gibst...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:

> der schließenden Klammer der Funktion. Ich verstehe die Fehlermeldung
> nicht.

>
>   if(Labyrinth[x][y] == ' ')
>     return 0;
> }

Und was wenn Labyrinth[x][y] eben nicht ' ' ist?
Was wird dann zurückgegeben?

> Ich hab bei der jeder if-Abfrage ein return.
> Warum gibt dann
> nicht alle Steuerelementpfade was zurück?

Weil es ja auch sein kann, dass kein einziges if zu einem return führt

> Wie kann ich das jetzt eigentlich ausgeben? Ich mein, ich möchte ja nun
> auch noch sehen, wie die Maus ihren Punkt hinterlässt und das M zum K
> wandert...

Indem du deine Ausgabefunktion an 'strategisch günstigen Stellen' 
aufrufst?

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
"Und was wenn Labyrinth[x][y] eben nicht ' ' ist?
Was wird dann zurückgegeben?"

Dann überspringt mein Programm momentan das return und macht beim 
nächsten if weiter. Ich will, aber das mir das Programm eine 1 
rückmeldet, wenn ' ' nicht erfüllt ist nicht wahr? Was mach ich dann? 
Ich denke ich sollte dann noch ein else an jedes if ranschreiben, die 
mir eben dann diese 1 zurückgibt, oder?

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Ich denke ich sollte dann noch ein else an jedes if ranschreiben, die
>mir eben dann diese 1 zurückgibt, oder?

Nein. Denn dann würde die erste nicht erfüllte Bedingung die Funktion 
beenden, ohne das die anderen if überhaupt beachtet werden.
if(....)
  return 1;

if(....)
  return 0;
 //<-- Hier ist KEIN if
return 2;

gibt 2 zurück wenn keine der Bedingungen wahr ist.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Es würde formal reichen, zum Schluß ein letztes return .. mit
irgendeinem zu nehmen.

Weil aber imemr nur einer der Zweige gemacht wird, wäre es
schöner zu lesen und einfacher zu erfassen, wenn man else so
einfügt:
  if(Labyrinth[x][y] == 'K' )
    return 1;
  else if(Labyrinth[x][y] == '#' )
    return 0;
  else if(Labyrinth[x][y] == '.')
    return 0;
  else if(SchrittNach(x-1, y))
    return 1;
  else if(SchrittNach(x+1, y))
    return 1;
  else if(SchrittNach(x, y-1))
    return 1;
  else if(SchrittNach(x, y+1))
    return 1;
  else if(Labyrinth[x][y] == ' ')
    return 0;
  else
    return 0; // sollte nie auftreten!


Weiterhion plädiere ich stark dafür, generell Blöcke zu klammern.
Es gibt auch gegenteilige Meinungen (Platzverschwendung!), aber
die sind alle doof.

Dann sieht es so aus:
  if(Labyrinth[x][y] == 'K' )
  {
    return 1;
  }
  else if(Labyrinth[x][y] == '#' )
  {
    return 0;
  }
  else if(Labyrinth[x][y] == '.')
  {
    return 0;
  }
  else if(SchrittNach(x-1, y))
  {
    return 1;
  }
  else if(SchrittNach(x+1, y))
  {
    return 1;
  }
  else if(SchrittNach(x, y-1))
  {
    return 1;
  }
  else if(SchrittNach(x, y+1))
  {
    return 1;
  }
  else if(Labyrinth[x][y] == ' ')
  {
    return 0;
  }
  else
  {
    return 0; // sollte nie auftreten!
  }

So wären alle zufrieden: ich und der Compiler.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok. Es sieht dann jetzt so aus:
#include<iostream>
using namespace std;



int SchrittNach(int x, int y)
{
  char Labyrinth[10][11];

  if(Labyrinth[x][y] == 'K')
  return 1;

  if(Labyrinth[x][y] == '#')
  return 0;

  if(Labyrinth[x][y] == '.')
  return 0;



  if(SchrittNach(x-1, y))
    return 1;

  if(SchrittNach(x+1, y))
    return 1;

  if(SchrittNach(x, y-1))
    return 1;

  if(SchrittNach(x, y+1))
    return 1;



  if(Labyrinth[x][y] == ' ')
    return 2;
}



int main()
{
  int x, y;
  char Labyrinth[10][11] = {
       "##########",
       "# #  #K  #",
       "# # #### #",
       "#   #    #",
       "# # # ####",
       "### # ## #",
       "#   #    #",
       "## ##### #",
       "#        #",
       "##########"
  };


  x = 1;
  y = 1;


  SchrittNach(x, y);


system("pause");
return 0;
}

Wenn ich es durchkompiliere, dann kommt aber der Fehler immer noch und 
das "Programm" bricht nach kurzer Zeit ab. -> Endlosschleife?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wo ist hier eine Schleife? Er wird halt fertig sein nach einem Schritt.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok. Es sieht dann jetzt so aus:
#include<iostream>
using namespace std;



int SchrittNach(int x, int y)
{
  char Labyrinth[10][11];

  if(Labyrinth[x][y] == 'K')
  {
    return 1;
  }
  else if(Labyrinth[x][y] == '#')
  {
    return 0;
  }
  else if(Labyrinth[x][y] == '.')
  {
    return 0;
  }
  else if(SchrittNach(x-1, y))
  {
    return 1;
  }
  else if(SchrittNach(x+1, y))
  {
    return 1;
  }
  else if(SchrittNach(x, y-1))
  {
    return 1;
  }
  else if(SchrittNach(x, y+1))
  {
    return 1;
  }
  else if(Labyrinth[x][y] == ' ')
  {
    return 0;
  }
  else
  {
    return 0;
  }
}



int main()
{
  int x, y;
  char Labyrinth[10][11] = {
       "##########",
       "# #  #K  #",
       "# # #### #",
       "#   #    #",
       "# # # ####",
       "### # ## #",
       "#   #    #",
       "## ##### #",
       "#        #",
       "##########"
  };


  x = 1;
  y = 1;


  SchrittNach(x, y);


system("pause");
return 0;
}

Wenn ich es durchkompiliere, bricht das "Programm" nach kurzer Zeit 
nachwie vor ab. Wenn es nach einem Schritt fertige ist, dann soll es ja 
nun noch mehr Schritt ausführen, oder?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Klaus Wachtler schrieb:
> else
>   {
>     return 0; // sollte nie auftreten!
>   }

So etwas (eine Annahme, von der man sicher ist, daß sie immer
und ewig stimmt und natürlich NIE verletzt wird) sollte man
schlauerweise generell absichern:

[/c]
#include <assert.h>

...
 else
   {
     assert( !"hier komme ich nie an" );
     return 0; // sollte nie auftreten!
   }
[/c]

In der Debugversion wird das Programm mit einer passenden
Fehlermeldung abgebrochen wenn die BEdingung zur Laufzeit dann
doch nicht erfüllt ist, in der Releaseversion macht der
Kompiler nichts aus dem assert, es kostet also keinen Code
und keine Rechenzeit - und gibt auch keine Fehlermeldung.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Wenn es nach einem Schritt fertige ist, dann soll es ja
> nun noch mehr Schritt ausführen, oder?

Mag sein, daß du dir das so vorstellst.
Dann musst du dem Compiler das auch sagen. Ich sehe nichts davon.
Der Compiler vermutlich auch nicht.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn du übrigens im Hauptprogramm ein Feld hast (oder irgendeine
Variable) und in einer Funktion nochmal, dann sind das zwei
verschiedene, auch wenn sie gleich heißen.
Willst du das bei Labyrinth[][]?

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mal eine andere Frage. Ist der Code soweit korrekt und der Fehler den 
ich bisher beschrieben habe kommt von den fehlenden Schritten? D.h. ich 
müsste jetzt irgendwie von Hand die Funktion SchrittNach per Hand wie 
z.B. durch Eingabe einer Taste immer wieder aufrufen. Könnte das so 
funzen?

"Willst du das bei Labyrinth[][]?"

Nein, eigentlich soll er immer wieder das gleiche Labyrinth hernehmen...

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann weisst du ja, was du im C-Buch deiner Wahl jetzt suchen musst.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Mal eine andere Frage. Ist der Code soweit korrekt und der Fehler den

korrekt ist er noch lange nicht, alleine weil er nichts tut.

> ich bisher beschrieben habe kommt von den fehlenden Schritten? D.h. ich
> müsste jetzt irgendwie von Hand die Funktion SchrittNach per Hand wie
> z.B. durch Eingabe einer Taste immer wieder aufrufen. Könnte das so
> funzen?

Könnte, aber willst du so ein Programm?

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ja, ich würde gerne die Maus durch Tastendruck da hinführen. Ist das 
jetzt schlecht wenn es das Programm nicht von alleine tut? Wie kann man 
Funktionen wiederholt per Hand aufrufen?

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Ist das
> jetzt schlecht wenn es das Programm nicht von alleine tut?

Wenn du das so willst, ist es in Ordnung.
Ich habe damit keine Probleme, nur ging ich davon aus, daß das
Programm eine Lösung suchen soll. Dann müsste dein Programm
halt die Bewegung vorgeben.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, ich hab die Aufgabenstellung so verstanden, dass nach jedem 
Tastendruck, z.B. die Enter-Taste, die Maus wieder ein Stück näher in 
Richtung des Käses rückt. Nur weiß ich eben nicht wie ich auf 
Tastendruck der Enter-Taste die Funktion SchrittNach in der main wieder 
aufrufen kann und man jeden einzelnen Schritt der Maus auch als Ausgabe 
sieht (aber das ist ja noch was anderes)...

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Wie kann man
> Funktionen wiederholt per Hand aufrufen?

In einer Schleife Zeichen lesen und dann die Funktion aufrufen?

Die Standardeingabe (getchar(), scanf(), getc(), gets()) ist
in C-Programmen üblicherweise gepuffert, sodaß man
lange tippen kann, bevor sich etwas tut - erst mit einem Return
oder Enter wird die ganze Zeile hingeworfen und dann abgearbeitet.
Das will man bei der Art von Programmen meist nicht.

Wenn du mit VC++ arbeitest, sollte es da eine Funktion getch()
oder _getch() geben, die nicht bis zum nächsten Enter hängt,
sondern jeden Tastendruck sofort liefert.
Mit kbhit() oder_kbhit() kann man abfragen, ob ein Tastendruck
stattgefunden hatte und man etwas abholen kann.
Für Linux hätte ich einen Ersatz für diese beiden Funktionen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Naja, ich hab die Aufgabenstellung so verstanden, dass nach jedem
> Tastendruck, z.B. die Enter-Taste, die Maus wieder ein Stück näher in
> Richtung des Käses rückt.

Das war gar nicht gefragt :-)
Gefragt war der Weg, den die Maus nehmen muss.
Dass der auf Tastendruck entstehen soll, ist in der Aufgabenstellung mit 
keinem Wort erwähnt.

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>Wenn du mit VC++ arbeitest, sollte es da eine Funktion getch()
GCC bzw. MinGw kennt die auch, conio.h.

Autor: Tobias Mehrl (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nunja, können wir es trotzdem so machen?

Ich hab das jetzt mal so versucht zu lösen. Jedes mal wenn man die 
Leertaste drückt, dann wird die Funktion SchrittNach aufgerufen. Seht 
selbst:
#include<iostream>
#include<stdlib.h>
using namespace std;



int SchrittNach(int x, int y)
{
  char Labyrinth[10][11];

  if(Labyrinth[x][y] == 'K')
  {
    return 1;
  }
  else if(Labyrinth[x][y] == '#')
  {
    return 0;
  }
  else if(Labyrinth[x][y] == '.')
  {
    return 0;
  }
  else if(SchrittNach(x-1, y))
  {
    return 1;
  }
  else if(SchrittNach(x+1, y))
  {
    return 1;
  }
  else if(SchrittNach(x, y-1))
  {
    return 1;
  }
  else if(SchrittNach(x, y+1))
  {
    return 1;
  }
  else if(Labyrinth[x][y] == ' ')
  {
    return 0;
  }
  else
  {
    return 0;
  }
}



int main()
{
  int x, y;
  char Labyrinth[10][11] = {
       "##########",
       "# #  #K  #",
       "# # #### #",
       "#   #    #",
       "# # # ####",
       "### # ## #",
       "#   #    #",
       "## ##### #",
       "#        #",
       "##########"
  };


  x = 1;
  y = 1;

  if(getchar() == ' ')
  {
  SchrittNach(x, y);
  }
  else
  {
  }


system("pause");
return 0;
}

Edit: Hab grad selbst bemerkt, dass das schon wieder völliger Blödsinn 
ist...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tobias Mehrl schrieb:
> Mal eine andere Frage. Ist der Code soweit korrekt

Nein.
Das ist so falsch, wie es nur sein kann.

Und das fängt schon mal damit an, das labyrinth keine lokale Variable 
der Funktion sein kann

Vergeude nicht deine Zeit. Stürz dich lieber auf sinnvollere Sachen, wie 
Arrays oder Strukturen oder Argument Passing. Die werden die nächsten 10 
Jahre dein Arbeitspferd sein, daher solltest du sie im Schlaf 
beherrschen. Und davon sehe ich in deinem Code noch nicht einmal 
Ansätze, dass du wenigstens in der Nähe von Können kommst. Von 
beherrschen red ich erst mal nicht.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So könnte sowas aussehen.
Compiliert mit VC++ (wegen der conio.h wichtig)

Die Maus macht mit jedem Tastendruck einen Schritt. Wird der Käse 
gefunden, kommt hinten nach eine Liste der Schritte raus (allerdings in 
umgekehrter Reihenfolge: vom Käse zur Startposition)

#include <stdio.h>
#include <conio.h>

#ifndef TRUE
#define TRUE 1
#define FALSE 0
#endif

char Labyrinth[10][11] = {
     "##########",
     "# #  #K  #",
     "# # #### #",
     "#   #    #",
     "# # # ####",
     "### # ## #",
     "#   #    #",
     "## ##### #",
     "#        #",
     "##########"
};

void Output()
{
  int x, y;
  
  for( y = 0; y < 10; ++y ) {
    for( x = 0; x < 10; ++x ) {
      printf( "%c", Labyrinth[x][y] );
    }
    printf( "\n" );
  }
  
  printf( "\n" );
  
  {
    char c = _getch();
  }
}

int SchrittNach(int x, int y)
{
  Output();
  printf( "Trying %d %d\n", x, y );
  
  // Hurra! Da liegt er ja
  //
  if( Labyrinth[x][y] == 'K' )
    return TRUE;

  // Käse nicht da, aber laufen wir in eine Mauer? Wenn ja
  // dann kann dieser Schritt nicht Teil der Lösung sein
  if( Labyrinth[x][y] == '#' )
    return FALSE;

  // OK. Die Maus steht im freien Feld und der Käse ist auch nicht da
  // Das bedeutet: dieser SChritt könnte Teil der Lösung sein, wenn
  // es in einer Richtung zum Käse geht
  //
  // allerdings hinterlässt sich die Maus eine Markierung, dass sie schon
  // mal hier war, damit sie dasselbe Feld nicht noch einmal besucht. Wenn
  // sie schon mal hier war, dann gehts hier auch nicht zum Käse
  if( Labyrinth[x][y] == '.' )
    return FALSE;

  Labyrinth[x][y] = '.';

  if( SchrittNach( x+1, y ) ||
      SchrittNach( x-1, y ) ||
      SchrittNach( x, y-1 ) ||
      SchrittNach( x, y+1 ) ) {
    printf( "-> %d %d\n", x, y );
    return TRUE;
  }

  // in keiner der 4 Richtungen gehts zum Käse
  // Schade. Damit steht auch fest, dass dieses Feld nicht auf
  // dem Lösungsweg liegen kann. Mach die Markierung wieder weg

  Labyrinth[x][y] = ' ';

  return FALSE;
}

int main()
{
  if( SchrittNach(1, 1) )
    printf( "Kaese gefunden!\n" );
  else
    printf( "Kaese nicht gefunden :-( \n" );

system("pause");
return 0;
}

Probehalber auch mal den Käse unerreichbar einbauen oder überhaupt 
rausnehmen.

Autor: M. B. (manubaum) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hey, lass dich nicht entmutigen. Du wirst das schon noch einsehen! 
Jedoch als Input möchte ich noch anfügen, das es in anderen Foren viele 
diskussionen gibt, die darum gehen, ob das in der Praxis jemals relevant 
ist (habs einmal gebraucht).

Folgendes ist auch noch zu erwähnen:
Die Rekursion ist ein schönes akademisches Anschauungsbeispiel (ich mag 
den Grundgedanken), jedoch ist ein For-Loop viel schneller und sicherer.

Autor: Klaus Wachtler (mfgkw)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
M. B. schrieb:
> jedoch ist ein For-Loop viel schneller und sicherer.

Dann gib mal einen Binärbaum ohne Rekursion mit einer for-Schleife
aus.

Es gibt halt Probleme, wo nur Rekursion sinnvoll ist, es gibt
welche wo es keinen Sinn macht, und einen weiten Bereich
dazwischen, wo man sich davor mehr oder weniger gut drücken kann.

Generell etwas anderes als Rekursion zu empfehlen, nur weil man
sie nicht mag ist aber schon etwas verwegen :-)

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Karl heinz Buchegger
Compiliert auch mit MinGW. Wegen system() sollte man noch stdlib.h 
includen und char c = _getch(); gibt ne Warnung von wegen unused 
variable, aber das brauch ich dir ja nicht zu erzählen. :-)

Davon mal abgesehen: Irgendwie stehen Maus und Rest der Welt auf dem 
Kopf...

Code:
##########
# #  #K  #
# # #### #
#   #    #
# # # ####
### # ## #
#   #    #
## ##### #
#        #
##########

Ausgabe:
##########
#    # # #
### ##   #
#      # #
# ###### #
###    # #
#K# ## # #
# # ## # #
#   #    #
##########

Jetzt stelle ich auch mal eine Frage die wohl in jedem C-Buch erklärt 
ist: Macht das einen Unterschied in den for-Schleifen ++x anstelle von 
x++ zu nutzen?

@M. B.
Zeig doch mal eine Lösung für die Maus welche ohne Rekursion auskommt. 
Der Vorteil im konkreten Fall ist ja das der Weg der Maus durch die 
ineinandergeschachtelten Funktionsaufrufe "gespeichert" wird, wenn ich 
an Schleifen denke lande ich da schnell bei realloc(). Ist das schöner?

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
abc schrieb:

> Davon mal abgesehen: Irgendwie stehen Maus und Rest der Welt auf dem
> Kopf...

:-)
Fast.
Ist um 90° gedreht

Das 'Problem'

wie ist in

  char Labyrinth[7][7] =
     { ....

in der Initialisierung X und Y angeordnet?

Und wenn man darüber nachdenkt, kommt man drauf, dass es so sein muss

     ---->   Y

  |   "##########",
  |   "# #  #K  #",
  |   "# # #### #",
  v   "#   #    #",
      "# # # ####",
  X   "### # ## #",
      "#   #    #",
      "## ##### #",
      "#        #",
      "##########"

( der letzte Index läuft am schnellsten )


> Jetzt stelle ich auch mal eine Frage die wohl in jedem C-Buch erklärt
> ist: Macht das einen Unterschied in den for-Schleifen ++x anstelle von
> x++ zu nutzen?

Nein.
In C macht es überhaupt keinen Unterschied.
C++ Leute gewöhnen sich aber meistens um, denn in C++ kann es einen 
Unterschied machen, wenn x kein einfacher Datentyp sondern eine eigene 
Klasse mit überladenen ++ Operatoren ist.

> @M. B.
> Zeig doch mal eine Lösung für die Maus welche ohne Rekursion auskommt.
> Der Vorteil im konkreten Fall ist ja das der Weg der Maus durch die
> ineinandergeschachtelten Funktionsaufrufe "gespeichert" wird, wenn ich
> an Schleifen denke lande ich da schnell bei realloc(). Ist das schöner?

Das geile ist, dass die oft verteufelte Rekursion gerne schon mal mit 
einem selbst geführten Stack ersetzt wird. Das das dem Prinzip nach 
immer noch eine Rekursion ist , .... :-)

Aber es stimmt schon. Viele brauchen tatsächlich Rekursionen nicht. In 
dem Moment wo allerdings härtere Datenstrukturen als Arrays ins Spiel 
kommen, sind aber Rekursionen oft die natürlichste Lösung. Grob gesagt: 
Alles was mit ineinander geschachtelten for-Schleifen gelöst wird, wobei 
die ANzahl der Ineinanderschachtelungen von vorne herein nicht 
feststeht, ist ein dankbarer Kandidat für Rekursion.

Autor: abc (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Nein.
> In C macht es überhaupt keinen Unterschied.
Danke, das wollte ich wissen.

Die gedrehte Welt lass ich jetzt mal in Ruhe, dafür bin ich schon zu 
müde...

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
abc schrieb:
> Karl heinz Buchegger schrieb:
>> Nein.
>> In C macht es überhaupt keinen Unterschied.
> Danke, das wollte ich wissen.
>
> Die gedrehte Welt lass ich jetzt mal in Ruhe, dafür bin ich schon zu
> müde...

Lässt sich in der Ausgabefunktion leicht korrigieren. Spielt aber im 
Grunde keine große Rolle.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.