Ruby
codeiq

CodeIQ「『タワー・ビルディング』問題」に参加しました。

CodeIQ「『タワー・ビルディング』問題」の公開期間が終了したということで、提出回答(Ruby)を共有したいと思います(´・ω・`) 詳しい問題内容については後日、CodeIQ Magazineで解説とともに公開されると思うので、そちらを参照お願いします(権利関係とかがよくわからないので)。

2018-01-11追記: 問題&解説がCodeIQMagazineで公開されていました!! 「数学の問題をプログラミングで解こう!「『タワー・ビルディング』問題解説 」

@cache = {}

def f(n, a, b)
  ky = [n, a, b]
  return @cache[ky] if @cache.key?(ky)

  if a < 0 || b < 0 || n < 0
    val = 0
  elsif n == 0
    val = 1    
  else
    val = f(n - 1, a - 1, b) + f(n - 2, a, b - 1)
  end

  @cache[ky] = val % 1000003 
end

n, a, b = STDIN.gets.split.map(&:to_i)
puts f(n, a, b)

「高さ1の箱を最大a個、高さ2の箱を最大b個使って、高さnになる組み合わせの総数」は

  • 「高さ1の箱を最大a-1個、高さ2の箱を最大b個使って、高さn-1になる組み合わせの総数」
  • 「高さ1の箱を最大a個、高さ2の箱を最大b-1個使って、高さn-2になる組み合わせの総数」

をそれぞれ足し合わせたものになります。上記の解答はこれを再帰を利用して実装しただけの単純なものになります。ただし再帰を利用するので「初期条件」と「StackOverFlow」には注意する必要があり、後者については「メモ化」(一度計算した条件を覚えておく)ことにより、その対策としています。