用链表解决约瑟夫环问题_约瑟夫问题链表解决法

文章目录

前言

众所周知，约瑟夫问题又名丢手绢问题，是一个经典的算法问题。这里就以丢手绢问题来模拟约瑟夫问题的大致内容。问题的大致内容是：已知n个小孩（以编号1，2，3…..，n)围成一个圈。从编号为k的人开始报数，数到m的那个人出列，出列之后，剩下的人又继续报数，同时他的下一个人又从1开始报数，数到m的那个人又出列，剩下的人又继续报数。以此规律重复下去，直到小孩全部出列。

如图，这里以6个小孩作为例子说明问题：这里有6个小孩围成一个圈

当k=1，m=3时，表示从第一个小孩开始报数，数到第三个小孩时，小孩出列。

当第三个小孩出列之后，队伍中只剩下5个小孩，同时，此时从4号小孩开始报数，数到3时，第6个孩子出列。

六号孩子出列之后，场上仅剩下1,2,4,5号小孩，他们四个小孩也进行同样的操作。

以此类推，当最后一个小孩出列时，游戏结束。

一、思路分析

在本篇文章中，我们将使用Java语言中的链表来解决约瑟夫问题（丢手绢问题）。

由上述所知，该文章一共有n个小孩，从第k个小孩开始报数，报到第m个小孩时小孩出列，剩下的小孩接着报数。在上方的图解中，我们可以清晰的看出，这些小孩围在一起形成了一个环，当数到第n个小孩时，该环又重新轮回到第1个小孩处，继续报数。在这里，我们可以制作一个环形链表来解决这个问题。我们把这个环叫做约瑟夫环，以下是实现的图解：

在这里，我们可以利用两个中间变量来进行问题的解决。其中，i变量是从1开始，表示当前报数报的是多少，all则表示当前已经出列了多少个小孩，如果小孩都出列完成，则程序运行结束。

在这里，我们使用chird来代表小孩，当开始数数时，从第k个小孩开始数，这里就是从第1个小孩开始，当1号小孩报数之后，由2号小孩进行报数，此时2号小孩报2，则中间变量i就等于2。

当报到第三个小孩时，3号小孩报3，此时与m相同，则3号小孩出列，当循环到4号小孩时，i又等于1，重新在环中继续报数

在这个过程中，chird代表当前正在报数的小孩。但是在实际编写环形链表的过程中，会出现一个“头小孩”的问题，我们要将报第一个数的小孩当做头小孩，以这一个小孩为基准，利用i这个中间变量来获取第i个小孩，从而解决问题。当i=m时，第i个小孩出列，此时将出列之后的下一个小孩重新当做“头小孩”，以此来进行环形链表的获取。

二、代码实现

1.Chird类的实现

为模拟小孩，在该类中我们重新创建了一个新类Chird来表示小孩，该小孩拥有id，以及下一个小孩的属性next，拥有一个构造函数来new一个小孩，拥有一个toString方法来对小孩信息进行打印，代码如下：

class Chird {
    int id;
    Chird next;
    public Chird(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "小孩id = "+this.id;
    }
}

2.链表的创建

在该类中，我们创建了一个单向链表新类，名为ChirdLinkedList，在这个类中，我们首先要定义一个“虚拟的头小孩”（头指针），有了这个“虚拟的头小孩”（头指针）之后，我们才可获取到第一个小孩。同时，我们在链表中实现了将单向链表转换为环形链表，已经链表的增删查功能。代码如下：

class ChirdLinkedList {
    Chird head = new Chird(0);
    //将链表更改为环形链表
    public void toCircularLinked() {
        Chird temp = head;
        if (temp.next == null) {
            return;
        }
        while (true) {
            if (temp.next == null) {
                temp.next = head.next;
                break;
            }
            temp = temp.next;
        }
    }
    // 更改头小孩
    public void changeHeadNext(Chird chird) {
        head.next = chird;
    }
    // 获取第i个小孩（相对于头小孩）
    public Chird getChird(int num) {
        if (num < 1) {
            return null;
        }
        int i = 0;
        Chird temp = head.next;
        while (temp != null) {
            i++;
            if (i == num) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
    //新增小孩
    public void addChird(int num) {
        Chird temp = head;
        while (true) {
            if (temp.next == null) {
                for (int i = 1; i <= num; i++) {
                    Chird chird = new Chird(i);
                    temp.next = chird;
                    temp = temp.next;
                }
                break;
            }
            else {
                temp = temp.next;
            }
        }
    }
    //删除小孩
    public void deleteChird(int num) {
        if (num < 1) {
            return;
        }
        int i = 0;
        Chird temp = head;
        while (temp.next != null) {
            i++;
            if (i == num) {
                if (temp.next == head.next) {
                    head.next = temp.next.next;
                }
                temp.next = temp.next.next;
                return;
            }
            temp = temp.next;
        }
        return;
    }
}

3.功能的实现

在实现了小孩和链表之后，我们就可以利用此对功能进行实现了。

public static void main(String[] args) {
        solveJosephQuestion(6,2,3);
    }

    public static void solveJosephQuestion(int n, int k , int m) {
        ChirdLinkedList chirdLinkedList = new ChirdLinkedList();
        chirdLinkedList.addChird(n);
        chirdLinkedList.toCircularLinked();
        Chird chird = chirdLinkedList.getChird(k);
        //更改第k个小孩为头小孩
        chirdLinkedList.changeHeadNext(chird);
        int i = 1;
        int all = 0;
        while (true) {
            if (i == m) {
                //输出出列的小孩名称
                System.out.println(chird.toString());
                all ++;
                //删除小孩并更改头小孩
                Chird chird2 = chirdLinkedList.getChird(m+1);
                chirdLinkedList.deleteChird(m);
                chirdLinkedList.changeHeadNext(chird2);
                //i归零
                i=0;
                //如果小孩总数等于出列小孩总数则退出循环
                if (n==all) {
                    return;
                }
            } else {
                //i累加
                i++;
                chird = chirdLinkedList.getChird(i);
            }

        }
    }

总结

以上就是利用环形链表实现约瑟夫问题（丢手绢问题）的过程，在这个过程中主要创建了小孩类和链表类，分别实现了不同的功能，最后在函数中解决了约瑟夫问题（丢手绢问题），在实际编程的过程中还是要非常注意逻辑关系和编写顺序，如果中间的一些关键步骤顺序错了也会导致最后的结果错误喔~

今天的文章用链表解决约瑟夫环问题_约瑟夫问题链表解决法分享到此就结束了，感谢您的阅读。