【java版数据结构】死亡游戏约瑟夫避免自杀问题
介绍:
有一天罗马人占领了犹太人的领地,39个犹太人与约瑟夫以及他的朋友躲
到一个山洞中,39个犹太人决定宁愿死也不要被罗马人招降,于是它们决定了一个自杀方式,41个人排成一个圆圈,第一个人从1开始报数,依次往后,如果有人报到3,那么这个人就必须自杀,然后由他的下一个人重新从1开始报数,直到所有人都自杀身亡。然而约瑟夫和他的朋友并不想遵从,于是约瑟夫要他的朋友先假装遵从,他将朋友与自己安排在第16与第31个位置,从而逃过 了这场死亡游戏。
问题转换: 41个人围坐一圈,第一个人编号为1,第二个人编号为2…第n个人编号为n
1.编号为1的人开始从1报数,报数为3的那个人退出圈
2.自退出的那个人开始的下一个人再次从1开始报数,以此类推
3.求出最后退出圈的那个人的编号
解题思路:
1.构建含有41个结点的单向循环链表,分别存储1-41的值,分别代表这41个人
2.使用计数器count,记录当前报数的值
3.遍历链表,每循环一次count++
4.假如count==3,则删除当前结点,并打印删除的结点的值,并把count重置为0
重点:用pre和before指针指向了当前结点下一个结点的上一个结点,方便做连接和删除操作
代码:
public class JosephTest {
public static void main(String[] args) {
Node first=null;
Node pre=null;
//1.创建循环链表
for (int i = 1; i <=41 ; i++) {
//创建第一个结点
if (i==1){
first = new Node(i, null);
//将当前结点变成下一个结点的上一个结点
pre=first;
continue;
}
//创建中间结点
Node newNode = new Node(i, null);
//建立连接
pre.next=newNode;
//将当前结点变成下一个结点的上一个结点
pre=newNode;
if (i==41){
//建立循环
pre.next=first;
}
}
//2.创建计数器,记录报数结果
int count=0;
//记录每次遍历拿到的结点,默认从首结点开始
Node n=first;
//记录当前结点的上一个结点,默认从首结点的上一个结点开始null
Node before=null;
//3.遍历循环链表
while(n!=n.next) {
//计数器累加
count++;
if (count == 3) {
// 如果计数到3,删除当前结点,并重置count=0
before.next = n.next;
count=0;
//打印被删除的结点
System.out.print(n.item + ",");
n = n.next;
} else {
//将当前结点变成下一个结点的上一个结点
before=n;
//如果没有计数到3,则往下移动一位
n = n.next;
}
}
//打印出剩余到最后的那个人
System.out.println(n.item);
}
//内部结点类
private static class Node<T>{
T item;
Node next;
public Node(T item, Node next) {
this.item = item;
this.next = next;
}
}
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码