约瑟夫斯问题
题目如下：
n个人(编号1~n)围成一圈从编号为1的开始报数，从1报数到m，报到m的人出来，下一个人继续重新从1开始报数，编程求最后一个留下的人的编号
如n=3，m=4
第一次出队：1
第二次出队：3
最后留下：2
def x(n, m):
a = [i for i in range(1, n+1)]
while len(a) > 1:
index = (m - 1) % len(a)
a = a[index+1:] + a[:index]
return a[0]
解答二¶
第二种同样利用数组，可以通过移动下标实现。
设第一次 index 为 0，表示从第一个开始算起，第一步出队的人的位置为 $(m-1)\%n$, 记为 A1, A1 出队之后 A1 后面的人都往前移一位。
第二步出队的人位置为 $(A1+m-1)\%(n-1)$ , 表示从上一步出队的人的位置开始算起。
由此可以得出，每一步出队的都是上一步的index计算得出, 得 $(index+m-1)\%len(list)$
代码如下:
def x(n, m):
l_number = list(range(1, n + 1))
index = 0
while len(l_number) > 1:
index = (index -1 + m) % len(l_number)
l_number.pop(index)
return l_number[0]
解答三¶
第三种，则在第二种的基础上，更进一步，通过数学代换直接得到每一步应该出队的人。
假设从0排列开始，第一次排列为:
0, 1, 2, 3, 4 ... n-3, n-2, n-1 (共n项)
此时出队的人的编号为 $(m-1)\%n$ 。
设第二次应该从 k 开始算起，则有式子 $k=m\%n$, 同时第二次的排列为:
k, k+1, k+2, K+3, ... k-3, k-2 (共n-1项)
此时设 k = 0, 则该排列可以简单代换为 n-1 项的求出队问题:
0, 1, 2, 3, ..., n-3, n-2 (共n-1项)
同样的，往下代换。 即，对于n个人报数的问题，可以分解为先求解（n–1）个人报数的子问题；而对于（n–1）个人报数的子问题，又可分解为先求(（N–1）–1)人个报数的子问题。
设当人数只有1个人的时候，不管怎么数编号都为 0:
则有 $f(1) = 0$。
当人数有2个人的时候，则有上一步的人的编号加 m，即:
$f(2) = (f(1) + m)\%n$
以此类推，则有公式:
$f(1) = 0 \\ f(x) = (f(x-1) + m)\%n \qquad (x>1)$
最后我们实际编号是从1开始，则将结果加一。
代码如下:
def x(n, m):
i = 2
s = 0
while i <= n:
s = (s + m) % i
i+=1
return s+1
Comments !