java 约瑟夫问题

心已赠人 2021-11-04 13:20 279阅读 0赞

约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”.）

例子：  
len个人围成一个圈，玩丢手绢游戏。从第k个人开始，从1开始数数，当数到m时，数m的人就退出圈子，当圈子只剩下一个人为止。

package day7;
    
    public class Damo2 {
    	
    	public static void main(String[] args) {
    //		Child c1=new Child(1);
    //		Child c2=new Child(2);
    //		Child c3=new Child(3);
    //		Child c4=new Child(4);
    //		Child c5=new Child(5);
    //		Child c6=new Child(6);
    	
    //		c1.setNext(c2);
    //		c2.setNext(c3);
    //		c3.setNext(c4);
    //		c4.setNext(c5);
    //		c5.setNext(c1);
    		//循环长度
    		int childCounts=41;	
    		//创建一个数组，在堆空间中创建一个这个数组的空间，也就是容量
    		Child[] childs=new Child[childCounts];
    		//给这个数组空间分配每个元素的空间
    		for(int i=0;i<childs.length;i++) {
    			childs[i]=new Child(i+1);
    		}
    		//建立起每个元素之间的联系1--》2---》3---》4....
    		for(int i=0;i<childs.length;i++) {
    			//类似于一个圈，从1到10，那么每个元素的下标就是从0到9
    			//如果当这个圈中最后一个元素下标等于第一个元素时（不是下标），那么久建立起最后一个元素和第一个元素直接的联系
    			if(i==childs.length-1) {
    //				c5.setNext(c1);
    				childs[i].setNext(childs[0]);
    				//否则在这个圈中第一个和最后一个之间的每个元素建立起联系
    			}else {
    //				c1.setNext(c2);
    //				c2.setNext(c3);
    //				c3.setNext(c4);
    //				c4.setNext(c5);
    				childs[i].setNext(childs[i+1]);
    			}
    		}		
    		//System.out.println(childs[0]);
    		//此时的ptr=1，从这个圈的起点开始走
    		Child ptr=childs[0];
    		//计步器，用来判断是否是3的倍数
    		int count=1;
    		int skip=3;//跳3步		
    		//整个大的循环是用来判断是否是3的倍数，是的话，就跳过
    		while(ptr!=ptr.getNext()) {			
    			System.out.println("#"+ptr);
    			//判断是否满足条件，如果满足是3的倍数，就跳过
    			if(count%(skip-1)==0) {
    				//2  2.next=3  2.next.next=4
    				//2.setNext(2.next.next)==2.setNext(4)   2-（3）-4  （）代表去掉  
    				//下一个的下一个
    				ptr.setNext(ptr.getNext().getNext());
    			}			
    //			ptr=ptr.getNext();	
    //			System.out.println("---"+ptr);
    			count++;		
    			//不满足的话，就继续获取这个index值
    			ptr=ptr.getNext();
    		}		
    		
    		System.out.println("-->"+ptr);		
    	}
    }
    class Child{
    	
    	private int index;
    	private Child next;
    	
    	public Child() {
    	}
    	public Child(int index) {
    		this.index=index;
    	}
    	public Child(int index, Child next) {
    		this.index = index;
    		this.next = next;
    	}
    	public int getIndex() {
    		return index;
    	}
    	public void setIndex(int index) {
    		this.index = index;
    	}
    	public Child getNext() {
    		return next;
    	}
    	public void setNext(Child next) {
    		this.next = next;
    	}
    	public String toString() {
    		return "Child [next=" + next + "]";
    	}
    }