この記事の例では、Java が循環リンク リスト構造を使用して Joseph の問題を解決する方法を説明します。皆さんの参考に共有してください。具体的な分析は次のとおりです。
これは、リンクされたリストを見たことがない学生にとっては、最初の Java 試験の問題ですが、今振り返ってみると、実際には難しいことではありません。
ジョセフの質問:
n 人の人がいます。その番号は 1、2、3、...、n です。このn人を順番に円形に並べます。 sとdが与えられたとして、s人目から順番に1から数え始めると、dまで数えた人が列から出てきて、次の人から順番に1から数えて、その人が列から出てきます。 d までのカウントが再びキューから出てきます。このサイクルは、最終的に全員が出てくるまで続きます。 Joseph の問題を解決するには、ノード クラスを定義し、循環リンク リスト構造を使用する必要があります。
次の Java バージョンの回答:
次のようにコードをコピーします。
public class LinkNode { //一方向リンクリストのノードクラス
public int データ; //ストレージノード値;
public LinkNode next; //ノード値のストレージ参照;
public LinkNode(int k){ //構築メソッド、値 k を持つノード
データ = k;
次 = null;
}
}
クラスヨセフス{
public static void printJosephus(int n,int s,int d){
int i=1; //長さ n の循環リストを作成します。
LinkNode q,tail;
LinkNode ヘッド = 新しい LinkNode(i);
head.next = 頭;
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) {
スキャナ入力 = 新しいスキャナ(System.in);
int n = input.nextInt();
int a = input.nextInt();
int b = input.nextInt();
Josephus.printJosephus(n, a, b);
}
}
この記事が皆さんの Java プログラミングに役立つことを願っています。