快捷搜索:

用环形链表解决约瑟夫问题

**

一、约瑟夫问题的描述

** ➢Josephu 问题 Josephu问题为:设编号为1, 2, … n的n个人围坐一圈,约定编号为k (1<=k<=n) 的人 从1开始报数,数到m的那个人出列,它的下一位又从1开始报数,数到m的那个人又出 列,依次类推,直到所有人出列为止,由此产生个出 队编号的序列。 ➢提示 用一个不带头结点的循环链表来处理Josephu问题:先构成一个有n个结 点的单循环链表, 然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,然后再从被刑除结点 的下一个结点又从1开始计数,直到最后一个结 点从链表中删除算法结束。

二、约瑟夫问题的分析

1、创建环形链表的思路图解 构成一个单项的环形链表思路: (1)先创建第一个节点,让first指向该节点,并形成环状 (2)后面当我们每创建一个新节点,就把该节点,加入到已有的环形链表中即可 遍历环形链表 (1)先让一个辅助指针(变量)curBoy,指向first节点 (2)然后通过一个while循环遍历该换装链表即可curboy.next = first(curboy的下一个节点指向第一个first节点,说明curboy已经遍历到了最后一个节点)程序结束 代码如下:

//添加小孩节点,构成一个环形的链表
	public void addBoy(int num){
          
   
		//num做一个校验
		if(num <1){
          
   
			System.out.println("num的值不正确");
			return ;
		}
		Boy curBoy = null; //辅助指针,帮助构建环形链表
		//使用for来创建我们的环形链表
		for(int i =1 ; i<=num;i++){
          
   
			Boy boy = new Boy(i);
			if(i==1){
          
   
				first=boy; //获取 boy的第一个节点所以first为首节点
				first.setBoy(first); //构成环形!
				curBoy = first;  //用curBoy 指向第一个节点
			}else{
          
   
				curBoy.setBoy(boy); //指向下一个节点boy=1
				//System.out.printf("curBoy:%d
",curBoy.getId());
				boy.setBoy(first);  //指回原来的首节点 first
			//	System.out.printf("boy:%d
",boy.getId());
				curBoy = boy ; //后移
			//	System.out.printf("curbBoy:%d
",curBoy.getId());
			}
			
		}
	}
2、约瑟夫问题-小孩出圈的思路分析图
根据用户的输入,生成一一个小孩出圈的顺序
n=5,即有5个人
k=1,从第一个人开始报数
m=2,数2下
1.需求创建一个辅助指针(变量)helper,事先应该指向环形链表的最后这个节点.
补充:小孩报数前,先让first和helper移动k- 1次
2.当小孩报题时,i让first 和helper指针同时的移动m -1次
3.这时就可以将first指向的小孩节点出圈
first= first .next
helper.next= first
原来first指向的节点就没有任何引用,就会被回收
出圈的顺序
2-24->1-35->3 
代码如下:
//小孩出圈
	/**
	 * 
	 * @param soid 定义有从哪个小孩先开始
	 * @param soNmae 定义每次数几下
	 * @param sum 定义总共有多少个小孩
	 */
	public void contBoy(int soid , int soName,int sum){
          
   
		//判断输入的数据是否合法
		if(first == null || soid<1 || soid>sum){
          
   
			System.out.println("输入的数据有误,请你重新输入");
			return ;
		}
		Boy helpboy = first;
		//先将helpbot循环至first的前一位 也就环状量表的最火一位
		while(true){
          
   
			if(helpboy.getBoy() == first){
          
   
				break ;
			}
			helpboy = helpboy.getBoy();
		}
		//小孩子报数前需要先让 first 和 helpBoy移动m-1位
		for(int i=0;i<soid -1; i ++ ){
          
   
			first=first.getBoy();   //往前移动一位
			helpboy=helpboy.getBoy();
		}
		//当小孩报数时,让first 和helpBoy指针同时一地哦那个m-1次,然后出圈
		//这里是一个循环操作,知道圈中只有一个节点
		int i=0;
		while(true){
          
   
			if(helpboy == first){
          
     //因为最后一个一个出圈的helpboy 和first都指向它
				break ;
			}
			//让fist和helpboy同时移动soName-1,
			for(int j =0;j< soName -1;j++){
          
   
				first=first.getBoy();   //往前移动一位
				helpboy=helpboy.getBoy();
			}//这时first指向的节点就是小孩出圈的节点
			System.out.printf("第%d个出圈的小孩为:%d
",++i,first.getId());
			//让小孩出圈
			first = first.getBoy();
		   helpboy.setBoy(first);
		}
		System.out.printf("最后出圈的小孩是:%d
",first.getId());
		
		
	}

三、代码实现

创建一个Boy的类

class Boy{
          
   
	private int id;
	private Boy boy;
	public Boy(int id) {
          
   
		super();
		this.id = id;
	}
	public int getId() {
          
   
		return id;
	}
	public void setId(int id) {
          
   
		this.id = id;
	}
	public Boy getBoy() {
          
   
		return boy;
	}
	public void setBoy(Boy boy) {
          
   
		this.boy = boy;
	}
	
	
}

创建一个实现类JuseptuWenti类用来实现方法

class JuseptuWenti{
          
   
	//创建一个first节点,当前没有编号作为头
	private Boy first = null;
	//添加小孩节点,构成一个环形的链表
	public void addBoy(int num){
          
   
		//num做一个校验
		if(num <1){
          
   
			System.out.println("num的值不正确");
			return ;
		}
		Boy curBoy = null; //辅助指针,帮助构建环形链表
		//使用for来创建我们的环形链表
		for(int i =1 ; i<=num;i++){
          
   
			Boy boy = new Boy(i);
			if(i==1){
          
   
				first=boy; //获取 boy的第一个节点所以first为首节点
				first.setBoy(first); //构成环形!
				curBoy = first;  //用curBoy 指向第一个节点
			}else{
          
   
				curBoy.setBoy(boy); //指向下一个节点boy=1
				//System.out.printf("curBoy:%d
",curBoy.getId());
				boy.setBoy(first);  //指回原来的首节点 first
			//	System.out.printf("boy:%d
",boy.getId());
				curBoy = boy ; //后移
			//	System.out.printf("curbBoy:%d
",curBoy.getId());
			}
			
		}
	}
	
	//小孩出圈
	/**
	 * 
	 * @param soid 定义有从哪个小孩先开始
	 * @param soNmae 定义每次数几下
	 * @param sum 定义总共有多少个小孩
	 */
	public void contBoy(int soid , int soName,int sum){
          
   
		//判断输入的数据是否合法
		if(first == null || soid<1 || soid>sum){
          
   
			System.out.println("输入的数据有误,请你重新输入");
			return ;
		}
		Boy helpboy = first;
		//先将helpbot循环至first的前一位 也就环状量表的最火一位
		while(true){
          
   
			if(helpboy.getBoy() == first){
          
   
				break ;
			}
			helpboy = helpboy.getBoy();
		}
		//小孩子报数前需要先让 first 和 helpBoy移动m-1位
		for(int i=0;i<soid -1; i ++ ){
          
   
			first=first.getBoy();   //往前移动一位
			helpboy=helpboy.getBoy();
		}
		//当小孩报数时,让first 和helpBoy指针同时一地哦那个m-1次,然后出圈
		//这里是一个循环操作,知道圈中只有一个节点
		int i=0;
		while(true){
          
   
			if(helpboy == first){
          
     //因为最后一个一个出圈的helpboy 和first都指向它
				break ;
			}
			//让fist和helpboy同时移动soName-1,
			for(int j =0;j< soName -1;j++){
          
   
				first=first.getBoy();   //往前移动一位
				helpboy=helpboy.getBoy();
			}//这时first指向的节点就是小孩出圈的节点
			System.out.printf("第%d个出圈的小孩为:%d
",++i,first.getId());
			//让小孩出圈
			first = first.getBoy();
		   helpboy.setBoy(first);
		}
		System.out.printf("最后出圈的小孩是:%d
",first.getId());
		
		
	}
	//遍历当前的节点
	public void list(){
          
   
		if(first == null ){
          
   
			System.out.println("当前节点为空节点");
			return ;
		}
		//提供辅助指针遍历
		Boy boy = first;
		int i= 0;
		while(true){
          
    
			//直接输出小孩的id
			System.out.printf("小孩的id:%d
",boy.getId());
			//判断循环是否结束
			if(boy.getBoy() == first){
          
     //说明遍历完毕
				break ;
			}
			boy = boy.getBoy(); // 让boy后移
		}
	}
	
}

最后在mian函数中运行

public class Testjuseptu {
          
   

	public static void main(String[] args) {
          
   
		
		JuseptuWenti juseptuwenti = new JuseptuWenti();
		
		juseptuwenti.addBoy(5);
		juseptuwenti.list();
		juseptuwenti.contBoy(1, 2, 5);
	}
}
经验分享 程序员 微信小程序 职场和发展