在Python中找到可以在一系列数字中平分的最小值,拼图

Question

我正在尝试解决下面详述的项目拼图.我当前的函数适用于数字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.谢谢

Answer 1

你的算法是非常低效的,但问题的核心是你的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子句; 当循环通过列表耗尽(with for)或条件变为false(with while)时终止,但是当循环被break语句终止时,它被执行.

一个更简洁的表达方式是:

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

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

由于这是一个难题,我将传递建议更好的算法.