首页   快速返回

约瑟夫环java实现     所属分类 algo 浏览量 10
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:
15个教徒和15个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,
于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。
问怎样排法,才能使每次投入大海的都是非教徒。

约瑟夫环 解决方法  数据  链表
最简单的数组解法


package algo;

public class YsfCycleArr {
	
	// 编号从0开始
	// forever Tim Duncan  21! surprise
    private static int num = 21;
    // 开始报数位置
    private static int start = 0;
    // 数到3 kill  
    private static int n = 3;
    
    private static int ALIVE = 1;
    private static int KILLED = 0;


	public static void main(String[] args) throws Exception {
		
		int[]mans = new int[num];
		for(int i=0;i<num;i++){
			mans[i] = ALIVE;
		}
		
		int alive = num;
		int index = start;
		int tmp = 0;
		while(true){
			if(alive<=0){
				break;
			}
			
			if(mans[index]==ALIVE){
				tmp++;
			}
			
			// 报数到n个 kill  ,重新开始报数
			if(tmp==n){
				alive--;
				tmp = 0;
				mans[index] = KILLED;
				System.out.println("killed,NO.="+index+",alive="+alive);
			}
			
			index++;
			if(index>=num){
				index = 0;
			}			
		}
	}
}




输出 killed,NO.=2,alive=20 killed,NO.=5,alive=19 killed,NO.=8,alive=18 killed,NO.=11,alive=17 killed,NO.=14,alive=16 killed,NO.=17,alive=15 killed,NO.=20,alive=14 killed,NO.=3,alive=13 killed,NO.=7,alive=12 killed,NO.=12,alive=11 killed,NO.=16,alive=10 killed,NO.=0,alive=9 killed,NO.=6,alive=8 killed,NO.=13,alive=7 killed,NO.=19,alive=6 killed,NO.=9,alive=5 killed,NO.=18,alive=4 killed,NO.=10,alive=3 killed,NO.=4,alive=2 killed,NO.=15,alive=1 killed,NO.=1,alive=0

上一篇     下一篇
jvm外挂工具揭秘

git查看某个文件的变更记录

eclipse关闭验证

大数据SQL引擎

git diff 命令

git reset 版本回退