シニア問題/C森の木
森の木
ビーバーの住む森の木には A, B の2種類があります。
Aの木の寿命は（種から）1年間で，その年の終わりに1本のAの木はBの木の種を1つ残します。
Bの木の寿命は永遠で，毎年の終わりに1本のBの木はAの木の種を1つ作ります。
最初にAの種が1個あったとき，10年後にはAの木とBの木は何本ずつになっているでしょう?
- 解説を見る
- 正解は「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) と呼ばれています．
- 正解は「A の木が 34 本，B の木が 55 本」
注があるものを除き, このサイトの内容物は
