プログラマの道は険しい

ruby

どう書く.orgの問題にまたまたチャレンジ。

問題文

2^i * 3^j * 5^k の形で表される整数を小さい方から順に 100 個列挙するプログラムを書いてください。 
i, j, k は 0 以上の整数です。
例えば最初の 10 個は次のようになります: 1 2 3 4 5 6 8 9 10 12

※解答では i, j, k の各値を示す必要はありません。

解答

さっそくオレオレ解答です。どう書く.orgの問題は勉強中のrubyで解くことにしている。

Num = [5,3,2]

def log(b, n)
  Math.log(n) / Math.log(b)
end

def r(num, sum=1, i=0)
  return false if i >= Num.size

  shou = num / sum

  return true if num % sum == 0 && log(Num[i], shou).to_s =~ /\d+\.0$/

  taisuu = log(Num[i], shou).to_i

  loop do
    return true if r(num, Num[i]**taisuu * sum, i+1)
    return false if 0 > taisuu-=1
  end
end

def found?(num)
  Num.each do |x|
    return true if log(x, num).to_s =~ /\d+\.0$/
  end

  return r(num)
end


target = 0
counter = 0

until counter >= 100
  if found? target+=1
    puts "#{target}"
    counter+=1
  end
end

いつもの様に解き終わった後、他の人の回答を見て卒倒しかけました。みんな短っ！自分のコードが恥ずかしすぎてblogに載せるの止めようかと思ったけど、まぁせっかく作ったんだし晒しておこう。後から振り返った時、成長の過程が楽しめるだろうさ。

他の人の解答

例えばlunlumoさんの解答と見比べてみよう。

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")

10行！すごいなぁ。
このプログラムのポイントは主に2つかな。
1つはgetメソッドにある「30**c % c == 0」ってところです。俺がlogメソッドを定義して色々やっているのがこれだけで終わっている。他にはtnkさんは次のように実装している（言語はJava）。ただ分かりやすいものの、計算量は多そうだ。

for (int n = 0, i = 1; n < limit; i++) {
    int tmp = i;
    while (tmp % 2 == 0) tmp /= 2;
    while (tmp % 3 == 0) tmp /= 3;
    while (tmp % 5 == 0) tmp /= 5;
    if (tmp == 1) {
        System.out.println(i);
        n++;
    }
}

もう1つはtakeメソッドそのもの。結果をgetメソッドを使ってcに代入しておき、見つかる度にnの数を減らして再帰的に100回繰り返す。面白いのは結果を見つけても即出力したり、結果をまとめる配列に入れたりするのではないところ。一旦nが0になった時点で始めて空配列をreturnし、再帰を逆に戻っていく時にunshiftメソッドでどんどん配列の先頭に追加していく。この発想は出てこないっす！


いやー、全くダメですな。。でも勉強になりました！これからも定期的にトライします。