noch eine Rekursionsgleichung

21.01.2007, 17:25

anka1

noch eine Rekursionsgleichung

hier ist meine andere aufgabe:

Sei f(n) die Anzahl der Strings der Länge n, in denen nur die Symbole 0,1,2 vorkommen und in denen keine zwei Nullen hintereinander stehen.
Geben Sie die Rekursionsgleichung an und lösen Sie sie.

Ich hab das jetzt wieder mit ausprobieren versucht zu lösen, naja und bin schnell an meine grenzen gestossen.

also ich hab für
a1= {0,1,2} 3 möglichkeiten
a2={11,22,12,21,01,10,02,20} 8 möglichkeite
a3={ 111,222,122,212,221,112,211,121,010,011,101,110,020,022,202,220,021,102,120
,012,201,210}
22 möglichkeite..

naja dann hörts auch schon auf, und ich komm irgendwie auf keine gleichung, gibts irgendwie ne andere bessere möglichkeit??

21.01.2007, 17:55

Auf diesen Beitrag antworten »

Für Zwischenrechnungen betrachte zusätzlich mal noch die Funktion

g(n) ... Anzahl der Strings der Länge n, in denen nur die Symbole 0,1,2 vorkommen und in denen keine zwei Nullen hintereinander stehen, und wo am Ende eine Null steht

Dann kannst du eine passende Rekursion für das Paar f(n),g(n) aufstellen, und am Ende sogar wieder das g(n) eliminieren. Augenzwinkern

21.01.2007, 18:07

anka1

Auf diesen Beitrag antworten »

naja das is ja das problem..
um auf g(n) zu kommen muss ich auch wieder rumprobieren und das ist doch viel zu viel...

und komme da auch auf keine rekursion bzw. erkenne sie nicht:

g1= 1 möglichkeit
g2= 2 möglichkeiten
g3= 4 möglichkeiten
g4= 14 möglichkeiten

...

21.01.2007, 18:30

Auf diesen Beitrag antworten »

Nein, ich meine folgendes:

Betrachten wir mal alle Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ , die auf 0 enden. Lassen wir diese 0 weg, dann darf an vorletzter Stelle keine 0 stehen. Also gilt

$\begin{eqnarray*} g(n) = f(n-1)-g(n-1)\qquad (*) \end{eqnarray*}$

Nun betrachten wir mal alle Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ , die nicht auf 0 enden. Also steht dort 1 oder 2, und die (n-1)-Sequenz davor muss nur die allgemeine Bedingung erfüllen:

$\begin{eqnarray*} f(n)-g(n) = 2f(n-1) \end{eqnarray*}$

Dies umgeformt ergibt $\begin{eqnarray*} g(n)=f(n)-2f(n-1) \end{eqnarray*}$ , und mit $\begin{eqnarray*} n-1 \end{eqnarray*}$ statt $\begin{eqnarray*} n \end{eqnarray*}$ heißt das $\begin{eqnarray*} g(n-1)=f(n-1)-2f(n-2) \end{eqnarray*}$ . Beides jetzt in (*) eingesetzt ergibt

$\begin{eqnarray*} f(n)-2f(n-1) = f(n-1)-[f(n-1)-2f(n-2)] \end{eqnarray*}$ , also

$\begin{eqnarray*} f(n)) = 2[f(n-1)+f(n-2)]\qquad (**) \end{eqnarray*}$ .

21.01.2007, 18:37

anka1

Auf diesen Beitrag antworten »

booor noch mal langsam.

du sagtes:

Lassen wir diese 0 weg, dann darf an vorletzter Stelle keine 0 stehen.

Wieso darf dann an vorletzter stelle keine null stehen?? Wenn hinten keine null steht??
Ich steh voll aufm schlauch..versteh nich wie du auf (*) kommst, kannste du nochn schritt zurückgehn?

21.01.2007, 18:39

Auf diesen Beitrag antworten »

Die Lösung steht da, m.E. auch ausreichend erläutert. Jetzt streng dich mal an, schließlich sind wir hier im Hochschulbereich des Forums!!!

22.01.2007, 00:08

anka1

Auf diesen Beitrag antworten »

hmm studiere grad mal 3 monate, soll ich die frage mal im schulbereich fragen?
nee
mir is der Lösungsweg viel wichtiger als die lösung, weil ich noch ein haufen solcher aufgaben zu lösen hab...hmm

also:
f(n) ist ist die Anzahl der Strings der Länge n, in denen nur die Symbole 0,1,2 vorkommen und in denen keine zwei Nullen hintereinander stehen

g(n) ist die Anzahl der Strings der Länge n, in denen nur die Symbole 0,1,2 vorkommen und in denen keine zwei Nullen hintereinander stehen, und wo am Ende eine Null steht

dann hast du gesagt g(n)=f(n-1) - g(n-1)

Und es muss doch erlaubt sein obwohl ich studentin bin, wieso das so ist? Bin doch kein mathegenie nur weil studiere?

wär schön wenn mir das jemand simpel erklären könnte unglücklich

22.01.2007, 01:06

therisen

Auf diesen Beitrag antworten »

Ok, ich formuliere mal die Begründung von (*) ein wenig um, vielleicht hilft das (bin ja selbst ein Erstsemester Big Laugh

).

Wir interessieren uns für die Sequenzen der Länge $\begin{eqnarray*} n \end{eqnarray*}$ , welche auf $\begin{eqnarray*} 0 \end{eqnarray*}$ enden, d.h. wir haben nur noch $\begin{eqnarray*} n-1 \end{eqnarray*}$ "Plätze" zu bestimmen. Da keine zwei Nullen hintereinander stehen dürfen, ist die einzige Einschränkung, dass an der vorletzten Stelle keine $\begin{eqnarray*} 0 \end{eqnarray*}$ steht. Nun, insgesamt gibt es $\begin{eqnarray*} f(n-1) \end{eqnarray*}$ Möglichkeiten für diese $\begin{eqnarray*} n-1 \end{eqnarray*}$ Plätze, aber dabei haben wir genau $\begin{eqnarray*} g(n-1) \end{eqnarray*}$ Anordnungen zu viel gezählt (nämlich die, die als letzte Ziffer, d.h. (n-1)-te Ziffer, eine Null stehen haben. Also ziehen wir diese Anzahl von der Gesamtzahl ab.

Gruß, therisen

PS: Behandelt ihr das in Diskrete Strukturen (also Informatik)?

22.01.2007, 09:32

anka1

Auf diesen Beitrag antworten »

ok,
also da wir wissen das am ende eine null steht, ist ein platz schon vergeben und es sind noch n-1 plätze für die vergabe von 0, 1, 2 übrig (das ist mir klar)
das sind dann f(n-1) möglichkeiten..
Aber bei diesen f(n-1) möglichkeiten darf die null nicht an letzter stelle stehn (da ja insgesamt gesehn dann zwei nullen hinterander stehn, nicht erlaubt)..
das hab ich erstmal verstanden..

Wir müssen also alle anordnungen abziehen die als letzte stelle ein null (n-1) hat.
Da ja g(n) so definiert ist (also genauso wie f(n) nur mit dem zusatz, am ende steht eine null) wir aber davon ausgegangen sind, das wir nur noch n-1 plätze haben, müssen g(n-1) möglichkeiten abgezogen werden, das sind die möglichkeiten die zusätzlich (gegenüber f) eine null am ende haben.

Das hab ich doch jetzt richtig verstanden oder?

jetzt habe ich noch zwei fragen:
Woher kommt die algemeine bedingung: f(n)-g(n)=2f(n-1) ??
Und wie kommt man auf die Idee, dass so zumachen, also mit dem g(n).

P.S. Ich studiere IST, da is ein bisschen Informatik dabei..

22.01.2007, 10:04

Auf diesen Beitrag antworten »

Zitat:

Original von anka1
Woher kommt die algemeine bedingung: f(n)-g(n)=2f(n-1) ??

Das hab ich doch geschrieben: Da zählen wir alle gültigen n-Folgen, die nicht auf 0 enden - also müssen sie auf 1 oder 2 enden. Diesmal haben wir keine zusätzliche Bedingung an die (n-1) Zahlen vorher, d.h. wir können die bekannte Anzahl $\begin{eqnarray*} f(n-1) \end{eqnarray*}$ zugrundelegen: Also haben wir dann f(n-1) Sequenzen aus (n-1) Zahlen, wo wir dann eine 1 anhängen, und wir haben auch noch f(n-1) Sequenzen aus (n-1) Zahlen, wo wir dann eine 2 anhängen. Und f(n-1)+f(n-1) macht nun mal 2*f(n-1).

Zitat:

Original von anka1
Und wie kommt man auf die Idee, dass so zumachen, also mit dem g(n).

Man muss es ja nicht g(n) nennen. Aber wenn man irgendeine Rekursion $\begin{eqnarray*} (n-1)\to n \end{eqnarray*}$ aufbauen will, dann braucht man wegen dieses "Verbots" von zwei aufeinanderfolgenden Nullen irgendwie die Information über die letzte Stelle der vorherigen (n-1)-Sequenz, und die habe ich eben auf diese Weise reingebracht. Für mich ist deshalb so ein Schritt mehr als naheliegend, ich denke für die meisten Informatiker auch.

Es ist natürlich nicht gesagt, dass bei anderen ähnlichen Problemen es mit einer vergleichbaren Methode auch gelingt, so eine Hilfsfunktion wie g(n) anschließend auch gleich wieder zu eliminieren. Aber man kann's ja zumindest versuchen! Wer nichts ausprobiert, wird auch nicht zum Erfolg kommen.

22.01.2007, 14:46

anka1

Auf diesen Beitrag antworten »

Ok ich glaub ich habs jetzt einigermaßen verstande.

Ich hab f(n) ausgerechnet und komme auf folgendes:

für $\begin{eqnarray*} f_0 = 1 \end{eqnarray*}$ und $\begin{eqnarray*} f_1 = 3 \end{eqnarray*}$ ist

$\begin{eqnarray*} \lambda_1 = 1+\sqrt{3} \end{eqnarray*}$

$\begin{eqnarray*} \lambda_2 = 1-\sqrt{3} \end{eqnarray*}$

$\begin{eqnarray*} c_1 = \frac{1}{\sqrt{3}}+\frac{1}{2} \end{eqnarray*}$

$\begin{eqnarray*} c_2 = -\frac{1}{\sqrt{3}}+\frac{1}{2} \end{eqnarray*}$

das in

$\begin{eqnarray*} f_n = c_1\lambda_1^n + c_2\lambda_2^n \end{eqnarray*}$

eingesetzt, dürfte die geschlossene Form sein?

Hab das ganze mal mit f0=0 versucht, was ja irgendwie logisch ist, denn wenn ein String die Länge 0 hat, gibts ja auch 0 Möglichkeiten 0,1,2 anzuordnen, oder? Jedenfalls haut das dann nicht mehr hin.

22.01.2007, 16:16

therisen

Auf diesen Beitrag antworten »

Jep, stimmt.

22.01.2007, 16:38

Auf diesen Beitrag antworten »

Nutzt man $\begin{eqnarray*} c_1 = \frac{\sqrt{3}}{12} \lambda_1^2 \end{eqnarray*}$ sowie $\begin{eqnarray*} c_2 = -\frac{\sqrt{3}}{12} \lambda_2^2 \end{eqnarray*}$ , dann sieht die erhaltene explizite Formel noch etwas übersichtlicher aus:

$\begin{eqnarray*} f_n = \frac{\sqrt{3}}{12} \left[ (1+\sqrt{3})^{n+2} - (1-\sqrt{3})^{n+2} \right] \end{eqnarray*}$

Wink

22.01.2007, 17:39

anka1

Auf diesen Beitrag antworten »

will ja kein Formel-Schönheitspreis gewinnen smile

Danke für die Hilfe

P.S. ich hab noch eine aufgabe dieser art, nur noch komplizierter...(neue post dann *g*)

22.01.2007, 17:46

Auf diesen Beitrag antworten »

Du nicht - aber ich. Big Laugh

Neue Frage »

Antworten »

noch eine Rekursionsgleichung

Verwandte Themen