0

我试图了解如何绘制递归树，例如：取自这里

在此处输入图像描述

在右侧，您可以看到特定问题的递归树。

任何如何开始构建递归树的想法，例如对于这个函数，它给出了一个目标数量和一些权重（例如 1、2、3），如果可以使用带有权重的旧式测量来计算目标，它会返回。

对于这个问题，您需要做的基本观察是向量中的每个重量都可以是： 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 次，因此树上最多有三个分支到递归级别。

于 2012-11-18T14:45:55.417 回答