| Autor |
Beitrag |
    
spockgeiger
| | Veröffentlicht am Freitag, den 07. Januar, 2000 - 14:37: | 
|
hallo leute
ich habe hier ein interessantes problem, bei dem ich nicht weiterkomme.
um einen turm von hanoi mit n scheiben zu bewegen, braucht man 2^n-1 zueg.
soweit einfach. es wird jetzt interessanter:
falls man den turm von stelle 1 nach stelle 3 bewegen will, und keine direkten zuege von 1 nach 3 oder 3 nach 1 erlaubt sind, braucht man 3^n-1 zuege.
jetzt das wirklich interessante:
wenn man den turm von stelle 1 nach stelle 3 bewegen will, aber nur zuege "im uhrzeigersinn" erlaubt sind, d.h. von 1 nach 2, von 2 nach 3, und von 3 nach 1, habe ich die folgende rekursive formel herausgefunden:
a0 = 0 (nur der Form halber, um a2 nicht vordefinieren zu muessen)
a1 = 2
an = 2(an-2 + an-1) + 3
das ergibt folgende werte:
a1 = 2
a2 = 7
a3 = 21
a4 = 59
a5 = 163
a6 = 447
a7 = 1223
a8 = 3343
a9 = 9135
a10 = 24959
welcher von euch schlauen koepfen findet hierzu eine explizite formel oder zumindest einen hinweis darauf???
vielen dank im voraus
spockgeiger |
Zaph
| | Veröffentlicht am Samstag, den 08. Januar, 2000 - 15:05: |
|
Ich kenne da eine Methode, die allerdings ziemlich rechenintensiv (mit jeder Menge Gefahren, sich zu verrechnen!) ist. (Nein, liebe Leute, auch diese Methode ist nicht meine Erfindung, siehe Kommentare bei anderer Aufgabe...)
Sagt dir "Matrizenrechnung" was? Hast du ein Computer-Algebra-Programm?
Hast du dir die Aufgabe eigentlich selbst ausgedacht? Die Rekursionsformel scheint korrekt zu sein. |
Zaph
| | Veröffentlicht am Samstag, den 08. Januar, 2000 - 16:01: |
|
an = Nächste ganze Zahl bei (1 + W(3))n * (3 + 2*W(3))/6 - 1. (W() = Wurzel)
Puh, das war ein hartes Stück Arbeit! |
spockgeiger
| | Veröffentlicht am Samstag, den 08. Januar, 2000 - 19:24: |
|
danke, aber wie beweist man das???
spockgeiger |
spockgeiger
| | Veröffentlicht am Samstag, den 08. Januar, 2000 - 19:32: |
|
nochmal was:
die aufageb hab ich aus dem informatikstudium, eine zusatzaufageb zum programmieren mit rekursion, gibt es nicht eigenzlich doch eine genaue formel, die gibt es fuer die fibbonacci-reihe doch auch
gruesse
spockgeiger |
Zaph
| | Veröffentlicht am Samstag, den 08. Januar, 2000 - 23:14: |
|
Die Formel ist genau! ... wenn auch vielleicht etwas ungewöhnlich. Um die Formel zu beweisen, gehe ich mal einen Schritt in der Herleitung zurück und schreibe
an = (1 + W(3))n * (3 + 2*W(3))/6 + (1 - W(3))n * (3 - 2*W(3))/6 - 1.
Mit dieser Darstellung kannst du nun die Richtigkeit mit vollständiger Induktion beweisen. (Zeige: a0 = 0, a1 = 2 und die Rekursionsformel.)
Da der Term (1 - W(3))n * (3 - 2*W(3))/6 kleiner als 1/2 und an ganzzahlig, folgt die Behauptung.
Die HERLEITUNG dieser Formel hingegen ist nicht ganz so einfach. Wie gesagt, mit Matrizenrechnung könnte ich dir das erklären. Vielleicht hat ja jemand eine elegantere Methode. |
Ingo
| | Veröffentlicht am Sonntag, den 09. Januar, 2000 - 11:44: |
|
Weiß nicht,ob das verständlicher ist,aber es gibt eine Theorie der Differenzengleichungen.Auf Deine Rekursion angewand liefe das wiefolgt :
Zunächst lautet die zugehörige Differenzengleichung an+1-2an-2an-1=0
Die charachteristische Gleichung hierzu ist x2-2x-2=0 und hat die Lösungen x1=1+Ö3 und x2=1-Ö3.Daraus läßt sich folgern,daß die Differenzengleichung die allgemeine Lösung an=C1(1+Ö3)n+c2(1-Ö3)n besitzt.
Jetzt muß man nur noch die Konstanten anpassen und überlegen wie sich das "+3" in der Rekursion auswirkt.Du kommst auf das Ergebnis,daß es +3n-1 in der expliziten Formel heißen muß.(Einfach mal mit und ohne +3 einsetzen und vergleichen)
Dann erhältst Du die Lösungsformel
an=[(1+Ö3)n - (1-Ö3)n]/Ö3 + 3n-1 für n³2
Sie gilt aber NICHT für n€{0,1} ! |
Zaph
| | Veröffentlicht am Sonntag, den 09. Januar, 2000 - 12:09: |
|
Nach deiner Formel, Ingo, bekomme ich a4 = 41 heraus. Wenn ich deine Formel beweisen will, klappt auch der Induktionsschritt nicht. Da die Formeln so unterschiedlich aussehen, kann ich mir auch kaum vorstellen, dass sie gleich sein sollen.
Kann es sein, dass es ähnlich wie bei den linearen Differenzialgleichungen noch eine Theorie zu inhomogenen Differenzengleichungen gibt? |
Ingo
| | Veröffentlicht am Sonntag, den 09. Januar, 2000 - 12:19: |
|
Schätze Du hast Dich verrechnet,denn
(1+Ö3)4 = 55.7128
(1-Ö3)4 = 0.2872
Also insgesamt a4=32+33=59 was auch über die Rekursion herauskommt : 0 / 2 / 7 / 21 / 59 |
Ingo
| | Veröffentlicht am Sonntag, den 09. Januar, 2000 - 12:32: |
|
...aber Du hast recht,daß die Formel so nicht stimmen kann,denn die Iduktion klappt tatsächlich nicht.Und ab n=5 ist das Ergebnis falsch. Hab mich von der übereinstimmung bis n=4 blenden lassen. |
habac
| | Veröffentlicht am Sonntag, den 09. Januar, 2000 - 12:48: |
|
Wennman das "+3" so berücksichtigt, dass man für an folgendes ansetzt:
an = c1(1+Ö3)n + c2(1-Ö3)n + c3
und a0, a1 und a2 einsetzt, dann klappts, wenn ich mich nicht verrechnet habe. |
Zaph
| | Veröffentlicht am Sonntag, den 09. Januar, 2000 - 20:10: |
|
Ja, so geht's! Und scheint auch universell zu klappen. Ist wirklich viel einfacher als meine Methode. |
spockgeiger
| | Veröffentlicht am Montag, den 10. Januar, 2000 - 15:32: |
|
hallo leute
erstmal vielen dank fuer eure hilfe, ich hab mir das mal abgeschrieben und werde mir das offline und auf papier ansehen (das altmodischste ist in mathe meiner meinung immer noch das beste;)
was ich aber noch nicht versteh, ist:
muesste es nicht an+1-2an-2an-1-3=0 heissen, oder warum faellt die konstante weg?
und der schritt danach, muss ich einfach akzeptieren, das fuer jedes hoehere index eine hoehere potenz von x genommen wird?
falls es nicht zu tief in die materie geht, wuerde ich gerne wissen, worauf das basiert, und in welchem simester man das lernt, und sollte es auch noch moeglich sein, warum folgt daraus, dass
an= c1x1n+c2x2n+c3
wie gesagt, ich habe nicht vor, dass ihr mir jetzt den stoff von wahrscheinlich monaten einpaukt, aber wenn ihr eine moeglichkeit seht, wuerde es mich schon interessieren :)
vielen dank fuer eure bisherige muehe und danke schon weiterhin im voraus :))
spockgeiger |
Zaph
| | Veröffentlicht am Montag, den 10. Januar, 2000 - 23:32: |
|
Hi spokgeiger, höhere Mathematik ist das eigentlich nicht und könnte durchaus Stoff vom ersten Silvester, äh Simester der Vorlesung "Lineare Algebra" sein.
Gegeben eine Rekursionsformel
(1) an+2 = j an+1 + k an + m
und die "Anfangswerte" a0, a1.
Es gibt genau eine Folge (an), die dies erfüllt (vollständige Induktion!). Gesucht: Explizite Darstellung.
Zunächst betrachtet man die zugehörige "homogene" Gleichung
(2) bn+2 = j bn+1 + k bn
und überlegt sich, dass mit zwei Folgen (xn), (yn), die (2) erfüllen, und zwei reellen Zahlen p,q stets auch die Folge (zn) mit zn = p xn + q yn die Gleichung (2) erfüllt.
Die Lösungen von (2) bilden also einen "Vektorraum".
Eine Basis dieses Vektorraums bilden die Folgen (bn) = (1,0,k,jk,...) und (cn) = (0,1,j,j²+k,...), denn durch sie kann man jede Folge, die (2) efüllt, erzeugen (z.B. (7,13,13j+7k,...) = 7 * (bn) + 13 * (cn)) und die beiden Folgen sind linear unabhängig.
Wir suchen nun eine "schönere" Basis des Vektorraums. Ansatz:
(3) bn = zn.
Einsetzen in (2) liefert:
zn+2 = j zn+1 + k zn.
Durch zn teilen:
(4) z2 = j z + k.
Dies ist die von Ingo als "charakteristisch" bezeichnete Gleichung. Für ein z, welches Lösung von (3) ist, ist dann die Folge, die durch (3) definiert ist, eine Lösung von (2). Im Allgemeinen hat (4) genau zwei (in unserem Fall glücklicherweise reelle) Lösungen z1,z2 und damit haben wir zwei Lösungen von (2).
Jetzt muss man sich überlegen, dass die Folgen (1,z1,z1²,z1³,...) und (1,z2,z2²,z2³,...) linear unabhängig sind. Das ist aber klar, da z1 und z2 verschieden. Wir haben also eine andere Basis gefunden, und somit lässt sich jede Lösung von (2) schreiben als
(5) bn = p z1n + q z2n.
Gesucht war aber eigentlich die Lösung von (1)! Dazu machen wir jetzt den Ansatz
(6) an = bn + c.
Eingesetzt von (6) in (1) ergibt
(7) an+2 + c = j (an+1 + c) + k (an + c) + m
und hieraus unter Ausnutzung von (2)
(8) c = m / (1 - j - k)
(Bei uns glücklicherweise j + k ungleich 1!)
Sicherheitshalber zeige jetzt nochmal mit vollständiger Induktion, dass für jede Wahl von p,q die Folge
(9) an = p z1n + q z2n + m / (1 - j - k)
die Gleichung (1) erfüllt. Jetzt sind nur noch p und q so zu bestimmen, dass a0 und a1 passen.
Frage an alle: Was ist, wenn j + k = 1 oder z1 = z2? |
|
