有如下游戏：n个人围成一圈，编号为0~n-1，从编号为0的数起，数到编号为m-1者（即数了m个人）剔除，接着从紧接的下一个人从0继续数，以此轮之，最后剩下的那个为胜利者，求其编号。

结果与问题规模n有关：

f(n)=( f(n-1)+m ) mod n，用 c 实现如下：模结果为游戏者的编号，按该递推式求解的时间复杂度为O(n)，代码实现的空间复杂度为O(1)；也可用循环链表模拟该游戏，每次去掉一个节点，复杂度仍为O(n*m)

int f(int n, int m){  int s = 0;  for (int i = 2; i <= n; i++)    s = (s + m) % i;  return s;}

扩展：

1、若求第k(从0起,k∈[0,n-1])个被剔除者的编号，则用 C 实现如下：时间复杂度为O(lgn)，空间复杂度为O(1)。参考资料：

int kth(int n, int m, int k){  if (m == 1) return n-1;  for (k = (k+1)*m-1; k >= n; k = k-n+(k-n)/(m-1));  return k;}

 

2、若最开始是从编号为a者数起，则最后剩下的那人的编号与问题规模的关系为：

g(n)=( f(n) +a ) mod n，对该递推式的实现与上类似，空间复杂度为O(n)，时间复杂度为O(1)。

 可用单向循环链表模拟求解每次去掉一个节点，空间复杂度、时间复杂度分别为O(n*m)、O(1)，代码如下：

1 //n个人，从第k个开始，每次数到m的退出，n、k，m都≥1 2 typedef struct node 3 { 4     int data; 5     struct node* link; 6 }LNode,*Linklist; 7 void Josephus(int n,int k,int m) 8 { 9     Linklist list,p,r;10     int i;11     //创建循环链表 12     for(i=1;i<=n;i++)13     {14         p=(Linklist)malloc(sizeof(LNode));15         p->data=i;16         if(i==1)17         {18             list=p;19         }20         else21         {22             r->link=p;23         }24         r=p;25     }//结束后r=p=最后一个节点 26     p->link=list;27     p=list;28     29     //找到第k个30     for(i=1;i
      
       link;34     }35     36     //数到m者去除直到只剩一个37     printf("remove: ");38     while(p!=p->link)39     {40         for(i=1;i
       
        link; 44         }45         printf("%4d",p->data);46         r->link=p->link;47         free(p);48         p=r->link;49     }50     printf("\nsurvivor:%4d",p->data);51 }
       
      

 

详细推导：http://www.cnblogs.com/qlwy/archive/2012/07/11/2587254.html