之后，罗马人占领Qiaotapate。39 犹太人和Josephus和他的朋友们藏在一个山洞，39犹太人决定宁死不被敌人抓到。我决定自杀，41个人设置在一个圆。通过节1个人报数，数据包每节数3该人就必须自杀。然后再由下一个又一次报数，直到全部人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人開始，越过k-2个人（由于第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行。直到终于仅仅剩下一个人留下，这个人就能够继续活着。问题是，给定了和，一開始要站在什么地方才干避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

      如今我们将问题一般化：N个人围成一圈，从第一个開始报数，第M个将被杀掉，输出它们的死亡顺序

      N=41，M=3时：

      声明一个struct,数据域记录它的序号，指针域指向下一结点。将指针p指向第一个结点位置，p=p->next,(后移一位置),此时要删掉p->next所指的位置的结点temp，然后运行

p->next=p->next->next，将temp的数据输出，然后p=p->next（即移到第四个结点）.......如此往复循环求解

      推广到普通情况则：

      M=4时，p=p-next运行2次后找到temp,M=5时，p=p->next运行3次找到temp......。对于一般的M。则（M-2）次指针位移后它的下一位置极为要删除的位置

#include 
     
      #include 
      
        typedef struct Node{    int data;    struct Node *next;}Node;Node *create(int m){    int i=1;    Node *head, *tail, *s;    head=(Node *)malloc(sizeof(Node));    tail=head;    if( m !=0 )    {        while( i <= m)        {            s=(Node *)malloc(sizeof(Node));            s->data=i++;            tail->next=s;            tail=s;        }                s->next = head->next;    }         free(head);    return s->next;}int main(void){    int m,n;biaoqian:    scanf("%d %d", &m, &n);    Node *p, *temp;    p=create(m);    int i;    while( p != p->next)    {        p=p->next;        for(i=1;i
       
        next;        temp=p->next;//切记不要写反成p->next=temp,这样链表就断了         p->next=temp->next;        printf("->>%d", temp->data);        free(temp);        p=p->next;     }    printf("->>%d\n", p->data);    if(getchar() != '#')    {        goto biaoqian;    }                return 0;}
       
      
     

执行结果

版权声明：本文博客原创文章。博客，未经同意，不得转载。