Problem14(2) -動的計画法-

Ocaml 30分プログラム

30分プログラム、その278。Problem14 3n+1問題の続き。
wikipedia:コラッツの問題の図を見ていたら、1まで計算する必要がないことに気がついた。例えば、20と21の場合、

20->10-> 5->16-> 8-> 4-> 2-> 1
21->64->32->16-> 8-> 4-> 2-> 1

のようになるので、16以下の計算は一回で済む。

これは動的計画法を用いて一回計算した値を覚えておけばいいんだな、ということでチャレンジしてみた。が、なぜか一部の数字(例: 77671)にものすごく時間がかかってしまい断念。
動的計画法の実現には、メモ化を用いたかったのだけれども、末尾再帰の関数をメモ化する方法が分らなかったので、諦めた。

使い方

$ ocamlopt -o problem14 probelm14.ml

$ ./problem14
found 87388
call 77676
found 87388
call 77675
found 87385
call 77674
call 77673
found 87383
call 77672
call 77671
^C

ソースコード

let ($) f g x = f (g x)
let (@@) f g = f g

let rec unfold f b = 
  match f b with
      Some (a,b') -> a :: unfold f b'
    | _ -> []


let even n = (n mod 2) = 0


let table = Hashtbl.create 10

(*let memo f =
  fun x ->
    if Hashtbl.mem table x then begin
      Printf.printf "found f(%d)\n" x;
      Hashtbl.find table x
    end else begin
      let r = f x in
	Hashtbl.add table x r;
	r
    end*)

let collatz n = 
  let rec loop n r =
    if Hashtbl.mem table n then begin
      Printf.printf "found %d\n" n;
      flush stdout;
      (Hashtbl.find table n) + r
    end else if n = 1 then
      r
    else if even n then
      loop (n/2) (1+r)
    else
      loop (3*n+1) (1+r)
  in 
    Printf.printf "call %d\n" n;
    flush stdout;
    let r = loop n 1 in
      Hashtbl.replace table n r;
      r

let range a b =
  let rec f r a b = 
    if a = b 
      then r
      else f (a::r) (a+1) b
  in
    f [] a b

let solve _ =
  let f a b = 
    let r = collatz b in
      if a < r then
	r
      else
	a
  in
    List.fold_left f 0 @@ range 1 1_00_000;;

let _ = 
  print_int @@ solve ();
  print_string "\n"

参考