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

#7638 さんのアルゴリズムを借用。
priority queueの代わりに、標準ライブラリのヒープキューを使います。

#!/usr/bin/python

from heapq import heappush, heappop

def doukaku206(num_answers):
    answers = []
    heap = [1]
    prev_answer = 0
    while len(answers) < num_answers:
        a = heappop(heap)
        if a == prev_answer:
            continue
        answers.append(a)
        heappush(heap, a * 2)
        heappush(heap, a * 3)
        heappush(heap, a * 5)
        prev_answer = a
    return answers

print doukaku206(100)

# eof

dictでmemo化

本来は配列でmemo化したほうがよいのだが、pythonでListのreserveを適切に行う方法がわからない。index errorをexceptするのもだるいし・・・。

appendするならdictを使うほうがマシでしょう。

class IsN235WithMemo(object):
  def __init__(self):
    self.memo = dict()
  def __call__(self, n):
    r = self.memo.get(n, None)
    if r is not None:
      return r
    if n == 1:
      return True
    d, m = divmod(n, 2)
    if d and m == 0:
      return is_n235(d)
    d, m = divmod(n, 3)
    if d and m == 0:
      return is_n235(d)
    d, m = divmod(n, 5)
    if d and m == 0:
      return is_n235(d)
    return False

is_n235 = IsN235WithMemo()

for i in range(10):
  print i, is_n235(i)

itertoolsを使って。

import itertools

def numbers():
    for n in itertools.count(1):
        t = n
        for i in (2, 3, 5):
            while t != 1 and t % i == 0:
                t //= i
        if t == 1:
            yield n

def main():
    for n in itertools.islice(numbers(), 100):
        print n

if __name__ == '__main__':
    main()

DouKaku?

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

Posted feedbacks - Python

Index

Feed

Other

Link

Pathtraq