0

再帰ツリーの描画方法を理解しようとしています 例:ここから撮影

ここに画像の説明を入力

右側には、特定の問題の再帰ツリーが表示されます。

たとえば、この関数の再帰ツリーの構築を開始する方法についてのアイデアは、ターゲットの量といくつかの重み (たとえば、1,2,3) を指定すると、重みで測定する昔ながらの方法を使用してターゲットを計算できる場合に返されます。

この問題に対して行う必要がある基本的な観察は、ベクトル内の各重量が次のいずれかである可能性があるということです。完全にバランスを崩して

再帰がどのように機能するかをよりよく理解するために、鉛筆と紙だけでプログラムでそれを行う方法を探していません。

static Boolean IsMeasurable3(int left, int right, ArrayList<Integer> weights,int weightIndex) {

    //Debug
    //System.out.println("Left is " + left + " Right is " + right);

    if (Math.abs(left - right) == 0){
    System.out.println("Found it! Left is " + left + " Right is " + right);
        return true;
    }

    if (weightIndex >= weights.size())
        return false;



        return IsMeasurable3(left + weights.get(weightIndex), right, weights,weightIndex + 1)
                || IsMeasurable3(left, right + weights.get(weightIndex), weights,weightIndex + 1)
                || IsMeasurable3(left, right, weights,weightIndex + 1);

}

この問題と入力重み 1、2、3 およびターゲット 5 の場合、出力は次のようになります。

Left is 5 Right is 0
Left is 6 Right is 0
Left is 8 Right is 0
Left is 11 Right is 0
Left is 8 Right is 3
Left is 8 Right is 0
Left is 6 Right is 2
Left is 9 Right is 2
Left is 6 Right is 5
Left is 6 Right is 2
Left is 6 Right is 0
Left is 9 Right is 0
Left is 6 Right is 3
Left is 6 Right is 0
Left is 5 Right is 1
Left is 7 Right is 1
Left is 10 Right is 1
Left is 7 Right is 4
Left is 7 Right is 1
Left is 5 Right is 3
Left is 8 Right is 3
Left is 5 Right is 6
Left is 5 Right is 3
Left is 5 Right is 1
Left is 8 Right is 1
Left is 5 Right is 4
Left is 5 Right is 1
Left is 5 Right is 0
Left is 7 Right is 0
Left is 10 Right is 0
Left is 7 Right is 3
Left is 7 Right is 0
Left is 5 Right is 2
Left is 8 Right is 2
Left is 5 Right is 5
Found it! Left is 5 Right is 5

ツリーを構築することをどのように考え始めますか? いつ幅を大きくし、いつ高さを..?

4

1 に答える 1

2

ツリーは、再帰呼び出しごとに高さが増加します。あなたの例では、呼び出しごとIsMeasurable3に高さが増加します。

再帰関数の同じ呼び出しから複数の呼び出しが行われると、ツリーの幅が広がります。あなたの例でIsMeasurable3は、3回呼び出されるため、ツリーには再帰レベルまで最大3つのブランチがあります。

于 2012-11-18T14:45:55.417 に答える