總和，性質，提示請

多少整數0 ≤ň< 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))

來源

2010-06-13 debragail

您試圖通過蠻力解決項目歐拉問題。這可能適用於前幾個問題，但對於大多數問題，您需要考慮更復雜的方法。

由於這是恕我直言，不能提供具體針對這個問題的建議，請看看this answer中的一般建議。

來源

2010-06-13 06:09:24 starblue

首先，你是來計數，而不是顯示命中。

這是非常重要的。所有你需要做的是設備一個有效的方法來計算它。像Jon Bentley在編程珍珠中寫道：「任何考慮到一個單詞的所有字母排列的方法都註定要失敗」。事實上，我嘗試了python，只要「我」擊中了10^9，系統就已經凍結了。 1.5 G內存被消耗。別說10^18。這也告訴我們，再次引用賓利，「定義這個問題大概是這場戰鬥的百分之九十。」

爲了解決這個問題，我看不到沒有動態編程（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稱爲「差異」作爲簽名的第二個元素。

OK，如果我們要找到3兩位數字作爲其最後一個數字，我們必須找到一個數字「M」是滿足

diff_of_digitsum (m, 137*m+carry) = -2 (1)

中和我們+2差異累積早。如果m可以這樣做，那麼你在你寫的紙上知道m * 10 + 3：「m3」是一個命中。例如，在我們的例子中，我們嘗試了數字1. diff_of_digitsum（digit，137 * digits + carry）= diff_of_digitsum（1,137 * 1 + 41）= -15。這不是-2，所以13不是命中。我們來看看99.9 * 137 = 1233.「diff」是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，diff：0;進位：0.表格[（0,0）] = 1

1：1 * 137 = 137. diff：1-7 = -6;攜帶：13.表格[（ - 6，13）] = 1

2：2 * 137 = 274. diff：2-7 = -5;攜帶：27.表格[（ - 5,27）] = 1

依此類推。

第二次迭代時，「10」位數字，我們將在數字0-9上作爲您的「m」並在（1）中使用它來查看它是否可以產生中和「差異」的結果。如果是的話，這意味着這將使所有這些amount_of_numbers_with_the_same_diff_and_carry變成命中。因此計數沒有顯示。然後我們可以計算新的差異，並加上這個數字，就像例9中的diff 6和carry 123但是99的差異9 - 6（最後一個數字從1356）= 3並攜帶135，替換舊錶使用新的信息。

最後的評論，小心數字0.它會在迭代中出現很多次，不要重複計算，因爲0009 = 009 = 09 = 9。如果你使用C++，確保總和在無符號長整型，因爲它很大。祝你好運。

來源

2010-07-28 01:15:59 dgg32

其實這沒有任何意義。 3 * 137 = 411和41不進入13 * 137的第二次計算。411進入它。如果有的話，41是不是攜帶，它是3 * 137/10，這就是我所看到的。你能修好你的措辭嗎？ – McTrafik 2011-01-05 18:21:00

這樣說，41 + 1 * 137 = 178和13 * 137 = 1781，看什麼？假設1781可以分爲兩部分178和1. 1是3 * 137中最左邊的數字，178是1 * 137和41的總和。41如果您從411中取出最右邊的數字，因此「攜帶」。通過進入計算，我的意思是在第二次迭代中，你現在需要的僅僅是41，並且將它保存在某種地圖中，在計算差異之後，最左邊的1可以被切掉。恕我直言，這是動態編程的精髓。 – dgg32 2011-01-11 14:46:06

Upvote正確性。這太複雜了...... – ftfish 2015-06-20 22:45:23

的7個位數這種蠻力Python的解決方案跑出了19秒，我說：

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

在同一臺機器上，單核，同Python解釋器，同樣的代碼，將需要大約3170年來計算18數字（如問題所述）。

請參閱dgg32的答案以獲得更快計數的靈感。

來源

2014-09-09 19:24:55 pts

總和，性質，提示請

回答

相關問題