本文實例講述了Java採用循環鍊錶結構來求解約瑟夫問題的方法。分享給大家供大家參考。具體分析如下:
這是第一次java考試的試題,對於沒看過鍊錶的同學來說就不會做,現在回頭看看,還真不難。
約瑟夫問題:
有n個人,其編號分別為1,2,3,…,n。這n個人按順序排成一個圈。現在給定s和d,從第s個人開始從1依次報數,數到d的人出列,然後又從下一個人開始又從1開始依次報數,數到d的人又出列,如此循環,直到最後所有人出列為止。要求定義一個節點類,採用循環鍊錶結構來求解約瑟夫問題。
以下java版的答案:
複製程式碼如下:import java.util.Scanner;
public class LinkNode { //單向鍊錶的節點類
public int data; //存放節點值
public LinkNode next; //存放節點值的引用
public LinkNode(int k){ //建構方法,值為k的節點
data = k;
next= null;
}
}
class Josephus{
public static void printJosephus(int n,int s,int d){
int i=1; //建立長為n的循環列表
LinkNode q,tail;
LinkNode head = new LinkNode(i);
head.next = head ;
tail = head; //第一個節點,尾巴和頭在一起
while(i<n){
i++;
q = new LinkNode(i); //增加一個新節點
q.next = head ; //節點的引用指向頭
tail.next = q; //最後一個元素的引用指向了q
tail = q; //那麼最後一個元素就是q
}
int j= 0; //從s開始報數,依序輸出出列人的編號
LinkNode p = head; //計數起點
while(j<s-1){
j++;
p = p.next;
}
while(p.next != p){
j = 1;
while(j<d-1) //計數的起始點
{
j++;
p = p.next;
}
System.out.print(p.next.data + " "); // 輸出出列的節點號
p.next = p.next.next;
p = p.next; //不斷指向下一個節點
}
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程式設計有幫助。