ヨセフスの問題
人の人間が円を描くように並び、処刑されるのを待っている。最初の人をスキップし、さらに \( k-2 \) 人をスキップし（つまり、\( k-1 \) 人をスキップして \(k \)番目の人に到達する）、\(k\)番目の人を処刑する。そしてそこから、再度 \( k-1 \) 人をスキップして \(k \)番目の人を処刑する。これを延々と続け（円は徐々に小さくなっていく）、最後に残った1人を釈放する。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
再帰を使った考え方は、以下の説明がとても分かりやすかったです。
Explaining the Josephus Algorithm
ここでは、循環リストを使って愚直に考えてみます。
循環リスト
循環リスト（circularly-linked list）では、先頭と最後尾のノードを相互に連結する。循環リストには片方向のものも双方向のものもある。循環リストを辿る場合、任意のノードから出発して、好きな方向にたどっていき、最初のノードに戻ってくるまで続ける。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ヨセフスの問題を、循環リストを使いそのまま表現します。
コード
def get_Josephus_position(n, m):
# 循環リストを構成するノード
class Node:
def __init__(self, data=None, next=None):
self.set_data(data)
self.set_next(next)
def set_data(self, data):
self.data = data
def get_data(self):
return self.data
def set_next(self, next):
self.next = next
def get_next(self):
return self.next
answer = []
# 循環リストを作成する。
head = Node(0)
prev = head
for i in range(1, n):
current_node = Node(i)
prev.set_next(current_node)
prev = current_node
prev.set_next(head)
# 最後の一つになるまで、循環リストからノードを一つずつ取り除く。
current_node = head
counter = 0
while current_node.get_next() != current_node:
counter += 1
if counter == m:
counter = 0
prev.set_next(current_node.next)
answer.append(current_node.get_data())
else:
prev = current_node
current_node = current_node.get_next()
answer.append(current_node.get_data())
return answer
print(get_Josephus_position(41, 3))