2013-森の木-解説
- 正解は「A の木が 34 本,B の木が 55 本」
- A は B を作り,その年で消える
- B は A を作り,次の年に残る
このことから,次がわかります。 - A の本数は,前年の B の本数
- B の本数は,前年の A の本数と B の本数の和
- (前年の A の本数)+(前年 B の本数) = (前年の A の本数)+(今年の A の本数) = (前々年のBの本数+前年の B の本数)
- 解説
この問題は,数列を再帰的な定義に関する問題で,数列中の数はそれ以前の数に基づき計算することで得られます.このような数列は,ただちに解を得るのは困難なため小さなサイズの問題から解かないとならない問題のアルゴリズムを設計する際に良く現れます.
この問題でも,すぐに10年後の木の本数を求められないので,1年後,2年後,3年後と順次求めます.このような手法は動的計画法 (dynamic programming) と呼ばれています.