Algo für Kock-Out-Rundenzahl?

[aikon]

Hallo!

Vielleicht kann mit jemand mit mehr mathematischem Hintergrund als ich bei diesem Problem helfen:

Ich habe vor, für Turniere (speziell) oder Entscheidungsbäume (allgemein) ein Knock-Out-System in PHP zu erstellen. Dabei möchte ich natürlich auch die Anzahl an benötigten Matches ermitteln, wofür ich mir gerne eine Funktion basteln würde.

Gegeben ist lediglich die Anzahl der "Teilnehmer", rauskommen soll die Anzahl an "Begegnungen" oder "Runden", die nötig ist, um einen Sieger zu ermitteln.

RUNDE 1:   X1    X2    X3    X4    X5    X6    X7

           |_____|     |_____|     |_____|     |

              |           |           |        |

RUNDE 2:      X1          X4          X5       X7

              |___________|           |________|

                    |                     |

RUNDE 3:            X4                    X5

                    |_____________________|

                               |

SIEGER:                        X4


[/PHP]

In diesem Beispiel werden 3 Runden benötigt. Um diese "3" für alle möglichen Xn zu ermitteln, hätte ich gerne eine Funktion. Leider komme ich bei dem Problem auf keinen Trichter. Es scheint nur so zu sein, dass die Rundenzahl immer doppelt so lang gleich bleibt, wie die letzte... Beispiel:

1 Teilnehmer: 0 Runden (Ausnahmefall)

2 Teilnehmer: 1 Runde

3-4 Teilnehmer: 2 Runden

5-8 Teilnehmer: 4 Runden

Das würde für 9-16 Teilnehmer bedeuten, dass sie 8 Runden zu spielen hätten... Doch wie komme ich dafür auf einen mathematischen Ausdruck? Eine Schleife, die mir die Runden dann errechnet (for oder do) wäre weder performant noch sauber programmiert.

Vielen Dank für alle Anregungen, die da kommen. Gruß,

aikon

[smokie]

Hallo!

Wie das in PHP zu realisieren geht kann ich dir nicht sagen, aber

ich wuerde in meinem jugendlichen Leichtsinn einfach zu einer

netten kleinen Rekursion greifen. Fuer die mathematische Loesung bin ich dann doch nicht fitt genug.

Etwa so:

1. Teilnehmer modulus Anzahl der Teilnehmer pro Spiel

2. Ergebnis > 1 --> Ein Spieler muss auf die naechste Runde warten

3. Anzahler der Spiele von Runde n berechnen (--> Teilnehmer / Teilnehmer pro Spiel + den evtl. wartenden Spieler)

5. Rundenzaehler um 1 erhoehen.

6. Mit dem Ergebnis von 3. bei Schritt 1 weiter machen solange das

Ergebnis ungleich 1 ist.

Bei interesse kann ich dir auch den Code in C zukommen lassen. Konnte dir hoffentlich ein bischen weiter helfen.

Gruss

smokie

[Goos]

Original geschrieben von aikon

1 Teilnehmer: 0 Runden (Ausnahmefall)

2 Teilnehmer: 1 Runde

3-4 Teilnehmer: 2 Runden

5-8 Teilnehmer: 4 Runden

...aehmmm in deinem Beispiel brauchen aber 7 Spieler 3 Runden und nicht 4

Aber gut, da die wenn man den Baum, mal andersrum betrachtet, die Spieleranzahl mit jeder Runde quadratisch steigt, sollte man um aus der Spieleranzahl die benoetigten Runden zu gewinnen, die Quadratqurzel aus der Spieleranzahl ziehen und diese dann auf die naechste Ganzzahl aufrunden.

So braucht man also bis zu 9 Spielern nur 3 Runden (der neunte hat halt in der ersten Runde noch ein Freilos), da die Quadratwurzel aus 9 ja bekanntlich 3 ist. Ab 10 Teilnehmern gehts dann los mit 4 Runden...usw.

Ist also alles gar nicht schwer berechnen

Goos

[Klotzkopp]

Die Teilnehmerzahl wächst nicht quadratisch, sondern exponentiell. Die Anzahl der Runden ist der Logarithmus zur Basis 2 der Anzahl der Teilnehmer, aufgerundet wegen der Freilose.

Und weil die meisten Sprachen nur dekadische und natürliche Logarithmen bieten:

log2(x) = ln(x) / ln(2)

[aikon]

Besten Dank, Leute! Ich hätte gar nicht so schnell mit Antworten gerechnet, da dieses Algo-Board nicht soooo belebt ist :-)

Viele Grüße,

der endlich ausgebildete Fachinformatiker... (JUHUU, 89%!! :bimei )

aikon :-)