Hatena::Grouprubyist

krystal: プログラミング超初心者(文系)

2008-12-10 (Wed)Ruby練習問題

ゼロをカウント[Part Ⅱ]

19:43

  • 今回は 0~1000万までカウント
require "benchmark"

puts Benchmark::CAPTION
puts Benchmark.measure{

#1~10万まで
a = (1..1e5).to_a.join.count("0")       

#10万1~20万まで
b = (100001..2e5).to_a.join.count("0")  

#0~100万まで
c = 1 + a.to_i + (b.to_i * 9) + 1       

#100万1から200万まで
d = (1000001..2e6).to_a.join.count("0") 

#0~1000万まで
p c + (d.to_i * 9) + 1   #=> 5888897 
}            
      user     system      total        real
5888897
  5.844000   0.000000   5.844000 (  5.234000)

(0..1e7).to_a.join.count("0")だと物凄く時間かかるから、分けて数えたほうが少し速くなるのかなって思って。

1 + (1~100000) + (100001~200000)*9 + 1 + (1000001~2000000)*9 + 1


違うやり方について、ヒントもらったので今書いてる最中。

たぶん↑よりもっともっと速くなるはず。たぶん


Stringクラスを使わずに計算してみる

require "benchmark"

puts Benchmark::CAPTION
puts Benchmark.measure{
def zerocount_from_zero_to(num)
  n = 10                 #10からゼロを数える
  count = 1              #↑は10からだから、10以内の場合は0がひとつしかないので、最初から一回カウント
  
  while n <= num  
    a,b = n.divmod(10)  
    while a >= 1         #商は1以上、つまりnは10以上の場合
      if b == 0          #余りは0であれば10の倍数ということで0で終わってる数字のはず
        count += 1       #なので、0を一つカウント
      end 
      a,b = a.divmod(10) #さらに10で割って判断する
    end
    n += 1               #nを一つずつ試していく。ここが効率悪い?
  end
  return count
end

p zerocount_from_zero_to(1e6)
}
      user     system      total        real
488896
  7.563000   0.000000   7.563000 (  6.782000)

これは100万まででもかなり時間かかってた。一つずつ試していくから効率が悪い。


↑二つの方法を合体してみる

require "benchmark"

puts Benchmark::CAPTION
puts Benchmark.measure{

def zerocount(n,num) #nもnumと同じように渡す

  count = 0
  
  while n <= num  
    a,b = n.divmod(10)  
    while a >= 1         #商は1以上、つまりnは10以上の場合
      if b == 0          #余りは0であれば10の倍数ということで0で終わってる数字のはず
        count += 1       #なので、0を一つカウント
      end 
      a,b = a.divmod(10) #さらに10で割って判断する
    end
    n += 1               
  end
  return count
end

a = zerocount(0,1e5)                    # 0から10万まで 
b = zerocount(100001,2e5)               # 10万1から20万まで
c = zerocount(1000001,1100000)          # 100万1から110万まで
p 1 + a + b*9 + 1 + (c + b*9 + 1)*9 + 1 # 足りないゼロの数は自分で追加しないとダメ...
}

      user     system      total        real
5888897
  2.219000   0.000000   2.219000 (  1.984000)

速くなったが、やっぱりややこしい。