[学习交流] java解决约瑟夫环问题的几种方法小结

由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.

import java.util.Scanner;
/**
*使用数组实现约瑟夫环问题
*由m个人围成一个首尾相连的圈报数。
*从第一个人开始，从1开始报数，报到n的人出圈，
*剩下的人继续从1开始报数，直到所有的人都出圈为止。
*对于给定的m和n，求出所有人的出圈顺序.
*/
public class RingTest{
public static void main(String[] args){
System.out.println("程序说明如下：");
System.out.println("由m个人围成一个首尾相连的圈报数。从第一个人开始，从1开始报数，报到n的人出圈，剩下的人继续从1开始报数，直到所有的人都出圈为止。对于给定的m和n，求出所有人的出圈顺序.");
//提示输入总人数
System.out.println("请输入做这个游戏的总人数：");
Scanner sca=new Scanner(System.in);
int m=sca.nextInt();
//提示输入要出圈的数值
System.out.println("请输入要出圈的数值：");
int n=sca.nextInt();
System.out.println("按出圈的次序输出序号：");
//创建有m个值的数组
int[] a=new int[m];
//初始长度，以后出圈一个，长度就减一
int len=m;
//给数组赋值
for(int i=0;i<a.length;i++)
a[i]=i+1;
//i为元素下表，j代表当前要报的数
int i=0;
int j=1;
while(len>0){
if(a[i%m]>0){
if(j%n==0){//找到要出圈的人，并把圈中人数减一
System.out.print(a[i%m]+" ");
a[i%m]=-1;
j=1;
i++;
len--;
}else{
i++;
j++;
}
}else{//遇到空位了，就跳到下一位，但j不加一，也就是这个位置没有报数
i++;
}
}
}
}

复制代码

方法2

import java.util.ArrayList;
import java.util.List;
public class Monkey {
private final static String SVN_VERSION = "$Id$";
public List sourceList= new ArrayList();//按顺序递增的序列链表，作为源链表，从该链表中移除报了数的成员
public List finalList= new ArrayList();//最终的结果链表；初始化时链表里全部成员都为零，长度跟源链表一样,每次从源链表中移除一个报数成员，就在该链表中的相同位置增加被移除的序号
public int k;
public int n;
/**
* 初始化源链表和最终的结果链表，原链表中的存放的是整数，按顺序递增；结果链表中存放的全部是零
* @param k 每报k次数后重新报数
* @param n 一共有n个人围成一圈报数
*/
public void init(int k,int n){
this.k=k;
this.n=n;
for(int i=1;i<=n;i++){
sourceList.add(i);
finalList.add(0);
}
}
/**
* 排序过程
*/
public void sequence(){
int index =0;//原链表的index，相当于报数指针
int seqNum =1;//报数报到K的人，出列顺序
System.out.println("链表总长 n="+n+";每次选择k个人报数，K="+k);
//只要还有人没报数报到k，就继续循环下去
while(!sourceList.isEmpty()){
System.out.println("每移除一次报数后的链表内容:");
//每次移除一个报到k的人时，从1开始报数，打印这时源链表中的内容
for(int a=0;a<sourceList.size();a++){
System.out.println("sourceList["+a+"]="+sourceList.get(a));
}
//count相当于报数K的计数器，大于k从1开始报数，报到k时移除k,并且跳出该循环
for(int count=1;count<=k;count++){
System.out.println("sourceList.size()="+sourceList.size()+";count="+count+";index="+index+";seqNum="+seqNum);
//当总人数只剩下一个人的时候
if(sourceList.size() == 1){
int objInt = (Integer) sourceList.get(0);
System.out.println("END--报数第K个... sourceList[0]="+objInt);
sourceList.remove(0);
finalList.set(objInt-1, seqNum);
break;
}
//当index已经循环到链表最后元素，并且最后一个元素被移除了,index从零算起
if(index == sourceList.size()){
index =0;
}else if(index > sourceList.size())//当index已经循环到链表最后元素可能超过了链表的总长度，index从它多余的元素开始从头算起
{
index =index%(sourceList.size());
}
System.out.println("【index】 =="+index);
//报数还没报到k时,Index增加一，表示报数向下一个元素移动
if(count !=k){
index++;
}else{//报数报到k时,原链表移除该元素，结果链表相应的位置增加被移除的顺序号，并且跳出该循环，从下一个位置开始重新报数
int objInt = (Integer) sourceList.get(index);
System.out.println("@@@报数第K个... sourceList["+index+"]="+objInt);
sourceList.remove(index);
finalList.set(objInt-1, seqNum);
seqNum++;
break;
}
}
}
System.out.println("排序后的链表内容为:");
//打印结果链表
for(int a=0;a<finalList.size();a++){
System.out.println("finalList["+a+"]="+finalList.get(a));
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
Monkey obj = new Monkey();
obj.init(3, 6);
obj.sequence();
}
}

复制代码

方法3:

import java.util.LinkedList;
/**
*
* @author Love yali_deng forever
*
*/
public class Yuesefu{
/**
* 约瑟夫环是一个数学的应用问题：
*
* 已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；
* 他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
*
* @param args
*/
private static StringBuffer removedStr = new StringBuffer("");// 记录删除的数字
public static void main(String[] args) {
long startTime = System.currentTimeMillis(); // 获取开始时间
process(5000, 10, 1);
System.out.println(removedStr.substring(0, removedStr.length() - 1));
long endTime = System.currentTimeMillis(); // 获取结束时间
System.out.println("程序运行时间： " + (endTime - startTime) + "ms");
}
public static void process(int n, int k, int m) {
// 构建一个list，存放人数
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
if (i + k > n) {
list.add(i + k - n);
} else {
list.add(i + k);
}
}
int count = 1;// 记录数的人数
cycleCal(list, count, m);
}
public static void cycleCal(LinkedList<Integer> list, int count, int m) {
int len = list.size();
if (len > 1) {
for (int i = 0; i < len; i++) {
if (count == m) {// 第m个时，remove
removedStr.append(list.get(i)).append(",");
list.remove(i);
len = list.size();
i--;
count = 0;
}
count++;
}
cycleCal(list, count, m);
} else {
if (len != 0) {
removedStr.append(list.get(0)).append(",");
}
}
}
}

复制代码

帐号		自动登录	找回密码
密码			加入黑马

[学习交流] java解决约瑟夫环问题的几种方法小结

0 个回复