乐趣区

关于程序员:Java约瑟夫环详尽分享

作者：

jiezi

在

Java_约瑟夫环详尽分享

先看代码后看分享

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环是一个数学的利用问题：已知n集体（以编号1，2，3…n别离示意）围坐在一张圆桌四周。从编号为k的人开始报数，数到m的那个人入列；他的下一个人又从1开始报数，数到m的那个人又入列；依此法则反复上来，直到圆桌四周的人全副出列。通常解决这类问题时把编号从0~n-1，最初后果+1即为原问题的解。

3. 了解约瑟夫环

3.1 实现节点类和数据类定义

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

下方LinkedNode就是咱们的节点类

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;
    }
}

下方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来制作图像，如下图所示

  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. 咱们再利用伪代码来制作图像，如下图所示

  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++;    //再次循环执行
        }
    }
}

以上就是本文全部内容，如果对你有帮忙，能够顺手点个赞，这对我真的很重要。

  1. 来自搜狗百科：https://baike.sogou.com/v7958… ↩
  2. 伪代码（Pseudocode）是一种非正式的，相似于英语构造的，用于形容模块结构图的语言。人们在用不同的编程语言实现同一个算法时意识到，他们的实现（留神：这里是实现，不是性能）很不同。尤其是对于那些纯熟于不同编程语言的程序员要了解一个（用其余编程语言编写的程序的）性能时可能很难，因为程序语言的模式限度了程序员对程序要害局部的了解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的形容都必须与设计结构图一起呈现。（来自搜狗百科：https://baike.sogou.com/v7860…） ↩
  3. 某个闻名的循环（while，循环语句，是计算机的一种根本循环模式。当满足条件时进入循环，不满足跳出。） ↩

评论

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理。

更多文章