Python中的euler 43项目

Question

我遇到了另一个困难的项目欧拉问题 Link to the problem

我的第一反应是尝试一个简单的暴力解决方案，这需要太多的时间来运行。在

所以我想了一个更好的解决方案，但我不知道如何编码。在

我想：

1. 生成所有必需的三胞胎。在
2. 把所有的组合放在一起。在
3. 计算总数。在

我做了第一步，结果如下：

Multiples of 17: [[0, 1, 7], [0, 3, 4], [0, 5, 1], [0, 6, 8], [0, 8, 5], [1,   0, 2], [1, 3, 6], [1, 5, 3], [1, 7, 0], [1, 8, 7], [2, 0, 4], [2, 3, 8], [2, 8, 9], [3, 0, 6], [3, 4, 0], [3, 5, 7], [3, 7, 4], [3, 9, 1], [4, 0, 8], [4, 2, 5], [4, 5, 9], [4, 7, 6], [4, 9, 3], [5, 1, 0], [5, 2, 7], [5, 6, 1], [5, 7, 8], [6, 1, 2], [6, 2, 9], [6, 8, 0], [6, 9, 7], [7, 1, 4], [7, 3, 1], [7, 4, 8], [7, 6, 5], [7, 8, 2], [8, 1, 6], [8, 5, 0], [8, 6, 7], [9, 0, 1], [9, 1, 8], [9, 3, 5], [9, 5, 2], [9, 8, 6]] etc...

现在对我来说棘手的部分来了。我试着用嵌套的循环把它们放在一起，但那真是一团糟。如果您有任何建议，请告诉我：）

Answer 1

首先，暴力解决方案几乎不需要任何时间来运行。在

正如@MooingRawr建议的那样，如果使用itertools.permutations则只有~0.9x9！不以零开头的0123456789排列。在

from itertools import permutations

primes = [17, 13, 11, 7, 5, 3, 2]

total = 0

# Generate permutations of 10 distict digits   10 factorial
for i in permutations('0123456789'):

  # Discard those that begin with zero   one-tenth of 10!
  if i[0] == '0':
    continue 

  # Convert into a string and assume that it is valid
  n = ''.join(list(i))
  valid = True

  # Check if the last three digits are divisible by 17, ...
  #    ... then shift left and check if those digits are divisible by 13, etc.
  for j in xrange(0, len(primes)):
    x = n[len(primes) - j:len(primes) - j + 3]
    if int(x) % primes[j]:
      valid = False
      break

  # Print and add
  if valid:
    print 'Valid number: %s' % n
    total += int(n)

print 'Total: %d' % total

如果您运行这个解决方案here，它将在几秒钟内运行，这对于PE来说应该没问题。在

不过，你建议的方法确实更有效。注意，您已经硬编码了七个循环，我只是使用factors来生成它们，其中factor[i]是一个系数d_I+1 d_I+2。在

您担心生成所有的组合，但是使用递归这很简单，每次迭代都检查最后两个数字并找到下一个有效的数字。在

^{pr2}$

您可能希望运行解决方案here，并可能在中间步骤打印值，以查看发生了什么。在

还有很多机会可以删减已探索状态的数量。你的方法使它从3265920下降到3000左右。在