亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

Chinaunix

標題: Project Euler - 014 [打印本頁]
作者: icymirror    時間: 2015-09-30 11:07
標題: Project Euler - 014
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:
下面是對正整數(shù)定義的操作序列：

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

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

代碼：

  2. package main

  4. import (
  5.         "fmt"
  6. )

  8. func FindCollatzPathLength(number int, knownPath map[int]int) int {
  9.         var result int = 0
  10.         path := make([]int, 0)

  12.         for {
  13.                 if steps, exist := knownPath[number]; exist {
  14.                         // Update all data into knownPath
  15.                         offset := len(path)
  16.                         result = offset + knownPath[number]

  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.         }

  35.         return result
  36. }

  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. }

  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    時間: 2015-10-09 11:18
回復(fù) 1# icymirror


There is a problem while provided number above 100000


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

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


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

int64 是一個解決方案




歡迎光臨 Chinaunix (http://72891.cn/) Powered by Discuz! X3.2