约瑟夫环问题
约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的将士在附近的一个洞穴中避难。在那里,这些叛乱者表决说“要投降毋宁死”。于是,约瑟夫建议每个人轮流杀死他旁边的人,而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签,并且,作为洞穴中的两个幸存者之一,他说服了他原先的牺牲品一起投降了罗马。
约瑟夫环问题的具体描述是:设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第1个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。
#include <stdio.h>
main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}/*运用了一点数学策略 N=8 M=3 幸存为7 ;少于3的时候还可以数,因为为一个环;从他的下一个人起重新报数*/
分享到:
相关推荐
用单链表解决约瑟夫环问题,数据结构实验报告。约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人...
使用c语言中的循环链表及结构体实现约瑟夫环问题
多种方法解决约瑟夫环问题,1.顺序表2.循环链表3.循环队列4.普通一位数组
约瑟夫环问题描述:编号为1,2,…,n的n个人按顺时针方向围成一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将...
用循环队列解决约瑟夫环问题减少用顺序表在出对是循环移动带来的空间复杂度
用数据结构循环队列实现约瑟夫环问题,数据结构的一次实验;
数据结构中的约瑟夫环问题 C语言编写,已经测试通过
用顺序表实现约瑟夫环问题,并分析算法的时间和空间复杂性。
约瑟夫环问题(c++实现),包含设计文档,实现了8个功能: 1.要求在实现约瑟夫环的同时,应该满足以下要求: 2.完整的图形用户界面,可以配置程序的运行参数,如:n的值,k的值、m的值、执行动画的速度等; 3.算法...
java解决约瑟夫环问题
约瑟夫环问题,用循环链表实现,最后输出胜利者
约瑟夫环问题解析报告
用数据结构中的链表实现著名的约瑟夫环问题比较麻烦,这是用C语言编写的约瑟夫环问题,代码和截图。
首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质,考虑采用循环链表,为了统一对表中任意给定的操作,循环链表不带头结点。
用单向循环链表来实现约瑟夫环问题.自己做的数据结构课设,供大家参考!
汇编语言编写的猴子选美,及约瑟夫环,有一定注释~
约瑟夫环问题解决