论坛徽章:: 4

电梯直达

1楼 [收藏(0)] [报告]

发表于 2015-09-30 11:07 |只看该作者 |倒序浏览

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.

问题14:
下面是对正整数定义的操作序列：

n → n/2 (n是偶数)
n → 3n + 1 (n是奇数)

当对13使用上面的规则时，我们得到下面的序列：
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
可以发现这个序列包含10个项。虽然还没有被证明(Collatz问题)，但是一致认为所有正数会收敛到1.
试找出1000000以内，到达1时产生最长序列的数是哪个。
说明：当序列运算开始之后，序列中的想允许超过1000000。

代码：

package main
import (
"fmt"
)
func FindCollatzPathLength(number int, knownPath map[int]int) int {
var result int = 0
path := make([]int, 0)
for {
if steps, exist := knownPath[number]; exist {
// Update all data into knownPath
offset := len(path)
result = offset + knownPath[number]
// Below steps to merge current data into record for future speed up
for index, value := range path {
knownPath[value] = steps + offset - index
}
break
} else {
path = append(path, number)
if number%2 == 0 {
// even number handling
number = number / 2
} else {
// odd number handling
number = number*3 + 1
}
}
}
return result
}
func Problem014(scope int) int{
var max_steps int = 0
var result int = 0
paths := make(map[int]int)
paths[1] = 1
paths[2] = 2
paths[4] = 3
for number := 0; number < scope; number++ {
steps := FindCollatzPathLength(number + 1, paths)
if steps > max_steps {
max_steps = steps
result = number + 1
}
}
return result
}
func main() {
// There is a problem while provided number above 100000, try update code later.
fmt.Println("Problem 014 result: ", Problem014(1000000))
}