noch eine Rekursionsgleichung |
21.01.2007, 17:25 | anka1 | Auf diesen Beitrag antworten » | ||||
noch eine Rekursionsgleichung 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 | AD | 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. |
||||||
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 | AD | Auf diesen Beitrag antworten » | ||||
Nein, ich meine folgendes: Betrachten wir mal alle Sequenzen der Länge , die auf 0 enden. Lassen wir diese 0 weg, dann darf an vorletzter Stelle keine 0 stehen. Also gilt Nun betrachten wir mal alle Sequenzen der Länge , die nicht auf 0 enden. Also steht dort 1 oder 2, und die (n-1)-Sequenz davor muss nur die allgemeine Bedingung erfüllen: Dies umgeformt ergibt , und mit statt heißt das . Beides jetzt in (*) eingesetzt ergibt , also . |
||||||
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 | AD | 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!!! |
||||||
Anzeige | ||||||
|
||||||
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 |
||||||
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 ). Wir interessieren uns für die Sequenzen der Länge , welche auf enden, d.h. wir haben nur noch "Plätze" zu bestimmen. Da keine zwei Nullen hintereinander stehen dürfen, ist die einzige Einschränkung, dass an der vorletzten Stelle keine steht. Nun, insgesamt gibt es Möglichkeiten für diese Plätze, aber dabei haben wir genau 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 | AD | Auf diesen Beitrag antworten » | ||||
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 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).
Man muss es ja nicht g(n) nennen. Aber wenn man irgendeine Rekursion 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 und ist das in 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 | AD | Auf diesen Beitrag antworten » | ||||
Nutzt man sowie , dann sieht die erhaltene explizite Formel noch etwas übersichtlicher aus: |
||||||
22.01.2007, 17:39 | anka1 | Auf diesen Beitrag antworten » | ||||
will ja kein Formel-Schönheitspreis gewinnen 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 | AD | Auf diesen Beitrag antworten » | ||||
Du nicht - aber ich. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |