24小时热门版块排行榜

返回列表

本帖产生 4 个程序强帖，点击这里进行查看

当前只显示满足指定条件的回帖，点击这里查看本话题的所有回帖

holmescn

金虫 (正式写手)

程序强帖: 37
应助: 1 (幼儿园)
金币: 1918.8
散金: 275
红花: 1
帖子: 699
在线: 102.6小时
虫号: 913482
注册: 2009-11-26
性别: GG
专业: 凝聚态物性 II ：电子结构

[交流] Euler 工程第14题：找最长的数列已有6人参与

周末了，放个题出来玩玩：

定义一个正整数数列，其迭代公式为：
n = n/2 (当n为偶数)
n = 3n+1 (当n为奇数)

比如从n=13开始，计算这个数列得：
13 ->40->20->10->5->16->8->4->1
这个数列一共有10项。
这个数列是不是总收敛到1还是个没有解决的问题（称为Collatz Problem)
不过，我们并不是要解这个难题，而是要求在小于1百万的所有起始数中，哪个数能产生最长的数列。

这里要注意的是，数列中间的项是可以大于1百万的，要看提最后数列终止到1时候的长度。

PS：这东西不能用归纳法证出来吗？
PS2：注意1分钟原则啊。不过，大于1分钟的程序也可以发上来，这样才有的交流。

Here we go!

回复此楼

» 猜你喜欢

2025年遐想已经有4人回复
投稿Elsevier的杂志（返修），总是在选择OA和subscription界面被踢皮球已经有8人回复
自然科学基金委宣布启动申请书“瘦身提质”行动已经有4人回复
求个博导看看已经有18人回复

» 本主题相关价值贴推荐，对您同样有帮助:

Euler 工程第四十四题已经有4人回复
Euler 工程第四十二题: 三角词已经有4人回复
Euler 工程第四十一题已经有5人回复
Euler 工程第三十八题已经有9人回复
Euler 工程第三十七题已经有6人回复
Euler 工程第三十六题：已经有18人回复
Euler 工程第三十五题：循环质数已经有16人回复
Euler 工程第三十二题：pandigital 数已经有3人回复
Euler 工程第三十一题: 换零钱已经有10人回复
Euler 工程第三十题已经有12人回复
Euler 工程第廿九题：有多少不同的项? 已经有30人回复
Euler 工程第廿八题：旋转矩阵对角线的和已经有6人回复
Euler 工程第廿七题：系数的积已经有15人回复
Euler 工程第廿六题：最长的循环节已经有9人回复
Euler 工程第廿五题：Fibonacci 数列第一个包含1000个数字的项已经有3人回复
Euler 工程第廿四题：全排列的第100万项已经有19人回复
Euler 工程第廿三题：已经有16人回复
Euler 工程第廿二题: 姓的总分已经有13人回复
Euler 工程第廿题：100! 的各项和已经有5人回复
Euler 工程第十九题：每月第一天是周日的天数已经有4人回复
Euler 工程第十八题：三角阵上最大的和已经有12人回复
Euler 工程第十六题：2的1000次方的各项和已经有14人回复
Euler 工程第十一题：相邻元素乘积最大已经有10人回复
Euler 工程第三题：寻找600851475143的最大质因子已经有18人回复

1楼 2011-05-20 16:41:24

已阅回复此楼关注TA 给TA发消息送TA红花 TA的回帖

holmescn

金虫 (正式写手)

程序强帖: 37
应助: 1 (幼儿园)
金币: 1918.8
散金: 275
红花: 1
帖子: 699
在线: 102.6小时
虫号: 913482
注册: 2009-11-26
性别: GG
专业: 凝聚态物性 II ：电子结构

微尘、梦想(程序强帖+1): 2011-05-21 19:19:52

matlab果然是不给力啊，Fortran版的只要0.75s

CODE:

Program euler14

    Implicit None

    Integer :: maxLen = 0, l

    Integer(8) :: n

    Integer :: start, maxStart

    Real :: t1, t2

    Call CPU_Time(t1)

    Do start = 2, 1000000

        n = start

        l = 0

        Do While (n .gt. 1) 

            If(mod(n, 2) .eq. 0) Then

                n = n / 2

            Else

                n = 3*n + 1

            EndIf

            l = l + 1

        EndDo

        l = l + 1

        If(l .gt. maxLen) Then

            maxLen = l

            maxStart = start

        EndIf

    EndDo

    Call CPU_Time(t2)

    Print *, "Result:", maxStart, maxLen, t2-t1

End Program euler14

结果同libralibra同学。不过恐怖的是，中间项居然会大于40亿啊。32位整数都保存不了了。最后总共有525项。这东西用Mathematica的NestList展开会是什么样？

现在的计算机速度太快了，以至于我们都不想去找一个更好的解法了，不过，这东西的解空间应该还能减小，我看到2到3000以内都还是单调上涨的呢。