在Python中用bruteforce解決歐拉＃14

Question

我試圖用python暴力破解euler problem 14，但沒有取得太大的成功。

我使用了itertools模塊，但速度太慢。然後我找到解決問題的公式。

有沒有辦法用bruteforce解決問題？

Answer 1

您可以將中間值存儲在字典中並進行一種動態編程。

numbers = {1:0} 
max = -1 
startMax = -1 
for i in range(2, 1000 000): 
    n = i 
    steps = 0 
    while n>=i: 
     if n&2 == 0: 
      n = n/2 
     else: 
      n = 3*n + 1 
     steps = steps + 1 
    # n < i, hence it must already be stored in the dictionary 
    steps = steps + numbers[n] 
    if steps > max: 
     max = steps 
     startMax = i 
    numbers[i] = steps 
    return startMax 

另一種方法可能是存儲您遇到的每個號碼，並始終檢查您當前所在號碼是否在地圖中。但我想，這可能需要更長的時間有這麼多的字典查詢，UPS：

numbers = {1:0} 
max = -1 
for i in range(2, 1000 000): 
    if i in numbers: 
     steps = numbers[i] 
    else: 
     n = i 
     steps = 0 
     found = False 

     while not found: 
      if n&2 == 0: 
       n = n/2 
      else: 
       n = 3*n + 1 
      if n in numbers: 
       steps = numbers[n] 
       found = True 
      else: 
       newNumbers.append(n) 
     # Store all the new numbers into the dictionary 
     for num in newNumbers: 
      steps = steps + 1 
      numbers[num] = steps 
    if steps>max: 
     max = steps 
     startMax = i 
return startMax 

您可能需要做一些測試，以找出哪一個是好，但我的選擇將是放在了第一位。

Answer 2

pypy是「優化開啓的python」。

從這裏下載： http://pypy.org/download.html#default-with-a-jit-compiler

要使用它，只寫pypy這裏你通常寫python。它非常兼容。主要區別在於爲python編寫的基於C的擴展在pypy中不起作用，儘管許多人正在努力解決這個問題。

---

我覺得不得不捍衛我的答案。鑑於這種非常簡單的蠻力解決方案：

"Solve Project-Eueler #14" 
from collections import namedtuple 
Chain = namedtuple('Chain', 'length, start') 


def calculate_chain(i): 
    start = i 
    length = 1 
    while i != 1: 
     length += 1 
     if i & 1: # `i` is odd 
      i = 3 * i + 1 
     else: 
      # Divide by two, efficiently. 
      i = i >> 1 
    return Chain(length, start) 

def find_largest_chain(maxint): 
    largest_chain = Chain(0, 0) 
    for i in xrange(1, maxint+1): 
     chain = calculate_chain(i) 
     if chain > largest_chain: 
      largest_chain = chain 
    return largest_chain 


def commandline_interface(): 
    from sys import argv 
    maxint = int(argv[1]) 
    print find_largest_chain(maxint) 

if __name__ == '__main__': 
    commandline_interface() 

在Python運行時爲23秒：

$ /usr/bin/time python 10177836.py 999999 
Chain(length=525, start=837799) 
22.94user 0.04system 0:23.09elapsed 99%CPU (0avgtext+0avgdata 15648maxresident)k 
0inputs+0outputs (0major+1109minor)pagefaults 0swaps 

，並在pypy這是0.93秒：

$ /usr/bin/time ~/packages/pypy-1.8/bin/pypy 10177836.py 999999 
Chain(length=525, start=837799) 
0.66user 0.10system 0:00.93elapsed 81%CPU (0avgtext+0avgdata 63152maxresident)k 
48inputs+0outputs (1major+4194minor)pagefaults 0swaps 

只需用pypy產量使用特定算法提高了2373％的速度。我沒有看到爲什麼OP沒有看到他自己的代碼有類似的改進。