约瑟夫问题的描述
丢手绢，sum个小朋友做成一圈，第一次从第k个人开始数，每次数m个则数到的人出列，直到只剩下1个人。输出出圈的顺序。
约瑟夫问题的抽象
节点的信息
class Boy {
public int no;
public Boy next;
public Boy(int no) {
this.no = no;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
1环形单向链表的创建思路
代码实现
//成圈方法
public Boy circle(int sum) {
if (sum <= 1) {
System.out.println("请输入至少两个节点");
return null;
}
//head节点是Boy head = new Boy(0)
Boy temp = head;
for (int i = 1; i <= sum; i++) {
Boy boy = new Boy(i);
temp.next = boy;
//始终将最后一个节点指向第一个节点
boy.next = head.next;
//辅助指针后移
temp = temp.next;
}
return head;
}
2环节点的遍历
代码实现
//传入的参数值应该是环形链表的头节点的指向
public void displayCircle( Boy head){
if(head.next==null){
System.out.println("链表为空");
return;
}
Boy temp=head.next;
while(temp.next!=head.next){
System.out.println(temp.no);
temp=temp.next;
}
//能退出，说明temp.next==head.next，即此temp节点是最后一个节点，也要输出
System.out.println(temp.no);
}
约瑟夫问题的实现
约瑟夫问题的抽象
几点说明：
- 首先最一开始helper指针是指向第一个节点的前一个节点，也就是最后一个节点，temp节点指向第一个节点。
- 以上图为例，当从1号开始后，每数三个数，删除一个节点，此时需要将temp和helper指针移动到相应的节点上（要移动两次，因为第一个节点要数一个），然后删除操作是：先让temp向下移动一个节点temp=temp.next,然后让helper指针指向新的temp即：helper.next=temp
- 注意：此图解中是从第一个节点开始数，但是当知道该从第k个小孩开始数之后，要移动两个指针，使temp节点移动到要删除的节点，此时需要有一个for循环，来指定两个指针移动的节点数目k-1!
代码实现
/**
* @sum:表示节点总数
* @k表示从第几个节点开始数
* @m表示每次数几个
*/
public void out(int sum, int k, int m) {
if (head.next == null || sum <= 1 || k > sum) {
System.out.println("你输入的参数有误");
return;
}
//创建辅助指针。帮助小孩出圈,helper指向第一个节点的前一个节点
Boy helper = head.next;
Boy temp = head.next;
//helper指向了最后一个节点
while (true) {
if (helper.next == temp) {
break;
}
helper = helper.next;
}
//因为要从第k个节点开始数，故要将helper节点和第一个节点往后移k-1个
for (int j = 0; j < k - 1; j++) {
temp = temp.next;
helper = helper.next;
}
while (true) {
//说明只剩一个小孩
if (helper == temp) {
break;
}
//每次数m个后，temp节点指向要出圈的节点
for (int j = 0; j < m - 1; j++) {
temp = temp.next;
helper = helper.next;
}
System.out.println("节点【" + temp.no + "】出圈");
//开始执行出圈操作时，要先让temp指向下一个节点，然后让helper指向此节点就可以删除
temp = temp.next;
helper.next = temp;
}
System.out.println("最后留的节点是" + helper.next);
}
测试代码：
package com.njupt.suanfa;
/**
* Creat with IntelliJ IDEA
*
* @Auther:倔强的加瓦
* @Date:2021/07/15/18:24
* @Description:
*/
public class Josephu {
public static void main(String[] args) {
Circle circle = new Circle();
Boy boy0 = circle.circle(4);
circle.displayCircle(boy0);
circle.out(4, 1, 3);
}
}
//创建环形链表
class Circle {
Boy head = new Boy(0);
//如何创建一个节点总数为sum的环形的链表
public Boy circle(int sum) {
if (sum <= 1) {
System.out.println("请输入至少两个节点");
return null;
}
Boy temp = head;
for (int i = 1; i <= sum; i++) {
Boy boy = new Boy(i);
temp.next = boy;
//始终将最后一个节点指向第一个节点
boy.next = head.next;
//辅助指针后移
temp = temp.next;
}
//返回的是head初始头节点，故遍历时应该从下一个节点开始遍历
return head;
}
public void displayCircle(Boy head) {
if (head.next == null) {
System.out.println("链表为空");
return;
}
Boy temp = head.next;
while (temp.next != head.next) {
System.out.println(temp.no);
temp = temp.next;
}
//能退出，说明temp.next==head.next，即此temp节点是最后一个节点，也要输出
System.out.println(temp.no);
}
/**
* @sum:表示节点总数
* @k表示从第几个节点开始数
* @m表示每次数几个
*/
public void out(int sum, int k, int m) {
if (head.next == null || sum <= 1 || k > sum) {
System.out.println("你输入的参数有误");
return;
}
//创建辅助指针。帮助小孩出圈,helper指向第一个节点的前一个节点
Boy helper = head.next;
Boy temp = head.next;
//helper指向了最后一个节点
while (true) {
if (helper.next == temp) {
break;
}
helper = helper.next;
}
//因为要从第k个节点开始数，故要将helper节点和第一个节点往后移k-1个
for (int j = 0; j < k - 1; j++) {
temp = temp.next;
helper = helper.next;
}
while (true) {
//说明只剩一个小孩
if (helper == temp) {
break;
}
//每次数m个后，temp节点指向要出圈的节点
for (int j = 0; j < m - 1; j++) {
temp = temp.next;
helper = helper.next;
}
System.out.println("节点【" + temp.no + "】出圈");
//开始执行出圈操作时，要先让temp指向下一个节点，然后让helper指向此节点就可以删除
temp = temp.next;
helper.next = temp;
}
System.out.println("最后留的节点是" + helper.next);
}
}
//创建节点的信息
class Boy {
public int no;
public Boy next;
public Boy(int no) {
this.no = no;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
结果:
1
2
3
4
节点【3】出圈
节点【2】出圈
节点【4】出圈
最后留的节点是Boy{no=1}
如果感兴趣的话，可以多输入几组数哦！！！