02746: 约瑟夫问题
implementation, http://cs101.openjudge.cn/practice/02746
约瑟夫问题：有ｎ只猴子，按顺时针方向围成一圈选大王（编号从１到ｎ），从第１号开始报数，一直数到ｍ，数到ｍ的猴子退出圈外，剩下的猴子再接着从1开始报数。就这样，直到圈内只剩下一只猴子时，这个猴子就是猴王，编程求输入ｎ，ｍ后，输出最后猴王的编号。
输入
每行是用空格分开的两个整数，第一个是 n, 第二个是 m ( 0 < m,n <=300)。最后一行是：
0 0
输出
对于每行输入数据（最后一行除外)，输出数据也是一行，即最后猴王的编号
样例输入
6 2
12 4
8 3
0 0样例输出
5
1
7最容易实现的方法是模拟法，其次是递归法，最后是递推法。
递推法：
在约瑟夫问题中，递推公式应该是 a = (a + m - 1) % i + 1。因为需要考虑从1开始编号，而不是从0开始编号。
⚠️ 但这里有一个“陷阱”：编号是从 1 开始的，而取模运算是从 0 开始的。
取模时，0代表“绕回到最后一个人”。
如果我们直接写
(x + m) % n，会出现偏移错误。 比如当(x + m)刚好是 n 的倍数时，结果是 0，而我们希望得到第 n 号，而不是 0 号。因此我们得调整为：
原编号 = ((x + m - 1) % n) + 1这里的 “−1” 和 “+1” 其实是一对相互抵消的编号系统平移修正：
操作 含义 −1把“1号起始编号体系”转换成“0号起始编号体系”，方便取模 % n环状取模操作 +1把结果再变回“1号起始编号体系”
while True:
n, m = map(int, input().split())
if n + m == 0:
break
a = 1 # 初始化 a 为 0，表示从 0 开始编号
for i in range(2, n + 1):
a = (a + m - 1) % i + 1
print(a) # 最终结果需要加 1，因为编号从 1 开始或者这样
while True:
n, m = map(int, input().split())
if n + m == 0:
break
a = 0 # 初始化 a 为 0，表示从 0 开始编号
for i in range(2, n + 1):
a = (a + m) % i
print(a + 1) # 最终结果需要加 1，因为编号从 1 开始模拟法：
说明：使用 队列queue 这种数据结构会方便。它有三种实现方式，我们最常用的 list 就支持，说明，https://www.geeksforgeeks.org/queue-in-python/
用list实现队列，O(n)
# 先使用pop从列表中取出，如果不符合要求再append回列表，相当于构成了一个圈
def hot_potato(name_list, num):
queue = []
for name in name_list:
queue.append(name)
while len(queue) > 1:
for i in range(num):
queue.append(queue.pop(0)) # O(N)
queue.pop(0) # O(N)
return queue.pop(0) # O(N)
while True:
n, m = map(int, input().split())
if {n,m} == {0}:
break
monkey = [i for i in range(1, n+1)]
print(hot_potato(monkey, m-1))用内置deque，O(1)
from collections import deque
# 先使用pop从列表中取出，如果不符合要求再append回列表，相当于构成了一个圈
def hot_potato(name_list, num):
queue = deque()
for name in name_list:
queue.append(name)
while len(queue) > 1:
for i in range(num):
queue.append(queue.popleft()) # O(1)
queue.popleft()
return queue.popleft()
while True:
n, m = map(int, input().split())
if {n,m} == {0}:
break
monkey = [i for i in range(1, n+1)]
print(hot_potato(monkey, m-1))# 2021cs101, 留美琪，1800090104
# 先使用pop从列表中取出，如果不符合要求再append回列表，相当于构成了一个圈
while True:
n, m = map(int, input().split())
if {n,m} == {0}:
break
monkey = [i for i in range(1, n+1)]
index = 0
while len(monkey) != 1:
temp = monkey.pop(0)
index += 1
if index == m:
index = 0
continue
monkey.append(temp)
print(monkey[0])思路：因为退出圈的起点会移动m步，所以加个m-1，又因为是个圆环，需要计算mod n。
while True:
n, m = map(int, input().split())
if n + m == 0:
break
mon = [] # monkey
for i in range(1, n+1):
mon.append(i)
t = m - 1
for j in range(n):
if len(mon) == 1:
print(sum(mon))
else:
del mon[t]
n -= 1
t = (t + m - 1) % n递归法：
2020fall-cs101，李元锋。
思路：没接触编程前就听说过此题的大名了，这题可以用递归思想。首先先简化问题，考虑当n=5,m=3 的情况： (1,2,3,4,5)，第一轮报数后变成 (4,5,1,2)。如果我们可以把 (4,5,1,2)变成(1,2,3,4)，那不就可以重复这个流程直到 1了嘛。这个流程可以用公式(func(n-1,m)+m-1)%n+1给出，直接递归即可。
https://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/
def func(n,m):
if n == 1:
return n
return (func(n-1, m) + m-1) % n + 1
while True:
n, m = map(int, input().split())
if n+m == 0:
break
print(func(n, m))while True:
n, m = map(int, input().split())
if n+m == 0:
break
dp = [0] + [1]*n
cur = 1
while sum(dp)!=1:
cnt = 0
while True:
if dp[cur] == 1:
cnt += 1
if cnt==m:
break
cur += 1
if cur>n:
cur = 1
else:
cur += 1
if cur>n:
cur = 1
dp[cur] = 0
cur += 1
if cur>n:
cur = 1
else:
print(dp.index(1))2022fall-cs101，刘丁硕。可以使用逆推法，从最后剩着的猴子的位置开始逆着找该猴的原位置。
while True:
try:
a=input().split()
if a==['0','0']:
break
b=1
c=0
while b<int(a[0]):
b+=1
c=(c+int(a[1]))%b
print(c+1)
except:
break想到python 写for 循环时一种特有的方式是直接iterate 列表的元素，而不是index。这题如果这样做，可以非常直接地实现题目的意图，不用取余，也不用考虑index 的改变。这个方法和上面的思路都不一样，而且比其中一些方法更加简单、容易理解。想到之后，我兴奋了很久。
# 2022fall-cs101, 杨文可，哲学系
while True:
n, m = map(int, input().split())
if n == 0:
break
li = list(range(1, n + 1))
if m == 1:
print(li[-1])
else:
i = 0
while len(li) > 1:
for monkey in li.copy():
i += 1
if i == m:
li.remove(monkey)
i = 0
print(li[0])