Josephův problém

O(n²)

Josephův problém se ptá: n lidí stojí v kruhu a opakovaně se eliminuje každý k-tý — kdo jako poslední zbyde? Klasický případ n=7, k=3 má dobře známou odpověď: pozice 4. Simulace udržuje seřazený seznam živých, posouvá ukazatel o k pozic, odstraní daného člověka a pokračuje, dokud nezůstane jeden. Problém se vyskytuje v kombinatorice, programátorských hádankách a má uzavřené řešení O(n log n) pomocí rekurence.

Posloupnost
Stiskni ▶ a spusť
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Umístíme n lidí číslovaných 1 až n do kruhu
  2. Posuneme ukazatel o k pozic a vyřadíme daného člověka
  3. Zaznamenáme vyřazeného a pokračujeme od následující pozice
  4. Opakujeme, dokud nezůstane jeden člověk — ten je přeživší

Pseudokód

1josephus(n, k):                       # O(n^2)2  circle = [1, 2, ..., n]3  pos = 04  while len(circle) > 1:5    pos = (pos + k - 1) % len(circle)6    eliminate circle[pos]7    if pos >= len(circle): pos = 08  return circle[0]                    # survivor