一文读懂约瑟夫环算法 | 原力计划

财经新闻新闻 / CSDN 来源:CSDN 发布日期:2020-05-25 热度:12C
敬告:本站部分内容转载于网络,若有侵权、侵害您的利益或其他不适宜之处,请联系我们,本站将立即删除。
联系邮箱:2876218132#qq.co m
本页标题:一文读懂约瑟夫环算法 | 原力计划
本页地址:http://www.gdbbs.cc/65000-1.html




作者 | 扬帆向海

责编 | 王晓曼

出品 | 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

 */


public class JosephCircle {

    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 = 0;

        // 循环链表当前节点的上一个节点

        Node beforeNode = null;

        // 遍历循环链表

        while (currentNode != currentNode.next) {

            count ;

            if (count == 3) {

                // 向后移动节点

                beforeNode.next = currentNode.next;

                System.out.println("出环的编号是: "   currentNode.data);

                count = 0;

                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 <= n; 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;

    }

}


/**

 * 链表节点

 */


class Node {

    // 当前存储的数据

    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


版权声明:本文为CSDN博主「扬帆向海」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/weixin_43570367/article/details/105896737
【END】

更多精彩推荐
 前端世界起争端,你是现代 Web 技术体系的坚定捍卫者吗?
新基建东风下,开发者这样抓住工业互联网风口!
15 岁黑进系统,发挑衅邮件意外获 Offer,不惑之年捐出全部财产,Twitter CEO 太牛了!
避坑!使用 Kubernetes 最易犯的 10 个错误
必读!53个Python经典面试题详解
赠书 | 1月以来 Tether 增发47亿 USDT,美元都去哪儿了?


你点的每个“在看”,我都认真当成了喜欢
论坛
  阅读原文
支持0次 | 反对0次  
  用户评论区,文明评论,做文明人!

通行证: *邮箱+888(如:123@qq.com888)