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

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 の各値を示す必要はありません。

SQLiteで。2,3,5の11乗まで計算し、その直積をとるだけ。
SQLiteで100行だけ取り出す方法がわからなかったので結果テーブルに一度格納してます。Oracleだとwhere rowno<=100が使えたような

-- 数字テーブル
create table d (
  n   integer,
  p2  integer,
  p3  integer,
  p5  integer
);
insert into d values (0,1,1,1);
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
insert into d select max(n)+1, max(p2)*2, max(p3)*3, max(p5)*5 from d;
-- 結果テーブル
create table result (
  id  integer primary key,
  i   integer,
  j   integer,
  k   integer,
  val integer
);
insert into result (i, j, k, val)
  select a.n, b.n, c.n, a.p2 * b.p3 * c.p5 val from d a, d b, d c order by val;
select val,'2^'||i||' * 3^'||j||' * 5^'||k from result where id <= 100;

バージョン 2.7.3の頃に使ったのでちょっと自信がありませんが、先頭から 100件という
ことであれば、

  e.g.
    select ... from ... limit 100;

のように limit句で、Oracleのrownumと同等のことを実現できたと思います。

# 先頭の位置(オフセット)はoffset句で調節します。

see: SQL As Understood By SQLite

DouKaku?

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

Posted feedbacks - SQL

Index

Feed

Other

Link

Pathtraq