看到别人的 Racket 版，心里痒痒，写了个 Haskell 版。只用了尾递归，没用什么高级特性。题目地址。
calc3xp1 :: Int -> Int
calc3xp1 n | even n = n `div` 2
| otherwise = 3 * n + 1
countlen :: Int -> Int
countlen = countlen_tail 0
countlen_tail :: Int -> Int -> Int
countlen_tail c n | n == 1 = c
| otherwise = countlen_tail (c+1) $ calc3xp1 n
findmax :: Int -> Int
findmax = findmax_tail 1 1 1
findmax_tail max maxn n final | n >= final = maxn
| otherwise = if new_len > max
then findmax_tail new_len n n' final
else findmax_tail max maxn n' final
where new_len = countlen n
n' = n + 1
main = print $ findmax 1000000
>>> time ./3xp1 ./3xp1 14.92s user 0.02s system 99% cpu 14.955 total
Erlang 版本直接照抄 Haskell 版：
-module(e3xp1).
-export([main/1]).
calc3xp1(N) when N rem 2 == 0 ->
N div 2;
calc3xp1(N) ->
3 * N + 1.
countlen(N) -> countlen_tail(0, N).
countlen_tail(C, 1) ->
C;
countlen_tail(C, N) ->
countlen_tail(C+1, calc3xp1(N)).
findmax(N) ->
findmax_tail(1, 1, 1, N).
findmax_tail(_, Maxn, N, Final) when N >= Final ->
Maxn;
findmax_tail(Max, Maxn, N, Final) ->
Newlen = countlen(N),
if Newlen > Max -> findmax_tail(Newlen, N, N+1, Final);
true -> findmax_tail(Max, Maxn, N+1, Final)
end.
main(_) ->
io:format("~B~n", [findmax(1000000)]).
它在六分钟后还没能输出结果……
>>> time escript e3xp1.erl ^C escript e3xp1.erl 374.55s user 0.94s system 99% cpu 6:15.76 total
Racket 版在同一机器上用时：
>>> time racket 3xp1.racket racket 3xp1.racket 3.22s user 0.22s system 99% cpu 3.448 total
这是为什么呢？
PS: C 更快，不到半秒就搞定了……
更新：又试了试 Lua 版本的，和 Haskell 版速度相当。但是——LuaJIT 竟然只 2.4s 出结果，因为换了机器，所以实际上它应该比 Racket 版快一倍以上。
再次更新：Erlang 版编译后还是挺快的：
>>> erlc e3xp1.erl >>> time erl -noshell -s e3xp1 main -s init stop erl -noshell -s e3xp1 main -s init stop 5.59s user 0.01s system 84% cpu 6.608 total
不过，它什么事都不干启动后立即停止也花了一秒多，比 Java 更厉害：
>>> time erl -noshell -s init stop erl -noshell -s init stop 0.06s user 0.01s system 6% cpu 1.077 total
2014年12月24日更新：Rust 版也非常快，而且写起来舒服：
fn calc3xpi(n: uint) -> uint { if n % 2 == 0 { n / 2 } else { 3 * n + 1 } } fn countlen(&n: &uint) -> uint { let mut c = 0; let mut x = n; while x != 1 { c += 1; x = calc3xpi(x); } c } fn findmax(n: uint) -> uint { range(1, n).max_by(countlen).unwrap() } fn main(){ let mut stdout = std::io::stdout(); stdout.write_uint(findmax(1000000)); stdout.write_char('\n'); }
