快捷導(dǎo)航

Java采用循環(huán)鏈表結(jié)構(gòu)求解約瑟夫問題

更新時(shí)間：2014年12月08日 10:09:24 投稿：shichen2014

這篇文章主要介紹了Java采用循環(huán)鏈表結(jié)構(gòu)求解約瑟夫問題的解決方法,是很多Java面試環(huán)節(jié)都會(huì)遇到的經(jīng)典考題,這里詳細(xì)給出了約瑟夫問題的原理及Java解決方法,是非常經(jīng)典的應(yīng)用實(shí)例,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

本文實(shí)例講述了Java采用循環(huán)鏈表結(jié)構(gòu)求解約瑟夫問題的方法。分享給大家供大家參考。具體分析如下：

這是第一次java考試的試題，對(duì)于沒看過鏈表的同學(xué)來說就不會(huì)做，現(xiàn)在回頭看看，還真不難。

約瑟夫問題：
有n個(gè)人，其編號(hào)分別為1，2，3，…，n。這n個(gè)人按順序排成一個(gè)圈?，F(xiàn)在給定s和d，從第s個(gè)人開始從1依次報(bào)數(shù)，數(shù)到d的人出列，然后又從下一個(gè)人開始又從1開始依次報(bào)數(shù)，數(shù)到d的人又出列，如此循環(huán)，直到最后所有人出列為止。要求定義一個(gè)節(jié)點(diǎn)類，采用循環(huán)鏈表結(jié)構(gòu)求解約瑟夫問題。

以下java版的答案：

復(fù)制代碼代碼如下:

import java.util.Scanner;
public class LinkNode {              //單向鏈表的節(jié)點(diǎn)類
    public int data;                 //存放節(jié)點(diǎn)值
    public LinkNode next;            //存放節(jié)點(diǎn)值的引用

    public LinkNode(int k){         //構(gòu)造方法，值為k的節(jié)點(diǎn)
        data = k;
        next= null;
    }
}
class Josephus{
    public static void printJosephus(int n,int s,int d){
        int i=1;                    //創(chuàng)建長(zhǎng)為n的循環(huán)列表
        LinkNode q,tail;

        LinkNode head = new LinkNode(i);
        head.next = head ;
        tail = head;             //第一個(gè)節(jié)點(diǎn)，尾巴和頭在一起

        while(i<n){
            i++;
            q = new LinkNode(i);    //增加一個(gè)新節(jié)點(diǎn)
            q.next = head ;        //節(jié)點(diǎn)的引用指向頭
            tail.next = q;            //最后一個(gè)元素的引用指向了q
            tail = q;              //那么最后一個(gè)元素就是q
        }

        int j= 0;               //從s開始報(bào)數(shù)，依次輸出出列人的編號(hào)
        LinkNode p = head;      //計(jì)數(shù)起點(diǎn)
        while(j<s-1){
            j++;
            p = p.next;
        }
        while(p.next != p){
            j = 1;
            while(j<d-1)   //計(jì)數(shù)的起始點(diǎn)
            {
                j++;
                p = p.next;
            }
            System.out.print(p.next.data + " "); // 輸出出列的節(jié)點(diǎn)號(hào)
            p.next = p.next.next;
            p = p.next;                                //不斷指向下一個(gè)節(jié)點(diǎn)
        }
        System.out.print(p.data);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int a = input.nextInt();
        int b = input.nextInt();
        Josephus.printJosephus(n, a, b);
    }
}

希望本文所述對(duì)大家的Java程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: