我正在嘗試完成Project Euler 問題 #30，我決定根據(jù)已知答案驗(yàn)證我的代碼。基本上問題是這樣的：找出所有可以寫成它們數(shù)字的五次方之和的數(shù)字的總和。這是我試圖用python證明的已知答案：1634 = 1^4 + 6^4 + 3^4 + 4^48208 = 8^4 + 2^4 + 0^4 + 8^49474 = 9^4 + 4^4 + 7^4 + 4^4由于 1 = 1^4 不是總和，因此不包括在內(nèi)。這些數(shù)字的總和是 1634 + 8208 + 9474 = 19316。當(dāng)我運(yùn)行我的代碼時(shí)，我得到所有三個(gè)加起來為 19316 的值，太棒了！但是在這些值中有一個(gè)不正確的值：6688這是我的代碼：i=1answer = []while True: list = [] i=i+1 digits = [int(x) for x in str(i)] for x in digits: a = x**4 list.append(a) if sum(list) == i: print(sum(list)) answer.append(sum(list))list返回三個(gè)正確值的總和，以及 value 6688。有人能發(fā)現(xiàn)我錯(cuò)過的東西嗎？
2 回答
幕布斯6054654
TA貢獻(xiàn)1876條經(jīng)驗(yàn) 獲得超7個(gè)贊
你過早地檢查總和。您檢查數(shù)字中每個(gè)單獨(dú)數(shù)字的匹配總和，并且6 ^ 4 + 6 ^ 4 + 8 ^ 4是6688。那是三個(gè)數(shù)字，而不是全部四個(gè)數(shù)字。
將你的sum()測(cè)試出你的for循環(huán)：
for x in digits:
a = x**4
list.append(a)
if sum(list) == i:
print(sum(list))
answer.append(sum(list))
當(dāng)總和已經(jīng)超過目標(biāo)時(shí)，您最多可以盡早丟棄一個(gè)數(shù)字：
digitsum = 0
for d in digits:
digitsum += d ** 4
if digitsum > i:
break
else:
if digitsum == i:
answer.append(i)
但我不會(huì)在這里打擾，只需使用生成器表達(dá)式來組合確定數(shù)字，將它們提高到 4 次方，然后求和：
if sum(int(d) ** 4 for d in str(i)) == i:
answer.append(i)
您尚未定義上限，即數(shù)字始終大于數(shù)字總和并且您需要停止遞增的點(diǎn)i。對(duì)于 n 次方的總和，您可以通過取 9 ^ n，計(jì)算其位數(shù)，然后取9的 n 次方乘以9的 n 次方的位數(shù)來找到這樣的點(diǎn)。如果這會(huì)創(chuàng)建一個(gè)具有更多位數(shù)的數(shù)字，請(qǐng)繼續(xù)操作，直到位數(shù)不再變化。
本著同樣的精神，你就可以開始i在max(10, 1 + 2 ** n)，因?yàn)槟憔涂梢詮臄?shù)字來最小總和將使用一個(gè)單一的2數(shù)字加的最小數(shù)目1和0數(shù)字，你可以逃脫，并在任何功率大于1， 1 和 0 以外的數(shù)字的冪總是大于數(shù)字值本身，您不能使用i = 1：
def determine_bounds(n):
"""Given a power n > 1, return the lower and upper bounds in which to search"""
nine_power, digit_count = 9 ** n, 1
while True:
upper = digit_count * nine_power
new_count = len(str(upper))
if new_count == digit_count:
return max(10, 2 ** n), upper
digit_count = new_count
如果將上述函數(shù)與range(*<expression>)傳遞給的可變長(zhǎng)度參數(shù)結(jié)合起來range()，則可以使用for循環(huán)：
for i in range(*determine_bounds(4)):
# ...
您可以n在函數(shù)中確定一個(gè)數(shù)字是否等于其數(shù)字的總和到給定的冪：
def is_digit_power_sum(i, n):
return sum(int(d) ** n for d in str(i)) == i
然后您可以將所有內(nèi)容放入列表理解中：
>>> n = 4
>>> [i for i in range(*determine_bounds(n)) if is_digit_power_sum(i, n)]
[1634, 8208, 9474]
>>> n = 5
>>> [i for i in range(*determine_bounds(n)) if is_digit_power_sum(i, n)]
[4150, 4151, 54748, 92727, 93084, 194979]
將is_digit_power_sum()可受益于權(quán)力的高速緩存; 添加緩存使函數(shù)對(duì)于 4 位輸入的速度提高兩倍以上：
def is_digit_power_sum(i, n, _cache={}):
try:
powers = _cache[n]
except KeyError:
powers = _cache[n] = {str(d): d ** n for d in range(10)}
return sum(powers[d] for d in str(i)) == i
當(dāng)然，問題的解決方案是數(shù)字的總和：
n = 5
answer = sum(i for i in range(*determine_bounds(n)) if is_digit_power_sum(i, n))
print(answer)
它在我的 2.9 GHz Intel Core i7 MacBook Pro 上使用 Python 3.8.0a3 在不到半秒的時(shí)間內(nèi)產(chǎn)生所需的輸出。
哈士奇WWW
TA貢獻(xiàn)1799條經(jīng)驗(yàn) 獲得超6個(gè)贊
這里固定：
i=1
answer = []
while True:
list = []
i=i+1
digits = [int(x) for x in str(i)]
for x in digits:
a = x**4
list.append(a)
if sum(list) == i and len(list) == 4:
print(sum(list))
answer.append(sum(list))
我發(fā)現(xiàn)的錯(cuò)誤：
6^4+6^4+8^4 = 6688
所以我只是檢查了列表的 len。
添加回答
舉報(bào)
0/150
提交
取消