时间戳

首页 > 解决方案 > 包含 5 的倍数的布尔递归

java - 包含 5 的倍数的布尔递归

问题描述

这是我正在处理的问题：“给定一个整数数组，是否可以选择一组整数，使得该组在这些附加约束下与给定目标相加：所有 5 的倍数数组必须包含在组中。如果紧跟在 5 的倍数后面的值为 1，则不能选择它。（不需要循环。）"

我尝试了以下方法：

public boolean groupSum5(int start, int[] nums, int target) {
  if (start == nums.length) return (target == 0);
  if (groupSum5(start + 1, nums, target - nums[start]) && nums[start] % 5 == 0)
    return true;
  if (groupSum5(start + 1, nums, target)) return true;
  return false;
}

但它只能得到 5 的倍数，我试过这个：

public boolean groupSum5(int start, int[] nums, int target) {
  if (start == nums.length) return (target == 0);
  if (groupSum5(start + 1, nums, target - nums[start]) && nums[start] % 5 == 0)
    return true;
  if (groupSum(start + 1, nums, target - nums[start])) return true;
  if (groupSum5(start + 1, nums, target)) return true;
  return false;
}

但它不起作用，因为有时不包括 5 的倍数。

我知道我的代码还没有满足第二个约束。

有任何想法吗？

编辑： 在此处输入图像描述

标签： javarecursionboolean

解决方案

if (groupSum5(start + 1, nums, target - nums[start]))

对于输入中的每个数字，您需要选择是否包含它。这if是“包含它”选项：这就是您将目标值减少的原因。

&& nums[start] % 5 == 0

...所以这意味着：不可能包含任何给定的值，除非它是 5 的倍数。这不是问题描述要你做的！

问题描述要你做的是：如果你所在的数字是 5 的倍数，那么它必须包括在内。您不能选择不包含它。

因此，您将约束限制在错误的 if 和错误的方式上。您真正想要的是第二个 if，它涵盖了要修改的“让不要选择这个数字”：

if (!num[start] % 5 == 0 && groupSum5(start, nums, target)) return true;

换句话说：如果我们所在的数字不是 5 的倍数，那么试着不包括这个数字，看看是否可行。（因为当它是 5 的倍数时试图不包括它是无效的）。

如果紧跟在 5 的倍数后面的值为 1，则不能选择它。

这是另一个约束，这个约束必须应用于第一个 if（代表“让包括这个数字”的那个）。如果需要一些额外&&的过滤 -OUT- 你所在的数字是 1，并且它不是序列中的第一个数字，并且序列中的前一个数字是 5 的倍数：在这种情况下， “包括号码”不是一个有效的举动。

使用倒置条件（!前面有 a）和&&，类似于上面的例子。您想要完成的是，如果由于附加约束而导致该步骤无效，则简单地跳过“尝试包含此数字，然后看看我们是否可以通过将此算法应用于列表的其余部分来解决它”的步骤.

推荐阅读