`

有n个人,按顺序围成一圈,从第1个开始报数,第m个出列,直至所有人都出列

阅读更多
问题:有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)
分享到:
评论

相关推荐

    约瑟夫环问题求解代码code.docx

    一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从下一个人开始重新从1开始报数,如此下去,直至所有人全部出列为止。...

    数据结构的文档

    问题描述如下:n个人围成一个圈,每个人持有正整数密码,从第一个人开始顺时针报数,报到m的人退出圈子,然后从下一个人继续报数,直到所有人都退出。解决这个问题通常采用循环链表来模拟这个过程。循环链表允许我们...

    数据结构实验-约瑟夫C语言实现

    1. 本程序针对约瑟夫问题的描述:编号为12,……n的n个人按顺时针方向围成一圈,每人持有一个密码(正整数),一开始任选一个正整数作为报数上限值m,从第一个人开始按顺序时针方向自1开始顺序报数,报道m时停止报数...

    数据结构实验一约瑟夫(Joseph)问题

    在这个特定的问题中,我们有n个人围成一个圈,并按照顺时针方向报数。 #### 二、问题描述与要求 1. **问题描述**: - **参与者**:编号为1,2,3,…,n的n个人; - **初始状态**:所有人都围坐在一个圆圈中; ...

    数据结构的约瑟夫患问题

    问题描述为:n个人围成一圈,从第一个人开始按顺序报数,报到m的人出列,然后从下一个人继续报数,直到所有人都出列。每次出列的人的密码作为新的m值,重复这一过程。 在数据结构中,这个问题通常使用单向循环链表...

    约瑟夫环帮助学生熟练掌握线性表的基本操作在两种存储结构上的实现

    在这个问题中,n个人围成一个圈,每个人都有一个唯一的编号,并按顺时针方向报数,报到m的人出列,然后从下一个人继续报数,直到所有人都出列为止。 问题的描述如下:假设编号为1到n的n个人围坐一圈,每个人都持有...

    “报数问题”C代码

    问题通常表述为:一群人围成一个圈,从某个人开始报数(从1报到某个数字N),凡数到N的人将会被淘汰出圈,接着下一个人继续从1开始报数,直到所有人都被数完为止。报数问题在现实生活中有着广泛的应用场景,如游戏...

    大数据结构实验报告材料.pdf

    约瑟夫问题是一个经典的算法问题,其描述如下:n个人按照顺时针方向围成一圈,从第s个人开始报数,每数到第m个人就出列,然后从下一个人继续开始报数,直至所有人都出列。这个问题可以通过两种不同的数据结构实现,...

    数据结构课程设计Joseph环

    在这个问题中,n个人围成一个圈,按照顺时针方向从1开始报数,每报到m的人出列,他的密码成为新的m值,从他的下一个位置继续报数,直至所有人均出列。本课程设计的目标是使用单向循环链表来模拟这一过程,并输出出列...

    数据结构课程设计Joseph环.pdf

    该问题的基本设定是:n个人围成一圈,按顺时针方向从1开始依次报数,报到m的人出列,然后从下一个人继续报数,直至所有人都出列。每次报数的上限m会随着出列人的密码更新,形成一个新的m值。问题的核心在于如何高效...

    约瑟夫环-数据结构.doc

    在该问题中,n个人围成一个圈,按照顺时针方向自1开始报数,报到m的人退出圈子,然后从下一个人继续报数,直至所有人退出。最终的目标是找出所有人的退出顺序。 **基本算法分析:** 1. **数据结构选择:**解决...

    python约瑟夫环.docx

    在该问题中,n 个人按照顺时针方向围成一个圈,从第一个人开始依次报数,数到 m 的人将被排除出圈,然后从下一个人继续开始计数,直至只剩下一个幸存者。这个幸存者在原始顺序中的位置是问题的关键。 Python 语言...

    数据结构Ⅰ课程设计约瑟夫环.doc

    该问题的基本设定是:n个人围成一圈,按照顺时针方向从1开始报数,每报到m的人出列,其位置的密码成为新的m值,然后从下一个人继续报数,直至所有人都出列。 ### 第1章:问题描述 问题的核心在于模拟一个循环链表,...

    部编版第二章 上机实习题目.doc

    问题描述了n个人围成一圈,从编号为k的人开始报数,数到m的人出列,然后从下一个人重新开始报数,直至所有人出列。解决方案通常采用循环链表,因为链表可以方便地进行插入和删除操作。在题目提供的代码中,首先创建...

    双向循环链表解决约瑟夫实验报告

    假设n个人编号从1到n,围成一个圈,从第1个人开始顺时针报数,数到m的人出列,然后从出列者的下一个位置继续报数,重复这个过程,直至只剩最后一个人。问题的目标是找出最后留下的那个人的编号。 二、数据结构——...

    约瑟夫环实验 建立单循环链表

    问题描述如下:n个人围成一个圈,按照顺时针方向从第1个人开始报数,数到m的人出局,然后从下一个人继续报数,直到所有人都出局为止。出局者的密码成为新的m值,继续游戏,直至只剩一人。本例中,我们使用单循环链表...

    数据结构 期末作业

    问题描述如下:有编号为1至n的n个人围成一个圈,从第一个人开始报数,每个人按顺序报数直至某个指定的数字m。每当某人报到m时,此人就会被淘汰出局,然后从下一个人重新开始报数,直到所有人都被淘汰为止。问题的...

Global site tag (gtag.js) - Google Analytics