解决丢番图
Solving a Diophantine
我的任务是解决分级丢番图问题。麦当劳以 6 个、9 个或 20 个 McNuggets 的包装出售 Chicken McNuggets。因此，例如，有可能恰好购买 15 块麦乐鸡块（一包 6 块和一包 9 块），但不可能恰好购买 16 块麦乐鸡块，因为没有 6、9 和 6 的非负整数组合20 加起来等于 16。要确定是否可以恰好购买 n 个 McNuggets，必须求解丢番图方程：找到 a、b 和 c 的非负整数值，使得
6a + 9b + 20c = n.
编写一个函数 buy_nuggets() 以数字 (n) 作为参数和 returns 四个数字的元组；卖出n个金块需要的总包数、6金包数、9金包数和20金包数。如果无法组合金块，那么它 return 是一个包含四个零的元组，即 (0,0,0,0)。
请注意，对于给定的 n 可以有多个解决方案，那么您的解决方案应确保在使用较大的包之前使用较小的包。例如，buy_nuggets(18) 应该 return (3,3,0,0) 而不是 (2,0,2,0)，即 3 盒 6 块金块超过 2 盒九块。
输入格式
整数 (n)
我得到了限制 -10^6<=a,b,c,n<=10^6
输出格式
4 个数字 (d,a,b,c) 的元组，其中
d = 包裹总数
a - 6 个包裹的数量
b - 9 个包裹的数量
c - 20 包的数量
然后我尝试了
def nugget_boxes(n):
# Write your code here- (above this was given)
def diophantine(a,b,c,d):
if a>b and c and d:
q=extended_nuggets(a,b,c,d)
a1=q[1]
b1=q[2]
c1=q[3]
d1=q[4]
if b>a and c and d:
q=extended_nuggets(a,b,c,d)
a1=q[2]
b1=q[1]
c1=q[3]
d1=q[4]
if c>a and b and d:
q=extended_nuggets(a,b,c,d)
a1=q[3]
b1=q[1]
c1=q[2]
d1=q[4]
else:
q=extended_nuggets(a,b,c,d)
a1=q[4]
b1=q[1]
c1=q[2]
d1=q[3]
assert c%q[0]==0
d=q[0]
p=c/d
return diophantine(int(p*x1),int(p*y1), int(p*z1))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(raw_input().strip())
results = nugget_boxes(n)
fptr.write(str(results) + '\n')
fptr.close()
我之前确实问过，并被建议 return 该功能，我被推荐给一个 python 教程，我很感激并且正在阅读它，它非常简洁但内容丰富。但是，这个具体问题一直让我很为难。我知道这可能是一项艰巨的任务，但我希望即使以我目前的编码知识，您仍然可以尝试教学。
不清楚您的代码遇到了什么问题，尽管它确实包含一些错误，例如 a>b and c and d 是一个表达式，可能并不代表您认为的意思。这意味着 'if a is greater than b and the boolean value of c is True and the boolean value of d is True' - 你可能想要像 'if a is greater than b, c, and d' 这样的东西，尽管从算法的角度来看这也没有太大意义
问题本身有点奇怪 - 谁会想要尽可能多的小盒子，因为大盒子通常会给您折扣。但显然，如果这是要求 - 客户永远是对的。
如果允许递归实现（显然是这样），问题就相当简单了：
from typing import Tuple
def pack_nuggets(n: int, sizes: Tuple[int]) -> Tuple[int]:
if n == 0:
return (0, *(0 for _ in sizes))
if not sizes:
return (0,)
for x in range(n // sizes[0], 0, -1):
total, *rest = pack_nuggets((remainder := n - x * sizes[0]), sizes[1:])
if sum(rest) or not remainder:
return (sum(rest) + x, x, *rest)
return (0, *(0 for _ in sizes))
print(pack_nuggets(0, (6, 9, 20))) # (0, 0, 0, 0)
print(pack_nuggets(10, tuple())) # (0, )
print(pack_nuggets(18, (6, 9, 20))) # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20))) # (5, 3, 1, 1)
编辑：用户@paxdiablo 正确指出解决方案是在 tuple 中返回一对 int 和 tuple；从文体的角度来看我更喜欢，但不符合 OP 的问题。新的解决方案正确 returns 单个元组。
万一打字不起作用，您可以使用它 - 但是，这可能意味着您使用的是旧版本的 Python，在这种情况下，海象运算符可能也不起作用工作。这是适用于旧 Python 3 版本的解决方案：
def pack_nuggets(n, sizes):
if n == 0:
return (0, *(0 for _ in sizes))
if not sizes:
return (0,)
for x in range(n // sizes[0], 0, -1):
remainder = n - x * sizes[0]
total, *rest = pack_nuggets(remainder, sizes[1:])
if sum(rest) or not remainder:
return (sum(rest) + x, x, *rest)
return (0, *(0 for _ in sizes))
print(pack_nuggets(0, (6, 9, 20))) # (0, 0, 0, 0)
print(pack_nuggets(10, tuple())) # (0, )
print(pack_nuggets(18, (6, 9, 20))) # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20))) # (5, 3, 1, 1)
下面是适用于特定框尺寸的迭代解决方案。通过简单地添加更多嵌套的 if 块，它可以扩展到其他盒子场景。
满足“首选较小的盒子”要求的方法很简单，就是确保我们适当地搜索解决方案 space。换句话说，我们从最大可能的six-boxes开始，然后向下搜索。
同样，我们从最大可能的nine-boxes开始（给定six-boxes的个数），向下搜索
我们不必搜索 twenty-boxes 的数量，因为给定两个较小尺寸的数量，只有 一个 的可能性：获得的数量为尽可能接近所需的数量而不超过。
然后，如果我们得到了准确的数量，我们会立即return解决方案。否则，我们继续寻找。如果在彻底搜索后没有找到解决方案，我们 return 标记值（全零）。
这肯定比测试计数的每个 可能 场景并保存满足“更喜欢小盒子”要求的场景的天真方法要好。
import typing as typ
def pack_nuggets(quant: int) -> typ.Tuple[int]:
""" Figure out how many nugget boxes are needed.
Given quantity of nuggets, calculates the best triplet
of boxes (of zize 6, 9, and 20) to satisfy the order.
Best in this case prefers smaller boxes to larger.
If no solution, give all zeros.
Args:
quant: the quantity of nuggets desired.
Returns:
Tuple with total box count followed by count of
each box in ascending size).
"""
# Start with maximum possible quantity of six-boxes
# and gradually reduce to zero.
max_sixes: int = quant // 6
for six in range(quant // 6, -1, -1):
# Start with maximum possible quantity of nine-boxes
# given current six-box count and gradually reduce
# to zero.
six_val: int = six * 6
max_nines_for_six: int = (quant - six_val) // 9
for nine in range(max_nines_for_six, -1, -1):
# There's only really one possible twenty-boxes
# count that can get to (or a little below) the
# desired quantity.
nine_val: int = nine * 9
twenty: int = (quant - six_val - nine_val) // 20
# If that's a viable solution, return it.
if six * 6 + nine * 9 + twenty * 20 == quant:
return (six + nine + twenty, six, nine, twenty)
# If there were NO viable solutions, let caller know.
return (0, 0, 0, 0)
没有测试工具，self-respecting 开发人员会 post 编写代码吗？ “不是我，”帕克斯说 :-)
# Test harness.
if __name__ == "__main__":
for test_val in range(55):
print(f"Result is {pack_nuggets(test_val)} for {test_val} nuggets.")
print(f"Result is {pack_nuggets(1_000_000)} for {1_000_000} nuggets.")
测试工具的输出显示了正在运行的功能（我添加的评论）：
Result is (0, 0, 0, 0) for 0 nuggets.
Result is (0, 0, 0, 0) for 1 nuggets.
Result is (0, 0, 0, 0) for 2 nuggets.
Result is (0, 0, 0, 0) for 3 nuggets.
Result is (0, 0, 0, 0) for 4 nuggets.
Result is (0, 0, 0, 0) for 5 nuggets.
Result is (1, 1, 0, 0) for 6 nuggets. # Six is first to satisfy.
Result is (0, 0, 0, 0) for 7 nuggets.
Result is (0, 0, 0, 0) for 8 nuggets.
Result is (1, 0, 1, 0) for 9 nuggets. # Then nine.
Result is (0, 0, 0, 0) for 10 nuggets.
Result is (0, 0, 0, 0) for 11 nuggets.
Result is (2, 2, 0, 0) for 12 nuggets.
Result is (0, 0, 0, 0) for 13 nuggets.
Result is (0, 0, 0, 0) for 14 nuggets.
Result is (2, 1, 1, 0) for 15 nuggets. # A six and a nine.
Result is (0, 0, 0, 0) for 16 nuggets.
Result is (0, 0, 0, 0) for 17 nuggets.
Result is (3, 3, 0, 0) for 18 nuggets. # Prefer 3*six over 2*nine.
Result is (0, 0, 0, 0) for 19 nuggets.
Result is (1, 0, 0, 1) for 20 nuggets. # A single twenty-box.
Result is (3, 2, 1, 0) for 21 nuggets.
Result is (0, 0, 0, 0) for 22 nuggets.
Result is (0, 0, 0, 0) for 23 nuggets.
Result is (4, 4, 0, 0) for 24 nuggets. # Use 4*six, not 2*nine + six.
Result is (0, 0, 0, 0) for 25 nuggets.
Result is (2, 1, 0, 1) for 26 nuggets.
Result is (4, 3, 1, 0) for 27 nuggets.
Result is (0, 0, 0, 0) for 28 nuggets.
Result is (2, 0, 1, 1) for 29 nuggets.
Result is (5, 5, 0, 0) for 30 nuggets.
Result is (0, 0, 0, 0) for 31 nuggets.
Result is (3, 2, 0, 1) for 32 nuggets.
Result is (5, 4, 1, 0) for 33 nuggets.
Result is (0, 0, 0, 0) for 34 nuggets.
Result is (3, 1, 1, 1) for 35 nuggets.
Result is (6, 6, 0, 0) for 36 nuggets.
Result is (0, 0, 0, 0) for 37 nuggets.
Result is (4, 3, 0, 1) for 38 nuggets.
Result is (6, 5, 1, 0) for 39 nuggets.
Result is (2, 0, 0, 2) for 40 nuggets. # Two twenty-boxes.
Result is (4, 2, 1, 1) for 41 nuggets.
Result is (7, 7, 0, 0) for 42 nuggets.
Result is (0, 0, 0, 0) for 43 nuggets.
Result is (5, 4, 0, 1) for 44 nuggets.
Result is (7, 6, 1, 0) for 45 nuggets.
Result is (3, 1, 0, 2) for 46 nuggets.
Result is (5, 3, 1, 1) for 47 nuggets.
Result is (8, 8, 0, 0) for 48 nuggets.
Result is (3, 0, 1, 2) for 49 nuggets.
Result is (6, 5, 0, 1) for 50 nuggets.
Result is (8, 7, 1, 0) for 51 nuggets.
Result is (4, 2, 0, 2) for 52 nuggets.
Result is (6, 4, 1, 1) for 53 nuggets. # 4*six + nine + twenty.
Result is (9, 9, 0, 0) for 54 nuggets. # Prefer 9*six over 6*nine.
# Still very fast, even for a million nuggets.
# But now I feel quite bloated :-)
Result is (166662, 166660, 0, 2) for 1000000 nuggets.
我的任务是解决分级丢番图问题。麦当劳以 6 个、9 个或 20 个 McNuggets 的包装出售 Chicken McNuggets。因此，例如，有可能恰好购买 15 块麦乐鸡块（一包 6 块和一包 9 块），但不可能恰好购买 16 块麦乐鸡块，因为没有 6、9 和 6 的非负整数组合20 加起来等于 16。要确定是否可以恰好购买 n 个 McNuggets，必须求解丢番图方程：找到 a、b 和 c 的非负整数值，使得
6a + 9b + 20c = n.
编写一个函数 buy_nuggets() 以数字 (n) 作为参数和 returns 四个数字的元组；卖出n个金块需要的总包数、6金包数、9金包数和20金包数。如果无法组合金块，那么它 return 是一个包含四个零的元组，即 (0,0,0,0)。
请注意，对于给定的 n 可以有多个解决方案，那么您的解决方案应确保在使用较大的包之前使用较小的包。例如，buy_nuggets(18) 应该 return (3,3,0,0) 而不是 (2,0,2,0)，即 3 盒 6 块金块超过 2 盒九块。 输入格式 整数 (n)
我得到了限制 -10^6<=a,b,c,n<=10^6
输出格式
4 个数字 (d,a,b,c) 的元组，其中
d = 包裹总数 a - 6 个包裹的数量 b - 9 个包裹的数量 c - 20 包的数量
然后我尝试了
def nugget_boxes(n):
# Write your code here- (above this was given)
def diophantine(a,b,c,d):
if a>b and c and d:
q=extended_nuggets(a,b,c,d)
a1=q[1]
b1=q[2]
c1=q[3]
d1=q[4]
if b>a and c and d:
q=extended_nuggets(a,b,c,d)
a1=q[2]
b1=q[1]
c1=q[3]
d1=q[4]
if c>a and b and d:
q=extended_nuggets(a,b,c,d)
a1=q[3]
b1=q[1]
c1=q[2]
d1=q[4]
else:
q=extended_nuggets(a,b,c,d)
a1=q[4]
b1=q[1]
c1=q[2]
d1=q[3]
assert c%q[0]==0
d=q[0]
p=c/d
return diophantine(int(p*x1),int(p*y1), int(p*z1))
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(raw_input().strip())
results = nugget_boxes(n)
fptr.write(str(results) + '\n')
fptr.close()
我之前确实问过，并被建议 return 该功能，我被推荐给一个 python 教程，我很感激并且正在阅读它，它非常简洁但内容丰富。但是，这个具体问题一直让我很为难。我知道这可能是一项艰巨的任务，但我希望即使以我目前的编码知识，您仍然可以尝试教学。
不清楚您的代码遇到了什么问题，尽管它确实包含一些错误，例如 a>b and c and d 是一个表达式，可能并不代表您认为的意思。这意味着 'if a is greater than b and the boolean value of c is True and the boolean value of d is True' - 你可能想要像 'if a is greater than b, c, and d' 这样的东西，尽管从算法的角度来看这也没有太大意义
问题本身有点奇怪 - 谁会想要尽可能多的小盒子，因为大盒子通常会给您折扣。但显然，如果这是要求 - 客户永远是对的。
如果允许递归实现（显然是这样），问题就相当简单了：
from typing import Tuple
def pack_nuggets(n: int, sizes: Tuple[int]) -> Tuple[int]:
if n == 0:
return (0, *(0 for _ in sizes))
if not sizes:
return (0,)
for x in range(n // sizes[0], 0, -1):
total, *rest = pack_nuggets((remainder := n - x * sizes[0]), sizes[1:])
if sum(rest) or not remainder:
return (sum(rest) + x, x, *rest)
return (0, *(0 for _ in sizes))
print(pack_nuggets(0, (6, 9, 20))) # (0, 0, 0, 0)
print(pack_nuggets(10, tuple())) # (0, )
print(pack_nuggets(18, (6, 9, 20))) # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20))) # (5, 3, 1, 1)
编辑：用户@paxdiablo 正确指出解决方案是在 tuple 中返回一对 int 和 tuple；从文体的角度来看我更喜欢，但不符合 OP 的问题。新的解决方案正确 returns 单个元组。
万一打字不起作用，您可以使用它 - 但是，这可能意味着您使用的是旧版本的 Python，在这种情况下，海象运算符可能也不起作用工作。这是适用于旧 Python 3 版本的解决方案：
def pack_nuggets(n, sizes):
if n == 0:
return (0, *(0 for _ in sizes))
if not sizes:
return (0,)
for x in range(n // sizes[0], 0, -1):
remainder = n - x * sizes[0]
total, *rest = pack_nuggets(remainder, sizes[1:])
if sum(rest) or not remainder:
return (sum(rest) + x, x, *rest)
return (0, *(0 for _ in sizes))
print(pack_nuggets(0, (6, 9, 20))) # (0, 0, 0, 0)
print(pack_nuggets(10, tuple())) # (0, )
print(pack_nuggets(18, (6, 9, 20))) # (3, 3, 0, 0)
print(pack_nuggets(47, (6, 9, 20))) # (5, 3, 1, 1)
下面是适用于特定框尺寸的迭代解决方案。通过简单地添加更多嵌套的 if 块，它可以扩展到其他盒子场景。
满足“首选较小的盒子”要求的方法很简单，就是确保我们适当地搜索解决方案 space。换句话说，我们从最大可能的six-boxes开始，然后向下搜索。
同样，我们从最大可能的nine-boxes开始（给定six-boxes的个数），向下搜索
我们不必搜索 twenty-boxes 的数量，因为给定两个较小尺寸的数量，只有 一个 的可能性：获得的数量为尽可能接近所需的数量而不超过。
然后，如果我们得到了准确的数量，我们会立即return解决方案。否则，我们继续寻找。如果在彻底搜索后没有找到解决方案，我们 return 标记值（全零）。
这肯定比测试计数的每个 可能 场景并保存满足“更喜欢小盒子”要求的场景的天真方法要好。
import typing as typ
def pack_nuggets(quant: int) -> typ.Tuple[int]:
""" Figure out how many nugget boxes are needed.
Given quantity of nuggets, calculates the best triplet
of boxes (of zize 6, 9, and 20) to satisfy the order.
Best in this case prefers smaller boxes to larger.
If no solution, give all zeros.
Args:
quant: the quantity of nuggets desired.
Returns:
Tuple with total box count followed by count of
each box in ascending size).
"""
# Start with maximum possible quantity of six-boxes
# and gradually reduce to zero.
max_sixes: int = quant // 6
for six in range(quant // 6, -1, -1):
# Start with maximum possible quantity of nine-boxes
# given current six-box count and gradually reduce
# to zero.
six_val: int = six * 6
max_nines_for_six: int = (quant - six_val) // 9
for nine in range(max_nines_for_six, -1, -1):
# There's only really one possible twenty-boxes
# count that can get to (or a little below) the
# desired quantity.
nine_val: int = nine * 9
twenty: int = (quant - six_val - nine_val) // 20
# If that's a viable solution, return it.
if six * 6 + nine * 9 + twenty * 20 == quant:
return (six + nine + twenty, six, nine, twenty)
# If there were NO viable solutions, let caller know.
return (0, 0, 0, 0)
没有测试工具，self-respecting 开发人员会 post 编写代码吗？ “不是我，”帕克斯说 :-)
# Test harness.
if __name__ == "__main__":
for test_val in range(55):
print(f"Result is {pack_nuggets(test_val)} for {test_val} nuggets.")
print(f"Result is {pack_nuggets(1_000_000)} for {1_000_000} nuggets.")
测试工具的输出显示了正在运行的功能（我添加的评论）：
Result is (0, 0, 0, 0) for 0 nuggets.
Result is (0, 0, 0, 0) for 1 nuggets.
Result is (0, 0, 0, 0) for 2 nuggets.
Result is (0, 0, 0, 0) for 3 nuggets.
Result is (0, 0, 0, 0) for 4 nuggets.
Result is (0, 0, 0, 0) for 5 nuggets.
Result is (1, 1, 0, 0) for 6 nuggets. # Six is first to satisfy.
Result is (0, 0, 0, 0) for 7 nuggets.
Result is (0, 0, 0, 0) for 8 nuggets.
Result is (1, 0, 1, 0) for 9 nuggets. # Then nine.
Result is (0, 0, 0, 0) for 10 nuggets.
Result is (0, 0, 0, 0) for 11 nuggets.
Result is (2, 2, 0, 0) for 12 nuggets.
Result is (0, 0, 0, 0) for 13 nuggets.
Result is (0, 0, 0, 0) for 14 nuggets.
Result is (2, 1, 1, 0) for 15 nuggets. # A six and a nine.
Result is (0, 0, 0, 0) for 16 nuggets.
Result is (0, 0, 0, 0) for 17 nuggets.
Result is (3, 3, 0, 0) for 18 nuggets. # Prefer 3*six over 2*nine.
Result is (0, 0, 0, 0) for 19 nuggets.
Result is (1, 0, 0, 1) for 20 nuggets. # A single twenty-box.
Result is (3, 2, 1, 0) for 21 nuggets.
Result is (0, 0, 0, 0) for 22 nuggets.
Result is (0, 0, 0, 0) for 23 nuggets.
Result is (4, 4, 0, 0) for 24 nuggets. # Use 4*six, not 2*nine + six.
Result is (0, 0, 0, 0) for 25 nuggets.
Result is (2, 1, 0, 1) for 26 nuggets.
Result is (4, 3, 1, 0) for 27 nuggets.
Result is (0, 0, 0, 0) for 28 nuggets.
Result is (2, 0, 1, 1) for 29 nuggets.
Result is (5, 5, 0, 0) for 30 nuggets.
Result is (0, 0, 0, 0) for 31 nuggets.
Result is (3, 2, 0, 1) for 32 nuggets.
Result is (5, 4, 1, 0) for 33 nuggets.
Result is (0, 0, 0, 0) for 34 nuggets.
Result is (3, 1, 1, 1) for 35 nuggets.
Result is (6, 6, 0, 0) for 36 nuggets.
Result is (0, 0, 0, 0) for 37 nuggets.
Result is (4, 3, 0, 1) for 38 nuggets.
Result is (6, 5, 1, 0) for 39 nuggets.
Result is (2, 0, 0, 2) for 40 nuggets. # Two twenty-boxes.
Result is (4, 2, 1, 1) for 41 nuggets.
Result is (7, 7, 0, 0) for 42 nuggets.
Result is (0, 0, 0, 0) for 43 nuggets.
Result is (5, 4, 0, 1) for 44 nuggets.
Result is (7, 6, 1, 0) for 45 nuggets.
Result is (3, 1, 0, 2) for 46 nuggets.
Result is (5, 3, 1, 1) for 47 nuggets.
Result is (8, 8, 0, 0) for 48 nuggets.
Result is (3, 0, 1, 2) for 49 nuggets.
Result is (6, 5, 0, 1) for 50 nuggets.
Result is (8, 7, 1, 0) for 51 nuggets.
Result is (4, 2, 0, 2) for 52 nuggets.
Result is (6, 4, 1, 1) for 53 nuggets. # 4*six + nine + twenty.
Result is (9, 9, 0, 0) for 54 nuggets. # Prefer 9*six over 6*nine.
# Still very fast, even for a million nuggets.
# But now I feel quite bloated :-)
Result is (166662, 166660, 0, 2) for 1000000 nuggets.