T(n) Rekursionsformel < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:37 Mi 17.02.2010 | | Autor: | hilado |
| Aufgabe | | Bei einem Fußballturnier spielen n = [mm] 2^k [/mm] für k [mm] \in \IN [/mm] Mannschaften nach KO-System. Das heißt, die [mm] \bruch{n}{2} [/mm] Gewinner der ersten [mm] \bruch{n}{2} [/mm] Begegnungen kommen in die zweite Runde usw. Finden Sie eine Rekursionsgleichung der Form T(1) = d, T(n) = a * [mm] T(\bruch{n}{b}) [/mm] + c für die Anzahl der Spieler T(n). Geben Sie eine explizite Formel für T(n) an. |
Ich hab folgende Lösungsansätze (ich hab erst einmal gedacht, ich probiers mal wie eine Folge aufzuschreiben)
rekursive Formel: [mm] a_{n} [/mm] = [mm] a_{n-1} [/mm] + [mm] 2^{k - n}
[/mm]
[mm] a_{0} [/mm] = [mm] 2^{k}
[/mm]
explizite Formel:
[mm] a_{n} [/mm] = [mm] \summe_{k = 0}^{n} \bruch{1}{2^k}*d
[/mm]
Nur wie schaff ich es das in eine Form zu bringen wie oben genannt vorgegeben ...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:28 Mi 17.02.2010 | | Autor: | Sigma |
Hallo hilado,
du meinst doch bestimmt Spiele. Spieler macht ja wenig Sinn. Oder?
mfg sigma10
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:25 Mi 17.02.2010 | | Autor: | leduart |
Hallo
1. ist T(k) oder T(n) gefragt, mit [mm] n=2^k [/mm] gibt es doch wenn es T(n-1)gibt T(n) gar nicht?
deshalb versteh ich deine Rekursionsformel nicht.
Deine explizite Formel probier mal für n=2 oder 4 aus. Was soll denn d sein?
überprüfe deine Ergebnisse wenichstens für n=2,4,8 wo dus noch an den ingern abzählen kannst.
Gruss leduart
|
|
|
|
