2^i * 3^j * 5^k なる整数 in OCaml DouKaku?

2^i * 3^j * 5^k なる整数

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。

例えば最初の 10 個は次のようになります:

 1 = 2^0 * 3^0 * 5^0
 2 = 2^1 * 3^0 * 5^0
 3 = 2^0 * 3^1 * 5^0
 4 = 2^2 * 3^0 * 5^0
 5 = 2^0 * 3^0 * 5^1
 6 = 2^1 * 3^1 * 5^0
 8 = 2^3 * 3^0 * 5^0
 9 = 2^0 * 3^2 * 5^0
10 = 2^1 * 3^0 * 5^1
12 = 2^2 * 3^1 * 5^0

※解答では i, j, k の各値を示す必要はありません。

post comment

Posted feedbacks - OCaml

SICP Prloblem 3.56を参考にストリームで。ただし、OCamlではvalue recursionは容易ではないので、ストリーム構築時に一部黒魔術(Objモジュール)を使っています。

時間効率性はO(n) (のはず)

type 'a t = Nil | Cons of 'a * 'a t lazy_t

let (!) = Lazy.force

let rec ( ** ) factor = function
    | Nil -> Nil
    | Cons (a, b) -> Cons (a * factor, lazy (factor ** !b))

let rec ( ++ ) s1 s2 = match s1, s2 with
    | Nil,          _            -> s2
    | _,            Nil          -> s1
    | Cons(h1, t1), Cons(h2, t2) ->
        if h1 < h2 then Cons(h1, lazy (!t1 ++  s2)) else
        if h1 > h2 then Cons(h2, lazy ( s1 ++ !t2)) else
                        Cons(h1, lazy (!t1 ++ !t2))

let hamming =
    let s = Cons(1, lazy Nil) in
    let _ = Obj.set_field (Obj.repr s) 1
        (Obj.repr (lazy (2**s ++ 3**s ++ 5**s) )) in
    s

let rec print n s = if n > 0 then match s with
    | Nil -> ()
    | Cons (a, b) -> Printf.printf "%d\n" a; print (n-1) !b

let _ = print 100 hamming

DouKaku?

2^i * 3^j * 5^k なる整数

Posted feedbacks - OCaml

Index

Feed

Other

Link

Pathtraq