首页 文章

递归地确定是否可以找到目标号码

提问于
浏览 次
2

我会更好地为初学者解释这个 Headers . 我的问题非常类似于常见问题：查找整数数组问题的所有排列 .

我试图找到一个整数列表和一个目标数字，如果可以从列表中选择任何数字组合，那么它们的总和与目标相匹配 . 它必须使用函数式编程实践来完成，这意味着所有循环和突变都是完整的，只有聪明的递归 . 完全披露：这是家庭作业，方法 Headers 由教授设定 . 这就是我所拥有的：

public static Integer sum(final List<Integer> values) {
     if(values.isEmpty() || values == null) {
             return 0;
     }
     else {
             return values.get(0) + sum(values.subList(1, values.size()));
     }
 }

public static boolean groupExists(final List<Integer> numbers, final int target) {
     if(numbers == null || numbers.isEmpty()) {
             return false;
     }
     if(numbers.contains(target)) {
             return true;
     }
      if(sum(numbers) == target) {
              return true;
      }
      else {
              groupExists(numbers.subList(1, numbers.size()), target);
              return false;
      }
  }

sum方法经过测试和工作，groupExists方法就是我正在研究的方法 . 我认为它非常接近，如果给出一个列表[1,2,3,4]，对于3和10等目标它将返回true，但对于6则为false，这使我感到困惑，因为1,2,3是正确的并添加到6.显然缺少一些东西 . 此外，我看到的主要问题是它没有测试所有可能的组合，例如，第一个和最后一个数字不是作为一种可能性加在一起的 .

更新：根据Simon的答案工作了一下后，这就是我在看的内容：

public static boolean groupExists(final List<Integer> numbers, final int target) {
     if(numbers == null || numbers.isEmpty()) {
             return false;
      }
     if(numbers.isEmpty()) {
              return false;
      }
      if(numbers.contains(target)) {
              return true;
      }
      if(sum(numbers.subList(1, numbers.size())) == (target - numbers.get(0))) {
              return true; }                                                                                                                                                                                                     
      else {
              return groupExists(numbers.subList(1, numbers.size()), target);
      }
  }
java recursion combinations

4 回答

  • 1

    为方便起见，申报

    static Integer head(final List<Integer> is) {
  return is == null || is.isEmpty()? null : is.get(0);
}
static List<Integer> tail(final List<Integer> is) {
  return is.size() < 2? null : is.subList(1, is.size());
}

    然后你的功能是这样的：

    static boolean groupExists(final List<Integer> is, final int target) {
  return target == 0 || target > 0 && head(is) != null &&
       (groupExists(tail(is), target) || groupExists(tail(is), target-head(is)));
}

    毫无疑问，实际上，定期检查基本案例加上最后一行，其中左右操作数搜索分别包括头部的“组” .

    我写它的方式乍看起来很明显这些都是纯函数，但是，由于这是Java而不是FP语言，因此这种编写方式非常不理想 . 最好将多次出现的任何函数调用缓存到最终的本地变量中 . 当然，那仍然是书 .

    回复于
  • 1

    假设您有 n 个数字 a[0] ， a[1] ，...， a[n-1] ，并且您想知道某些子集是否为 N .

    假设你有这样一个子集 . 现在，要么包含 a[0] ，要么包括't. If it'，那么必须存在 a[1] ，...， a[n] 的子集，其总和为 N - a[0] . 如果不是，则存在 a[1] ，...， a[n] 的子集，其总和为 N .

    这将引导您进行递归解决方案 .

    回复于
  • 0

    检查所有组合是因子（实现中有点缺失） . 为什么不尝试不同的（动态）方法：参见Hitchhikers Guide to Programming Contests，第1页（子集和） .

    你的主要方法是这样的：

    boolean canSum(numbers, target) {
  return computeVector(numbers)[target]
}

    computeVector 返回带有所有数字的向量，该数字可以与 numbers 的集合求和 . 递归执行方法 computeVector 有点棘手，但您可以执行以下操作：

    boolean[] computeVector(numbers, vector) {
  if numbers is empty:
    return vector

  addNumber(numbers[0], vector)

  return computeVector(tail(numbers), vector);
}

    addNumber 将使用向量和'fill it'与新的'doable'数字（请参阅搭便车的解释） . addNumber 也可能有点棘手，我会留给你的 . 基本上你需要以recrusive方式编写以下循环：

    for(j=M; j>=a[i]; j--)
  m[j] |= m[j-a[i]];
    回复于
  • 1

    通过在每次递归时询问一个非常简单的决定，可以达到所有可能组合的列表 . 这个组合是否包含我的列表的头部？无论是它有没有，所以每个阶段有2条路径 . 如果任一路径导致解决方案，那么我们想要返回true .

    boolean combination(targetList, sourceList, target)
{
    if ( sourceList.isEmpty() ) {
        return sum(targetList) == target;
    } else {
        head = sourceList.pop();
        without = combination(targetList, sourceList, target); // without head
        targetList.push(head);
        with = combination(targetList, sourceList, target); // with head
        return with || without;
    }
}
    回复于

相关问题