2^i * 3^j * 5^k なる整数
Posted feedbacks - Scheme
出題時に考えていた答。平衡木を使うので、求める数の個数を n としたとき、時間計算量は O(log n)、空間計算量は O(n) のはず。
see: Gauche ユーザリファレンス: 6.14 ツリーマップ
1 2 3 4 5 6 7 8 9 10 11 12 13 | (define (main args)
(let ((tm (alist->tree-map '((1 . #t)) = <)))
(let loop ((n (string->number (cadr args)))
(rs '()))
(cond
((zero? n)
(print (reverse rs))
0)
(else
(let ((m (car (tree-map-pop-min! tm))))
(for-each (cut tree-map-put! tm <> #t)
(map (cute * m <>) '(2 3 5)))
(loop (- n 1) (cons m rs))))))))
|
leque
#7554()
Rating1/3=0.33
2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。
例えば最初の 10 個は次のようになります:
※解答では i, j, k の各値を示す必要はありません。
[ reply ]