Hi Leute!
Ich hab heute ein Programm geschrieben, dass mir die Fakultät für
unterschiedliche Werte mittles Rekursion berechnet. Hier der Code:
1
#include<iostream>
2
usingnamespacestd;
3
4
5
6
intfakultaet(intn)
7
{
8
if(n==1)
9
{
10
return1;
11
}
12
else
13
{
14
returnn*fakultaet(n-1);
15
}
16
}
17
18
19
20
intmain()
21
{
22
intn;
23
cin>>n;
24
25
cout<<fakultaet(n)<<endl;
26
27
28
29
system("pause");
30
return0;
31
}
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?
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.
>Normalerweise müsste sich doch die Funktion fakultaet wieder aufrufen.
Das tut sie auch. Nämlich genau hier.
1
returnn*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
1
cout<<fakultaet(n)<<endl;
in main.
>Aber wo wird da n-1 berechnet?
Auch genau hier:
1
returnn*fakultaet(n-1);
Bevor die Funktion aufgerufen wird, werden die Ausdrücke berechnet die
sich in der Parameterliste befinden.
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
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
1
#include<iostream>
2
usingnamespacestd;
3
4
voiddoIndent(intn)
5
{
6
for(inti=0;i<n;++i)
7
cout<<' ';
8
}
9
10
intfakultaet(intn,intindent)
11
{
12
doIndent(indent);
13
cout<<"Gesucht die Fakultaet von "<<n<<endl;
14
15
if(n==1)
16
{
17
doIndent(indent);
18
cout<<"das ist einfach, die ist 1"<<endl;
19
return1;
20
}
21
22
else
23
{
24
doIndent(indent);
25
cout<<"dazu berechne ich die Fakultaet von "<<n-1<<endl;
26
27
inttmp=fakultaet(n-1,indent+2);;
28
29
doIndent(indent);
30
cout<<"also: Die Fakultaet von "<<n-1<<" ist gleich "<<tmp<<endl;
31
doIndent(indent);
32
cout<<"daher ist die Fakultaet von "<<n<<" gleich "<<n<<"*"<<tmp<<endl;
33
34
tmp=n*tmp;
35
36
doIndent(indent);
37
cout<<"das ergibt "<<tmp<<endl;
38
39
returntmp;
40
}
41
}
42
43
44
45
intmain()
46
{
47
intn;
48
cin>>n;
49
50
cout<<fakultaet(n,0)<<endl;
51
52
system("pause");
53
return0;
54
}
Jetzt erzählt dir das Programm, wann es was warum berechnet. Jede
Einrückstufe im Output entspricht einem Aufruf der Funktion fakultaet
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.
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.
> 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.
@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?
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!
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
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?
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
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.
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...
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.
>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
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:
1
#include<iostream>
2
usingnamespacestd;
3
4
5
6
//minmax
7
longminmax(shortarray[],intlen)
8
{
9
shortteil1[3],teil2[3];
10
11
cout<<"Teil1: ";
12
13
for(inti=0;i<3;i=i+1)
14
{
15
teil1[i]=array[i];
16
cout<<teil1[i];
17
}
18
19
cout<<endl<<"Teil2: ";
20
21
for(intj=3;j<6;j=j+1)
22
{
23
teil2[j-3]=array[j];
24
cout<<teil2[j-3];
25
}
26
27
minmax(teil1,teil2);
28
}
29
30
31
32
33
intmain()
34
{
35
shortarray[6]={4,3,7,2,1,6};
36
intlen=6;
37
longergebnis;
38
39
40
minmax(array,len);
41
42
43
44
system("pause");
45
return0;
46
}
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...
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
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)
1
|<--------- n ------->|
2
3
* * * * * * * * * * * *
4
5
|<--- 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.
> 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))
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!
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
ist der Versuch einer Zuweisung, wenn ich mir die [10][10] mal großzügig
wegdenke.
Arrays können initialisiert werden!
1
#include<iostream>
2
usingnamespacestd;
3
4
intmain()
5
{
6
inti,j;
7
charlabyrinth[10][10]={
8
{"##########"},
9
{"# # #K #"},
10
{"# # #### #"},
11
{"# # #"},
12
{"# # # ####"},
13
{"### # ## #"},
14
{"# # #"},
15
{"## ##### #"},
16
{"# #"},
17
{"##########"}
18
};
19
20
21
for(i=0;i<10;i=i+1)
22
{
23
cout<<endl;
24
for(j=0;j<10;j=j+1)
25
{
26
cout<<labyrinth[i][j];
27
}
28
}
29
30
31
system("pause");
32
return0;
33
}
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
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 :-)
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 ?
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!
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++.
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.
> 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 :-)
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... :-)
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
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...
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.
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:
1
#include<iostream>
2
usingnamespacestd;
3
4
5
6
intSchrittNach(intx,inty)
7
{
8
if(((x-1)=='#')||((y-1)=='#'))
9
{
10
SchrittNach(x+1,y+1);
11
}
12
else
13
{
14
if(((x+1)=='#')||((y+1)=='#'))
15
{
16
SchrittNach(x-1,y-1);
17
}
18
}
19
return1;
20
}
21
22
23
24
25
intmain()
26
{
27
intx,y;
28
charlabyrinth[10][11]={
29
"##########",
30
"# # #K #",
31
"# # #### #",
32
"# # #",
33
"# # # ####",
34
"### # ## #",
35
"# # #",
36
"## ##### #",
37
"# #",
38
"##########"
39
};
40
41
42
x=1;
43
y=1;
44
45
cout<<SchrittNach(x,y);
46
47
48
system("pause");
49
return0;
50
}
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.
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):
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)
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.
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
1
intSchrittNach(intx,inty)
2
{
3
// Hurra! Da liegt er ja
4
//
5
if(labyrinth[x][y]=='K')
6
returnTRUE;
7
8
// Käse nicht da, aber laufen wir in eine Mauer? Wenn ja
9
// dann kann dieser Schritt nicht Teil der Lösung sein
10
if(labyrinth[x][y]='#')
11
returnFALSE;
12
13
// OK. Die Maus steht im freien Feld und der Käse ist auch nicht da
14
// Das bedeutet: dieser SChritt könnte Teil der Lösung sein, wenn
15
// es in einer Richtung zum Käse geht
16
//
17
// allerdings hinterlässt sich die Maus eine Markierung, dass sie schon
18
// mal hier war, damit sie dasselbe Feld nicht noch einmal besucht. Wenn
19
// sie schon mal hier war, dann gehts hier auch nicht zum Käse
20
if(labyrinth[x][y]=='.')
21
returnFALSE;
22
23
labyrinth[x][y]='.';
24
25
//
26
// probiers nach rechts
27
if(SchrittNach[x+1][y])
28
returnTRUE;
29
30
// rechts wahr wohl nichts, probiers nach links
31
if(SchrittNach[x-1][y])
32
returnTRUE;
33
34
// rechts links war nichts, nach oben
35
if(SchrittNach[x][y-1])
36
returnTRUE;
37
38
// bleibt nur noch nach unten
39
if(SchrittNach[x][y+1])
40
returnTRUE;
41
42
// in keiner der 4 Richtungen gehts zum Käse
43
// Schade. Damit steht auch fest, dass dieses Feld nicht auf
44
// dem Lösungsweg liegen kann. Mach die Markierung wieder weg
45
46
labyrinth[x][y]=' ';
47
48
returnFALSE;
49
}
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
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 :-)
@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.
@ 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!
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):
1
#include<iostream>
2
usingnamespacestd;
3
4
5
6
intSchrittNach(intx,inty)
7
{
8
charLabyrinth[10][11];
9
10
if(Labyrinth[x][y]=='K')
11
return1;
12
13
if(Labyrinth[x][y]=='#')
14
return0;
15
16
if(Labyrinth[x][y]=='.')
17
return0;
18
19
20
21
if(SchrittNach(x-1,y))
22
return1;
23
24
if(SchrittNach(x+1,y))
25
return1;
26
27
if(SchrittNach(x,y-1))
28
return1;
29
30
if(SchrittNach(x,y+1))
31
return1;
32
33
34
35
if(Labyrinth[x][y]==' ')
36
return0;
37
}
38
39
40
41
intmain()
42
{
43
intx,y;
44
charLabyrinth[10][11]={
45
"##########",
46
"# # #K #",
47
"# # #### #",
48
"# # #",
49
"# # # ####",
50
"### # ## #",
51
"# # #",
52
"## ##### #",
53
"# #",
54
"##########"
55
};
56
57
58
x=1;
59
y=1;
60
61
62
SchrittNach(x,y);
63
64
65
system("pause");
66
return0;
67
}
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...
> 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...
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?
"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?
>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.
1
if(....)
2
return1;
3
4
if(....)
5
return0;
6
//<-- Hier ist KEIN if
7
return2;
gibt 2 zurück wenn keine der Bedingungen wahr ist.
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:
1
if(Labyrinth[x][y]=='K')
2
return1;
3
elseif(Labyrinth[x][y]=='#')
4
return0;
5
elseif(Labyrinth[x][y]=='.')
6
return0;
7
elseif(SchrittNach(x-1,y))
8
return1;
9
elseif(SchrittNach(x+1,y))
10
return1;
11
elseif(SchrittNach(x,y-1))
12
return1;
13
elseif(SchrittNach(x,y+1))
14
return1;
15
elseif(Labyrinth[x][y]==' ')
16
return0;
17
else
18
return0;// 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:
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?
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.
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.
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[][]?
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...
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?
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?
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.
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)...
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.
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.
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:
1
#include<iostream>
2
#include<stdlib.h>
3
usingnamespacestd;
4
5
6
7
intSchrittNach(intx,inty)
8
{
9
charLabyrinth[10][11];
10
11
if(Labyrinth[x][y]=='K')
12
{
13
return1;
14
}
15
elseif(Labyrinth[x][y]=='#')
16
{
17
return0;
18
}
19
elseif(Labyrinth[x][y]=='.')
20
{
21
return0;
22
}
23
elseif(SchrittNach(x-1,y))
24
{
25
return1;
26
}
27
elseif(SchrittNach(x+1,y))
28
{
29
return1;
30
}
31
elseif(SchrittNach(x,y-1))
32
{
33
return1;
34
}
35
elseif(SchrittNach(x,y+1))
36
{
37
return1;
38
}
39
elseif(Labyrinth[x][y]==' ')
40
{
41
return0;
42
}
43
else
44
{
45
return0;
46
}
47
}
48
49
50
51
intmain()
52
{
53
intx,y;
54
charLabyrinth[10][11]={
55
"##########",
56
"# # #K #",
57
"# # #### #",
58
"# # #",
59
"# # # ####",
60
"### # ## #",
61
"# # #",
62
"## ##### #",
63
"# #",
64
"##########"
65
};
66
67
68
x=1;
69
y=1;
70
71
if(getchar()==' ')
72
{
73
SchrittNach(x,y);
74
}
75
else
76
{
77
}
78
79
80
system("pause");
81
return0;
82
}
Edit: Hab grad selbst bemerkt, dass das schon wieder völliger Blödsinn
ist...
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.
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)
1
#include<stdio.h>
2
#include<conio.h>
3
4
#ifndef TRUE
5
#define TRUE 1
6
#define FALSE 0
7
#endif
8
9
charLabyrinth[10][11]={
10
"##########",
11
"# # #K #",
12
"# # #### #",
13
"# # #",
14
"# # # ####",
15
"### # ## #",
16
"# # #",
17
"## ##### #",
18
"# #",
19
"##########"
20
};
21
22
voidOutput()
23
{
24
intx,y;
25
26
for(y=0;y<10;++y){
27
for(x=0;x<10;++x){
28
printf("%c",Labyrinth[x][y]);
29
}
30
printf("\n");
31
}
32
33
printf("\n");
34
35
{
36
charc=_getch();
37
}
38
}
39
40
intSchrittNach(intx,inty)
41
{
42
Output();
43
printf("Trying %d %d\n",x,y);
44
45
// Hurra! Da liegt er ja
46
//
47
if(Labyrinth[x][y]=='K')
48
returnTRUE;
49
50
// Käse nicht da, aber laufen wir in eine Mauer? Wenn ja
51
// dann kann dieser Schritt nicht Teil der Lösung sein
52
if(Labyrinth[x][y]=='#')
53
returnFALSE;
54
55
// OK. Die Maus steht im freien Feld und der Käse ist auch nicht da
56
// Das bedeutet: dieser SChritt könnte Teil der Lösung sein, wenn
57
// es in einer Richtung zum Käse geht
58
//
59
// allerdings hinterlässt sich die Maus eine Markierung, dass sie schon
60
// mal hier war, damit sie dasselbe Feld nicht noch einmal besucht. Wenn
61
// sie schon mal hier war, dann gehts hier auch nicht zum Käse
62
if(Labyrinth[x][y]=='.')
63
returnFALSE;
64
65
Labyrinth[x][y]='.';
66
67
if(SchrittNach(x+1,y)||
68
SchrittNach(x-1,y)||
69
SchrittNach(x,y-1)||
70
SchrittNach(x,y+1)){
71
printf("-> %d %d\n",x,y);
72
returnTRUE;
73
}
74
75
// in keiner der 4 Richtungen gehts zum Käse
76
// Schade. Damit steht auch fest, dass dieses Feld nicht auf
77
// dem Lösungsweg liegen kann. Mach die Markierung wieder weg
78
79
Labyrinth[x][y]=' ';
80
81
returnFALSE;
82
}
83
84
intmain()
85
{
86
if(SchrittNach(1,1))
87
printf("Kaese gefunden!\n");
88
else
89
printf("Kaese nicht gefunden :-( \n");
90
91
system("pause");
92
return0;
93
}
Probehalber auch mal den Käse unerreichbar einbauen oder überhaupt
rausnehmen.
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.
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 :-)
@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:
1
##########
2
# # #K #
3
# # #### #
4
# # #
5
# # # ####
6
### # ## #
7
# # #
8
## ##### #
9
# #
10
##########
Ausgabe:
1
##########
2
# # # #
3
### ## #
4
# # #
5
# ###### #
6
### # #
7
#K# ## # #
8
# # ## # #
9
# # #
10
##########
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?
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.
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...
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.
Thread beobachten
Seitenaufteilung abschalten