Take a second to imagine that you are in a room with 100 chairs arranged in a circle. These chairs are numbered sequentially from One to One Hundred.
At some point in time, the person in chair #1 will be told to leave the room. The person in chair #2 will be skipped, and the person in chair #3 will be told to leave. Next to go is person in chair #6. In other words, 1 person will be skipped initially, and then 2, 3, 4.. and so on. This pattern of skipping will keep going around the circle until there is only one person remaining.. the survivor. Note that the chair is removed when the person leaves the room. Write a program to figure out which chair the survivor is sitting in. Please send us the answer and your working code.
Answer: The survivor is sitting in chair# 31.
Solution 1: using array list
public int findSurvivor() { int n = 100; // number of chairs List<Integer> chairs = new ArrayList<>(); for(int i=1; i<=n; i++) { chairs.add(i); } int victim = 0; // the index of chair to be removed int step = 0; while (chairs.size() > 1) { chairs.remove(victim); victim += ++step; victim %= chairs.size(); } return chairs.get(0); }
Solution 2: using linked list
public int findSurvivor() { int n = 100; // number of chairs List<Integer> chairs = new LinkedList<>(); for(int i=1; i<=n; i++) { chairs.add(i); } int step = 1; Iterator<Integer> itr = chairs.iterator(); while (chairs.size() > 1) { for (int i = 0; i < step; i++) { if (!itr.hasNext()) itr = chairs.iterator(); itr.next(); } itr.remove(); step++; } return chairs.get(0); }
相关推荐
约瑟夫环代码约瑟夫环代码约瑟夫环代码约瑟夫环代码约瑟夫环代码约瑟夫环代码
单链表解决约瑟夫环问题
本程序主要是以建立单循环链表的形式,利用单向循环链表存储结构模拟此过程,建立起一个约瑟夫环,然后根据之前创立的结点,输入结点里的一些数据,程序有主函数开始,首先,提示输入创建约瑟夫环环数以及每个环上所...
约瑟夫环~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
用C语言实现约瑟夫环,适合初学者学习 用C语言实现约瑟夫环,适合初学者学习 用C语言实现约瑟夫环,适合初学者学习 用C语言实现约瑟夫环,适合初学者学习 用C语言实现约瑟夫环,适合初学者学习 用C语言实现约瑟夫环...
约瑟夫环c单链表问题描述:约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数...
c# 约瑟夫环问题算法 的实现。
用vc6.0环境实现的约瑟夫环的上机实验报告
约瑟夫环的例子,约瑟夫环的例子 约瑟夫环的例子,约瑟夫环的例子
用顺序表表示约瑟夫环,其中密码相同,即为静态存储约瑟夫环的内容
采用单向环表实现约瑟夫环。请按以下要求编程实现:①从键盘输入整数m,通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1,2,……,m。②从键盘输入整数s(1<=s<=m)和n,从环表的第s...
大二时数据结构课上做的一个约瑟夫环,带有图形界面,开发语言是c++
用单链表解决约瑟夫环问题,数据结构实验报告。约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人...
使用c语言中的循环链表及结构体实现约瑟夫环问题
在VC++6.0环境下C语言编程实现,实现了约瑟夫环的问题。
这个约瑟夫环代码简单易懂,附解释,是在老师的辅导下完成的,相信大家看了就会懂
多种方法解决约瑟夫环问题,1.顺序表2.循环链表3.循环队列4.普通一位数组
约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的...
数据结构实习报告,约瑟夫环,内附源代码,有注释。
约瑟夫环(Joseph)问题的一种描述是:编号为1、2、3……n的n个人按照顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按照顺时针的方向自1开始顺序报数,...