Rekursive Definitionen < Induktion < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:23 Mo 18.01.2010 | | Autor: | Pacapear |
Hallo zusammen!
Ich habe mal eine Frage zum Prinzip der rekursiven Definitionen.
Wir haben hier folgendes stehen:
Man sucht für jedes [mm] n\in\IN [/mm] ein f(n), indem man
(a) f(1) angibt,
(b) eine Vorschrift definiert, die f(n+1) aus den Elementen f(1) bis f(n) bestimmt für [mm] n\in\IN. [/mm]
Als Beispiel haben wir die Definition der Potenz gegeben:
[mm] x^n [/mm] wird definiert durch [mm] x^1=x [/mm] und [mm] x^{n+1}=x^1*x^n
[/mm]
So, ich hab mir da mal ein Beispiel zu gemacht.
Wenn nun also [mm] x^n=f(n) [/mm] ist, und ich möchte für n=5 [mm] f(5)=x^5 [/mm] berechnen, dann müsste ich ja dann folgendes machen:
[mm] x^1=x [/mm] und [mm] x^6=x^1*x^5
[/mm]
Aber was will ich denn da mit dem [mm] x^6, [/mm] das interessiert mich doch gar nicht... ![[haee]](/images/smileys/haee.gif "[haee]")
LG, Nadine
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:29 Mo 18.01.2010 | | Autor: | fred97 |
> Hallo zusammen!
>
> Ich habe mal eine Frage zum Prinzip der rekursiven
> Definitionen.
>
> Wir haben hier folgendes stehen:
>
> Man sucht für jedes [mm]n\in\IN[/mm] ein f(n), indem man
> (a) f(1) angibt,
> (b) eine Vorschrift definiert, die f(n+1) aus den
> Elementen f(1) bis f(n) bestimmt für [mm]n\in\IN.[/mm]
>
> Als Beispiel haben wir die Definition der Potenz gegeben:
>
> [mm]x^n[/mm] wird definiert durch [mm]x^1=x[/mm] und [mm]x^{n+1}=x^1*x^n[/mm]
>
> So, ich hab mir da mal ein Beispiel zu gemacht.
>
> Wenn nun also [mm]x^n=f(n)[/mm] ist, und ich möchte für n=5
> [mm]f(5)=x^5[/mm] berechnen, dann müsste ich ja dann folgendes
> machen:
>
> [mm]x^1=x[/mm] und [mm]x^6=x^1*x^5[/mm]
>
> Aber was will ich denn da mit dem [mm]x^6,[/mm] das interessiert
> mich doch gar nicht...
Nimm n=4
FRED
>
> LG, Nadine
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:04 Mo 18.01.2010 | | Autor: | Pacapear |
Hallo Fred!
> Nimm n=4
Das hatte ich auch erst überlegt, aber ich war dann etwas verwirrt, weil in der Erklärung der rekursiven Defintion ja stand, dass ich, wenn ich f(n) - bei mir also f(5) - suche, dass ich das dann aus den Elementen f(1) bis f(n+1) - bei mir dann eben f(6) - erhalte.
Wenn ich jetzt n=4 wähle, würde ich ja laut er der Erklärung f(4) suchen... ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
LG Nadine
|
|
|
| |
|
Bei dir steht:
Wir haben hier folgendes stehen:
Man sucht für jedes $ [mm] n\in\IN [/mm] $ ein f(n), indem man
(a) f(1) angibt,
(b) eine Vorschrift definiert, die f(n+1) aus den Elementen f(1) bis f(n) bestimmt für $ [mm] n\in\IN. [/mm] $
D.h., dass du f(n+1) suchst und es dir aus f(1) bis f(n) konstruierst.
Demzufolge erhälst du [mm] f(5)=x^{1} [/mm] * [mm] x^{4} [/mm] .
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:53 Fr 22.01.2010 | | Autor: | Pacapear |
Hallo!
> Bei dir steht:
>
> Wir haben hier folgendes stehen:
>
> Man sucht für jedes [mm]n\in\IN[/mm] ein f(n), indem man
> (a) f(1) angibt,
> (b) eine Vorschrift definiert, die f(n+1) aus den
> Elementen f(1) bis f(n) bestimmt für [mm]n\in\IN.[/mm]
>
> D.h., dass du f(n+1) suchst und es dir aus f(1) bis f(n)
> konstruierst.
> Demzufolge erhälst du [mm]f(5)=x^{1}[/mm] * [mm]x^{4}[/mm] .
Hmm...
Im Buch steht, dass wir f(n) suchen mittels einer Vorschrift, die f(n+1) aus f(1) bis f(n) ermittelt.
Und du sagst mir nun, dass ich eigentlich f(n+1) suche.
Das verwirrt mich irgendwie...
Kannst du mir vielleicht nochmal erklären, warum bei mir die 5 nun nicht mehr n ist
(obwohl ich ja f(n)=f(5) suche) sondern plötzlich n+1?
LG Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:19 Fr 22.01.2010 | | Autor: | rainerS |
Hallo Nadine!
> Hallo!
>
> > Bei dir steht:
> >
> > Wir haben hier folgendes stehen:
> >
> > Man sucht für jedes [mm]n\in\IN[/mm] ein f(n), indem man
> > (a) f(1) angibt,
> > (b) eine Vorschrift definiert, die f(n+1) aus den
> > Elementen f(1) bis f(n) bestimmt für [mm]n\in\IN.[/mm]
> >
> > D.h., dass du f(n+1) suchst und es dir aus f(1) bis f(n)
> > konstruierst.
> > Demzufolge erhälst du [mm]f(5)=x^{1}[/mm] * [mm]x^{4}[/mm] .
>
> Hmm...
>
> Im Buch steht, dass wir f(n) suchen mittels einer
> Vorschrift, die f(n+1) aus f(1) bis f(n) ermittelt.
>
> Und du sagst mir nun, dass ich eigentlich f(n+1) suche.
>
> Das verwirrt mich irgendwie...
Ich denke, dich verwirrt die Notation: das Problem ist, dass hier die Variable $n$ in zwei verschiedenen Bedeutungen benutzt wird:
1. als unabhängige Variable einer Funktion: $f(n)$ ist der Wert der Funktion [mm] $f:\IN\to [/mm] M$ an der Stelle [mm] $n\in \IN$ [/mm] (für irgendein $M$, das für jedes konkrte Beispiel angegeben wird). Das ist die Stelle "wir suchen $f(n)$", wo eine abstrakte Funktion gemeint ist. Wie diese Funktion definiert ist, ist zunächst nicht gesagt.
Aber dann haben wir die zweite Bedeutung:
2. $n$ als Platzhalter für eine Zahl: für einen gegebenen Wert [mm] $n\in\IN$ [/mm] habe ich eine Vorschrift, die mir $f(n+1)$ durch [mm] $f(1)$,\dots,$f(n)$ [/mm] ausdrückt. Das heisst, da steht eigentlich:
[mm] \forall n\in\IN: f(n+1) = \dots \text{(hier kommen $f(1)$,\dots,$f(n)$ vor)} [/mm]
Um das auseinanderzuhalten, kannst du doch einfach unterschiedliche Symbole nehmen:
1. Es geht um eine Funktion [mm] $f:\IN\to [/mm] M$, deren Funktionswert an der Stelle $k$ durch $f(k)$ gegeben ist.
2. Für einen gegebenen Wert [mm] $n\in\IN$ [/mm] habe ich eine Vorschrift, die mir $f(n+1)$ durch [mm] $f(1)$,\dots,$f(n)$ [/mm] ausdrückt.
>
> Kannst du mir vielleicht nochmal erklären, warum bei mir
> die 5 nun nicht mehr n ist
>
> (obwohl ich ja f(n)=f(5) suche) sondern plötzlich n+1?
Ich versuche mal, das in Worten zu formulieren: die Vorschrift (b) bedeutet doch, dass du ein Element (hier: $f(n+1)$) berechnen kannst, wenn du alle Vorgängerelemente [mm] $f(1),\dots,f(n)$ [/mm] kennst.
So, die Fragestellung war: wie berechnest du [mm] $x^5$. [/mm] Regel (b) sagt dir, das du das kannst, wenn du alle Vorgänger [mm] $x^1$, $x^2$, $x^3$, $x^4$ [/mm] kennst. Jetzt musst du das formalisieren: was ist in diesem Fall $f(n)$? Wenn wir sagen, [mm] $f(n)=x^n$, [/mm] dann bedeutet das:
[mm]\begin{matrix} f(1) & f(2) & f(3) & f(4) & f(5) \\
x^1 & x^2 & x^3 & x^4 & x^5 \end{matrix}[/mm]
Und wenn du $f(5)$ suchst, dann muss das, damit Regel (b) passt gerade $f(n+1)$ sein, also $n=4$.
Viele Grüße
Rainer
|
|
|
| |
|
Das n soll dir bei der Nummerierung helfen (s.u.). Grundsätzlich bedeutet f(n+1) nur:
Wenn ich schon f(1) bis f(n) kenne, wie berechne ich dann (daraus) das nächste Glied.
Wenn Du also die Nr. 100 berechnen willst, so musst du die Glieder bis 99 kennen. "Von 1 bis n bekannt" bedeutet dann: "Von 1 bis 99 bekannt". Also ist n=99. Da du Nr. 100 berechnen willst, ist 100 dann n+1.
__________________
Nun ein Beispiel, wozu man das so "kompliziert" schreibt: f(0)=1, f(1)=1 und f(n+1)=f(n)+f(n-1).
Was jetzt?
Wenn du das nächste (n+1) Glied ausrechnen willst, musst du den Vorgänger (n) und den Vor-Vorgänger (n-1) kennen und beide zusammenzählen. Also
n=1: Wir kennen Nr. 0 und Nr. 1. Nun wird Nr. 2 berechnet als
f(2)=f(1+1)=f(1)+f(1-1)=f(1)+f(0)=1+1=2 (Summe der beiden Vorgänger)
n=2: Wir kennen Nr. 1 und Nr. 2. Nun wird Nr. 3 berechnet als
f(3)=f(2+1)=f(2)+f(2-1)=f(2)+f(1)=2+1=3 (Summe der beiden Vorgänger)
n=3: Wir kennen Nr. 2 und Nr. 3. Nun wird Nr. 4 berechnet als
f(4)=f(3+1)=f(3)+f(3-1)=f(3)+f(2)=3+2=5 (Summe der beiden Vorgänger)
n=4: Wir kennen Nr. 3 und Nr. 4. Nun wird Nr. 5 berechnet als
f(5)=f(4+1)=f(4)+f(4-1)=f(4)+f(3)=5+3=8 (Summe der beiden Vorgänger)
n=5: Wir kennen Nr. 4 und Nr. 5. Nun wird Nr. 6 berechnet als
f(6)=f(5+1)=f(5)+f(5-1)=f(5)+f(4)=8+5=13 (Summe der beiden Vorgänger)
usw.
Wie du erkennen kannst, helfen die Ausdrücke wie n, n+1, n-1 usw., zu erkennen, welches Glied du nehmen musst.
Wenn du das obige Beispiel verstanden hast, hier noch mal eine nicht-rekursive Darstellung:
[mm] a_1 =\bruch{3^4}{2}, a_2 =\bruch{4^5}{3},a_3 =\bruch{5^6}{4} [/mm] usw.
Wie schreibt man das so auf, dass andere nun die Gesetzmäßigkeit erkennen und ein Computer aus der Index-Nr. sofort den Wert errechnen kann?
Lösung: [mm] a_n =\bruch{(n+2)^{n+3}}{n+1}
[/mm]
|
|
|
|
