Project Euler - 014

icymirror

Problem 014:
The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

問(wèn)題14:
下面是對(duì)正整數(shù)定義的操作序列：

n → n/2 (n是偶數(shù))
n → 3n + 1 (n是奇數(shù))

當(dāng)對(duì)13使用上面的規(guī)則時(shí)，我們得到下面的序列：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
可以發(fā)現(xiàn)這個(gè)序列包含10個(gè)項(xiàng)。雖然還沒(méi)有被證明(Collatz問(wèn)題)，但是一致認(rèn)為所有正數(shù)會(huì)收斂到1.
試找出1000000以?xún)?nèi)，到達(dá)1時(shí)產(chǎn)生最長(zhǎng)序列的數(shù)是哪個(gè)。
說(shuō)明：當(dāng)序列運(yùn)算開(kāi)始之后，序列中的想允許超過(guò)1000000。

代碼：

1. 
   
2. package main
   
3. 
   
4. import (
   
5.         "fmt"
   
6. )
   
7. 
   
8. func FindCollatzPathLength(number int, knownPath map[int]int) int {
   
9.         var result int = 0
   
10.         path := make([]int, 0)
    
11. 
    
12.         for {
    
13.                 if steps, exist := knownPath[number]; exist {
    
14.                         // Update all data into knownPath
    
15.                         offset := len(path)
    
16.                         result = offset + knownPath[number]
    
17. 
    
18.                         // Below steps to merge current data into record for future speed up
    
19.                         for index, value := range path {
    
20.                                 knownPath[value] = steps + offset - index
    
21.                         }
    
22.                         break
    
23.                 } else {
    
24.                         path = append(path, number)
    
25.                         if number%2 == 0 {
    
26.                                 // even number handling
    
27.                                 number = number / 2
    
28.                         } else {
    
29.                                 // odd number handling
    
30.                                 number = number*3 + 1
    
31.                         }
    
32.                 }
    
33.         }
    
34. 
    
35.         return result
    
36. }
    
37. 
    
38. func Problem014(scope int) int{
    
39.         var max_steps int = 0
    
40.         var result int = 0
    
41.        
    
42.         paths := make(map[int]int)
    
43.         paths[1] = 1
    
44.         paths[2] = 2
    
45.         paths[4] = 3
    
46.        
    
47.         for number := 0; number < scope; number++ {
    
48.                 steps := FindCollatzPathLength(number + 1, paths)
    
49.                 if steps > max_steps {
    
50.                         max_steps = steps
    
51.                         result = number + 1
    
52.                 }
    
53.         }
    
54.         return result
    
55. }
    
56. 
    
57. func main() {
    
58.         // There is a problem while provided number above 100000, try update code later.
    
59.         fmt.Println("Problem 014 result: ", Problem014(1000000))
    
60. }
    

復(fù)制代碼

ba_du_co

回復(fù) 1# icymirror

There is a problem while provided number above 100000

也許問(wèn)題是 int32
當(dāng) number = 113383

113383, 340150, 170075 ... 827370449, 2482111348, 1241055674 ... 4, 2, 1

有一個(gè)最大的值 2482111348
大于 2147483647   (int32 2 ** 31 - 1)

int64 是一個(gè)解決方案