No.683

メモ化再帰で逆から計算する.

\(F(X, Y)\) を, \((X, Y)\) が作れるかどうかを返す関数とする. このとき,

• \(X = 0 \lor Y = 0\) ならば \(F(X, Y) = true\) である. \(+1\) の操作を繰り返せばいいからである.
• \(X\) が2で割り切れるならば, \(F(X/2, Y-1)\) を計算してこれが \(true\) ならば \(F(X, Y)\) は \(true\) である.
• \(Y\) が2で割り切れるならば, \(F(X-1, Y/2)\) を計算してこれが \(true\) ならば \(F(X, Y)\) は \(true\) である.
• 上で \(true\) にならなければ \(F(X, Y) = false\) である.

となる.