解丢番图解

问题描述

我的任务是解决分级丢番图问题。麦当劳出售6块、9块或20块一包的麦乐鸡。因此，例如，可以恰好购买15个麦乐鸡(一个6个包装和一个9个包装)，但是不可能恰好购买16个麦乐鸡，因为6、9和20的非负整数组合不等于16。要确定是否可以购买恰好n个麦乐鸡，必须求解丢番图方程：找出a、b和c的非负整数值，使得

6a+9b+20c=n。

编写一个以数字(N)为参数的函数Buy_Nuggets()，并返回四个数字的元组，这四个数字分别是：销售n个鸡块所需的包裹总数、6个鸡块的包数、9个鸡块的包数和20个鸡块的包数。如果无法组合块，则返回四个零的元组，即(0，0，0，0)。

请注意，对于给定的n，可以有多个解决方案，那么您的解决方案应该确保在使用较大的包之前先使用较小的包。例如，buy_nuggets(18)应该返回(3，3，0，0)而不是(2，0，2，0)，即3箱6块块除以2箱9块。 输入格式 整数(%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) + '
')

    fptr.close()

我以前确实问过，并被建议返回函数，我被推荐到一个Python教程，我对此表示感谢，我正在阅读，非常简洁，但信息丰富。然而，这个具体的问题一直让我很难熬。我知道这可能是一项艰巨的任务，但我希望即使以我目前的编程知识，您也可以尝试教学。

---

解决方案

不清楚您的代码遇到了什么问题，尽管它确实包含几个错误，例如a>b and c and d是一个表达式，它的意思可能与您认为的不同。它的意思是‘如果a大于b，c的布尔值是True，d的布尔值是True’-您可能想要类似‘ifa大于b，c和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)

Edit：user@paxdiablo正确地指出，解决方案在tuple中返回一对int和tuple；从风格的角度来看，我更喜欢这样，但不符合OP的问题。新解决方案正确返回单个元组。

如果键入内容不起作用，您可以使用这个-但是，这很可能意味着您使用的是较旧版本的Python，在这种情况下，walrus操作符可能也不起作用。以下是适用于旧版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)