python - 数字总和，属性，请提示

Question

这就是问题:

How many integers 0 ≤ n < 10^18 have the property that the sum of the digits of n equals the sum of digits of 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))

Answer 1

首先，您是计数，不显示点击量 .

这是非常重要的。您所要做的就是找到一种有效的方法来计算它。就像 Jon Bentley 在 Programming Pearls 中所写的那样:“任何考虑单词所有字母排列的方法都注定要失败”。事实上，我在python中尝试过，“i”一达到10^9，系统就已经卡住了。消耗了1.5G内存。更不用说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”称为进位，即签名的第一个元素。当我们继续计算 13 * 137、23 * 137、33 * 137 或 43 * 137 时，“1”将保留为最右边的数字。所有这些 *3 数字都有一个“3”作为它们最右边的数字和最后一个数字137*n 总是1。也就是说，这个“3”和“1”之间的差是+2，把这个+2称为“diff”作为签名的第二个元素。

好的，如果我们要找到一个以 3 为最后一位的两位数，我们必须找到一个满足以下条件的数字“m”
diff_of_digitsum (m, 137*m+carry) = -2 (1)
抵消我们之前积累的 +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 次迭代。在第一轮中，我们处理单个数字，第二轮处理 2 位数字，然后是 3 位数字……直到我们得到 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) 中使用它，看看它是否可以产生抵消“差异”的结果。如果是，这意味着这个 m 将使所有这些 amount_of_numbers_with_the_same_diff_and_carry 成为命中。因此计数不显示。然后我们可以计算新的差异和添加这个数字的进位，就像在例子中 9 有差异 6 和进位 123 但 99 有差异 9 - 6(最后一位数字来自 1356)= 3 和进位 135，替换旧表使用新信息。

最后一条评论，注意数字0。它会在迭代中出现很多次，不要多计，因为0009 = 009 = 09 = 9。如果你使用c++，请确保总和是unsigned long long和那种，因为它很大。祝你好运。