问题:有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)
相关推荐
然后从第一个人开始顺时针自1开始报数,报到m的人出列,将其密码作为新的m值,从他的下一个人开始,同样顺时针自1开始报数,依次循环下去,直到所有的人都出列!要求得到依次出列的那些人的编号序列! 基本要求: 用...
Josehus问题算法 设有N个人围坐一圈,现从某人开始报数, 数到M的人出列,接着从出列的下一个人重新报数,数到M的人又出列,如此下去直到所有人都出列为止,给出他们的出列次序。
有10个小孩围成一圈并依次编号,教师指定从第2个小孩开始报数,报到第3个小孩即令其出列。然后从下一个孩子继续报数,数到第3个小孩又令其出列,如此直到所有的孩子都出列。求小孩出列的先后顺序。
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从下一个人开始重新从1开始报数,如此下去,直至所有人全部出列为止。...
编号为1到20的二十个人围成一圈,从编号为K的人开始从1报数,报到M的人出列,求出列的编号顺序,这是用链表实现的小程序,可以不止20个人,任意人数也行
编序为1,2,...n的n个人按顺时针方向围坐一圈,选一个整数作为密码m,从第一个人开始按顺时针方向从自1开始顺序报数,报到m时停止报数.报m的人出列,从他的顺时针方向上的下一个人开始从1报数,直到报到m的人又出列...
一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新报数,如此下去,直至所有人全部...
一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部...
问题描述:编号为1,2,3…,n的n个人按顺时针方向围坐一圈,每人...报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序
有N个人围成一环形圈,第一个人从1开始报数,报道M的人出列,直到最后一个同学,请写出算法。.txt
N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到第S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数)。
# 题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。
问题描述 编号为1,2,……,n的n个人按顺时针方向围坐一圈,...报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部...
功能: 丢手帕 说明: m个小孩围 坐一起.从第一个小孩从1开始数数.数到n的小孩出局.下一个小孩子从1开始数.问最终小孩出列的顺序.
开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他的下一个人开始重新从1报数。如此下去,直到所有人全部出列为止。令n最大...
一开始任忿一个正整教作为报教上限值m,从第一个人开始按服时针方向自1开始顺序报数,报到m时停止报教。报m的人出列。将他的密妈作为新的m值.从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人...
设有n个人围成一圈,现从第s个人开始,拨顺时针方向从1开始报数,数到d的人退出圆圈,然后从退出圆圈的下一个人重新开始报数,数到d的人又退出國圈,依此重复下去,直到最后一个人出圈为止。对于任意给定的n, s和d,...
约瑟夫(Joseph)问题的一种描述是:编号为1,2,…,n的n个人...报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始从新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。
Josephus问题,n个人围坐成一圈,按顺序编号为1-n,确定一个整数m,从1号开始数数,每数到第m个人出列,剩下的人从下一个人重新开始数,直至只剩下一个人为止。