Josephus环

/*************************************************************************
  *                             约瑟夫环问题
  *n个人围成一圈，用1-n编号，从1号开始报数，报到m的人出局，下一个人从1继续
  *报数，求最后出列的人的编号。
  *
  *                                 解法
  *（1）稍微将问题转化一下，让编号从0开始，到n-1；
  *（2）假设第一次报数后，s出局，则s=m%n-1,下次从k=m%n开始报数;
  *（3）此时重新编号，k->0,k+1->1,k+2->2,...
  *（4）恰好我们在这个时候知道了问题的答案，这个人在第二次编号中为q，
  *     在第一次编号中为p，则有p=(q+k)%n=(q+m%n)%n=(q+m)%n,
  *（5）则得到此问题的通项公式
  *     f(1)=0;
  *     f(n)=(f(n-1)+m)%n n>1;
  *（6）若从1开始编号，假设m%n==0,则第一次出局的人的编号是0（实际是n），
        这样就要再做进一步处理。如果从0开始编号，就会避免这个问题。
  *     最后的结果转换只相差1.
  ************************************************************************/
#include <stdio.h>

/**
 * josephus - 
 * @n: total persons
 * @m: count to
 * @k: start with the person k
 */
int josephus(int n, int m, int k)
{
        int i;
        int s=0;
        for(i=2;i<=n;i++)
                s=(s+m)%i;
        return (s+k-1)%n+1;
}
int main(int argc, char *argv[])
{
        int m, i;
        m = 3;
        /*start with person 1 */
        for(i=1;i<=20;i++)
                printf("\tThe result is :%d when n=%d m=%d k=1\n",josephus(i,m,1),i,m);
        return 0;
}

 结果

	The result is :1 when n=1 m=3 k=1
	The result is :2 when n=2 m=3 k=1
	The result is :2 when n=3 m=3 k=1
	The result is :1 when n=4 m=3 k=1
	The result is :4 when n=5 m=3 k=1
	The result is :1 when n=6 m=3 k=1
	The result is :4 when n=7 m=3 k=1
	The result is :7 when n=8 m=3 k=1
	The result is :1 when n=9 m=3 k=1
	The result is :4 when n=10 m=3 k=1
	The result is :7 when n=11 m=3 k=1
	The result is :10 when n=12 m=3 k=1
	The result is :13 when n=13 m=3 k=1
	The result is :2 when n=14 m=3 k=1
	The result is :5 when n=15 m=3 k=1
	The result is :8 when n=16 m=3 k=1
	The result is :11 when n=17 m=3 k=1
	The result is :14 when n=18 m=3 k=1
	The result is :17 when n=19 m=3 k=1
	The result is :20 when n=20 m=3 k=1