Java中使用链表解决约瑟夫问题(丢手绢问题)

2023-04-25 21:26:14

文章目录


前言

众所周知,约瑟夫问题又名丢手绢问题,是一个经典的算法问题。这里就以丢手绢问题来模拟约瑟夫问题的大致内容。问题的大致内容是:已知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);
            }

        }
    }

总结

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

  • 作者:醉倾梦
  • 原文链接:https://dream-y.blog.csdn.net/article/details/127159914
    更新时间:2023-04-25 21:26:14