今天在一个OJ上做了一个Joseph Problem（解约瑟夫问题）的题，题目不难，直接用循环链表模拟实际操作即可完成，但是用此种方法的时间太长，超时，所以我就用了一个大家对这类问题比较常用的解法——数学方法。

问题再现：

题目内容： 实作Joseph problem. 假设一开始有N个人，编号1~N， 按照顺序以顺时针围成一个圆圈。 游戏开始时，编号1的人拿刀。 之后每一轮刀子会被往下传M个人， 而当轮最后拿到刀子的人会将他的下一个人杀掉， 杀完后刀子会再传给被杀的下一个人。 这样一轮就算结束。 游戏会进行许多轮，直到只剩下最后一个人。范例1：N=5, M=2 第一轮：刀子传给3号，4号被杀，刀子再传给5号 (1 2 3 5) 第二轮：刀子传给2号，3号被杀，刀子再传给5号 (1 2 5) 第三轮：刀子传给2号，5号被杀，刀子再传给1号 (1 2) 第四轮：刀子传给1号，2号被杀，最后1号存活。 范例2：N=4, M=3 第一轮：刀子传给4号，1号被杀，刀子再传给2号 (2 3 4) 第二轮：刀子传给2号，3号被杀，刀子再传给4号 (2 4) 第三轮：刀子传给2号，4号被杀，最后2号存活。输入格式: 输入第一行为一个数字T，代表测资的笔数。 接下来会有T笔测资，每一笔测资一行， 会有两个数字N,M，数字间以空格区隔。 数字范围： T < 1000 0 < N <= 1000 0 < M <= 1000输出格式： 输出一行数字，将每笔测资最后存活下来的人的编号加总。输入样例： 3 5 2 4 3 8 4输出样例： 4 时间限制：1000ms内存限制：32000kb

算法实现：

• 循环链表（真实模拟）算法

第一点想到的实现算法就是完全模拟问题中的方法进行算法设计，代码如下：

#include <stdio.h>int arrQ[1000]; //循环队列，此处用固定值 int Qcount, head, tail; //队列操作 void add(int x, int size){if(Qcount == 0){arrQ[0] = x;}else{tail = (tail + 1) % size;arrQ[tail] = x;}Qcount ++; }void del(int size){head = (head + 1) % size;Qcount --; }int main(){int T, N, M, sum = 0;int i, j, k, tmp;scanf("%d", &T);for(i = 0; i < T; i ++){scanf("%d", &N);scanf("%d", &M);Qcount = head = tail = 0;for(j = 0; j < N; j ++){ //初始队列 add(j + 1, N);}while(Qcount != 1){ //直到剩下最后一个人 for(k = 0; k <= M; k ++){ //根据题意 执行M+1次操作 tmp = arrQ[head];del(N);add(tmp, N);}del(N);}sum += arrQ[head]; }printf("%d", sum);return 0; } 此算法虽然很容易理解，但是时间复杂度是O(nm)，执行大队列时会超时。

• 数学推导进行求解

这里先拿一个经典的例子进行说明。

问题:有n个人站成环 从1开始报数,报k的人出列,之后下一个人报1,问最后存在的是谁?

这里设n = 11，k = 3。下面将处理的所有过程写下来。

最后存在的是7。

这里可以用 f(n, k)来描述每一轮的操作，n是当前队列中的人数，k是出列的人，f(n,k) = (f(n - 1,k) + k) % n，下面来实现。

最底端是 f(1,k)  f(1,k) = 0 就是说只有一个人的时候存在者的下标是0，编号是7

向上，f(2,k) = (f(1,k) + k) % n  =  f(2,3)=(f(1,3) + 3) % 2 = 3 % 2 = 1，在只剩两个人时，存在者在这一轮数组中的下标位置是1（下标位置为1 编号是7 ）

向上，f(3,3) = (f(2,3) + 3) % 3 = 4 % 3 = 1，在只剩三个人时 在存者在这一轮数组中的下标位置是1 （下标位置为1 编号是7）
向上，f(4,3) = (f(3,3) + 3) % 4 = 4 % 4 = 0
……

……

最后，f(11,3) = (f(10,3) + 3) % 11 = 6 % 11 = 6  (看看上面的表格第一行 下标位置为6 编号是7 )

在只剩三个人时 幸存者在这一轮数组中的下标位置是0  (看看上面的表格 下标位置为0 编号是7 )

通过上述很容易写出程序来：

int fn(int n,int k){int s = 0; //最后存在者的下标 for(int i=2;i<=n;i++) {s = (s + k) % i;}return s + 1; //因为是从数组下标是从0开始的，所以这里要加1 }

好了，经典问题说完后，来看一下我们这个题，把这种数学推导出来的公式移植到程序中，如下：

#include <stdio.h>int main() {int N, M, T, sum = 0;int i, s;scanf("%d", &T);while(T--) {scanf("%d %d", &N, &M);s = 0;for(i = 2; i <= N; i ++){s = (s + M + 2) % i; //因为题目中要求是从当前位置的M个位置的下一个人出列，所以这里要加2 }sum += s+1;}printf ("%d", sum);return 0; }

这里的时间复杂度是O(n)，所以完胜。

博客名称：王乐平博客
博客地址：http://blog.lepingde.com
CSDN博客地址：http://blog.csdn.net/lecepin

总结

以上是生活随笔为你收集整理的Joseph Problem（解约瑟夫问题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。