"Rekursiv definierte Funktion" < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:35 Di 03.11.2009 | | Autor: | berschel |
| Aufgabe | | [Dateianhang nicht öffentlich] |
Hallo,
ich soll ein Programm schreiben das o.g. "Funktion" benutzt.
Das Zeichen habe ich noch nie zuvor gesehen (ist das nicht ein kyrillisches F oder sowas?) und Wikipedias Definition von diesem Zeichen bringt mich auch kein bisschen weiter.
Was ist denn damit gemeint?
Ich hoffe ihr könnt mir helfen.
Viele Grüße
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
Hallo Sandra,
> [Dateianhang nicht öffentlich]
> Hallo,
> ich soll ein Programm schreiben das o.g. "Funktion"
> benutzt.
> Das Zeichen habe ich noch nie zuvor gesehen (ist das nicht
> ein kyrillisches F oder sowas?) 
> und Wikipedias Definition
> von diesem Zeichen bringt mich auch kein bisschen weiter.
> Was ist denn damit gemeint?
Das ist das griechische Phi (als Großbuchstabe), im Latexcode ist das ein /Phi [mm] $\Phi$; [/mm] schaue mal ![[]](/images/popup.gif) dort rein, da ist das ganze Alphabet mal in einer Übersicht dargestellt.
Das [mm] $\Phi$ [/mm] ist lediglich ein Name bzw. eine Bezeichnung für die Funktion, wenn es dich sehr stört, ersetze es überall durch das "vertraute" f: $f(a,b)=...$
>
> Ich hoffe ihr könnt mir helfen.
>
> Viele Grüße
Gruß
schachuzipus
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:46 Mi 04.11.2009 | | Autor: | berschel |
Ich habe das jetzt mal so umgeschrieben:
(1) f (0, b) = b + 1
(2) f ((a + 1), 0) = f (a, 1)
(3) f ((a + 1), (b + 1)) = f (a, f((a + 1), b))
Aber irgendwie bringt mich das nicht weiter. Ich sehe auch keinen Zusammenhang zwischen den drei Gleichungen.
Die muss ich jetzt doch irgendwie verknüpfen, oder?
Das einzige, was mir da in den Sinn kommt, ist Gleichung (1) in Gleichung (3) einzufügen:
(3) f ((a+1), f(0, b)) = f (a, f((a + 1), b))
Wie mache ich denn jetzt weiter?
Würde mich über Tipps echt freuen.
Eure verzweifelte Studentin
|
|
|
| |
|
Hiho,
letztlich sieht es schlimmer aus, als es ist.
Du hast hier folgendes Problem:
Was ist denn bspw $f(2,5)$ ? Wie du feststellst, kannst du das nicht ausrechnen, weil es dafür keine direkte Berechnungsvorschrift gibt, aber du kannst es "runterbrechen" auf eine bekannte Form.
Ziel ist es natürlich, es auf die einzige Form zu bringen, wo ein "richtiges Ergebnis" rauskommt, nämlich $f(0,b)$, denn das ist nämlich $b+1$.
Dafür müssen wir also versuchen die erste Zahl auf 0 runterzubekommen und wie man erkennt, können wir bei dieser Form nur den 3. Schritt anwenden, da beim ersten Schritt ja die erste Zahl 0 ist, beim zweiten die Zweite Zahl 0.
Das ist hier nicht gegeben, also die dritte Form, die sieht wie folgt aus:
$f(a+1,b+1) = f(a,f(a+1,b))$
Für unseren Fall also:
$f(2,5) = f(1,f(2,4))$
Um nun weiterzumachen, müssten wir also erst $f(2,4)$ ausrechen.
Und da würden wir wieder von Vorne anfangen.
Du hast also 3 Schritte.
1.) Welche Form hat meine Eingabe
2.) Umformen und prüfen ob ich fertig bin
3.) Wenn nicht => bei 1. mit den neuen Werten anfangen oder fertig.
Und das sollst du nun Programmieren.
Ist gar nicht so schwer 
MFG,
Gono.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:15 Mi 04.11.2009 | | Autor: | berschel |
Ok also also den einen Schritt hab ich soweit glaub ich verstanden.
Wenn ich so weitermache erhalte ich:
[mm] f (2,5) = f (1, f (2,4)) [/mm]
[mm] f (2,4) = f (1, f (2,3)) [/mm]
[mm] f (2,3) = f (1, f (2,2)) [/mm]
[mm] f (2,2) = f (1, f (2,1)) [/mm]
[mm] f (2,1) = f (1, f (2,0)) [/mm]
Aber jetzt ist ja die zweite Zahl 0 und nicht die erste? Oder hab ich's doch falsch verstanden?
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:21 Mi 04.11.2009 | | Autor: | Teufel |
Hi!
Wenn du jetzt f(2,0) weiter zerkleinerst, wird irgendwann auch das a 0.
f(2,0)=f(1,1)
f(1,1)=f(0,1)
f(0,1)=2
Also ist f(2,0)=2, was du dann wieder zurück einsetzen kannst... anstrengende Angelegenheit, aber das zu programmieren ist viel einfacher als das zu Fuß zu rechnen.
Hast du schon mal rekursive Funktionen programmiert?
![[anon]](/images/smileys/anon.png "[anon]") Teufel
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:34 Mi 04.11.2009 | | Autor: | berschel |
Habe soweit ich weiß noch nie eine rekursive Funktion programmiert, eventuell mal in der Schule (war auf nem TG mit Informatikprofil) aber dann weiß ichs nicht mehr). Weiß nur, dass die Funktion sich dann selbst aufrufen muss.
Aber naja, ich sollte vielleicht erstmal wissen, was die Funktion denn machen soll, bevor ich sie programmieren kann ;)
Mit welcher von den Formeln kann ich denn das a auch noch zerkleinern? Da blick ich jetzt leider nicht durch :(
|
|
|
| |
|
> Habe soweit ich weiß noch nie eine rekursive Funktion
> programmiert, eventuell mal in der Schule (war auf nem TG
> mit Informatikprofil) aber dann weiß ichs nicht mehr).
> Weiß nur, dass die Funktion sich dann selbst aufrufen
> muss.
>
> Aber naja, ich sollte vielleicht erstmal wissen, was die
> Funktion denn machen soll, bevor ich sie programmieren kann
Es empfiehlt sich natürlich, zuerst mal mittels Papier
und Bleistift eine kleine Tabelle für f aufzustellen.
>
> Mit welcher von den Formeln kann ich denn das a auch noch
> zerkleinern? Da blick ich jetzt leider nicht durch :(
R1: f(0,b)=b+1
R2: f(a+1,0)=f(a,1)
R3: f(a+1,b+1)=f(a,f(a+1,b))
Hallo Sandra,
Nennen wir die zwei Argumente der Funktion f
einmal x und y. Die stehen hier natürlich für
Zahlen aus [mm] \IN_0. [/mm] Nun seien zwei beliebige
derartige Werte für x und y gegeben. Wie erhalten
wir f(x,y) ? Jetzt sind verschiedene Fälle zu
unterscheiden:
1.) x=0
in diesem Fall sagt Regel R1, dass f(x,y)=f(0,y)=y+1
2.) x>0 und y=0
in diesem Fall sagt R2: f(x,y)=f(x,0)=f(x-1,1)
3.) x>0 und y>0
jetzt kommt R3 zum Zug: f(x,y)=f(x-1,f(x,y-1))
Ich kenne Ada nicht. Kurz skizziert könnte man aber
die rekursive Definition für f so fassen:
[mm] f(x,y):=\begin{cases} y+1 & \mbox{falls } x=0 \\ f(x-1,1) & \mbox{falls } x>0\ \wedge\ y=0\\ f(x-1,f(x,y-1)) & \mbox{falls } x>0\ \wedge\ y>0 \end{cases}
[/mm]
Der rekursive Aufruf nach diesem Rezept landet
zwangsläufig nach einer endlichen Anzahl von
Schritten bei Regel 1 und kann dann "Nägel mit
Köpfen" machen, also konkrete Zahlenwerte
berechnen.
Natürlich muss die so definierte Funktion für jedes
eingegebene Paar (x,y) von neuem die gesamte
Rechnerei durchführen. Sollte die Absicht sein,
die Funktion f zu tabellieren, würde sich wohl
ein anderer, weniger rechenintensiver Weg empfehlen,
bei welchem die schon berechneten Werte tabellarisch
gespeichert werden.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:10 Mi 04.11.2009 | | Autor: | berschel |
Okay!
Mensch, ich bin das alles falsch angegangen. Ist ja wirklich harmloser als es aussieht!
Die Aufgabenstellung war so unklar formuliert und dazu dann noch die seltsam anmutenden Gleichungen... Ich wusste nicht, ob ich A und B vom Benutzer eingeben lassen bzw. ob oder was das Programm ausgeben muss.
Ich habe es soweit implementiert, jedoch verstehe ich eins noch nicht ganz.
Normalerweise hatte eine Funktion wie ich sie in der Schule kennen gelernt habe z.B. die Form f(x) = x².
Hier stehen aber in der Klammer zwei Werte. Wie ist das denn zu verstehen?
Das Programm gibt am Ende eine einzelne Zahl aus, ist das richtig so?
Viele Grüße
|
|
|
| |
|
> Okay!
> Mensch, ich bin das alles falsch angegangen. Ist ja
> wirklich harmloser als es aussieht!
> Die Aufgabenstellung war so unklar formuliert und dazu
> dann noch die seltsam anmutenden Gleichungen... Ich wusste
> nicht, ob ich A und B vom Benutzer eingeben lassen bzw. ob
> oder was das Programm ausgeben muss.
>
> Ich habe es soweit implementiert, jedoch verstehe ich eins
> noch nicht ganz.
>
> Normalerweise hatte eine Funktion wie ich sie in der Schule
> kennen gelernt habe z.B. die Form f(x) = x².
> Hier stehen aber in der Klammer zwei Werte. Wie ist das
> denn zu verstehen?
Irgendwie etwas schade, dass man in der Schule nur
oder fast nur Funktionen mit einer Variablen benützt,
aber mit ein paar wichtigen Ausnahmen, die man dann
aber eben meist nicht "Funktionen", sondern "Opera-
tionen" nennt. Eigentlich sind die Rechenoperationen
wie Addition, Subtraktion etc. nichts anderes als
Funktionen mit zwei Variablen:
[mm] f_1(x,y)=x+y [/mm] Addition
[mm] f_2(x,y)=x-y [/mm] Subtraktion
[mm] f_3(x,y)=x*y [/mm] Multiplikation
[mm] f_4(x,y)=x:y [/mm] Division
[mm] f_5(x,y)=x^y [/mm] Potenzieren
Oder: die Formel für die Berechnung des Zylinder-
volumens stellt eine Funktion mit zwei Variablen
r und h dar:
$\ [mm] V_{Zyl.}(r,h)\ [/mm] =\ [mm] \pi*r^2*h$
[/mm]
> Das Programm gibt am Ende eine einzelne Zahl aus, ist das
> richtig so?
Für ein gegebenes Zahlenpaar [mm] $(x,y)\in\IN_0^{\,2}$: [/mm] ja
Ein Beispiel: $\ f(3,4)\ =\ 125$
(das war das höchste, was mein Pascalprogramm
gerade noch schaffte, bevor es Probleme mit der
Rekursionstiefe bekam)
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:38 Mi 04.11.2009 | | Autor: | berschel |
Hab mich gerade lange gewundert, warum bei größeren Werten das Programm hängen bleibt... Tatsächlich geht es aber auch bei mir nicht weiter als bis (3,4)...
Vielen Dank an alle für die vielen Antworten!!!
|
|
|
|
