[[386837]]

 Josephu問(wèn)題

設(shè)編號(hào)為1,2,....n的n個(gè)人圍坐一圈,約定編號(hào)為k(1<<k<<n)的人開(kāi)始報(bào)數(shù),數(shù)到m的那個(gè)人出列,它的下一位又從1開(kāi)始報(bào)數(shù),數(shù)到m的那個(gè)人又出列,依次類(lèi)推,知道所有人出列為止,由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列.

循環(huán)鏈表處理Josephu問(wèn)題

先構(gòu)成一個(gè)有n個(gè)節(jié)點(diǎn)的單向循環(huán)鏈表,然后由k節(jié)點(diǎn)器從1開(kāi)始計(jì)數(shù),計(jì)到m時(shí),對(duì)應(yīng)節(jié)點(diǎn)從鏈表刪除,然后再?gòu)谋粍h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)又從1開(kāi)始計(jì)數(shù),直到最后一個(gè)節(jié)點(diǎn)從鏈表中刪除.

構(gòu)建一個(gè)單向環(huán)形鏈表

1. 先創(chuàng)建第一個(gè)節(jié)點(diǎn),讓first指向該節(jié)點(diǎn),并形成環(huán).

2. 后面每創(chuàng)建一個(gè)新的節(jié)點(diǎn),就把該節(jié)點(diǎn),加入環(huán)形鏈表即可.

代碼案例

package com.structures.linkedlist; 
 
public class Josephu { 
    public static void main(String[] args) { 
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList(); 
        circleSingleLinkedList.addBoy(5); 
        circleSingleLinkedList.showBoys(); 
        circleSingleLinkedList.countBoy(1,2,5); 
 
        /* 
        小孩的編號(hào):1 
        小孩的編號(hào):2 
        小孩的編號(hào):3 
        小孩的編號(hào):4 
        小孩的編號(hào):5 
        小孩2出圈 
        小孩4出圈 
        小孩1出圈 
        小孩5出圈 
        最后留在圈中的小孩編號(hào)3 
        */ 
    } 
} 
 
//創(chuàng)建一個(gè)環(huán)形的單向鏈表 
class CircleSingleLinkedList { 
    //創(chuàng)建一個(gè)first節(jié)點(diǎn),當(dāng)前沒(méi)有編號(hào) 
    private Boy first = new Boy(-1); 
 
    //添加小孩節(jié)點(diǎn),構(gòu)建成一個(gè)環(huán)形鏈表 
    public void addBoy(int nums) { 
        if (nums < 1) { 
            System.out.println("nums 值不正確"); 
            return; 
        } 
        Boy curBoy = null; 
        //for循環(huán)創(chuàng)建環(huán)形鏈表 
        for (int i = 1; i <= nums; i++) { 
            Boy boy = new Boy(i); 
            //如果是第一個(gè)小孩 
            if (i == 1) { 
                first = boy; 
                first.setNext(first); 
                curBoy = first;//讓curBoy指向第一個(gè) 
            } else { 
                curBoy.setNext(boy); 
                boy.setNext(first); 
                curBoy = boy; 
            } 
        } 
    } 
 
    //遍歷當(dāng)前環(huán)形鏈表 
    public void showBoys() { 
        if (first.getNext() == null) { 
            System.out.println("沒(méi)有任何小孩~~"); 
            return; 
        } 
        Boy temp = first; 
        while (true) { 
            System.out.println("小孩的編號(hào):" + temp.getNo()); 
            if (temp.getNext() == first) { 
                break; 
            } 
            temp = temp.getNext(); 
        } 
    } 
 
    /** 
     * 根據(jù)用戶(hù)輸入,計(jì)算小孩出圈順序 
     * 
     * @param startNo  表示從第幾個(gè)小孩開(kāi)始計(jì)數(shù) 
     * @param countNum 表示數(shù)幾下 
     * @param nums     表示多少個(gè)小孩在圈中 
     */ 
    public void countBoy(int startNo, int countNum, int nums) { 
        //先進(jìn)行數(shù)據(jù)校驗(yàn) 
        if (first == null || startNo < 1 || startNo > nums) { 
            System.out.println("參數(shù)輸入有誤,請(qǐng)重新輸入"); 
            return; 
        } 
        //創(chuàng)建一個(gè)輔助指針,幫助完成小孩出圈 
        Boy helper = first; 
        //讓helper指向環(huán)形鏈表的最后節(jié)點(diǎn) 
        while (helper.getNext() != first) { 
            helper = helper.getNext(); 
        } 
        //報(bào)數(shù)前,先讓helper和first移動(dòng),移動(dòng)k-1次,這樣first定位到開(kāi)始節(jié)點(diǎn),helper緊接著first 
        for (int i = 0; i < startNo - 1; i++) { 
            first = first.getNext(); 
            helper = helper.getNext(); 
        } 
        //報(bào)數(shù)時(shí),讓first和helper指針同時(shí)移動(dòng),然后出圈 
        while (true) { 
            //當(dāng)圈中只有一個(gè)節(jié)點(diǎn) 
            if (helper == first) { 
                break; 
            } 
            //讓first和helper指針同時(shí)移動(dòng)countNum - 1次 
            for (int i = 0; i < countNum - 1; i++) { 
                first = first.getNext(); 
                helper = helper.getNext(); 
            } 
            //此時(shí)first節(jié)點(diǎn)就是小孩要出圈的節(jié)點(diǎn) 
            System.out.printf("小孩%d出圈\n", first.getNo()); 
            first = first.getNext(); 
            helper.setNext(first); 
        } 
        System.out.printf("最后留在圈中的小孩編號(hào)%d \n", first.getNo()); 
    } 
} 
 
//創(chuàng)建一個(gè)Boy類(lèi),表示節(jié)點(diǎn) 
class Boy { 
    private int no;//編號(hào) 
    private Boy next;//指向下一個(gè)節(jié)點(diǎn),默認(rèn)null 
 
    public Boy(int no) { 
        this.no = no; 
    } 
 
    public int getNo() { 
        return no; 
    } 
 
    public void setNo(int no) { 
        this.no = no; 
    } 
 
    public Boy getNext() { 
        return next; 
    } 
 
    public void setNext(Boy next) { 
        this.next = next; 
    } 
} 

 【編輯推薦】