import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。<br />
* 从编号为k的人开始报数,数到m的那个人出列,<br />
* 他的下一个人又从1开始报数,数到m的那个人又出列;<br />
* 依此规律重复下去,直到圆桌周围的人全部出列。
*/
public class Josephus {
public static void main(String[] args) {
int n = 9;
int k = 1;
int m = 5;
List<Integer> list = process(n, k, m);
System.out.print("依次出列的人为:");
for (int i = 0; i < list.size(); i++) {
System.out.print((list.get(i) + 1) + " ");
}
System.out.println();
// 当k=1时,可用此方法求剩下的人
System.out.print("剩下的人为:" + (getLast(n, m) + 1));
}
public static int getLast(int total, int num) {
int result = 0;
for (int i = 2; i <= total; i++)
result = (result + num) % i;
return result;
}
public static List<Integer> process(int n, int k, int m) {
List<Integer> result = new ArrayList<Integer>(n);
boolean[] arr = new boolean[n];
Arrays.fill(arr, true);
int next = 1;
int index = k - 1;
int remain = n;
while (remain > 1) {
if (arr[index]) {
if (next == m) {
arr[index] = false;
remain--;
next = 1;
result.add(index);
} else {
next++;
}
}
index++;
if (index == n) {
index = 0;
}
}
for (int i = 0; i < n; i++) {
if (arr[i])
result.add(i);
}
return result;
}
}
结果:
依次出列的人为:5 1 7 4 3 6 9 2 8
剩下的人为:8
分享到:
相关推荐
Java约瑟夫环演示Applet源码,程序组成: MainApplet类:主要实现了界面的显示 MainSrc类:主要实现了界面图形变化的控制 ParaDialog类:实现了测试参数的输入
约瑟夫环演示程序,实现了界面,图形变化,参数等问题。很好的源代码。
Java约瑟夫环演示Applet源码.zip
约瑟夫环java实现
java源码:Java约瑟夫环演示Applet源码.rar
Java约瑟夫环演示Applet源码.7z
Java编写的约瑟夫环程序,使用do...while循环和while循环进行数据的判断,然后进行while次执行完毕
数据结构(Java)实践作业约瑟夫环参考书本可直接运行交作业
java解决约瑟夫环问题
用JAVA实现约瑟夫环
循环链表 实现约瑟夫环 java 自己写的 测试通过 有注释
约瑟夫环是一个数学的应用问题: 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,...
利用java写的约瑟夫环,在Eclipse平台上开发的,很简单的算法
java用数组实现的约瑟夫环问题。代码简单易懂。
java实现约瑟夫环问题Josephus 约瑟夫问题 * 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k(1,2,3...n)的人开始报数,数到m(1,2,3...)的那个人出列; * 他的下一个人又从1开始报数,...
内容索引:Java源码,初学实例,约瑟夫环,初学实例 Java约瑟夫环演示Applet源码,只要安装有JRE包,就可以打开压缩包中的MainApplet.html运行程序,看到演示效果。 关于约瑟夫环: 假设编号为1,2,...,n(n>0)...
/* 显示结果* 原顺序* 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20* 21 22 23 24 25