给定一些小数和大数，制作所需数字 - 无需循环

Question

我正在用Python解决codingbat上的编程题。其中有一个叫make_bricks的问题，内容是：

我们想要用砖块搭建一排，长度要达到目标的英寸数。我们有一些小砖块（每块1英寸）和大砖块（每块5英寸）。如果可以通过选择这些砖块来达到目标长度，就返回True。这个问题看起来有点难，但其实可以不使用任何循环来解决。

make_bricks(3, 1, 8) → True
make_bricks(3, 1, 9) → False
make_bricks(3, 2, 10) → True

我想到的第一个解决方案是：

from itertools import permutations

def make_bricks(small, big, goal):
    l = small*[1]+big*[5]
    return any([(goal in i) for i in ([[sum(j) for j in set(permutations(l,i))] \
    for i in range(2,len(l)+1)])])

这个方案是正确的，但被评测软件拒绝了，因为不允许使用导入功能。所以我接下来的解决方案是：

def make_bricks(small, big, goal):
    bricks = small*[1]+big*[5]
    for step in range(len(bricks)+1,1,-1):
        for start in range(len(bricks)):
            if len(bricks[start:start+step])==step:
                if sum(bricks[start:start+step])==goal:
                    return True
    return False

这个方案也正确，但在处理像make_bricks(1000000, 1000, 1000100)这样的输入时超时了。

那么，你会如何在Python中解决这个问题呢？不使用导入，不使用循环，并且在时间限制内？

Answer 1

记住，你只需要达到最终的长度。所以，砖块放置的顺序其实并不重要。

下一个重要的点是，尽量使用5英寸的砖块。用一块5英寸的砖块可以覆盖5英寸的长度，而用5块1英寸的砖块也能覆盖5英寸。因此，使用一块5英寸的砖块更划算。

现在你其实已经差不多完成了：检查一下你能用手头的5英寸砖块拼出多长的长度，直到你用完5英寸的砖块，或者距离目标长度还差的长度小于5英寸。不管怎样，肯定会有一些长度是缺少的，这部分你需要用剩下的1英寸砖块来填补。

我这里不提供代码，因为这个问题真的很简单。只要你理解了上面说的内容，就应该能轻松解决它。

Answer 2

def make_bricks(small, big, goal):
  if goal > small + big * 5:
    return False
  else:
    return goal % 5 <= small

当然可以！请把你想要翻译的内容发给我，我会帮你用简单易懂的语言解释清楚。

Answer 3

这是一个数学问题。假设你有 S 块小砖和 B 块大砖，你想要一个长度为 L 的块。

你可以使用 K = min(B, L div 5) 块大砖，和 L - 5K 块小砖，所以你只需要检查一下你的小砖够不够。

div 是整数除法（向下取整）。

编辑 把 L-K 改成了 L-5K，是个打字错误。