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

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. 什么是约瑟夫环

约瑟夫¹环是一个数学的利用问题：已知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. 接下来咱们利用图像写出代码，如下所示

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

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

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

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