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

sedだと割り算のコストが高すぎるので、他のアルゴリズムでは難しそうです。
乗算＋ソートのために内部は2進で計算しています。

#!/bin/sed
s/.*/lol/
: loop
    s/^\([^l]*\)l*o\([lo]*\)\(\n.*\)\?$/\1a\2\3\nx\2o\nx\2o+\2=\nx\2oo+\2=/
    : 2->10
        s/[f-j]/#&/g
        s/[a-j][#l]/\U&/g
        y/AbBcCdDeEfFgGhHiIjJ/bcdefghijabcdefghij/
        s/^#/b/m
        s/#//g
        s/\([a-j]\)[Lo]/\1/
    /[a-j][lo]/ b 2->10
    y/abcdefghij/0123456789/
    : add
        s/\([xo]l*\)l+\([lo]*\)l=/\U\1\E+\2=o/g
        s/X/xl/g
        y/LO/ol/
        s/l+\([lo]*\)o=/+\1=l/g
        s/o+\([lo]*\)\([lo]\)=/+\1=\2/g
        s/+=//g
    t add
    s/^x\([lo]*\)$/\U\1\Eo\1/gm
    y/LO/ll/
    : sort
        s/^\([lo]*\)\n\1$/\1/gm
        s/^\(\([lo]*\)l[lo]*\)\n\(\2o[lo]*\)$/\3\n\1/gm
    t sort
    s/^\(\(\w*\n\)\{99\}\w*\)\n.*$/\1/
/[lo]/ b loop

DouKaku?

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

Posted feedbacks - sed

Index

Feed

Other

Link

Pathtraq