Runde in einem Turnier berechnen

Question

Ich habe ein Turnier im Koordinatensystem mit n Spielern, wobei n immer eine Zweierpotenz ist. Die Matches sind durchnummeriert, in Runde 1 gibt es damit die Matches M(1) bis M(n/2). In Runde 2 dann die Matches ab M(n/2+1) und so weiter.

Ein Beispiel für n = 8:

M1 --|

         |-- M5 --|

M2 --|             |

                      |-- M7 --

M3 --|             |

         |-- M6 --|

M4 --|

Die Frage ist: Wie kann ich mit Hilfe von n und der Matchnummer berechnen, in welcher Runde das Match stattfindet?

Answer 1

Eingabe: Anzahl n der Teilnehmer, Nummer s des Spiels

Ausgabe: Nummer der Runde, in der das Spiel stattfindet

r := 1
while n > 1 and s > n/2
  r := r+1
  s := s - n/2
  n := n/2
return r