java - 找不到错误我对 makeBricks 问题 java 的解决方案

Question

我找到了一个简单的 Java 练习并回答了它，但我的代码似乎有问题而且我似乎找不到问题所在。请指出我的问题:

问题是:

我们想制作一排 goal 英寸长的砖 block 。我们有一些小砖 block (每 block 1 英寸)和大砖 block (每 block 5 英寸)。如果可以通过从给定的积木中进行选择来实现目标，则返回 true。这比看起来要难一点，并且可以在没有任何循环的情况下完成。

我把这个函数作为答案:

 public boolean makeBricks(int small, int big, int goal) {
  if (small>=goal) return true;
  if ((goal>=5) && (big>=1)){  makeBricks(small,big-1,goal-5);}
  return false;
}

然而在 https://codingbat.com/prob/p183562 上运行它时它说这是错误的，但对我来说一切都是正确的。

Answer 1

添加 return语句解决了您无法确定堆栈中调用的真值的技术问题，但这是一个可以通过基本数学在恒定时间内解决的问题的线性解决方案:

public boolean makeBricks(int small, int big, int goal) {
    return big * 5 + small >= goal && goal % 5 <= small;
}

这里的想法是首先确定我们所有的积木组合是否达到或超过目标:big * 5 + small >= goal .如果我们不能满足这个等式，那我们肯定不走运。

然而，这过于乐观并且没有考虑到我们有足够的 block 来超过目标但没有足够的小块来移除一些较大的 block 并达到目标的情况。检测goal % 5 <= small确保我们有足够的小块来弥补每个大块被移除时留下的 5 的差距。

如果仍然不清楚，让我们检查一个边缘案例:makeBricks(3, 2, 9) .我们的目标是 9，我们有 3 个小积木和 2 个大积木。将我们的整个武器库加起来总共有 13 个，这似乎足以实现目标。但是，如果我们省略一个大块，最接近的是 8。如果我们省略所有的小块，我们最接近的是 10。无论我们做什么，目标都是遥不可及的.

让我们检查一下我们的公式:9 mod 5 == 4 ，这比我们的小块数 3 多 1，并且与我们的手算相匹配。我们应该返回 false在这个输入上。另一方面，如果我们有一个额外的小块，9 % 5 == small将是真实的，我们将有足够的 block 来弥合差距。