Collat​​z猜想腳本 - Python

Question

我正在研究項目歐拉檔案中的最長Collat​​z問題，並且無法弄清楚爲什麼我需要這麼長時間。我將它與其他成功的腳本進行了比較，通常只需幾秒鐘。

下面的代碼如下，但是想法是，對於給定範圍內的每個數字，程序開始強制下降。如果在下降的任何一點發現一個數字，它已經看到並計算出下降，它只是將當前下降的長度加到先前確定的數字上。

我見過的其他代碼也是這樣，我無法弄清楚爲什麼我的速度沒有提高。我和範圍內運行多達1000並能正常工作，並吐出了所有正確的答案，但大約10,000它減緩一路下滑，而我的目標爲100萬

爲了記錄在案，我非常新的編程（一直在Python上工作一週），但對數論非常熟悉。

編輯：稍微調整了代碼，感謝Glibdud！

collatz_dic = {1:3} 
d=1 

for x in range(1,10001): 
    collatz_list = [x] 
    while x != 1: 
     if x % 2 == 0: 
      x = x/2 
      collatz_list.append(x) 
      if x in collatz_dic.keys() == True: 
       collatz_dic[d] = ((len(collatz_list)-1) + collatz_dic.get(x)) 
      else: 
       collatz_dic[d] = (len(collatz_list)-1) 
     else: 
      x = (3*x)+1 
      collatz_list.append(x) 
      if x in collatz_dic.keys() == True: 
       collatz_dic[d] = ((len(collatz_list)-1) + collatz_dic.get(x)) 
      else: 
       collatz_dic[d] = (len(collatz_list)-1) 
    d = d+1 

print(max(collatz_dic, key=collatz_dic.get)) 

Answer 1

此代碼中更顯著邏輯的缺陷是這樣一句話：（兩個occurances它可以摺疊成一個）

if x in collatz_dic.keys() == True: 
    collatz_dic[d] = ((len(collatz_list)-1) + collatz_dic.get(x)) 
else: 
    collatz_dic[d] = (len(collatz_list)-1) 

應該有break第一collatz_dic[d]分配後，你現在知道答案，所以停止你的循環！ else子句不屬於這裏，而應該是while循環的else子句，因爲我們現在還不知道答案，所以爲什麼要將當前值保存到字典中。

較小的編碼問題inlclude：if的兩半的大部分可以摺疊爲通用代碼; collatz_list不需要是一個列表，只需一個計數器;你不想做的事：

if x in collatz_dic.keys() == True: 

而是：

if x in collatz_dic: 

因爲你並不需要建立一個新的數據結構，當你手上有特別快的一個搜索。把所有這些修復了一些風格變化一起，我們得到：

collatz_dic = {1: 3} 

for d in range(2, 1_000_001): 
    x = d 

    collatz_count = 0 

    while x != 1: 
     if x % 2 == 0: 
      x = x/2 
     else: 
      x = 3 * x + 1 

     collatz_count += 1 

     if x in collatz_dic: 
      collatz_count += collatz_dic[x] 
      break 

    collatz_dic[d] = collatz_count 

print(max(collatz_dic, key=collatz_dic.get)) 

下五秒鐘1,000,000（837799）解決了，內1分鐘的時間限制好。