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

ちゃんと計算してないけど、時間計算量はO(n logn)、空間計算量はO(1)ぐらい？再帰してるから空間計算量はO(logn)なのかな。

class P
{
  static void Main(string[] args)
  {
    for (int i = 1, c = 0; c < 100; i++)
    {
      int[] f = F(i);
      if (f != null)
      {
        ++c;
        System.Console.WriteLine
          ("{0} = 2^{1} * 3^{2} * 5^{3}", i, f[2], f[3], f[5]);
      }
    }
  }

  static int[] F(int n)
  {
    if (n == 1) return new int[6];
    int[] a = { 2, 3, 5 };
    foreach (int d in a)
      if (n % d == 0)
      {
        int[] r = F(n / d);
        if (r == null) return null;
        ++r[d];
        return r;
      }
    return null;
  }
}

DouKaku?

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

Posted feedbacks - C#

Index

Feed

Other

Link

Pathtraq