ブルート フォース アプローチは、問題を解決することを意図したものではなく、その調査を支援することを目的としています。私はプロジェクト オイラーの問題に取り組んでおり、X から Y 未満の 1 までのすべての数値のうち、数値の桁数で割り切れる「部分文字列」が 1 つだけあるものを見つける必要があります。
これらは一人っ子番号と呼ばれます。104は一人っ子の数字です。その部分文字列 [1, 0, 4, 10, 04, 104] のうち、0 だけが 3 で割り切れます。この質問は、10* 17 未満で発生する 1 つの子の数の量を見つけることを求めています。力ずくの方法ではありません。正しいアプローチ; ただし、10 * 11の前に発生する 1 つの子の数の量を知る必要があるという理論があります。
ラップトップを半日放置した後でも、この番号を見つけることができませんでした. Cython を試してみましたが、私は C について何も知らない初心者プログラマーでした。結果は本当に悪かったです。クラウド コンピューティングも試しましたが、プロセスが完了する前に ssh パイプが壊れてしまいます。
誰かが、この問題に対してBRUTE FORCE メソッドを最大 10**11 まで実行するためのいくつかの異なるアプローチまたは最適化を特定するのを手伝ってくれれば、大歓迎です。
しないでください...
私はかなりの時間それに取り組んできたので、数論またはこの問題に対するあなたの答えについてアドバイスを貸してください。
## a one child number has only one "substring" divisable by the
## number of digits in the number. Example: 104 is a one child number as 0
## is the only substring which 3 may divide, of the set [1,0,4,10,04,104]
## FYI one-child numbers are positive, so the number 0 is not one-child
from multiprocessing import Pool
import os.path
def OneChild(numRange): # hopefully(10*11,1)
OneChild = []
start = numRange[0]
number = numRange[1]
## top loop handles one number at a time
## loop ends when start become larger then end
while number >= start:
## preparing to analayze one number
## for exactly one divisableSubstrings
numberString = str(start)
numDigits = len(numberString)
divisableSubstrings = 0
ticker1,ticker2 = 0, numDigits
## ticker1 starts at 0 and ends at number of digits - 1
## ticker2 starts at number of digits and ends +1 from ticker1
## an example for a three digit number: (0,3) (0,2) (0,1) (1,3) (1,2) (2,3)
while ticker1 <= numDigits+1:
while ticker2 > ticker1:
if int(numberString[ticker1:ticker2]) % numDigits == 0:
divisableSubstrings += 1
if divisableSubstrings == 2:
ticker1 = numDigits+1
ticker2 = ticker1
##Counters
ticker2 -= 1
ticker1 += 1
ticker2 = numDigits
if divisableSubstrings == 1: ## One-Child Bouncer
OneChild.append(start) ## inefficient but I want the specifics
start += 1
return (OneChild)
## Speed seems improve with more pool arguments, labeled here as cores
## Im guessing this is due to pypy preforming best when task is neither
## to large nor small
def MultiProcList(numRange,start = 1,cores = 100): # multiprocessing
print "Asked to use %i cores between %i numbers: From %s to %s" % (cores,numRange-start, start,numRange)
cores = adjustCores(numRange,start,cores)
print "Using %i cores" % (cores)
chunk = (numRange+1-start)/cores
end = chunk+start -1
total, argsList= 0, []
for i in range(cores):
# print start,end-1
argsList.append((start,end-1))
start, end = end , end + chunk
pool = Pool(processes=cores)
data = pool.map(OneChild,argsList)
for d in data:
total += len(d)
print total
## f = open("Result.txt", "w+")
## f.write(str(total))
## f.close()
def adjustCores(numRange,start,cores):
if start == 1:
start = 0
else:
pass
while (numRange-start)%cores != 0:
cores -= 1
return cores
#MultiProcList(10**7)
from timeit import Timer
t = Timer(lambda: MultiProcList(10**6))
print t.timeit(number=1)