読者です 読者をやめる 読者になる 読者になる

Codeへの愛とCuriosity

CodeIQ への出題・解説解題・その周辺について、思いつくままに。

バイナリカウント解いてみた

バイナリカウント問題解いてみた。

提出コードはこんな感じ。

# 平易で遅い計算。テスト用。
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乗を大きく超える数でも問題なく計算できるので、計算量の削減作業はこれ以上は行うのをやめた。