0

我需要了解这种递归是如何工作的，我了解简单的递归示例，但更高级的递归示例很难。甚至认为只有两行代码我遇到了问题……return语句本身。我只是对它的工作原理持空白，尤其是 and/or 运算符。任何见解都非常受欢迎。

      bool subsetSumExists(Set<int> & set, int target) {
      if (set.isEmpty()) {
         return target == 0;
      } else {
         int element = set.first();
         Set<int> rest = set - element;
         return subsetSumExists(rest, target)
             || subsetSumExists(rest, target - element);
         } 
      }
4

6 回答 6

5

递归代码通常与归约的概念相结合。一般来说，归约是一种通过某种变换将未知问题归结为已知问题的方法。

让我们看一下您的代码。您需要确定是否可以从输入数据集的元素构造给定的目标总和。如果数据集为空，则除了将目标总和与 0 进行比较外，别无他法。

否则，让我们应用减少。如果我们从集合中选择一个数字，实际上可能有 2 种可能性 - 选择的数字参与您正在寻求的总和或不参与。这里没有其他可能性（涵盖所有可能性非常重要！）。事实上，选择哪个数据元素并不重要，只要您能涵盖剩余数据的所有可能性即可。

第一种情况：数字不参与求和。我们可以将问题减少到一个较小的问题，数据集没有被检查的元素和相同的目标总和。

第二种情况：数字参与求和。我们可以将问题减少到一个较小的问题，数据集没有被检查的元素，并且请求的总和减少了数字的值。

请注意，此时您不知道这些情况是否属实。您只需继续减少它们，直到您找到可以确定答案的微不足道的空案例。

如果这两种情况中的任何一种都是正确的，那么原始问题的答案就是正确的。这正是 operator||所做的 - 如果它的任何操作数（两种情况的结果）为真，它将产生真。

于 2012-11-30T09:52:08.887 回答
3

||是逻辑或。它从左到右进行评估并短路。

这意味着在表达式A || B中，A首先评估。如果是true，则整个表达式是true并且不进行进一步的评估。如果A是false,B被评估并且表达式得到 的值B。

在您的示例中，A是“尝试在不使用集合中的第一个元素的情况下获得相同的总和”。B是“使用集合中的第一个元素，这会减少总和，并尝试与元素的其余部分一起获得。”

于 2012-11-30T09:40:05.487 回答
2

让我们先看看算法..

  • 基本情况（即递归终止的情况）是集合为空的情况。

  • 否则，程序将第一个元素从集合中减去。

  • 现在它将调用subsetSumExists(rest, target)并检查它是否为真，如果是，它将返回真，否则它将调用 subsetSumExists(rest, target - element)并返回它返回的任何内容。

简单来说，subsetSumExists(rest, target - element)只有当第一个subsetSumExists(rest, target)返回 false 时才会调用。

现在让我们尝试用一个小样本集 {3,5} 和总和 8 来干运行这段代码。从现在开始我将调用函数 sSE

sSE({3,5}, 8) => "sSE({5}, 8) || sSE({5},(8-3))"

sSE({5}, 8)   => sSE({}, 8) || sSE({}, (8-5)) 

sSE({}, 8)    => false.. now will call sSE({}, (8-5))

sSE({}, 3)    => false.. now will call sSE({5}, (8-3))

sSE({5}, 5)   => sSE({}, 5} || sSE({}, (5-5))

sSE({}, 5)    => false.. now will call sSE({}, (5-5))

sSE({}, 0)    => true.. ends here and return true
于 2012-11-30T09:41:57.410 回答
1

要了解递归，您需要了解递归。要做到这一点，你需要反复思考。

在这种特殊情况下。

对于任何：subsetSum(set, target)

  1. 如果set为空target且为0，则subsetSum存在

  2. 否则，删除set. 检查是否subdetSum(set, target)存在或subdetSum(set, target - removed_element)存在（使用步骤 0）

于 2012-11-30T09:41:11.767 回答
1

集合减法看起来是一种奇怪的语法，但我认为它意味着元素上的 pop()。

它通过找到所有可能的组合来“工作”，尽管它是指数级的。

在||语句中，LHS 是包括当前元素的总和，而 RHS 是不包括它的总和。所以你会得到，沿着指数树，每个元素的每个组合要么打开要么关闭。

顺便说一句，指数意味着如果你有 30 个元素，它将产生 2 的 30 次方，即0x40000000接近十亿个组合。

当然，您可能会耗尽内存。

如果它找到解决方案，它可能不会运行所有 2^N 案例。如果没有解决方案，它将始终访问它们。

于 2012-11-30T09:41:13.600 回答
0

如果我为自己说话，理解问题的困难源于||操作员。让我们用另一种方式看一下相同代码的底部返回语句，

if (subsetSumExists(rest, target - element))
        return true;
if (subsetSumExists(rest, target))
        return true;

return false;
于 2018-09-28T17:52:54.883 回答