2008-03-25 Ruby 测试题(00006)

题目取自php?name=Euler" onclick="tagshow(event)" class="t_tag">Euler-14
3N+1猜想，任意一个自然数K，对其进行如下操作：
n → n/2 (n为偶数)
n → 3n + 1 (n为奇数)
比如：13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
3N+1猜想认为，所有自然数都可以经过这样一系列变化最终得到1。
13就是经历了9步之后变成了1。
现在的问题是，在K<10000时，哪个自然数经历了最长的序列才变成1的。

今天的题目要的是比快。10000只是一个测试数，写完了之后可以看看1000000的运行时间是多少。
这道题我写的并不是很好，就先不贴出来了。我的程序在算10000时大概2秒不到，100000在10秒。

中规中矩的。 BS一下自己。
而且速度很慢……

楼上的跟我想法一样，就是把历史记录留下来，可以少做很多判断。
记录也有不一样，楼上的做法是把曾经算过的步数留下来。我的做法是发现我是人家路上的就结束不计算。
在100000级别上，楼上的比我快。
但是我的100W能出解。

[ 本帖最后由 jmouse 于 2008-3-25 14:49 编辑 ]

没想出什么特别好的办法，基本上还是原来的答案。
Ruby这东西看机器的，不知道我的算法在jmouse机器上要花多久。

love8909的问题我知道了，因为有3×n+1存在，所以数组下标越界了。
稍微改一下就可以了。
把

呵呵，在没有更好的选择下，我也情愿选择自己的第2个程序，慢1点点就慢1点点~
毕竟可读性强多了~

再提升一小步。
用位运算
elsif num % 2 == 0
    num /= 2
改成
elsif (num & 1) == 0
    num >>= 1

厄 我是小菜，有个可能很傻的想法 ： 能不能从1往上推呢？
   1
    / \
  2   X
  / \
 4  X 
 / \
8 1
.......