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

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

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

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

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

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

以下java版的答案：

復制代碼代碼如下:

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

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

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

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

        int j= 0;               //從s開始報數(shù)，依次輸出出列人的編號
        LinkNode p = head;      //計數(shù)起點
        while(j<s-1){
            j++;
            p = p.next;
        }
        while(p.next != p){
            j = 1;
            while(j<d-1)   //計數(shù)的起始點
            {
                j++;
                p = p.next;
            }
            System.out.print(p.next.data + " "); // 輸出出列的節(jié)點號
            p.next = p.next.next;
            p = p.next;                                //不斷指向下一個節(jié)點
        }
        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);
    }
}

希望本文所述對大家的Java程序設計有所幫助。

您可能感興趣的文章: