作者 | 扬帆向海
责编 | 王晓曼
出品 | CSDN博客
问题描述
约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。又称“丢手绢问题”)
据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从。
首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。
问题是,给定了和,一开始要站在什么地方才能避免被处决?Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。
问题分析
这个问题可以这样来看,有N个人围成一圈,第一个人从1开始报数,报到3的出圈被杀掉;下一个人接着从1开始报数……这样循环反复,直到剩下最后两个人,求出最后两个人的位置。
实现逻辑
1. 构建一个单向循环链表(链表的尾部指向开头)
① 首先创建循环链表的头节点,让head指向该节点,并形成环形;
② 之后每当创建一个新的节点,就把该节点添加到已有的环形链表中。
2. 遍历单向的循环链表
在此遍历中,当有节点被删除以后,就要向后移动节点。
注意:
当当前节点的值等于当前节点的下一个节点的值的时候,循环结束!
代码实现
package com.study.algorithm;
import java.util.Scanner;
/**
* @Description: 使用循环链表解决约瑟夫环问题
* @Author: 扬帆向海
* @Date: Created in 2020/5/2
*/
publicclassJosephCircle{
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("请输入总人数N(N>=2):");
int n = scanner.nextInt();
if (n 2) {
System.out.println("您好!请确保输入的人数大于等于 2");
return;
}
// 构建链表并获取头节点,把头节点赋值给currentNode
Node currentNode = buildData(n);
// 用来计数
int count = ;
// 循环链表当前节点的上一个节点
Node beforeNode = null;
// 遍历循环链表
while (currentNode != currentNode.next) {
count++;
if (count == 3) {
// 向后移动节点
beforeNode.next = currentNode.next;
System.out.println("出环的编号是: " + currentNode.data);
count = ;
currentNode = currentNode.next;
} else { // 向后移动节点
beforeNode = currentNode;
currentNode = currentNode.next;
}
// 表示只有两个节点了,不再进行出环操作
if (beforeNode.data == currentNode.next.data) {
break;// 跳出循环
}
}
// 输出最后留在环中的编号
System.out.println("最后留在环中的编号是: " + currentNode.data + "," + currentNode.next.data);
}
/**
* 构建单向循环链表
*
* @param n 人数
* @return 返回头节点
*/
private static Node buildData(int n) {
// 循环链表的头节点
Node head = null;
// 循环链表当前节点的前一个节点
Node prev = null;
for (int i = 1; i
Node newNode = new Node(i);
// 如果是第一个节点
if (i == 1) {
head = newNode;
prev = head;
// 跳出当前循环,进行下一次循环
continue;
}
// 如果不是第一个节点
prev.next = newNode;
prev = newNode;
// 如果是最后一个节点
if (i == n) {
prev.next = head;
}
}
return head;
}
}
/**
* 链表节点
*/
classNode{
// 当前存储的数据
int data;
// 当前节点的下一个节点
Node next;
public Node(int data) {
this.data = data;
}
}
测试结果:
请输入总人数:41
出环的编号是:3
出环的编号是:6
出环的编号是:9
出环的编号是:12
出环的编号是:15
出环的编号是:18
出环的编号是:21
出环的编号是:24
出环的编号是:27
出环的编号是:30
出环的编号是:33
出环的编号是:36
出环的编号是:39
出环的编号是:1
出环的编号是:5
出环的编号是:10
出环的编号是:14
出环的编号是:19
出环的编号是:23
出环的编号是:28
出环的编号是:32
出环的编号是:37
出环的编号是:41
出环的编号是:7
出环的编号是:13
出环的编号是:20
出环的编号是:26
出环的编号是:34
出环的编号是:40
出环的编号是:8
出环的编号是:17
出环的编号是:29
出环的编号是:38
出环的编号是:11
出环的编号是:25
出环的编号是:2
出环的编号是:22
出环的编号是:4
出环的编号是:35
最后留在环中的编号是:16,31
新基建东风下,开发者这样抓住工业互联网风口!
15 岁黑进系统,发挑衅邮件意外获 Offer,不惑之年捐出全部财产,Twitter CEO 太牛了!
避坑!使用 Kubernetes 最易犯的 10 个错误
4000520066 欢迎批评指正
All Rights Reserved 新浪公司 版权所有