0

我正在尝试解决下面详述的投影仪难题。我当前的函数适用于数字 1 到 10，但是当我尝试 1 到 20 时，它只会永远循环而没有结果。

2520 是可以除以 1 到 10 的每个数字而没有任何余数的最小数字。能被 1 到 20 的所有数整除的最小正数是多少？

def calculate():
    results = dict()
    target = 20
    num_to_test = 1
    while len(results) < target:
        for j in range(1, target+1):
            results[num_to_test] = True
            if num_to_test % j != 0:
                # current num_to_test failed in the 1-10, move on
                del results[num_to_test]
                break

        num_to_test += 1
    return min(results)

任何人都可以看到逻辑中的任何问题，特别是我想知道为什么它适用于 10 的目标，而不是 20 的目标。谢谢

4

5 回答 5

5

您的算法效率很低，但问题的核心是您的results字典为每个整数累积 1 个值，该整数可以被 1-20 的数字整除，并且您的while循环试图继续运行，直到它有 20 个这样的数字。

这是实现这种低效算法的一种正确方法：

def calculate():
    target = 20
    candidate = 1
    success = False
    divisors = range(1, target+1)
    while not success:
        for divisor in divisors:
            if candidate % divisor != 0:
                candidate += 1
                break
        else:
            success = True

    return candidate

请注意，该else子句实际上是在 for 循环上，而不是 if。来自关于流量控制的教程：

循环语句可能有一个 else 子句；它在循环因列表用尽而终止时（使用 for）或条件变为假（使用 while）时执行，但不是在循环由 break 语句终止时执行。

更简洁的表达方式是：

candidate = 0
while not success:
    candidate += 1
    success = all((candidate % divisor == 0 for divisor in divisors))

它使用生成器表达式，因此all可以短路并避免进行不必要的计算。

由于这是一个难题，我将继续建议更好的算法。

于 2013-07-31T20:25:37.680 回答
4

实际上我有非常有效的算法来解决这个问题。我不会给你代码，但我可以告诉你方法

对于 N = 10

1.计算5到10所有数的所有因数：

 [[2, 3], [7], [2, 2, 2], [3, 3], [2, 5]]

2.计算列表中每个素数的最大数量

 {2: 3, 3: 2, 5: 1, 7: 1}

3.得到关键功率值的乘积

 2^3 * 3^2 * 5 * 7 = 2520
于 2013-07-31T20:51:23.450 回答
2

许多其他答案都提到原始代码效率低下，但它们仍然循环遍历几乎每个数字。使用 lcm 功能不是更有效吗？

def calculate(num, current_lcm = 1):
    if (num == 1): return current_lcm
    return calculate(num - 1, lcm(num, current_lcm))

def lcm(a, b):
    return a * b // gcd(a, b)

def gcd(a, b):
    while b:      
        a, b = b, a % b
    return a

print calculate(20)
于 2013-07-31T20:39:03.367 回答
1

不要全部存储它们，而是在找到它时尽早返回，摆脱那个结果字典，顺便说一句，这根本不是最佳的，只是一个清理

def calculate():
    target = 20
    num_to_test = 0
    while True:
        num_to_test += target
        if all((num_to_test % j == 0) for j in range(1,target+1)):
            return num_to_test
    return -1

此外，您不需要测试不是最大值倍数的数字。它的运行速度会快 20 倍。

我改用生成器来测试这个数字是否可以被all()1 到 20的数字整除

编写自己的算法而不是复制一个的道具:)

于 2013-07-31T20:30:35.247 回答
1

虽然您的算法效率非常低，但进行这个小改动可能会有所帮助

        if num_to_test % j = 0:
            results[num_to_test] = True
        else:
            # current num_to_test failed in the 1-10, move on
            break

不知道为什么要全部存储它们？也许是为了调试？

暗示。最好计算结果的主要因素并将它们简单地相乘。

# spoiler  






























def calculate(target):
    n = 1
    for i in range(1, target+1):
        for j in range(1, target+1):
            if (n * j) % i == 0:
                n *= j
                break
    return n
于 2013-07-31T20:32:33.487 回答