约瑟夫出圈问题 两种方法实现,数据和链表 n个人围成一个圈,一个个首尾相连的圈报数,从第一个开始报数
报到m的人出圈,剩下的人继续从1开始报数,直到所有人都出圈为止。
import java.util.LinkedList;
import java.util.Scanner;
/**
* 约瑟夫出圈问题 两种方法实现,数据和链表 n个人围成一个圈,一个个首尾相连的圈报数,从第一个开始报数
* 报到m的人出圈,剩下的人继续从1开始报数,直到所有人都出圈为止。
*
* @author sesame.yangj
*/
public class Joseph {
/**
* @param args
*/
public static void main(String[] args) {
Joseph j = new Joseph();
System.out.println("约瑟夫出圈");
System.out.println("输入人数:");
Scanner s = new Scanner(System.in);
int n = s.nextInt();
System.out.println("输入出圈的位置:");
int m = s.nextInt();
System.out.println("数组实现");
j.arrayJoseph(n, m);
System.out.println("链表实现");
j.listJoseph(n, m);
}
/**
* 用数组实现
*
* @param n 总的人数
* @param m 当前报的数
*/
public void arrayJoseph(int n, int m) {
//数组存储编号
int array[] = new int[n];
int len = n;
for (int i = 0; i < array.length; i++) {
array[i] = i + 1;
}
int i = 0;
//当前报的数
int j = 1;
while (len > 0) {
if (array[i % n] > 0) {
//位置有人
if (j % m == 0) {
//报到出圈的人
System.out.println(array[i % n]);
//为之置空
array[i % n] = -1;
//从1开始报数
j = 1;
i++;
len--;
} else {
i++;
j++;
}
} else {
//遇到空位
i++;
}
}
}
/**
* 用双向链表实现
*
* @param n
* @param m
*/
public void listJoseph(int n, int m) {
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
//添加数据,与编号对应
list.add(i + 1);
}
int moved = 0;
while (list.size() > 0) {
moved = (moved + m - 1) % list.size();
System.out.println(list.get(moved));
list.remove(moved);
}
}
}
分享到:
相关推荐
用循环单向链表解决约瑟夫问题 原题: 设有n个人站成一圈,每个人持有一个密码(正整数)。现从第t个人开始,按顺时针方向“1,2,3,4,…”循环报数,数到m1(第t个人所持密码)的人出列,然后从出列者的下一个人重新...
约瑟夫环(Josephus)问题是由古罗马的史学家约瑟夫(Josephus)提出的,他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军,设法守住了裘达伯特城达47天之久,在城市沦陷之后,他和40名死硬的...
约瑟夫环~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
java实现约瑟夫环问题Josephus 约瑟夫问题 * 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k(1,2,3...n)的人开始报数,数到m(1,2,3...)的那个人出列; * 他的下一个人又从1开始报数,...
约瑟夫环c单链表问题描述:约瑟夫问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数...
约瑟夫环(Joseph)问题的一种描述是:编号为1、2、3……n的n个人按照顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按照顺时针的方向自1开始顺序报数,...
本程序主要是以建立单循环链表的形式,利用单向循环链表存储结构模拟此过程,建立起一个约瑟夫环,然后根据之前创立的结点,输入结点里的一些数据,程序有主函数开始,首先,提示输入创建约瑟夫环环数以及每个环上所...
用单链表解决约瑟夫环问题,数据结构实验报告。约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人...
问题描述:约瑟夫生者死者游戏:30个旅客同乘一条船,因为严重超载,非常危险,大家一致同意将一半的旅客投入海中。30个旅客围成一圈,由第一个人开始,依次报数,数到第9人,便把他投入大海中,然后从他的下一个...
8. 【题目】约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到k的那个人出列;他的下一个人又从1开始报数,数到k的那个人又...
约瑟夫(Joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人可有代表本人的序号。一开始任选一个正整数m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,从...
单链表解决约瑟夫环问题
约瑟夫(Joseph)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止...
已知n个人(不妨分别以编号1,2,3,…,n 代表 )围坐在一张圆桌周围,首先从编号为 k 的人从1开始顺时针报数,1, 2, 3, ...,记下顺时针数到 m 的那个人,同时从编号为 k ...数据结构中经典的双向约瑟夫问题c语言代码
简单的约瑟夫环代码约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3,1。 分析: (1)由于对于每个...
约瑟夫环代码约瑟夫环代码约瑟夫环代码约瑟夫环代码约瑟夫环代码约瑟夫环代码
采用单向环表实现约瑟夫环。请按以下要求编程实现:①从键盘输入整数m,通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1,2,……,m。②从键盘输入整数s(1<=s<=m)和n,从环表的第s...
约瑟夫问题: 这是 17 世纪的法国数学家加斯帕在《数目的游戏问题》中讲的一个故事: 15 个教徒和 15 个 非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个 办 法: 30 个人围成一...
2.约瑟夫(Joseph)问题。具体描述是:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈。每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m...
约瑟夫环问题描述:编号为1,2,…,n的n个人按顺时针方向围成一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将...