循环链表实现约瑟夫环问题数据结构与算法tan-1210的博客-

1、问题来源

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.） 来源于百度百科
☆本篇文章就约瑟夫环问题利用循环链表实现展开！

2、问题描述

约瑟夫(Josephus)环问题:
设有n个人围成一圈，现从第s个人开始，拨顺时针方向从1开始报数，数到d的人退出圆圈，然后从退出圆圈的下一个人重新开始报数，数到d的人又退出國圈，依此重复下去，直到最后一个人出圈为止。对于任意给定的n, s和d,求出按退出圆圈次序得到的n个人员的序列。试将Josephus问题的求解过程用链表结构实现。

3、设计思想

• 首先,设计实现约瑟大环问题的存储结构。由丁约瑟大环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。
• 其次，建立一个不带头结点的循环链表并由头指针first指示。
• 最后，设计约瑟夫环问题的算法。

4、算法描述

下面给出伪代码描述 

1、工作指针 pre 和 p 初始化，计数器 count 初始化； pre = first; p = first; count = 2;//为便于删除操作，从 2 开始计数 2、循环直到  p = pre  2.1 如果 count = m ,则   2.1.1 输出结点 p ; 2.1.2 删除结点 p ; 2.1.3 计数器 count 清零，重新开始计数；  2.2 否则，执行   2.2.1 工作指针 pre 和 p 后移；   2.2.2 计数器增 1 ； 3、退出循环，链表中只剩下一个结点 p ,输出结点 p 后将结点 p 删除； 

5、代码实现

//代码如下 #include<stdio.h> typedef struct Node{ int data;//存放单链表元素值 struct Node *next; }LNode,*LinkList; int main(){ int n,s,d; int i,count;  LinkList p,q; printf("请输入n的值："); scanf("%d",&n); printf("请输入s的值："); scanf("%d",&s); printf("请输入d的值："); scanf("%d",&d); //判断参数是否合法 if((n<1)||(s<1)||(s>n)||(d<1)){ printf("输入参数错误！n"); return 1; } //建立链表  p = new LNode;//申请一个结点  p->data = 1;  p->next = p; for(i =2;i <= n;i++){   q = new LNode;   q->data = i;   q->next = p->next;   p->next = q;   p = q; } //查找报数的起始结点 for(i = 1;i <= s;i++){   p = q;   q = q->next;//q指向报数的起点 } //开始报数 printf("退出圆圈的次序为："); while(q){   count = 1;//设置计数器初值为1 while(count != d){    count++;    p = q;    q = q->next; } printf("%d ",q->data); if(p != q){    p->next = q->next; delete q;//释放结点所占存储空间    q = p->next; } else{ delete q;//释放结点所占存储空间    q = NULL; } } printf("n"); return 0; } 

运行结果

请输入n的值：8 请输入s的值：3 请输入d的值：4 退出圆圈的次序为：6 2 7 4 3 5 1 8 

作者：文坛写于2020年5月1日