约瑟夫问题

1. 用数组

/* n个人，从s开始间隔m，结果存到p指向的数组 */
void josephus(int n,int s,int m,int *p)
{
    int i,j=0,sum,a[100];
    for(i=0;i<n;i++)
        a[i]=0;
    for(i = s; i < n; i++,i%=n)
    {
        if(a[i] != 1)
          j++;
        if(j == m)
        {
            j = 0;
            a[i] = 1;
            sum += a[i];
            if(i==0)
                *p++ = n;
            else
                *p++ = i;
            /* printf(" %d",i); */
        }
        if(sum==n)break;
    }
}

2. 单向循环链表

//带头结点的循环链表解约瑟夫问题
#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
    int num;
    /* char card; */
    struct Node *next;
}JNode, *Link;

// create circle link exclude head
void init_link(JNode *head, int n)
{
    int i;
    JNode *p;
    for(i = 1, p = head; i <= n; ++i)
    {
        p->next = (JNode *)malloc( sizeof(JNode) );
        p = p->next;
        if(!p) /* perror(); */
            exit(-1);
        p->num = i;
    }
    p->next = head->next;
}

void josephus(int n, int k)
{
    int i;
    JNode *head, *p;
    head = (JNode *)malloc( sizeof(JNode) );
    head->num = n;
    head->next = head;
    // initial link->num with 1,2...n
    init_link(head, n);
    p = head;

    for(i = 1; p != p->next; ++i)
    {
        if(i == k)
        {
            i = 1;
            printf("%d ", p->next->num);
            //remove the next node;
            JNode *removed = p->next;
            p->next = removed->next;
            free(removed);
        }
        p = p->next;
    }
    printf("left:%d\n", p->num);
    printf("head->num=%d\n", head->num);
    free(p);
    free(head);
    head = NULL;
}

int main()
{
    int n, k;
    printf("Please input n,k :\n");
    scanf("%d,%d", &n, &k);
    josephus(n,k);

    return 0;
}

//不带头结点，更简洁
//n个人，从k开始，每次数到m者出列。
void josephus(int n, int k, int m)
{
    int i;
    LinkList list = NULL;
    LinkList p;

    /* create and initial a cycle link. */
    list = (LinkList)malloc( sizeof(LNode) );
    list->num = 1; /* head is the first element */
    list->next = list;
    p = list;
    if(!p) exit(-1);

    for(i = 2; i <= n; ++i)
    {
        LNode *node = (LinkList)malloc( sizeof(LNode) );
        if(!node) exit(-1);
        node->num = i;
        p->next = node;
        p = node;
    }
    p->next = list;
    /* skip the first k element. */
    p = list;
    for(i = 1; i < k; ++i)
    {
        p = p->next;
    }
    /* get the out sequence*/
    LNode *pre = p;
    while(p->next != p)
    {
        for(i = 1; i < m; ++i)
        {
            pre = p;
            p = p->next; /* m will be here. */
        }
        pre->next = p->next;
        printf("%4d ", p->num);
        free(p);
        p = pre->next;
    }
    printf("left:%4d\n", p->num);
    free(p);
}

int main()
{
    int n, k;
    printf("Please input n,k,m :\n");
    scanf("%d,%d,%d", &n, &k, &m);
    josephus(n,k,m);

    return 0;
}

3. 数学推导
为了讨论方便，先把问题稍微改变一下，并不影响原意：
问题描述：n个人编号0~(n-1)，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。
网上流传甚广的所谓数学方法都写得不清不楚让人费解。
    我们知道第一个人(编号一定是m%n-1) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
    我们先看第一个人出列后的情况，显而易见，第一个出列的人的编号一定是m%n-1,这个人出列后，剩下的n-1个人组成了一个新的约瑟夫环，这个约瑟夫环的第一个人在最开始的环中的编号是k=m%n（就是第一个出列的人的下一个）
        k  k+1  k+2  ... n-2, n-1, 0, 1, 2, ... k-2并且从k开始报0。
    事实上，可以把这个环又映射成为一个新的环：
    n-2个   n-1个       n个
            0 k     -->   0
            1 k+1   -->   1
            2 k+2   -->   2
    x''--> x' k+3   -->   x   // x倒推 n-1次即可。x=f(n), f(1)=0
              ...    ....
              k-2   -->  n-2
                         n-1
    可以看出，这就是原问题中把n替换成n-1的情况，假设我们已经求出来在这种情况下最后胜利的那个人的顺序是x'，
    那个倒推回去的那个人的编号就正好是我们要求的答案，显而易见，x应该是(x'+k)%n 。
注意，x'代表被映射的x在(n-1)个人中的顺序号。
    那么如何知道n-1个人下面的这个x呢，yes，就是n-2个人情况下得到的x''倒推回去，那么如何知道n-2情况下的x'呢，当然是求n-3个人，这就是一个递归的过程
    x=(x'+k)%n, x'=(x''+k)%(n-1), x是n个人的f(n)，x'是f(n-1)，依次倒推，得
        f(n)=(f(n-1)+m)%n。
    那么我们要求f(n)，就从f(1)倒推回去即可
    f(n):表示n个人时，最后一个出列的人在这n个人中的顺序号(从0开始)。
    f(2)表示2个人时，最后一个出列的人在这2个人中的顺序号，是第0个还是第1个。
    最后f(1)若出列只能是第0个，但不是上述最后一个出列的人。
    f(1) = 0 , f(1)就是现在还剩下1个人，那么无论m为几，这个人总会出列，因此f(1)=0.
    f(n) = (f(n-1)+m)%n 

int josephus(int n, int m)
{
    int i, s;
    s = 0;  // f(1)=0;
    for(i = 2; i <= n; ++i)
    {
        s = (s + m) % i;
    }
    printf("the last is %d\n", s+1);
    return (s+1);
}