引入

罗马占领乔塔帕特之后，39个犹太人与 Joseph 及1个朋友躲进山洞避难，39个人宁死也不愿意被敌人抓到，决定了一种自杀方式：

  • 41 个人排成一个圆圈（39个犹太人 + Joseph + 1 个朋友）
  • 第 1 个人开始报数，每报数到第3人，这个人就自杀
  • 然后再从下一个，也就是原来的第 4 人开始，数到第 3 人自杀
  • 直到所有人都自杀身亡为止

但是 Joseph 和朋友并不想死，所以就有如下那排

  • 朋友去了 16 号
  • Joseph 去了 31 号
  • 于是，逃过了死亡游戏

约瑟夫问题

那么这个有趣得约瑟夫和朋友逃难的问题跟我们得循环链表有什么关系呢？我们想用计算机帮助我们把41个人的自杀编号输出出来：

代码实现

#include <stdio.h>
#include <stdlib.h>
#define NUM 41
#define LEN sizeof(struct joseph)

struct joseph{
    int data;
    struct joseph *next;
};

struct joseph *create(void){
    struct joseph *a,*b,*head;
    int i=0;
    while(i<NUM){
        i++;
        a=(struct joseph * )malloc(LEN);
        if(i==1){
            head=a;
            b=a;
        }else{
            b->next=a;
            b=a;
        }
        a->data=i;
    }
    b->next=head;
    return head;
}

void joseph_kill(struct joseph *loop){
    int n=1;
    do{
        if(n==2){
            printf("%d->",loop->next->data);
            loop->next=loop->next->next;
            n=0;
        }
        loop=loop->next;
        n++;
    }while(loop->next!=loop);
    printf("%d",loop->data);
}

int main(){
    struct joseph *ring;
    ring=create();
    joseph_kill(ring);
    return 0;
}

其实创建循环链表并不难，难的是如何删除人，并且将其序号提取出来，思路大致如下：

  • 找到要删除的结点得前一结点，也就是每隔2个人
  • 找到前一结点，将它得 next==nxte->next，删除第三个节点
  • 删除之前，将其编号进行输出

升级问题

如果 N 个人围成一圈，每人持有一个100内的正整数

  • 开始人的真正数位 M
  • 顺时针开始报数，报到第 M 次时，这个人出列
  • 然后出列人手上的正整数位 M，再次报数
  • 直到所有人都出列，写出出列顺序
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM 41
#define LEN sizeof(struct joseph)

struct joseph{
    int data;
    int num;
    struct joseph *next;
};

struct joseph *create(void){
    struct joseph *a,*b,*head;
    int i=1;
    while(i<=NUM){
        a=(struct joseph * )malloc(LEN);
        if(i==1){
            head=a;
        }else{
            b->next=a;
        }
        b=a;
        a->data=i++;
        a->num=rand()%100;
    }
    b->next=head;
    return head;
}

void joseph_kill(struct joseph *loop){
    int n=loop->num;
    do{
        if(n==0){
            n=loop->num-1;
            printf("%d->",loop->next->data);
            loop->next=loop->next->next;
        }
         n--;
        loop=loop->next;
    }while(loop->next!=loop);
    printf("%d",loop->data);
}

int main(){
    srand((time(0)));
    struct joseph *ring;
    ring=create();
    joseph_kill(ring);
    return 0;
}

这个改变其实并不难，思路大致如下：

  • 找到要删除的结点得前一结点，也就是 m-1 个
  • 找到前一结点，将它得 next==nxte->next，删除第三个节点
  • 删除之前，将其正整数赋值给 m，记得 -1 ！

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。