Was macht folgendes Programm? < C/C++ < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:44 Mo 19.03.2007 | | Autor: | sven75 |
Hallo ich habe hier folgendes Programm:
#include <stdio.h>
float funk (int zahl) ;
main ()
{
int i;
printf(" Eingabe");
scanf("%d", &i);
printf(" Ausgabe(%d) = %f",i,funk(i));
}
float funk (int zahl)
{
float erg=0.0;
if (zahl>0)
erg=zahl+funk(zahl/3) /funk(zahl-1);
else erg=1.0;
return(erg);
}
Nun meine Fragen dazu:Erstmal terminiert dieses Programm für jede zulässige Eingabe?Habe das Programm mal getestet und es geht bis 999 das schafft der Rechner noch, danach hängt er sich dann auf bzw. er kann es wohl nicht mehr berechnen.Wie kann ich jetzt erkennen ob das Programm für jede zulässige Eingabe terminiert?
Das Programm ist meiner Meinung nach entweder Rekursion oder Iteration wenn ich mich nicht täusche.Sorry aber meine C++ Kenntnisse sind absolut begrenzt.
Das größte Problem habe ich mit folgender Zeile:
erg=zahl+funk(zahl/3) /funk(zahl-1);
Wie geht man am besten daran das man versteht was genau in diesem Schritt abläuft?
Hoffe jemand kann ein wenig Licht ins Dunkel bringen.Danke schonmal!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:37 Di 20.03.2007 | | Autor: | comix |
"terminiert dieses Programm für jede zulässige Eingabe?"
Was sind die zulässigen Eingaben? Das kann man an der Definition von funk() ablesen.
Für welche dieser Eingaben terminiert das Programm sofort? (if-Abfrage)
Was passiert bei den anderen Werten?
Ablauf des Programms (ab dem ersten Aufruf von funk()):
funk() wird von main aufgerufen mit einem zulässigen Wert:
Ist der Wert größer 0, so wird ein Term ausgewertet. Bei der Auswertung wird funk () zweimal aufgerufen.
Für jeden dieser Aufrufe geht jetzt die Sache von vorn los. Hier ein Beispiel:
funk (10) führt zum Aufruf von funk(3) und funk(9).
funk(3) führt zum Aufruf von funk(1) und funk(2).
funk(9) führt zum Aufruf von funk(3) und funk(8).
funk(1) führt zum Aufruf von funk(0) und funk(0)
funk(2) ...
funk(3) ...
funk(8) ...
funk (0) liefert den Wert 1 zurück.
...
Hast Du jetzt eine Idee, wie Du das Terminieren zeigen kannst?
Technisch gesehen:
Bei jedem Aufruf von funk() werden die lokalen Variablen auf den Stack geschrieben (in diesem Fall: int und float).
Falls funk in den then-Teil verzweigt wird funk bei jeder Rekursion zweimal aufgerufen, die Anzahl der Aufrufe verdoppelt sich also. Der Speicherbedarf vergrößert sich exponentiell, ähnlich wie beim Weizenkorn auf dem Schachbrett ("Lege auf das erste Feld ein Korn und auf die nächsten jeweils die doppelte Anzahl". Der Wunsch des Mannes konnte nicht erfüllt werden, er wurde geköpft (der Mann).)
(Iteration wird mit einer Schleife implementiert: while, for, ... Eine Iteration ist oft schneller, aber nicht so elegant!)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:17 Di 20.03.2007 | | Autor: | sven75 |
Danke schonmal für die ausführlichen Erläuterungen.Hab das ganze mal für verschiedene Werte versucht nachzuvollziehen und versucht auf das Ergebnis das der PC liefert zu kommen muß aber leider passen.Nehmen wir mal das Beispiel 5:
funk(5) ruft funk(1) und funk(4) auf
funk(1) ruft funk(0) und funk(0) auf
funk(4) ruft funk(1) und funk(3) auf
funk(0) liefert 1 zurück
funk(0) liefert 1 zurück
funk(1) ruft funk(0) und funk(0) auf
funk(3) ruft funk(0) und funk(2) auf
oder ist hier schon Schluß da funk(0) schon das Ende bedeutet wegen Vorbedingung?Sorry aber ich steh hier absolut auf dem Schlauch und es ärgert mich kolossal das ich das nicht nachvollziehen kann.Das ist schon schlimm genug und noch übler macht es die Frage ob das Programm für jede zulässige Eingabe terminiert.Wie kann ich mir das Wissen am besten aneignen.Ist "nur" ein Nebenfach aber trotzdem würd ich gern dahintersteigen.
|
|
|
| |
|
um zu zeigen dass es terminiert, muss Du einfach zeigen dass es auf jedem Pfad irgendwann zum Abbruchkriterium kommt. Man kann das in etwa mit der Vollständigen Induktion vergleichen.
Ich weiß nicht wie man das Wissen aneignet. Ich hatte noch in deer Scule ein Paar rekursive Programme gemacht und Sie nachfolzogen. In der eit hatte ich versucht das ganze mal im Kopf ablaufen zu lassen.  Na ja ist schon ein irres Ding die Rekursion. Mit der Zeit aber bekommt man da so ein Griff.
Bis dann
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 06:37 Mi 21.03.2007 | | Autor: | comix |
Um zu beweisen, dass das Programm terminiert, muss in diesem Fall am Ende jeder Kette funk(0) aufgerufen werden. Das kann mit vollständiger Induktion bewiesen werden: Da bei jedem Rekursiondurchlauf die Eingabeparameter (echt) kleiner werden ist das jetzt eine Frage des hinschreibens.
Um den Ablauf bei der Rekursion zu verstehen würde ich ein Blatt Papier verwenden. Versuch es mal mit diesem Beispiel:
main () {
printf ("Fakultät von 5: %ld", fakultaet (5));
}
long fakultaet (long wert) {
if (wert <= 1)
return (1);
return (wert * fakultaet (wert - 1));
}
Am besten Schritt für Schritt auf dem Papier nachvollziehen. Das Programm habe ich nicht kompiliert, dafür musst Du sicher noch ein paar Kleinigkeiten hinzufügen.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:05 Mo 26.03.2007 | | Autor: | balbina |
Hallo,
ich hab das selbe Problem, arbeite an der selben Aufgabe.
Also ich habe das Programm getestet und es geht sogar bis 3000´, die Berechnung dauer aber sehr lange min. 10 min. Bis 1000 geht es sehr schnell.
Nun meine Frage:
Ist es richtig das es sich hier um Rekursion handelt?
Ich meine ja.
Terminiert das Programm bei jeder zulässiger Eingabe?
Ich meine ja, es gibt aber eine Speicher und Prozessorleistungsbegrenzung. Ab 2000 dauert die Berechnung schon viel zu lange, wäre meine Antwort.
Berechnen Sie das Ergebniss für I=5
es kommt 5.441861 raus.
Aber es soll auch Schritt für in einer Tabelle die Werte für erg und zahl (bzw. i) angeben werten. Wodurch sind die Schritte bestimmt d.h an welcher Stelle im Programm verändert sich jeweils zahl und erg?
Hier stehe ich total auf der Leitung.
Vielen Dank im Vorraus.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:22 Do 29.03.2007 | | Autor: | Becks |
>Hallo,
Hallo :)
>
>ich hab das selbe Problem, arbeite an der selben Aufgabe.
>
>Also ich habe das Programm getestet und es geht sogar bis >3000´, die Berechnung dauer aber sehr lange min. 10 min. >Bis 1000 geht es sehr schnell.
Glaub mir, es wird auch mit höheren Zahlen gehen, denn wie schon gesagt wird bei jedem Funktionsaufruf der Wert kleiner.
>
>Nun meine Frage:
>
>Ist es richtig das es sich hier um Rekursion handelt?
>
>Ich meine ja.
Und damit hast du Recht. Rekursion ist ein Selbstaufruf. Und wie du siehst, ruft sich die Funktion funk selbst auf. :)
>Terminiert das Programm bei jeder zulässiger Eingabe?
>Ich meine ja, es gibt aber eine Speicher und >Prozessorleistungsbegrenzung. Ab 2000 dauert die >Berechnung schon viel zu lange, wäre meine Antwort.
Das Programm terminiert bei jeder zulässigen Eingabe. Ja. Ich würde aber auf jeden Fall schreiben, warum es terminiert. Und zwar, weil doch immer der Wert von Zahl von Aufruf zu Aufruf verkleinert wird.
Wenn man für I = 5 wählt hat man folgende Aufrufe von der Funktion funk:
Funktionsaufruf mit zahl = 5
Funktionsaufruf mit zahl = 1
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 4
Funktionsaufruf mit zahl = 1
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 3
Funktionsaufruf mit zahl = 1
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 2
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 1
Funktionsaufruf mit zahl = 0
Funktionsaufruf mit zahl = 0
Schau dir das genau an und ich denke dann sollte klar sein wie es läuft. :)
>
>Berechnen Sie das Ergebniss für I=5
>es kommt 5.441861 raus.
genau. :)
>Aber es soll auch Schritt für in einer Tabelle die Werte >für erg und zahl (bzw. i) angeben werten. Wodurch sind die >Schritte bestimmt d.h an welcher Stelle im Programm >verändert sich jeweils zahl und erg?
Ich denke mal, dass die Schritte die Funktionsaufrufe sein werden. Bau doch einfach ein paar Ausgaben in das Programm mit ein. So kannst du am Besten sehen, wo was passiert.
Und denke daran, jede Funktion hat einen Rückgabewert. Das gilt auch bei Rekursion. Das ist zwar fürchterlich verschachtelt dann, aber wenn man es sich in Ruhe anschaut, klappt es.
>
>Hier stehe ich total auf der Leitung.
>
>Vielen Dank im Vorraus.
Bitte :)
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:56 So 01.04.2007 | | Autor: | balbina |
Hallo,
hier nochmal eine Aufstellung wenn das richtig ist habe ich es kappiert. Ist eigentlich gar nicht so schwer.
Funk (5) ruft funk (4) und funk (1) auf
Funk (4) ruft funk (3) und funk (1) auf
funk (1) ruft funk (0) und funk (0) auf
Funk (3) ruft Funk (2) und funk (1) auf
funk (1) ruft funk (0) und funk (0) auf
Funk (1) ruft funk (0) und funk (0) auf
Funk (2) ruft Funk (1) und Funk (0) auf
Funk (1) ruft funk (0) und funk (0) auf
Habe jeweil die Aufrufe untereinander geschrieben um es hoffentlich übersichtlicher zu machen.
Nochmal eine Frage wie bekomme ich hin das ich das Programm so verändere das es mir für jede Zeile das Ergebnis ausgibt?
Grüße und danke für die Hilfe, bin jetzt um einiges vorrangekommen zum Thema Rekursion.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:25 Mo 02.04.2007 | | Autor: | Becks |
Hallo :)
Ja, man muss sich immer erst in Rekursionen eindenken. Aber ich weiß nicht ob du es richtig verstanden hast.
Schau nochmal auf die Zeile:
erg=zahl+funk(zahl/3) /funk(zahl-1);
Wenn zahl = 5, wird zuerst funk(5/3) aufgerufen. Der hintere Teil wird es später abgearbeitet. Also der "/funk(5-1)"
funk(5/3) wird also aufgerufen und bei dem Aufruf ist dann zahl = 1.
Jetzt wird also funk(1/3) aufgerufen und wir bekommen den Rückgabewert 1. jetzt wird der nächste Teil betrachtet also "/funk(1-1)" Da bekommen wir wieder den Rückgabewert 1.
Jetzt betrachten wir erst den hinteren Teil "/funk(5-1)"
Bei diesem Programm läuft alles nacheinander ab. :)
Wegen der Ausgabe: Lass dir einfach die Variablen ausgeben, die du haben magst. Im Quellcode steht eigentlich alles was du brauchst. Und Ausgaben kriegst du bestimmt hin. ;)
MFG Becks
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 09:24 Mi 20.06.2007 | | Autor: | nic070 |
Hallo,
sitze gerade an der selben Aufgabe.Habe aber ein Verständisproblem bei der Frage:Wodurch sind die Schritte bestimmt,d.h. an welcher Stelle im Programm verändern sich jeweils zahl und erg?Kann mir jemand auf die Sprünge helfen.
Vielen Dank.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:20 Fr 22.06.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
