環形連結清單——約瑟夫問題

問題描述

Josephu問題：設編号為1，2，3…n的n個人圍坐成一圈，約定編号為k的人從1開始報數，數到m的那個人出列，他的下一位從1開始報數，數到m那個人又出列，直到所有人都出列為止，由此産生一個出隊列編号的序号。

解決方法

1. 建立一個輔助指針helper，指向頭指針的前一個節點
2. 當小孩報數的時候，first指針和helper指針向後移 m-1 位

3. 移動後進行出列，先将first指針後移一位，然後連接配接help指針

      first = first.next

      helper.next = first

代碼部分

  需要實作的功能

• 建立環形連結清單，通過輸入數字n，确定要建立多少個人的環形連結清單
• 周遊列印環形連結清單
• 實作約瑟夫算法，輸入m确定數幾下出列

n=5（五個人）

k=1（從第一個人開始數）

m=2（數兩下就出列）

package LinkList;

public class Josephu {

    public static void main(String[] args) {
        Josephu jDemo = new Josephu();
        jDemo.josephu(5,1,2);
    }
    
    /**
     * 約瑟夫算法
     * @param n 環形連結清單中有多少小孩
     * @param m 數幾下進行出圈
     * @param k 從第幾個小孩開始報數
     */
    public void josephu(int n, int k, int m)
    {
        CircleSimpleLinkList csl = new CircleSimpleLinkList();
        Boy first = csl.CreateCircleLinkList(n);
        Boy helper = csl.end;
        //在開始之前需要移動到開始位置
        for(int i=0; i<k-1; i++)
        {
            first = first.next;
            helper = helper.next;
        }
        //數數到要出圈的男孩那,進行出圈
        while(true)
        {
            if(helper == first)//到了最後一個人
            {
                break;
            }
            for(int i=0; i<m-1; i++)
            {
                first = first.next;
                helper = helper.next;
            }
            //進行出圈
            System.out.print(first.getNo() + "->");
            first = first.next;
            helper.next = first;
        }
        //輸出最後一個男孩
        System.out.println(first.getNo());
    }
}

class CircleSimpleLinkList{
    public Boy head = null;//指向頭部
    public Boy end = null;//指向尾部
    //建立環形連結清單
    public Boy CreateCircleLinkList(int no)
    {
        for(int i = 1; i <= no; i++)
        {
            Boy boy = new Boy(i);
            //判斷是否為頭節點
            if(i == 1)
            {
                head = boy;
                end = boy;
                end.next = head;
            }else //不為頭
            {
                end.next = boy;
                end = boy;
                end.next = head;
            }
        }
        return head;
    }
    //周遊循環連結清單
    public void showCircleLinkList(Boy head)
    {
        Boy sign = head;//标記
        do{
            System.out.print(sign.getNo() + "->");
            sign = sign.next;
        }while(sign != head);
    }
}

class Boy{
    private int No;
    protected Boy next;
    public Boy(int no)
    {
        this.No = no;
    }
    public int getNo() {
        return No;
    }
}