忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 视频 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 910 | 回复: 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 是一个解决方案
您需要登录后才可以回帖 登录 | 注册

本版积分规则

久等啦!10张门票开启你的DTCC2017之旅

2017中国数据库技术大会将于2017年5月11-13日如约而至,本届大会以“数据驱动•价值发现”为主题,共设定2大主场和21个技术专场,云集海内外120+位技术大牛,共同探讨Oracle、MySQL、NoSQL、云端数据库、区块链、深度学习等领域的前瞻性热点话题。
即日起,填写DTCC2017会前调查问卷,即有机会赢取价值2600元的大会门票1张!仅限10张!
----------------------------------------
活动截止时间:2017年5月5日统一公布

问卷入口>>
  

北京皓辰网域网络信息技术有限公司. 版权所有 京ICP证:060528号 北京市公安局海淀分局网监中心备案编号:1101082001
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP