Laufzeitanalyse, lin Rekursion < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 01:15 Fr 12.12.2008 | | Autor: | supersim |
| Aufgabe | T(n)=T(n-1)*4+8
Geben sie unter der Vorraussetzung T(1)=3 eine direkte Formel an. |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Ich weiß leider nicht, wie ich diese rekursive Funktion in eine allgemeine Funktion umwandele. [mm] "T(n)=3*4^{n-1}+8*(n-1)" [/mm] ist leider nicht ganz die allgemeine Funktion.
Das "+8" macht für mich die umwandlung zu schwierig.
Hat da jemand einen Tipp, wie ich da weiter kommne.
|
|
| |
|
Hallo supersim,
nur weil's noch niemand gesagt hat, hier ein spätes ![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]") !
Deine Folge sieht in der Tat mühsam aus.
Es hilft aber erheblich, wenn Du sie einmal 4-adisch aufschreibst:
3, 110, 1120, 11220, 112220, 1122220, 11222220 ...
Aus der Formel für die Summe geometrischer Reihen kannst Du Dir noch herleiten, dass eine Zahl, die aus n aufeinanderfolgenden Einsen besteht im Zahlensystem zur Basis a wie folgt dargestellt werden kann:
[mm] \underbrace{1111...11}_{=n\ mal}_a=\bruch{a^n-1}{a-1}
[/mm]
Mit diesem Material kannst Du Deine Formel für [mm] \a{}T(n) [/mm] aufstellen. Sie wird allerdings erst ab n=2 gelten (je nach Formulierung vielleicht auch erst ab n=3), so dass [mm] a_1 [/mm] eine eigene Definition erfordert (und die hat es ja auch schon).
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:11 Fr 12.12.2008 | | Autor: | supersim |
Danke für die schnelle Antwort, aber was meinst du mit "4-adisch" aufschreiben.
Die ersten 10 Folgen sehen so aus: [3,20,88,360,1448,5800,23208,92840,371368,1485480]
|
|
|
| |
|
"4-adisch" heißt: im Vierersystem, also dem Zahlensystem zur Basis 4. Ich dachte, diese mathematische Bezeichung sei auch unter Informatikern geläufig, wenn Ihr auch häufiger im Binär- oder Hexadezimalsystem rechnet.
Im Dezimalsystem erkennt man an den ersten 10 Folgengliedern ja kein offensichtliches "Bauprinzip", im Vierersystem aber sofort.
Vorhin musste ich zu einem längeren Außentermin, und erst im Auto fiel mir auf, dass die Formel, die bazzzty angibt [bei mir hieß sie [mm] \bruch{1}{3}(17*4^{n-1}-8)], [/mm] doch den Fall n=1 mit abdeckt.
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:24 Fr 12.12.2008 | | Autor: | bazzzty |
> T(n)=T(n-1)*4+8
> Geben sie unter der Vorraussetzung T(1)=3 eine direkte
> Formel an.
Als Alternative zum Vorschlag von Reverend:
Schreibs doch einfach mal hin:
[mm]T(1) = 3[/mm]
[mm]T(2) = 3\cdot 4+8[/mm]
[mm]T(3) = 3\cdot 4^2+8\cdot 4+8[/mm]
[mm]T(4) = 3\cdot 4^3+8\cdot 4^2+8\cdot 4+8[/mm]
Da erkennt man doch ein System, und da warst Du auch dicht dran:
[mm]T(n) = 3\cdot 4^{n-1}+8\sum_{i=0}^{n-2} 4^i[/mm]
Um da weiterzukommen, braucht man die geometrische Reihe:
[mm] \sum_{i=0}^{k} q^i=\frac{q^{k+1}-1}{q-1}[/mm] für [mm]q=4[/mm] und [mm]k=n-2[/mm], also
[mm]T(n) = 3\cdot 4^{n-1}+8\frac{4^{n-1}-1}{3}[/mm]
Jetzt kann man sogar noch ein bißchen vereinfachen zu
[mm]T(n) = (3+8/3)\cdot 4^{n-1}-8/3[/mm]
(Edit: Typo korrigiert)
|
|
|
|
