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 了解插入过程
咱们有两个步骤来帮忙了解
- 咱们利用 伪代码 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;
}之后同样的咱们还用两个步骤来持续帮忙了解
- 咱们再利用伪代码来制作图像，如下图所示
-
接下来咱们利用图像写出代码，如下所示
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++; // 再次循环执行
}
}
}以上就是本文全部内容，如果对你有帮忙，能够顺手点个赞，这对我真的很重要。
- 来自搜狗百科：https://baike.sogou.com/v7958… ↩
- 伪代码（Pseudocode）是一种非正式的，相似于英语构造的，用于形容模块结构图的语言。人们在用不同的编程语言实现同一个算法时意识到，他们的实现（留神：这里是实现，不是性能）很不同。尤其是对于那些纯熟于不同编程语言的程序员要了解一个（用其余编程语言编写的程序的）性能时可能很难，因为程序语言的模式限度了程序员对程序要害局部的了解。这样伪代码就应运而生了。伪代码提供了更多的设计信息，每一个模块的形容都必须与设计结构图一起呈现。（来自搜狗百科：https://baike.sogou.com/v7860…）↩
- 某个闻名的循环（while，循环语句，是计算机的一种根本循环模式。当满足条件时进入循环，不满足跳出。）↩