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

ChinaUnix.net

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

本版积分规则

【有奖调查】AI时代如何迎接未知挑战?

人工智能一直在医疗行业扮演着重要角色,最早的专家系统和后来的基因诊断都是人工智能技术在医疗的行业探索。近年来,随着深度学习等技术的进步,人工智能在医疗行业的应用领域不断扩展,医学影像智能诊断、语音电子病历、癌症智能诊断等均已逐渐成为热门发展方向。
而作为人工智能重要推动力的深度学习技术的快速发展却亟需认知系统的强力支撑。
----------------------------------------
活动时间:2017年5月15日-6月5日

调查入口>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP