2^i * 3^j * 5^k なる整数 in Erlang 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 - Erlang

しらみつぶしに計算してからsortする方式ですが、その境界の目処はたてるようにしてみました。 http://en.wikipedia.org/wiki/Image:Regular_divisibility_lattice.svg　の図を、3次元空間のある象限に存在する三角錐とみて、それを含む直方体の中の格子点を取り出します。最低でも、およそ5/6が無駄なデータなのですが、うまく三角錐の部分だけの格子点を巡回する順序を決めるアルゴリズムが思い浮かばなかったので、そのままにしてあります。

$ erlc スクリプトのファイル名

$ erl -noshell -s len main 100 -s init stop

として実行します。

see: ハミング数

-module(len).
-export([main/1]).

main([N|_]) ->
        Limit = list_to_integer(atom_to_list(N)),
        Factor = math:pow(Limit * math:log(5) * math:log(2)/ (math:log(2) * math:log(3)), 1 / 3),
        L = lists:sort([round(math:pow(2, X)*math:pow(3,Y)*math:pow(5,Z)) ||
                 X <- lists:seq(0,round(1 + Factor * math:log(5) / math:log(2)) ),
                 Y <- lists:seq(0,round(1 + Factor * math:log(5) / math:log(3)) ),
                 Z <- lists:seq(0,round(1 + Factor))]),
        io:format("~p~n",[lists:sublist(L,Limit)]).

DouKaku?

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

Posted feedbacks - Erlang

Index

Feed

Other

Link

Pathtraq