Java_Josephus problem 约瑟夫环详尽分享

女爷i 2024-04-03 08:13 71阅读 0赞

## Java\_Josephus problem 约瑟夫环详尽分享 ##

先看代码后看分享

#### 文章目录 ####

*  Java\_Josephus problem 约瑟夫环详尽分享
 *   *  1. 约瑟夫环代码
     *  2. 什么是约瑟夫环
     *  3. 理解约瑟夫环
     *   *  3.1 完成节点类和数据类定义
         *  3.2 理解插入过程
         *  3.3 理解运行过程
         *  3.4 理解更新密码值
         *  3.5 将更新密码值放入我们的调用类中去
     *  4.运行结果

### 1. 约瑟夫环代码 ###

> 下面是完整代码与注释

public class LinkedNode<T> {
        
    	//设置私人的对象
        private T data; //定义泛型数据域
        private LinkedNode<T> next; //定义后继引用域
    	
        public LinkedNode() {
        	//无参构造函数，构造空结点
            data = null;next = null;
        }
    
        public LinkedNode(T element){
        	//构造函数，构造数据域为element值的结点
            data = element;next= null;
        }
    
        public T getData() {
        	//获取数据域data的值
            return data;
        }
    
        public void setData(T data) {
        	//设置数据域data值
            this.data = data;
        }
    
        public LinkedNode<T> getNext() {
        	//获取next值
            return next;
        }
    
        public void setNext(LinkedNode<T> next) {
        	//设置next值
            this.next = next;
        }
    }
    
    
    public class datatype {
        
        private int id;	//存放我们的id
        private int password;	//存放我们的密码
    
        public datatype() {
        	//构造无参构造函数，构造空结点
        }
    
        public datatype(int id, int password) {
         //构造函数，让其与引入的内容对接
            this.id = id;
            this.password = password;
        }
    
        public int getId() {
        	//获取我们的id值
            return id;
        }
    
        public void setId(int id) {
        	//设置我们的id值
            this.id = id;
        }
    
        public int getPassword() {
        	//获取我们的密码
            return password;
        }
    
        public void setPassword(int password) {
        	//设置我们的密码
            this.password = password;
        }
    }
    
    import java.util.Scanner;
    
     class CList<T> {
        
        private LinkedNode<T> rear ;//生成一个节点,定义尾指针
    
        public CList() {
        
            rear = null;
        }
    
        public LinkedNode<T> getRear() {
        
            return rear;
        }
    
        public void setRear(LinkedNode<T> rear) {
        
            this.rear = rear;
        }
    
        public T yunxingCircular(int m) {
        
            if (isEmpty()){
        //判断是否为空
                throw new RuntimeException("空表");
            }
            else {
        //如果不是空表,判断当前是否是一个元素
                if (rear.getNext() == rear) {
        //如果只有一个元素
                    LinkedNode<T> cz = rear;//设置一个新节点，承载rear节点
                    rear = null;//让此时rear的值为null,即删除此处元素
                    return cz.getData();//返回此时用于承载节点的数据域
                }
                else {
        //如果不是只有一个元素
                    int a = 1;//定义第一个个人报数为1
                    while (a < m) {
        //当报数上限值<该次密码值时
                        rear = rear.getNext();//尾指针向后移一位
                        a++;//报数值加一
                    }
                    LinkedNode<T> cz = rear.getNext();//设置新节点承载rear的后一个节点
                    rear.setNext(rear.getNext().getNext());//让rear的引用域为之前rear的下下一个节点的地址
                    return cz.getData();//返回承载节点cz的数据域
                }
            }
        }
    
        public void insert(T element){
        //用于表达插入元素进约瑟夫表的方法
            LinkedNode<T> cr = new LinkedNode<T>(element);//设置一个新节点cr，其数据域为element
            if (rear == null){
        //如果rear值为null，即只有一个元素
                rear = cr;//rear此时就等于刚刚插入的新节点cr
                rear.setNext(rear);//加入一个元素之后，rear的下一个元素还是rear，构成了循环
            }
            else {
        //如果不是一个元素
                cr.setNext(rear.getNext());//插入的元素的引用域就是此时尾指针指向元素的引用域中的地址，即与当时的尾结点相接
                rear.setNext(cr);//此时尾指针指向元素的引用域为cr元素
                rear = cr;//再把尾指针向后移一位
            }
        }
    
         public boolean isEmpty() {
        //用于判断循环链表为空的方法
             if (rear == null)//根据rear是否=null来判断返回的值是true还是false
                 return true;
             else
                 return false;
         }
    
    
    }
    
    public class Ysf {
        
       public static void main(String[] args) {
        
           CList zx = new CList();//建立一个Clist的对象
           Scanner sr =  new Scanner(System.in);
           System.out.println("请输入环内人数");
           int peoples = sr.nextInt();//确定环内总人数
           System.out.println("请输入初始密码值");
           int password  = sr.nextInt();
           int jl = 1;//用于跟随记录第几几人的密码值
           do {
        
               System.out.println("请输入第"+jl+"人的密码值");
               int password0 =sr.nextInt();//挨个输入每一个人的密码值
               datatype jd = new datatype(jl,password0);//创建datatype的节点，节点内存储着每一个人和其对应的密码值
               zx.insert(jd);//将节点依次加入到约瑟夫环内
               jl++;//记录数就加一
           }while (jl <= peoples);//只要记录数不超出人数
           int b = 0;
           while (b<peoples){
        //当人数小于people数时
               datatype  c = (datatype) zx.yunxingCircular(password);//将初始密码值加进去去运行约瑟夫环
               System.out.println(c.getId());//输出c对象的id值
               password = c.getPassword();//让密码值更新，去寻找
               b++;//再次循环执行
           }
       }
    }

### 2. 什么是约瑟夫环 ###

**约瑟夫环**1问题是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码。一开始 任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。

### 3. 理解约瑟夫环 ###

#### 3.1 完成节点类和数据类定义 ####

在真正开始设计我们的约瑟夫环之前，我们需要有**节点类**和**数据类**的支撑，如下所示

下方LinkedNode就是我们的节点类

下方datatype就是我们的数据类

public class datatype {
        
        private int id;	//存放我们的id
        private int password;	//存放我们的密码
    
        public datatype() {
        	//构造无参构造函数，构造空结点
        }
    
        public datatype(int id, int password) {
         //构造函数，让其与引入的内容对接
            this.id = id;
            this.password = password;
        }
    
        public int getId() {
        	//获取我们的id值
            return id;
        }
    
        public void setId(int id) {
        	//设置我们的id值
            this.id = id;
        }
    
        public int getPassword() {
        	//获取我们的密码
            return password;
        }
    
        public void setPassword(int password) {
        	//设置我们的密码
            this.password = password;
        }
    }

#### 3.2 理解插入过程 ####

我们有两个步骤来帮助理解

1.  我们利用**伪代码**2来制作图像，如下图所示

![擅自制作][60b2faeec52f4d4f84ef900e7df3485e.png_pic_center]

1.  接下来我们利用**图像**写出代码，如下所示

public void insert(T element){
        	//用于表达插入元素进约瑟夫表的方法
           LinkedNode<T> cr = new LinkedNode<T>(element);	//设置一个新节点cr，其数据域为element
           if (rear == null){
        	//如果rear值为null，即只有一个元素
               rear = cr;	//rear此时就等于刚刚插入的新节点cr
               rear.setNext(rear);	//加入一个元素之后，rear的下一个元素还是rear，构成了循环
           }
           else {
        	//如果不是一个元素
               cr.setNext(rear.getNext());	//插入的元素的引用域就是此时尾指针指向元素的引用域中的地址，即与当时的尾结点相接
               rear.setNext(cr);	//此时尾指针指向元素的引用域为cr元素
               rear = cr;	//再把尾指针向后移一位
           }
       }

#### 3.3 理解运行过程 ####

首先，我们要知道判断循环链表为空的方法，如下所示

public boolean isEmpty() {
        	//用于判断循环链表为空的方法
    	         if (rear == null)	//根据rear是否=null来判断返回的值是true还是false
    	             return true;
    	         else
    	             return false;
    	     }

之后同样的我们还用两个步骤来继续帮助理解

1.  我们再利用伪代码来制作图像，如下图所示

![擅自制作][6c379f32418c4362a3e642218e94d4a4.png_pic_center]

1.  接下来我们利用图像写出代码，如下所示

private LinkedNode<T> rear ;	//生成一个节点,定义尾指针
    
        public CList() {
        
            rear = null;
        }
    
        public LinkedNode<T> getRear() {
        	//获取尾指针
            return rear;
        }
    
        public void setRear(LinkedNode<T> rear) {
        	//设置尾指针
            this.rear = rear;
        }
        
    	public T yunxingCircular(int m) {
        
    	        if (isEmpty()){
        	//判断是否为空
    	            throw new RuntimeException("空表");
    	        }
    	        else {
        	//如果不是空表,判断当前是否是一个元素
    	            if (rear.getNext() == rear) {
        	//如果只有一个元素
    	                LinkedNode<T> cz = rear;	//设置一个新节点，承载rear节点
    	                rear = null;	//让此时rear的值为null,即删除此处元素
    	                return cz.getData();	//返回此时用于承载节点的数据域
    	            }
    	            else {
        	//如果不是只有一个元素
    	                int a = 1;	//定义第一个个人报数为1
    	                while (a < m) {
        	//当报数上限值<该次密码值时
    	                    rear = rear.getNext();	//尾指针向后移一位
    	                    a++;	//报数值加一
    	                }
    	                LinkedNode<T> cz = rear.getNext();	//设置新节点承载rear的后一个节点
    	                rear.setNext(rear.getNext().getNext());	//让rear的引用域为之前rear的下下一个节点的地址
    	                return cz.getData();	//返回承载节点cz的数据域
    	            }
    	        }
    	    }

#### 3.4 理解更新密码值 ####

我们用文字来理解：先把运行和更新密码分开来，设立一个单独的**while循环**3，每执行一次yunxingCircular，就获取一次getpassword，并且让password等于获取到getpassword ，把新的password放入循环中。yunxingCircular和更新密码值在一个循环内，所以能够实现每次的密码值更新，如下所示

int b = 0;
    while (b<peoples){
        	//当人数小于people数时
        datatype  c = (datatype) zx.yunxingCircular(password);	//将初始密码值加进去去运行约瑟夫环
        System.out.println(c.getId());	//输出c对象的id值
        password = c.getPassword();	//让密码值更新，去寻找
        b++;	//再次循环执行
        }

#### 3.5 将更新密码值放入我们的调用类中去 ####

如下所示

public class Ysf {
        
        public static void main(String[] args) {
        
            CList zx = new CList();	//建立一个Clist的对象
            Scanner sr =  new Scanner(System.in);
            System.out.println("请输入环内人数");
            int peoples = sr.nextInt();	//确定环内总人数
            System.out.println("请输入初始密码值");
            int password  = sr.nextInt();
            int jl = 1;	//用于跟随记录第几几人的密码值
            do {
        
                System.out.println("请输入第"+jl+"人的密码值");
                int password0 =sr.nextInt();	//挨个输入每一个人的密码值
                datatype jd = new datatype(jl,password0);	//创建datatype的节点，节点内存储着每一个人和其对应的密码值
                zx.insert(jd);	//将节点依次加入到约瑟夫环内
                jl++;	//记录数就加一
            }while (jl <= peoples);	//只要记录数不超出人数
            int b = 0;
            while (b<peoples){
        	//当人数小于people数时
                datatype  c = (datatype) zx.yunxingCircular(password);	//将初始密码值加进去去运行约瑟夫环
                System.out.println(c.getId());	//输出c对象的id值
                password = c.getPassword();	//让密码值更新，去寻找
                b++;	//再次循环执行
            }
        }
    }

### 4.运行结果 ###

M的初值为20，n=7,7个人的密码依次为3,1,7,2,4,8,4。则首先出列的值为6，依次，正确的出列顺序应该为6,1,4,7,2,3,5。  
![结果截图][cc891a5088db47918f8eac203fc7de94.png_pic_center]

以上就是本文全部内容，如果它对您有帮助，请您帮我点个赞，这对我真的很重要

--------------------

1.  来自书本 ↩︎
2.  伪代码（Pseudocode）是一种非正式的，类似于英语结构的，用于描述模块结构图的语言。人们在用不同的编程语言实现同一个算法时意识到，他们的实现（注意：这里是实现，不是功能）很不同。尤其是对于那些熟练于不同编程语言的程序员要理解一个（用其他编程语言编写的程序的）功能时可能很难，因为程序语言的形式限制了程序员对程序关键部分的理解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的描述都必须与设计结构图一起出现。（来自搜狗百科：https://baike.sogou.com/v7860434.htm?fromTitle=%E4%BC%AA%E4%BB%A3%E7%A0%81） ↩︎
3.  某个出名的循环（while，循环语句，是计算机的一种基本循环模式。当满足条件时进入循环，不满足跳出。） ↩︎

[60b2faeec52f4d4f84ef900e7df3485e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/45cd2273b19b45bd947f908cdae45c8b.png
[6c379f32418c4362a3e642218e94d4a4.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/1346b3b25c8841fab7e1ac11dc5ace47.png
[cc891a5088db47918f8eac203fc7de94.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/86fcf60c890f47b99a95db077ed99353.png