首页 > 代码库 > 约瑟夫环问题的优化及终极优化
约瑟夫环问题的优化及终极优化
约瑟夫问题大致描述：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为1的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，求最后一个出列人的编号。
算法1：模拟
链表维护每个人的相对位置，每次模拟报数的过程，每次踢掉一个人，求出最后被踢掉的人。
时间复杂度O(nm)
由于该算法比较暴力，就不贴呆马了
算法2：数学递推
考虑每次踢掉一个人后，问题会变成一个子问题，即（n-1）个人围一桌，从编号为上次被踢出的后一个人开始报数，数到m的人被踢掉，求出此次被踢掉的人的编号。
假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n;
所以这就变成了一个递推的问题：
令 f[i] 表示 i个人玩约瑟夫游戏，报到m的人被踢出，胜利的人的编号。
f[i]=(f[i-1]+m) % i; (i>1) 边界条件f[1]=0;
所以该问题可以递推解决，时间复杂度O(n)
1 var 2 n,k,i :longint; 3 f :array[0..1000050] of longint; 4 begin 5 read(n,k); 6 f[1]:=0; 7 for i:=2 to n do f[i]:=(f[i-1]+k) mod i; 8 writeln(f[n]+1); 9 end.
算法3：优化递推
上面的算法相比最初的模拟算法效率已经大大提升了，那么，该算法还有改进的余地么？
事实上，如果我们观察上述算法中的变量k，他的初始值为第一个出圈人的编号，但在循环的过程中，我们会发现它常常处在一种等差递增的状态，我来看这个式子：k = (k + m - 1) % i + 1，可以看出，当i比较大而k+m-1比较小的时候，k就处于一种等差递增的状态，这个等差递增的过程并不是必须的，可以跳过。
我们设一中间变量x，列出如下等式：
k + m * x – 1 = i + x
解出x，令k = k + m * x，将i + x直接赋值给 i，这样就跳过了中间共x重的循环，从而节省了等差递增的时间开销。
可是其中求出来的x + i可能会超过n，这样的结果事实上已经告诉我们此时可以直接结束算法了，即：
k = k + m * (n - i) ;
i = n;
结束。
另外对于m = 1的情况可以单独讨论：
当k == 1时，最终结果就是n；
当k != 1时，最终结果就是(k + n - 1) % n。
1 var 2 n,m :int64; 3 4 function ysf(n,m,k:int64):int64; 5 var 6 i,j,x :int64; 7 begin 8 if m=1 then 9 begin 10 if (k=1) then k:=n else k:=(k+n-1) mod n; 11 end else 12 begin 13 i:=1; 14 while i<=n do 15 begin 16 if (k+m<i) then 17 begin 18 x:=(i-k+1) div (m-1) -1; 19 if (i+x<n) then 20 begin 21 i:=i+x; 22 k:=(k+m*x); 23 end else 24 begin 25 k:=k+m*(n-i); 26 i:=n; 27 end; 28 end; 29 k:=(k+m-1) mod i+1; 30 inc(i); 31 end; 32 end; 33 exit(k); 34 end; 35 36 begin 37 read(n,m); 38 writeln(ysf(n,m,0)); 39 end.
约瑟夫环问题的优化及终极优化