数字和，性质，提示请

Question

数字和，性质，提示请

4

这是问题:

有多少个整数 0 ≤ n < 10^18 满足n的每一位数字之和等于137n的每一位数字之和？

这个解决方案非常低效。我错过了什么吗？

#!/usr/bin/env python
#coding: utf-8

import time
from timestrings import *

start = time.clock()

maxpower = 18
count = 0

for i in range(0, 10 ** maxpower - 1):
    if i % 9 == 0:
        result1 = list(str(i))
        result2 = list(str(137 * i))
        sum1 = 0
        for j in result1:
            sum1 += int(j)
        sum2 = 0
        for j in result2:
            sum2 += int(j)
        if sum1 == sum2:
            print (i, sum1)
            count += 1

finish = time.clock()

print ("Project Euler, Project 290")
print ()
print ("Answer:", count)
print ("Time:", stringifytime(finish - start))

- debragail

3个回答

4

你正在尝试通过暴力破解来解决一个Project Euler问题。这可能适用于前几个问题，但对于大多数问题，你需要考虑更复杂的方法。

由于根据此问题提供具体建议不太合适，因此请查看此答案中的通用建议。

- starblue

0

这个暴力破解的 Python 解决方案有 7 位数字，对我来说运行了 19 秒：

print sum(sum(map(int, str(n))) == sum(map(int, str(137 * n)))
          for n in xrange(0, 10 ** 7, 9))

在同一台机器上，单核心，相同的Python解释器，相同的代码，计算18位数（如问题所述）大约需要3170年。

请参考dgg32的答案，以获得更快的计数灵感。

- pts

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dgg32 · Accepted Answer

首先，你需要进行计数，而不是显示命中次数。

这非常重要。你所要做的就是设计一种高效的计数方法。就像Jon Bentley在《编程珠玑》中写道：“任何一个考虑单词所有字母排列的方法都注定会失败。”事实上，我在python中尝试过，当“i”达到10^9时，系统已经崩溃。1.5 G内存已被消耗。更不用说10^18了。这也告诉我们（再引用Bentley），“定义问题是解决问题的90%。”

为了解决这个问题，我认为没有什么方法比动态规划（dp）更好的了。事实上，那些非常巨大的欧拉问题大多需要某种形式的dp。dp本身的理论相当学术和枯燥，但是将dp的思想应用于解决实际问题并不是，实际上，这样的实践是有趣和多彩的。

该问题的一种解决方法是，我们从0-9，然后是10-99，再是100-999等等，提取数字的签名，汇总相同签名的数字，并将它们作为一个整体处理，从而节省空间和时间。

观察：

3 * 137 = 411，13 * 137 = 1781。让我们把第一个结果“411”分解成两部分：前两位“41”和最后一位“1”。 “1”保留，但是“41”部分将被“进位”到进一步的计算中。让我们把“41”称为进位，签名的第一个元素。“1”将作为最右边的数字继续计算13 * 137、23 * 137、33 * 137或43 * 137。所有这些*3的数字的最右边的数字都是“3”，而137 * n的最后一位数字总是1。也就是说，这个“3”和“1”的差别是+2，将其称为签名的第二个元素+2。

好了，如果我们要找到以3为结尾的两位数，那么我们必须找到一个数字“m”，满足

diff_of_digitsum（m，137 * m + carry）=-2

来抵消我们之前累积的+2差异。如果m可以做到这一点，那么你知道m * 10 + 3，在纸上写成：“m3”，就是一个命中。

例如，在我们的例子中，我们尝试了数字1。diff_of_digitsum（digit，137 * digit + carry）= diff_of_digitsum（1，137 * 1 + 41）= -15。这不是-2，所以13不是一个命中。

让我们来看一下99.9 * 137 = 1233。"差异"是9 - 3 = +6。"进位"是123。在第二次迭代中，当我们尝试将数字9加到9并使其变成99时，我们有diff_of_digitsum（digit，137*digit+carry）= diff_of_digitsum（9，137*9+123）= diff_of_digitsum（9，1356）= -6，这抵消了我们的剩余6。所以99是一个命中！在代码中，我们只需要18次迭代。在第一轮中，我们处理单个数字，第二轮处理两位数，然后是三位数......直到我们到达18位数。在迭代之前制作一张表格，其结构如下：

table[(diff, carry)] = amount_of_numbers_with_the_same_diff_and_carry

然后开始迭代，需要在进行时不断更新表格。如果遇到新的签名，请添加新条目，并始终更新amount_of_numbers_with_the_same_diff_and_carry。第一轮是个位数，填充表格：

0：0 * 137 = 0，差异：0；进位：0。table[(0,0)] = 1

1：1 * 137 = 137，差异：1-7 = -6；进位：13。table[(-6,13)] = 1

2：2 * 137 = 274，差异：2-7 = -5；进位：27。table[(-5,27)] = 1

以此类推。

第二轮是“10”的数字，我们将检查数字0-9作为“m”并在（1）中使用它来查看是否可以产生抵消“diff”的结果。如果是，则表示该m将使所有amount_of_numbers_with_the_same_diff_and_carry成为命中。因此不计入计数。然后，我们可以使用添加了此数字的新diff和carry计算新的表格，例如，9具有diff 6和carry 123，但99具有diff 9-6（1356的最后一位数字）= 3和carry 135，使用新信息替换旧表格。

最后注意，要小心数字0。它会在迭代中出现很多次，不要过度计数，因为0009 = 009 = 09 = 9。如果使用c ++，请确保总和为unsigned long long并且进行排序，因为它很大。祝你好运。