免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1665 | 回复: 1

[其他] Project Euler - 014 [复制链接]

论坛徽章:
4
白羊座
日期:2013-11-05 10:26:09冥斗士
日期:2015-11-17 14:19:55白银圣斗士
日期:2015-11-17 15:13:0815-16赛季CBA联赛之新疆
日期:2016-04-01 09:10:58
发表于 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。

代码:

  1. package main

  2. import (
  3.         "fmt"
  4. )

  5. func FindCollatzPathLength(number int, knownPath map[int]int) int {
  6.         var result int = 0
  7.         path := make([]int, 0)

  8.         for {
  9.                 if steps, exist := knownPath[number]; exist {
  10.                         // Update all data into knownPath
  11.                         offset := len(path)
  12.                         result = offset + knownPath[number]

  13.                         // Below steps to merge current data into record for future speed up
  14.                         for index, value := range path {
  15.                                 knownPath[value] = steps + offset - index
  16.                         }
  17.                         break
  18.                 } else {
  19.                         path = append(path, number)
  20.                         if number%2 == 0 {
  21.                                 // even number handling
  22.                                 number = number / 2
  23.                         } else {
  24.                                 // odd number handling
  25.                                 number = number*3 + 1
  26.                         }
  27.                 }
  28.         }

  29.         return result
  30. }

  31. func Problem014(scope int) int{
  32.         var max_steps int = 0
  33.         var result int = 0
  34.        
  35.         paths := make(map[int]int)
  36.         paths[1] = 1
  37.         paths[2] = 2
  38.         paths[4] = 3
  39.        
  40.         for number := 0; number < scope; number++ {
  41.                 steps := FindCollatzPathLength(number + 1, paths)
  42.                 if steps > max_steps {
  43.                         max_steps = steps
  44.                         result = number + 1
  45.                 }
  46.         }
  47.         return result
  48. }

  49. func main() {
  50.         // There is a problem while provided number above 100000, try update code later.
  51.         fmt.Println("Problem 014 result: ", Problem014(1000000))
  52. }
复制代码

论坛徽章:
0
发表于 2015-10-09 11:18 |显示全部楼层
回复 1# icymirror


There is a problem while provided number above 100000


也许问题是 int32
当 number = 113383

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


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

int64 是一个解决方案
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会 限时8.5折

【架构革新 高效可控】2020年8月17日~19日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP