问题:有n个人,按顺序围成一圈,从第1个开始报数,第m个出列,直至所有人都出列。
1、设计思路
1)
使用集合存放n个值;
循环n次 {
每次获取第m个,并删除第m个
}
1.1)循环n次
通过for循环n次,或者通过while语句遍历集合至空为止
1.2)每次获取第m个,并删除第m个
循环查找,每次循环计数1,当计数值count==m时,获取值并删除相应元素;
进入下一轮查找直到结束。
由于m可能大于n,一次循环不一定满足要求,所以需要用到递归算法。
2、代码实现
import java.util.ArrayList; import java.util.List; public class DeleteCyclicData1 { /** 原始数据 */ private List<Integer> list; /** * 开始执行 * * @param n * @param m * @return void */ public void exec(int n, int m) { initData(n); deleteElements(n, m); } /** * 初始化数据 * * @param n * @return void */ public void initData(int n) { list = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { list.add(i); } } /** * 逐个删除并输出元素 * * @param n * @param m * @return void */ public void deleteElements(int n, int m) { System.out.print(String.format("\nn=%s, m=%s, results:", n, m)); for (int i = 1; i <= n; i++) { System.out.print(deleteElement(m, 0) + " "); } } /** * 开始执行 * * @param n * @param m * @return int 返回本次删除的元素 */ public int deleteElement(int m, int count) { for (int i = 0; i < list.size(); i++) { if (++count == m) { return list.remove(i); } } return deleteElement(m, count); } public static void main(String[] args) { DeleteCyclicData1 obj = new DeleteCyclicData1(); obj.exec(5, 2); obj.exec(5, 3); obj.exec(5, 6); obj.exec(5, 12); } }
import java.util.ArrayList; import java.util.List; public class DeleteCyclicData2 { /** 原始数据 */ private List<Integer> list; /** * 开始执行 * * @param n * @param m * @return void */ public void exec(int n, int m) { initData(n); deleteElements(n, m); } /** * 初始化数据 * * @param n * @return void */ public void initData(int n) { list = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { list.add(i); } } /** * 逐个删除并输出元素 * * @param n * @param m * @return void */ public void deleteElements(int n, int m) { System.out.print(String.format("\nn=%s, m=%s, results:", n, m)); while (list.size() > 0) { System.out.print(deleteElement(m, 0) + " "); } } /** * 开始执行 * * @param n * @param m * @return int 返回本次删除的元素 */ public int deleteElement(int m, int count) { for (int i = 0; i < list.size(); i++) { if (++count == m) { return list.remove(i); } } return deleteElement(m, count); } public static void main(String[] args) { DeleteCyclicData2 obj = new DeleteCyclicData2(); obj.exec(5, 2); obj.exec(5, 3); obj.exec(5, 6); obj.exec(5, 12); } }
以上是看到这个问题的第一个思路,但总感觉这样递归似乎比较麻烦。
假设m<=n,那么其实只需要直接从集合中获取第m个值即可;
如果m>n,那么m对n取余的余数可以重复使用以上规则;
但是,有一种特殊情况,当m>n,且m能够被n整除的时候,此时余数为0,这种情况不能直接使用余数获取相应值,而应该获取集合的最后一个元素。
于是,代码如下:
import java.util.ArrayList; import java.util.List; public class DeleteCyclicData3 { /** 原始数据 */ private List<Integer> list; /** * 开始执行 * * @param n * @param m * @return void */ public void exec(int n, int m) { initData(n); deleteElements(n, m); } /** * 初始化数据 * * @param n * @return void */ public void initData(int n) { list = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { list.add(i); } } /** * 逐个删除并输出元素 * * @param n * @param m * @return void */ public void deleteElements(int n, int m) { System.out.print(String.format("\nn=%s, m=%s, results:", n, m)); while (list.size() > 0) { int remainder = m % list.size(); System.out.print(list.remove(remainder == 0 ? list.size() - 1 : remainder - 1) + " "); } } public static void main(String[] args) { DeleteCyclicData3 obj = new DeleteCyclicData3(); obj.exec(5, 2); obj.exec(5, 3); obj.exec(5, 6); obj.exec(5, 12); } }
运行结果:
n=5, m=2, results:2 3 4 5 1 n=5, m=3, results:3 4 5 1 2 n=5, m=6, results:1 3 5 4 2 n=5, m=12, results:2 5 4 3 1
事实上,第1种思路比较简单,易于理解。第2种思路虽然代码简洁一点,但反而容易出错。
(转载请注明来源:http://zhanjia.iteye.com/admin/blogs/2028617)
相关推荐
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从下一个人开始重新从1开始报数,如此下去,直至所有人全部出列为止。...
问题描述如下:n个人围成一个圈,每个人持有正整数密码,从第一个人开始顺时针报数,报到m的人退出圈子,然后从下一个人继续报数,直到所有人都退出。解决这个问题通常采用循环链表来模拟这个过程。循环链表允许我们...
1. 本程序针对约瑟夫问题的描述:编号为12,……n的n个人按顺时针方向围成一圈,每人持有一个密码(正整数),一开始任选一个正整数作为报数上限值m,从第一个人开始按顺序时针方向自1开始顺序报数,报道m时停止报数...
在这个特定的问题中,我们有n个人围成一个圈,并按照顺时针方向报数。 #### 二、问题描述与要求 1. **问题描述**: - **参与者**:编号为1,2,3,…,n的n个人; - **初始状态**:所有人都围坐在一个圆圈中; ...
问题描述为:n个人围成一圈,从第一个人开始按顺序报数,报到m的人出列,然后从下一个人继续报数,直到所有人都出列。每次出列的人的密码作为新的m值,重复这一过程。 在数据结构中,这个问题通常使用单向循环链表...
在这个问题中,n个人围成一个圈,每个人都有一个唯一的编号,并按顺时针方向报数,报到m的人出列,然后从下一个人继续报数,直到所有人都出列为止。 问题的描述如下:假设编号为1到n的n个人围坐一圈,每个人都持有...
问题通常表述为:一群人围成一个圈,从某个人开始报数(从1报到某个数字N),凡数到N的人将会被淘汰出圈,接着下一个人继续从1开始报数,直到所有人都被数完为止。报数问题在现实生活中有着广泛的应用场景,如游戏...
约瑟夫问题是一个经典的算法问题,其描述如下:n个人按照顺时针方向围成一圈,从第s个人开始报数,每数到第m个人就出列,然后从下一个人继续开始报数,直至所有人都出列。这个问题可以通过两种不同的数据结构实现,...
在这个问题中,n个人围成一个圈,按照顺时针方向从1开始报数,每报到m的人出列,他的密码成为新的m值,从他的下一个位置继续报数,直至所有人均出列。本课程设计的目标是使用单向循环链表来模拟这一过程,并输出出列...
该问题的基本设定是:n个人围成一圈,按顺时针方向从1开始依次报数,报到m的人出列,然后从下一个人继续报数,直至所有人都出列。每次报数的上限m会随着出列人的密码更新,形成一个新的m值。问题的核心在于如何高效...
在该问题中,n个人围成一个圈,按照顺时针方向自1开始报数,报到m的人退出圈子,然后从下一个人继续报数,直至所有人退出。最终的目标是找出所有人的退出顺序。 **基本算法分析:** 1. **数据结构选择:**解决...
在该问题中,n 个人按照顺时针方向围成一个圈,从第一个人开始依次报数,数到 m 的人将被排除出圈,然后从下一个人继续开始计数,直至只剩下一个幸存者。这个幸存者在原始顺序中的位置是问题的关键。 Python 语言...
该问题的基本设定是:n个人围成一圈,按照顺时针方向从1开始报数,每报到m的人出列,其位置的密码成为新的m值,然后从下一个人继续报数,直至所有人都出列。 ### 第1章:问题描述 问题的核心在于模拟一个循环链表,...
问题描述了n个人围成一圈,从编号为k的人开始报数,数到m的人出列,然后从下一个人重新开始报数,直至所有人出列。解决方案通常采用循环链表,因为链表可以方便地进行插入和删除操作。在题目提供的代码中,首先创建...
假设n个人编号从1到n,围成一个圈,从第1个人开始顺时针报数,数到m的人出列,然后从出列者的下一个位置继续报数,重复这个过程,直至只剩最后一个人。问题的目标是找出最后留下的那个人的编号。 二、数据结构——...
问题描述如下:n个人围成一个圈,按照顺时针方向从第1个人开始报数,数到m的人出局,然后从下一个人继续报数,直到所有人都出局为止。出局者的密码成为新的m值,继续游戏,直至只剩一人。本例中,我们使用单循环链表...
问题描述如下:有编号为1至n的n个人围成一个圈,从第一个人开始报数,每个人按顺序报数直至某个指定的数字m。每当某人报到m时,此人就会被淘汰出局,然后从下一个人重新开始报数,直到所有人都被淘汰为止。问题的...