铭记:

源码下载

背景

约瑟夫问题，是一个计算机科学和数学中的问题，在计算机编程的算法中，类似问题又称为约瑟夫环，又称“丢手绢问题”
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=3，被杀掉的顺序是：3，6，4，2，5，1。

初始数据.png 第一次报数-找到3.png 第二次报数-找到6.png 第三次报数-找到4.png 第四次报数-找到2.png 第五次报数-找到5.png

解决思路

定义两个辅助变量，一个currentNode指向第一个节点，一个lastNode指向最后一个节点。它们之间的关系为：lastNode.next = currentNode。当 lastNode = currentNode 时代表只有一个节点，直接输出，退出循环。

image.png

代码

• Joseph

package com.raven.alg.s3linked;

/**
 * 约瑟夫
 */
public class Joseph {
    // head
    private Boy head;


    public Joseph() {
    }

    /**
     * 初始化数据
     */
    public Joseph(Integer maxSize) {
        Boy first = null;
        for (Integer i = 1; i <= maxSize; i++) {
            Boy boy = new Boy(i);
            if (null == this.head) {
                this.head = boy;
                first = this.head;
            } else {
                first.next = boy;
                Boy next = first.next;
                first = next;
            }
            // 新增boy的 next 执行 head
            boy.next = this.head;
        }

    }

    /**
     * 约瑟夫输出数据顺序
     *
     * @param start
     * @param step
     */
    public void run(Integer start, Integer step) {
        if (null == this.head) {
            System.out.println("约瑟夫链表为空！！！");
            return;
        }
        // 当前节点
        Boy currentNode = this.head;
        // 最后节点，lastNode.next = currentNode，当 lastNode = currentNode 时代码只有一个
        Boy lastNode = this.getLast();

        // 通过 start 来指定节点位置
        for (Integer i = 1; i < start; i++) {
            currentNode = currentNode.next;
            lastNode = lastNode.next;
        }

        while (true) {
            // 最后一个
            if (currentNode == lastNode) {
                System.out.println("输出数据：" + currentNode);
                break;
            }
            for (Integer i = 1; i < step; i++) {
                currentNode = currentNode.next;
                lastNode = lastNode.next;
            }
            // 找到数据
            System.out.println("输出数据：" + currentNode);
            currentNode = currentNode.next;
            lastNode.next = currentNode;
        }
    }

    /**
     * 输出链表
     */
    public void list() {
        if (null == this.head) {
            System.out.println("约瑟夫链表为空！！！");
            return;
        }
        Boy head = this.head;
        while (true) {
            System.out.println(head);
            if (this.head == head.next) {
                break;
            }
            head = head.next;
        }
    }

    public Boy getLast() {
        if (null == this.head) {
            System.out.println("约瑟夫链表为空！！！");
            return null;
        }
        Boy head = this.head;
        while (true) {
            if (this.head == head.next) {
                return head;
            }
            head = head.next;
        }
    }
}

class Boy {
    Integer no;
    Boy next;

    public Boy(Integer no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "no=" + no;
    }
}

• 测试代码

    /**
     * 约瑟夫问题
     */
    private static void josephTest() {
        Joseph joseph = new Joseph(3);
        joseph.list();
        joseph.run(3, 3);
    }