约瑟夫斯环问题的几种经典解法

今天药忘吃喽~ 2023-08-17 16:44 130阅读 0赞

## 经典的约瑟夫斯 ##

问题描述：

有n个人围成一圈，从1开始顺序排号。从第一个人开始报数(从1~3报数)，凡报到3的人退出圈子，问最后留下的是原来的第几号?

## 数组循环模拟法 ##

const int N = 1000; int person[N]={0}; int getJosePhus(int n,int m) { if (n <= 0 || m <= 0) //检查参数的有效值 return -1; for(int j=0;j<n;j++) //对下标为0~n-1赋值1~n { person[j] = j+1; } int leave = 0; //离开的人 int count = 0; //计数1、2、3 int index = 0; //记录下标，超过n要取模，形成环形 while (leave<n-1) //当离开的人数比n-1少(即未退出人数大于1时，执行循环) { if(person[index]!=0) //i下标的人还活着，计数就+1 { count++; } if(count==m) //当数到下标为m时，下标值置为0，计数器置0，离开人数+1 { person[index] = 0; count = 0; leave++; } index++; //每次循环下标仅+1 if(index==n) //达到了数组的最大下标，取模回到开头 { index = index%n; } } index = 0; while (person[index]==0) //循环找出剩下最后的值未清零的那个人的数组下标 { index++; } return person[index]; }

## 双向链表模拟法 ##

int getJosePhus(int n,int m) { list<int> circle; for(int i=1;i<=n;i++) { circle.push_back(i); } list<int>::iterator cur = circle.begin(); while (circle.size()>1) { for(int i=0;i<m-1;++i) { ++cur; if(cur==circle.end()) //走到end，就是头节点的前一个结点,要跳到第一个begin头节点 { cur = circle.begin(); } } list<int>::iterator next = ++cur; //删除数到m的人要记录下一个人的地址,如果下一个人是end(头节点的前一个结点),要跳到第一个begin头节点 if(next==circle.end()) { next = circle.begin(); } --cur; circle.erase(cur); //erase函数会析构此结点，在返回的时候，指向当前迭代器的下一个节点 cur = next; } return circle.front(); }

## 数学推理法 ##

无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。

如果原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。

为了讨论方便，先把问题稍微改变一下，并不影响原意：  
问题描述：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-2  
k-1   --> n-1  
变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x'=(x+k)%n  
如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：  
令f\[i\]表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f\[n\]  
递推公式

> f\[1\] = 0; (i = 1)  
> f\[i\] = (f\[i - 1\] + m) % i; (i > 1)

有了这个公式，我们要做的就是从1-n顺序算出f\[i\]的数值，最后结果是f\[n\]。因为实际生活中编号总是从1开始，我们输出f\[n\]+1.由于是逐级递推，不需要保存每个f\[i\]，程序也是异常简单：

int getJosePhus(int n,int m) { if(n<=0||m<=0) { return -1; } int last = 0; for(int i=2;i<=n;i++) { last = (last + m) % i; } return last + 1; }

转载于:https://www.cnblogs.com/WindSun/p/11440904.html