Python邏輯 - 歐拉62

我想通過解決projecteuler.net問題來學習python。我一直在試圖解決問題62，但我無法找到我要出錯的地方。因此，問題指出：Python邏輯 - 歐拉62

The cube, 41063625 (345^3), can be permuted to produce two other cubes: 56623104 (384^3) and 66430125 (405^3). 
In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube. 
Find the smallest cube for which exactly five permutations of its digits are cube.

我對解決這個問題的邏輯：
- 產生多達10000立方體並將其存儲在一組
- 對於集合中的每個立方體（從最大的開始），找到可以使用數字中的數字形成的最大數字。如果兩個立方體具有相同的數字，它們將形成相同的最大數量。
- 將這些最大數量存儲在另一組中。如果最大數量已經在該組中，則增加與該最大數量相對應的計數器。
- 如果計數器爲5，則停止。

這是我爲實現上述邏輯而編寫的代碼。它給了我140283769536的答案，但這不是正確的答案。我哪裏錯了？

def maxperm(number): 
    maxnum=0 
    digits=[0 for x in range(10)] 
    while number>0: 
     digits[number%10]+=1 
     number/=10 
    numdigits=sum(digits) 
    for i in range(9,-1,-1): 
     if digits[i]>0: 
      for x in range(digits[i]): 
       numdigits-=1 
       maxnum+=i*10**numdigits 
    return maxnum 

uniquecubes=dict() 
cubes=[x**3 for x in range(10000)] 
cubeset=set(cubes) 
maxperms=set() 

for i in reversed(cubes): 
    a=maxperm(i) 
    if a in maxperms: 
     uniquecubes[a]+=1 
     if uniquecubes[a]==5: 
      print i 
      break 
    else: 
     uniquecubes[a]=1 
     maxperms.add(a)

來源

2016-01-22 Naren

我懷疑你的算法是錯誤的。有兩件事我能想到。 1：有這些數字的第六個立方體（不太可能）。 2：你沒有選擇5個立方體中最小的一個（但其他四個中的一個）。或者，也許'maxperm'壞了？您的算法是否爲簡單案例提供了正確的結果？ –

更好地看待您的算法：確實可能出現小型解決方案。嘗試從1開始向上工作，而不是從大數字向下工作。 –

謝謝Sjoerd，我檢查了maxperm - 它確實給出了正確的結果。如果我向上工作，我會結束最大的魔方，對吧？這就是爲什麼我想從頂端開始。 – Naren

的算法旨在發現是否存在5個最低排列，同時也是多維數據集，這是不問的問題。

解決方案1：修改算法以檢查第6條是否存在，如果存在，則垃圾回答並繼續查找。

解決方案2（首選）：有一個函數permCheck()需要一個立方體，創建該立方體數字的每個置換，並返回多少個置換也是立方體。一旦你有：

int i = 1 
while True: 
    if permCheck(i*i*i) == 5: 
     break 
    i += 1 
return i*i*i # i^3 is now the answer

來源

2016-01-22 21:22:12 James

謝謝！我認爲只有一個立方體有5個排列也是立方體。原來還有另一個。我刪除了中斷，並將所有結果附加到列表中，並從列表中提取最小值。 – Naren

Python邏輯 - 歐拉62

回答

相關問題