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

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 1147 | 回复: 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张SACC2017门票等你来拿~

在数字化转型时代,云已成为万物智能的数字化大脑。而随着大数据应用、人工智能、移动互联网等技术的飞速发展,“智慧 +” 的概念正在深入到各行各业,提升企业效率,释放商业潜能,创造全新机遇。作为国内顶级技术盛会之一,2017 中国系统架构师大会(SACC2017)将于 10 月 19-21 日在北京新云南皇冠假日酒店震撼来袭。今年,大会以 “云智未来” 为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置 2 大主会场,18 个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100 余位技术专家及行业领袖来分享他们的经验;并将吸引 4000 + 人次的系统运维、架构师及 IT 决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年10月19日前

活动链接>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP