package demo;
import java.util.*;

public class WeightedNineTailModel extends NineTailModel {
    /** Construct a model */
    public WeightedNineTailModel() {
        // Create edges
        List edges = getEdges();

        // Create a graph
        WeightedGraph graph = new WeightedGraph(edges, NUMBER_OF_NODES);

        // Obtain a shortest path tree rooted at the target node
        tree = graph.getShortestPath(511);
    }

    /** Create all edges for the graph */
    private List getEdges() {
        // Store edges
        List edges = new ArrayList();

        for(int u = 0; u .ShortestPathTree)tree).getCost(u);
    }
}

WeightedNineTailModel は、NineTailModel を拡張して、重み付き 9 尾問題をモデル化する WeightedGraph を構築します (行 10 ～ 11)。各ノード u について、getEdges() メソッドは反転したノード v を見つけ、反転の数をエッジの重みとして割り当てます (v、u) (30 行目)。 getNumberOfFlips(int u, int v) メソッドは、ノード u からノード v までのフリップ数を返します (行 38 ～ 47)。フリップの数は、 の間にある異なるセルの数です。 2 つのノード (44 行目).

WeightedNineTailModelは、ターゲット ノード 511 をルートとする ShortestPathTree を取得します (14 行目)。 tree は NineTailModel で定義された保護されたデータ フィールドであり、ShortestPathTree は Tree のサブクラスであることに注意してください。 NineTailModel で定義されたメソッドは、tree プロパティを使用します。

getNumberOfFlips(int u) メソッド (49 ～ 52 行目) は、ノード u からターゲット ノードまでのフリップ数を返します。これは、ノードからのパスのコストです。 u をターゲット ノードに送信します。このコストは、ShortestPathTree クラス (51 行目) で定義されている getCost(u) メソッドを呼び出すことで取得できます。 以下のコードは、ユーザーに初期ノードの入力を促し、ターゲット ノードに到達するまでの最小フリップ回数を表示するプログラムを提供します。

パッケージデモ; java.util.Scannerをインポートします。 パブリック クラス WeightedNineTail { public static void main(String[] args) { // ユーザーに 9 つのコインの H と T を入力するよう求める System.out.print("最初の 9 つのコイン H と T を入力してください: "); スキャナ入力 = 新しいスキャナ(System.in); 文字列 s = input.nextLine(); char[] 初期ノード = s.toCharArray(); WeightedNineTailModel モデル = new WeightedNineTailModel(); java.util.List パス = model.getShortestPath(NineTailModel.getIndex(initialNode)); System.out.println("コインを投げる手順は "); for (int i = 0; i

package demo;

import java.util.Scanner;

public class WeightedNineTail {

    public static void main(String[] args) {
        // Prompt the user to enter nine coins' Hs and Ts
        System.out.print("Enter the initial nine coins Hs and Ts: ");
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        char[] initialNode = s.toCharArray();

        WeightedNineTailModel model = new WeightedNineTailModel();
        java.util.List path = model.getShortestPath(NineTailModel.getIndex(initialNode));

        System.out.println("The steps to flip the coins are ");
        for (int i = 0; i 

コインを投げる手順は

うーん
TT

はあ

うーん
THT

TT

TT
TT

TT

フリップ回数は8回です

プログラムは、ユーザーに、
H
s と Ts を組み合わせた 9 文字の初期ノードを 8 行目の文字列として入力するよう求め、次から文字の配列を取得します。文字列 (9 行目)、モデルを作成 (11 行目)、最初のノードからターゲット ノードまでの最短パスを取得 (12 ～ 13 行目)、パス内のノードを表示します (行目) 16–17)、getNumberOfFlips を呼び出して、ターゲット ノードに到達するために必要なフリップ数を取得します (20 行目)。