约瑟夫环问题
程序员文章站
2022-03-13 15:35:42
...
约瑟夫环是一个数学的应用问题:
写道
已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
如同杀人游戏啊,哈哈,假如有6个人,要杀掉5个人,从1开始报数,叫到2的杀掉,用程序怎么写呢,作为程序员的我,开始吭哧吭哧的写了,不会数学算法啊,只能用程序员的方式解决。
package com.ssm.common;
import java.util.ArrayList;
import java.util.List;
public class Josephus {
List<Peple> pepleList = new ArrayList<Peple>();
class Peple {
int next;//下一个人
int index;// 本人序号
boolean flag = true;//是否活着
}
/**
* 杀人
* @param total 总人数
* @param killNum 需要杀死的人数
* @param m 报到此数将被杀死
*/
public void jsph(int total,int killNum,int m) {
int startIndex = 0;//开始序号
int count = 1;//报数开始
int killedCount=0;//被杀的人总数
while (killedCount<killNum) {//被杀的人数等于设定的杀人数量 则结束
//1、判断当前这个人是否可以杀
if (count == m)
{
pepleList.get(startIndex).flag = false;//杀死
++killedCount;
count=0;
System.out.println(pepleList.get(startIndex).index+" is killed");
}
//2、找到下一个人,进行报数
do
{
startIndex=pepleList.get(startIndex).next;//被杀的下一个人
}
while(!pepleList.get(startIndex).flag);//循环直到找到活人
//2、向下报数
++count;
}
showResult();//显示结果
}
private void showResult()
{
System.out.print("\n\nresult:");
for (int i = 0; i < pepleList.size(); i++) {
if(pepleList.get(i).flag)
System.out.print(pepleList.get(i).index+"[live] ");
else
System.out.print(pepleList.get(i).index+"[dead] ");
}
}
/**
* 启动游戏
* @param total 总人数
* @param killNum 需要杀死的人数
* @param m 报到次数将被杀死
*/
public void startGame(int total,int killNum,int m) {
System.out.println("Rule:total is "+total+",killNum is "+killNum+",callNum is "+m);
System.out.println("\n\nInit peples...");
for (int i = 0; i < total; i++) {
Peple p = new Peple();
p.index = i;// 序号
p.next = (i == total-1) ? 0 : i+1;
pepleList.add(p);
System.out.print("["+p.index+"]");
}
System.out.println("\n\nGame is starting...");
this.jsph(total,killNum,m);//杀人
}
public static void main(String[] args) {
new Josephus().startGame(6, 5, 2);
}
}
运行结果:
Rule:total is 6,killNum is 5,callNum is 2
Init peples...
[0][1][2][3][4][5]
Game is starting...
1 is killed
3 is killed
5 is killed
2 is killed
0 is killed
result:0[dead] 1[dead] 2[dead] 3[dead] 4[live] 5[dead]
Init peples...
[0][1][2][3][4][5]
Game is starting...
1 is killed
3 is killed
5 is killed
2 is killed
0 is killed
result:0[dead] 1[dead] 2[dead] 3[dead] 4[live] 5[dead]
没学过算法设计啊,只能这么写,最后发现这个问题有个公式啊,请看http://baike.baidu.com/view/717633.htm#sub717633,最后想说的是,学好数学还是蛮有用的啊,后悔ing.