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\) である.
となる.