2^i * 3^j * 5^k なる整数
Posted feedbacks - Common Lisp
kozima
#7645()
[
Common Lisp
]
適当に生成しながら小さい順に並べてます。動けばいい的な作りですが。考え方は 84q さんのと同じでしょうか。
計算量は時間 O(N^2) 空間 O(N) かと思いましたが、実際に試してみた感じだともっと小さいかもしれません。また balanced tree をつかうなど真面目に効率化をやればもっと速くなると思います。
1 2 3 4 5 6 7 8 9 | (defun add (n list)
(if (find n list) list (merge 'list list (list n) #'<)))
(defun h (n)
(let ((a (list 1)) (c 0))
(loop (let ((m (pop a)))
(print m)
(setf a (add (* m 2) (add (* m 3) (add (* m 5) a))))
(if (= (incf c) n) (return))))))
|
leque
#7554()
Rating1/3=0.33
2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 i, j, k は 0 以上の整数です。アルゴリズムのオーダーについても考えてみてください。
例えば最初の 10 個は次のようになります:
※解答では i, j, k の各値を示す必要はありません。
[ reply ]