單向循環連結清單求解約瑟夫環

問題後面的小故事:

       公元66年，約瑟夫參與上司了猶太同胞反抗羅馬統治的起義，起義失敗，他和一些甯死不降的起義者被困于一個山洞之中。羅馬将軍派人來勸降，他主張投降，其餘的人不答應，并以死相逼。最後，約瑟夫提議，與其死在自己的手上，不如死在彼此的手上。他提出了從第一個人開始，每數到三，則第三個人自殺，從下一個人開始繼續從1開始數，每數到三，則第三個人繼續自殺…..直到所有人都死亡為之，就這樣執行下去，最後隻有他和另外一人出了山洞投降。這個問題被後來人們稱為約瑟夫環.

求解思路:

       采用單向循環連結清單，每個人代表一個結點，假設1号是頭結點，從頭結點開始數，數到3，則先列印第3個人的編号，繼續向下數，直到所有的結點都被周遊一遍，循環結束。

輸入輸出描述：

       假設輸入 n 個人， 數到第 m 個人，删除第m個人,

如 n = 41, m = 3, 則删除順序為 3 -> 6 -> 9 -> 12 -> 15…..

結點代碼：

public class Node {
    int c;
    Node next;

    public Node() {
    }

    public Node(int c, Node next) {
        super();
        this.c = c;
        this.next = next;
    }
}
           

主函數代碼:

/*
* @Description: 求解約瑟夫環
*               假設有 n 個結點,從第一個結點開始數，每數到m,第m個人  *            出列(這裡就先列印第m個結點的值,再删除m結點)
*               使用單向循環連結清單
*               最後輸出被删除的先後順序,即m的删除順序
*/
public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n;  // 結點個數
        int m;  // 第m出列
        System.out.print("Input N and M:");
        n = sc.nextInt();
        m = sc.nextInt();

        //聲明n個結點
        Node[] node = new Node[n];
        //為每個結點指派
        for(int i=; i<node.length; i++){
            node[i] = new Node(i+, null);
        }
        //将第一個結點指向下一個結點
        for(int i=; i<node.length-; i++){
            node[i].next = node[i+];
        }
        //将最後一個結點指向第一個結點,構成一個環
        node[node.length-].next = node[];

        //先将p指向第一個結點, p在以後表示要删除結點的前驅結點
        Node p = node[];

        int k = ; //控制輸入的一行的個數

        // 隻要還有結點,就繼續循環,即結點p自己指向自己，循環結束
        while(p.next != p ){
            //找到被删除結點的前驅結點
            for(int i=; i<m-; i++){
                p = p.next;
            }
            //每輸出6個元素輸出一個換行
            if (k %  == ){
                System.out.format("\n %02d - ", p.next.c);
            }else{
                System.out.format(" %02d - ", p.next.c);
            }
            k++;
            //删除 p的後繼結點, 即被出列的結點
            Node s = p.next;
            p.next = s.next;
            s.next = null;

            //最後使p指向開始數的第一個結點,即被删除結點的下一結點
            p = p.next;  
        }
        //輸出最後一個結點
        System.out.format(" %02d", p.c);

        sc.close();//關閉輸入流
    }
}   
           

運作效果圖:

源碼下載下傳:

約瑟夫環源碼下載下傳(點選我即可下載下傳)