专栏首页JavaEE约瑟夫问题

约瑟夫问题

一、约瑟夫问题介绍

1、约瑟夫问题原题: n个小孩子手拉手围成一个圈,编号为k(1 <= k <= n )的人从1开始报数,报到m的那个人出列,它的下一位又从1开始报数,报到m的又出列……依此类推,直到所有人都出列,由此产生一个出队编号的序列。

2、问题分析: 根据题目的描述,很容易可以想到用单向循环链表来模拟。先构成一个有n个节点的单向循环链表,然后节点K由1开始计数,计到m时,对应的节点从链表中删除,然后再从被删除的下一个节点由1开始计数,直到所有节点都被删除掉。

单向循环链表

如上图,n等于5,假设从1号开始报数,报到2就出列,即k等于1,m等于2。那么最后出列的结果应该是:2,4,1,5,3。

二、单向环形链表的构建

1、构建思路:

  • 首先创建第一个节点,用first指针指向它,它的next指向自己,如下图:

第一个节点

  • 然后创建第二个节点,将第一个节点的next指向第二个节点,第二个节点的next指向第一个节点,如图:

第二个节点

依此类推,就可以构建出单向环形链表。遍历的时候,当节点的next等于first时,表示遍历完毕。

2、代码实现:

根据上面的分析,可以写出如下代码:

package com.zhu.study.linkedList;

/**
 * 约瑟夫问题,即单向循环链表问题
 * @author: zhu
 * @date: 2020/8/30 17:57
 */
public class Josepfu {
    public static void main(String[] args){
        CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();
        linkedlist.add(5);
        linkedlist.showNodes();
    }
}

/**
 * 单向循环链表
 */
class CircleSingleLinkedlist{
    private Node first = null;
    /**
     * 添加节点
     * @param num 需要添加的节点个数
     */
    public void add(int num){
        if (num < 1){
            throw new RuntimeException("非法参数");
        }
        Node cur = null; // 当前node
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.setNext(first); // next指向自己,构成环
                cur = first;
            } else {
                cur.setNext(node);
                node.setNext(first);
                cur = node;
            }
        }
    }

    /**
     * 遍历
     */
    public void showNodes(){
        if (first == null){ // 链表为空
            return;
        }
        Node cur = first;
        while (true){
            System.out.printf("小孩编号%d \n", cur.getNo());
            if (cur.getNext() == first){ // 遍历完毕
                break;
            } else {
                cur = cur.getNext();
            }
        }
    }   
}

/**
 * 节点内部类
 */
class Node{
    private int no; // 编号
    private Node next; // 下一个节点

    public Node(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

三、小孩出列的实现

1、思路: 先要找到开始报数的节点,用cur记录下来,比如从第k个开始数,那么cur应该指向k号节点;然后再找到cur的前一个节点,用pre记录下来;找到这两个节点后,由cur开始数(m-1)次,即cur和pre同时移动(m-1)次,此时cur就指向了要被删除的节点;打印要被删除的节点,然后将cur移动到被删除节点的下一个节点,即cur = cur.next,pre的next指向新的cur,即pre.next = cur

2、代码实现:

/**
     * 出圈,圈中共有n个人,从第k个开始,数m个开始出圈
     * @param k
     * @param m
     * @param n
     */
    public void get(int k, int m, int n){
        if (k > n || k < 1 || first == null || m > n){
            throw new IllegalArgumentException("非法参数");
        }
        // 先找到k节点,即开始报数的节点,用cur记录下来
        Node cur = first;
        for (int i = 1; i < k; i++) {
            cur = cur.getNext();
        }
        // 找到k的前一个节点,用pre记录下来
        Node pre = cur;
        while (true){
            if (pre.getNext() == cur){
                break;
            } else{
                pre = pre.getNext();
            }
        }
        // 出圈
        while (true) {
            if (pre == cur) { // 只有一个节点了
                System.out.printf("小孩编号%d\n", cur.getNo());
                break;
            }
            // cur和pre同时移动 m-1次
            for (int i = 1; i < m; i++) {
                cur = cur.getNext(); // 这个就是要出圈的节点
                pre = pre.getNext(); // 这个是要出圈节点的前一个节点
            }
            System.out.printf("小孩编号%d\n", cur.getNo());
            cur = cur.getNext();
            pre.setNext(cur);
        }
    }

调用该方法,k、m、n分别输入1、2、5,最后发现结果和上面分析的一样,打印的是2,4,1,5,3。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 二叉树详细教程 --- 请食用

    为了后续学习堆排序以及MySQL索引等知识,接下来会重温一下树这种数据结构,包括二叉树、赫夫曼树、二叉排序树(BST)、平衡二叉树(AVL)、B树和B+树。

    贪挽懒月
  • thumbnails图像处理库的使用前言:thumbnails的使用:

    贪挽懒月
  • spring整合quartz框架前言:quartz简介:spring整合quartz:总结:

    在一些项目中,往往需要定时的去执行一些任务,比如商城项目,每天0点去统计前一天的销量。那么如何实现呢,总不可能我们每天0点手动的去执行统计销量的方法吧,这时就q...

    贪挽懒月
  • 【张其中】拥有21个超级节点的EOS,背叛了区块链的去中心化理想?

    伴随着EOS主网的上线,围绕谁来启动主网、启动哪一条链作为主网展开了明争暗斗,甚至出现了诸如EOS还未上线就将面临分叉危机的舆论恐慌。这些消息确实牵动着每一个E...

    圆方圆学院
  • 完全二叉树结点个数

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/count-complete-tree-nodes 著作...

    你的益达
  • 图的割点 --《啊哈!算法》

       这个算法的关键在于:当深度优先遍历访问到顶点u时,假设图中还有顶点v是没有访问过的点,如何判断顶点v在不经过u

    用户2965768
  • 让终端支持https,移植OpenSSL和libcurl到嵌入式linux,遇到的问题总结

    从官网下载openssl源码和 libcurl源码。OpenSSL顺利交叉编译通过。

    特立独行的猫a
  • 甲骨文艰难的第二季:只有吹嘘云增长

    12月16日,甲骨文公布了其第二季度的财报,并承诺其的增长势头将会持续。这个科技巨头此次财报中关于云方面的消息是一个亮点,总收入下降、本季度净利润与去年同比下降...

    人称T客
  • Python 爬虫保存图片

    孤独的明月
  • 如何根据账户资金比例下单?

    目前vn.py所提供的示例代码都是按照固定数量下单,本文将介绍‘如何根据账户资金情况计算交易数量进而下单’。感谢‘爱茶语’以及‘王玥’在「维恩的派」论坛内的分享...

    用Python的交易员

扫码关注云+社区

领取腾讯云代金券