TAG：约瑟夫问题

一个标准的Joseph问题，n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。 我们知道靠前个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且从k开始报0。 现在我们把他们的编号做一下转换： k --> 0 k+1 --> 1 k+2 --> 2 ... ... k-2...

阅读更多

约瑟夫问题是一个著名的数学和计算机科学问题，通常描述为：N个人围成一圈，从靠前个人开始报数，每报到M的人将被***掉，下一个人接着从1开始报。如此反复，直到最后只剩下一个人，求最后的胜利者。 对于这个问题，有一种数学解法是基于递推公式的。递推公式可以表示为：f(N,M) = (f(N-1,M) + M) % N，其中f(N,M)表示N个人报数，每报到M时***掉那个人，最终胜利者的编号。f(N-1,M)表示N-1个人报数，每报到M时***掉那个人...

阅读更多