バイナリカウント解いてみた
バイナリカウント問題解いてみた。
提出コードはこんな感じ。
# 平易で遅い計算。テスト用。 def solve_slow(x) (1..x).inject(0) do |acc,x| acc+x.to_s(2).count("1") end end # F(x) の xが奇数の場合のアルゴリズム。 def solve_odd( x ) (x+1)/2 + 2*solve(x/2) end # 10**100 でも計算できるアルゴリズム。 def solve( x ) return x if x<3 if x.odd? solve_odd(x) else x.to_s(2).count(?1) + solve_odd( x-1 ) end end # 計算が正しいことの確認 GIVEN_DATA = [ [3, 4], [13, 25] ].freeze TEST_DATA = GIVEN_DATA + (1..1000).map{ |s| [s, solve_slow(s)] } TEST_DATA.each do |src, expected| actual = solve(src) okay = actual==expected p [ src, expected, actual ] unless okay end # 答えを出力する { "・第1問:"=>3, "・第2問:"=>10 }.each do |name, pow| puts "#{name}#{solve(10**pow)}" end
もともと solve_odd は solve の中に埋め込まれていて
# 10**100 でも計算できるアルゴリズム。 def solve( x ) return x if x<3 cur = ( x.even? ? x.to_s(2).count(?1) : 0 ) cur + (x+1)/2 + 2*solve((x-1)/2) end
という感じだった。
これではわかりにくいということで、説明の都合でふたつに分けて提出してみた。
計算量としては大いに改善の余地ありなんだけど、目標だった 10の10乗を大きく超える数でも問題なく計算できるので、計算量の削減作業はこれ以上は行うのをやめた。