[ProjectEuler.net] 14

n按照下面的规则产生的序列：

n  n/2 (n is even)
n  3n + 1 (n is odd)

比如13：

13  40  20  10  5  16  8  4  2  1

 

求在100万以下的数中，哪个数产出的序列最长。

产出的序列中会包含很多以前计算过的，所以要缓存起来，以下使用了字典。

要注意的是当一个数很大的时候，如果是奇数，那么下一个数可能会超出类型的最大值。所以以下F#就用int64了

其实下面代码是haskell直接转型过来的，唉，haskell怎么写才快起来呢..

let isEven (n:int64) =
    n % 2L = 0L

let next n=
    match isEven n with
    | true -> n/2L
    | false -> 3L*n+1L


open System.Collections.Generic 

let dict =new Dictionary<int64 ,int64 list>()

let rec gen (n:int64)=
    if n =1L then [1L]
    elif dict.ContainsKey n then dict.[n]
    else 
        let x =gen<| next n in
        dict.Add(n,n::x)
        n::x
        
let mapToLen xs =
    List.map (fun x-> 
                    let xs = gen x 
                    match xs with
                    | h:: t->(h, List.length xs)) xs
    
List.maxBy (fun (v,l)->l) <| mapToLen [1L..1000000L]           

  --haskell

import qualified Data.Map as Map

longlength ::[a] -> Integer
longlength =fromIntegral . length

isEven :: Integer -> Bool
isEven x
  | x `mod`2 == 0 = True
  | otherwise     =False

next :: Integer -> Integer
next n
  | isEven n =n `div` 2
  | otherwise =3*n+1
tree =Map.empty
--使用Map缓存
gen' :: Integer ->Map.Map Integer [Integer] -> ([Integer],Map.Map Integer [Integer])
gen' 1 t =([1],t)
gen' n t =
  case Map.lookup n t of
    Just v -> (v,t)
    Nothing ->(ret,Map.insert n ret t')
    where (nxts,t') =gen' (next n) t
          ret =n:nxts

mapToLen:: [Integer]->Map.Map Integer [Integer]->[Integer]
mapToLen [] t =[]  
mapToLen (x:xs) t =
  let (lst,t')=gen' x t in
  (longlength lst):mapToLen xs t'
--Ghci中 maximum $ rang 1 1000000
range a b =
  mapToLen [a.. b] tree