约瑟夫问题

约瑟夫问题：

     据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

 

这是一个循环链表的问题，将链表的尾节点的指针指向头结点，按照一定的条件将其中的元素取出，直到最后一个元素：

#include <stdio.h>
#include <stdlib.h>

#define N 41
#define STEP 3

typedef struct _node_
{
    int data;
    struct _node_ *next;
}linknode, *linklist;

int main(int argc, char *argv[])
{
    int i;
    linklist p, q;
    p = (linklist)malloc(sizeof(linknode));
    p->data = 1;
    q = p;

    for(i=2; i<=N; i++){
        q->next = (linklist)malloc(sizeof(linknode));
        q = q->next;
        q->data = i;
    }
    q->next = p;

    while(p->next != p){
        for(i=0; i<STEP-2; i++)
            p = p->next;
        q = p->next;
        p->next = q->next;
        printf("%d ", q->data);
        free(q);
        p = p->next;
    }
    printf("%d \n", p->data);

    return 0;
}