當然有更好的方法。你應該建立自下而上的數字,也就是說,如果一個數字a1 ... ak(這些數字是k數字)的數量不是N,那麼在結果的前k個數字中出現兩次數字,對於任何被乘數2..N,那麼既不是任何數字b1 ... bm a1 ... ak。這提供了一個分類更快的遞歸枚舉過程,因爲它將指數量的搜索空間分割開來。作爲OP的練習留下了細節。
較長的解釋:
假設有計算用於在10個鹼基所代表的數number_str
大小的過程
magnitude(number_str)
,因此該過程返回0,如果number_str
含有至少一個雙如果number_str
每個數字都不同,但是將數字乘以2會導致數字出現多次,那麼將出現1個數字。
此過程c一個可以在另一個
unique_digits(number_str)
如果number_str
所有的數字都是獨特返回true條款執行,否則爲false。
現在然後magnitude
可以被實現爲
magnitude(number_str):
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(int_to_str(k))):
k = k + n
i = i + 1
return i
現在這個magnitude
過程可以被改變爲nocarry_magnitude
巧妙地改變檢查:
nocarry_magnitude(number_str, limit):
l = length(number_str)
assert (l > 0)
n = str_to_int(number_str)
k = n
i = 0
while (unique_digits(right_substring(int_to_str(k), l))):
k = k + n
i = i + 1
if (i == limit):
break
return i
發生的數字的多次該過程檢查只有在循環中產品的最右邊數字(最低位數字)與原始輸入中的數字一樣多。需要一個限制參數來確保過程終止,否則該過程可能在無限循環中運行。顯然,對於任何字符串s
它認爲
magnitude(s) <= nocarry_magnitude(s, M) for large M
例如,拿號19:
19 * 1 = 19
19 * 2 = 38
19 * 3 = 57
19 * 4 = 76
19 * 5 = 95
19 * 6 = 114 // magnitude("19") = 5
19 * 7 = 133 // nocarry_magnitude("19", 100) = 6
我在上面的簡短描述寫的是,如果
nocarry_magnitude(s, x) == k for x > k
那麼對於任何通過後綴s
(下面表示爲x + s
)獲得的字符串,它認爲
x : string of digits
magnitude(x + s) <= nocarry_magnitude(x + s, m) <= nocarry_magnitude(s, m)
when m >= magnitude(x + s)
第一個不平等來自上述要求,第二個不平等來自nocarry_magnitude
的定義。注意,幅度(X + S)= <幅度(S)是一種非定理通常通過
magnitude("56") = 1 // 56 * 2 = 112
magnitude("256") = 12 // the first duplicate occurs at 3328
其由進位引起的所例示。 nocarry_magnitude
忽略了進位這就是爲什麼字符串的後綴總是與它的任何延伸(向左,即更高位數字)一樣大的非零值。
那麼現在你可以寫一個顯著更快的遞歸過程,因爲這與幅度至少M個搜索數字:
search(str):
if (str != ""):
int n = nocarry_magnitude(str, M)
if (n < M):
return # the optimization
int k = magnitude(str)
if (k >= M):
store_answer(str)
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + str)
search("")
這裏是一個完整的Python實現(搜索幅度36):
def unique_digits(s):
r = (len(list(s)) == len(set(s)))
return r
def magnitude(s):
n = int(s)
k = n
assert n > 0
i = 0
while (unique_digits(str(k))):
k = k + n
i = i + 1
return i
def nocarry_magnitude(s, limit):
l = len(s)
assert l > 0
n = int(s)
assert n > 0
k = n
i = 0
while (unique_digits(str(k)[-l:])):
k = k + n
i = i + 1
if (i >= limit):
break
return i
M = 36
def search(s):
if (not(s == "")):
n = nocarry_magnitude(s, M)
if (n < M):
return
k = magnitude(s)
if (k >= M):
print "Answer: %s |" % s,
i = int(s)
k = i
n = 1
while (n <= M):
print k,
k = k + i
n = n + 1
print
for d in ['1', '2', '3', '4', '5', '6', '7', '8', '9',
'10', '20', '30', '40', '50', '60', '70', '80', '90']:
search(d + s)
search("")
這是一個只需不到一秒的運行;這找到了答案'27'這似乎是提供記錄幅度36的唯一數字:
Answer: 27 | 27 54 81 108 135 162 189 216 243 270 297 324 351 378 405
432 459 486 513 540 567 594 621 648 675 702 729 756 783
810 837 864 891 918 945 972
好的,加了更長的解釋 – 2011-05-10 16:13:22