约瑟夫问题（GIF图解）

科技前沿 • 2025-03-25 11:50 • 阅读 36

大家好，我是讯享网，很高兴认识大家。

约瑟夫问题

据说著名犹太历史学家Josephus有过一下的故事：
在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲在一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3个人该人必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而Josephus和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在了第16个与第31个位置，于是逃过了这场死亡游戏。

讯享网

分析：

在这里分析的时候，图中所给的人数为20，对于原题人数增加但思考方式依然不变.
在这里插入图片描述
如上动图所示，首先我们画20个圆代替人的位置，由题意可得每3个人，则第3个人自杀，也就是如上图所示，每3个圆把第3个圆去掉.依次这样，最终只剩下2个圆，这2个圆的位置也就是人存活的位置.
下面我们叙述一下用链表来实现一圈圆和找位置的过程.
首先创建一个链表将尾指针指向头，这样就形成了一个圈，然后我们创建一个指针 p 从头开始走，找到要删除圆的位置的前一个位置，然后把要删的圆（结点）暂存一下，以便于指针 p 的移动.（如下图所示）
在这里插入图片描述
如上图，首先移动 p 指针到 2 位置时，将 3 号删除，之后指针 p 更新到 4 号位置将重新找下一个3个圆的最后一个圆的前一个位置，如此循环即可.

代码实现：

public class JosephusLoop { 
    private Node head; //定义头指针 private Node rear; //定义尾指针 private int size; //创建一个给定圆数量围成的圆圈 public JosephusLoop(int count){ 
    head=new Node(1,null); //先把第一个圆创建出来 rear=head; rear.next=head; for(int i=2;i<=count;i++){ 
    //创建剩下的圆 用尾插的方式 rear.next=new Node(i,rear.next); rear=rear.next; } size=count; } //获取最后的位置 public List<Integer> getSurvivePosition(){ 
    ArrayList<Integer> list=new ArrayList<>(); Node p=head; //创建一个p指针 while(size>2){ 
    p=p.next; Node del=p.next; //创建一个del指针 暂存要删除的结点 p.next=del.next; p=p.next; //更新p指针的位置 size--; } list.addLast(p.position); //将p所指位置的数据加入到链表中 list.addLast(p.next.position); //将p所指位置的下一个位置的数据加入到链表中 return list; } //一个结点内部类 private class Node{ 
    int position; Node next; public Node(){ 
   } //无参构造函数 public Node(int position,Node next){ 
    this.position=position; this.next=next; } } public static void main(String[] args) { 
    JosephusLoop jp=new JosephusLoop(20); //创建jp对象 传入20个圆 List<Integer> list=jp.getSurvivePosition(); //获取链表的元素 即可 System.out.println(list); } }

讯享网

约瑟夫问题（GIF图解）

约瑟夫问题

分析：

代码实现：

相关推荐