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

　#7652を参考に書いてみました。

class HummingNumbers
    def self.get(c)
        (30**c % c == 0) ? c : get(c+1)
    end
    def self.take(n,c=1)
        (n==0) ? [] : ((c = get(c)) && take(n-1,c+1).unshift(c))
    end
end

puts HummingNumbers.take(ARGV.length == 1 ? ARGV[0].to_i : 100).join("\n")

無限リストのつもりです。

class Hamming < Array
  def hamming(&p)
    x = 1
    loop {
      p.call x if 30**x%x == 0
      x += 1
    }
  end
end

p Enumerable::Enumerator.new(Hamming.new, :hamming).take(100)

2,3,5以外の素数の組合せ(3,7,11)にも対応。

def hamming(n ,a = [1 ,2 ,3 ,5])
  r = []
  h = {}
  a.each{|x|h[x] = true}
  1.upto(n){
    r << cnt = h.keys.sort[0]
    a.each{|x|h[x * cnt] = true}
    h.delete(cnt)
  }
  r
end

p "n = "
p hamming(gets.chomp.to_i)

DouKaku?

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

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq