循环链表实现约瑟夫环问题

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 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)||(sn)||(ddata = 1; p->next = p; for(i =2;i data = i; q->next = p->next; p->next = q; p = q; } //查找报数的起始结点 for(i = 1;i 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日

tan-1210 原创文章 10获赞 20访问量 1406 关注 私信 展开阅读全文
作者：tan-1210

约瑟夫环问题 约瑟夫环 循环 循环链表 链表