2^i * 3^j * 5^k なる整数 in Other 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 の各値を示す必要はありません。

VBA for Excel (2003)

Sub main()
  Dim r, s, t
  Range("B1").Value = "2^x"
  Range("C1").Value = "3^y"
  Range("D1").Value = "5^z"
  Range("B2:D2").Value = 0
  Set r = Range("A1")
  n = 1
  c = 0
  While c < 100
    Set s = r.Offset(n)
    s.Value = n
    If Not IsEmpty(s.Offset(0, 1)) Then
      c = c + 1
      For i = 0 To 2
        Set t = r.Offset(n * ((i * (i + 1) / 2) + 2))
        For j = 0 To 2
          t.Offset(0, j + 1).Value = s.Offset(0, j + 1).Value + IIf(i = j, 1, 0)
        Next
      Next
    End If
    n = n + 1
  Wend
  Cells.AutoFilter Field:=1, Criteria1:="<>"
  Cells.AutoFilter Field:=2, Criteria1:="<>"
End Sub

グッドです。以下のように書いて結果テーブルは不要になりました。
バージョン 2.8.17 と 3.6.1 で動くことを確認してあります。

1	select (a.p2b.p3c.p5) val, a.n, b.n, c.n from d a, d b, d c order by val limit 100;

Forth の実績追加のため、実装してみました。

: DIV_CHECK ( n d -- n/d^m )
BEGIN
  2DUP MOD 0=
WHILE
  DUP -ROT / SWAP
REPEAT
DROP ;

: HummingNumbers ( n -- )
1
BEGIN
  OVER 0>
WHILE
  DUP
  2 DIV_CHECK
  3 DIV_CHECK
  5 DIV_CHECK
  1 = IF
    DUP .
    SWAP 1- SWAP
  THEN
  1+
REPEAT
2DROP
;

DouKaku?

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

Posted feedbacks - Other

Index

Feed

Other

Link

Pathtraq