本文實例講述了Java采用循環(huán)鏈表結構求解約瑟夫問題的方法。分享給大家供大家參考。具體分析如下：
這是第一次java考試的試題，對于沒看過鏈表的同學來說就不會做，現(xiàn)在回頭看看，還真不難。
約瑟夫問題：
有n個人，其編號分別為1，2，3，…，n。這n個人按順序排成一個圈。現(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程序設計有所幫助。
