#001 フィボナッチ数列

問題

15段の階段を上るとき、1段上るか、2段上るか、2通りの方法を組み合わせて登ると、何通りの登り方があるか。

イズミの解答への道

いきなり15段を考えるのは難しいので、少ない数から考えてみましょう。数学では、このように、
「少ない数で試す」
ことは非常に大事な考え方です。

まずは3段ではどうでしょうか。3段の登り方だったらすべて数えられます。

  • 1段 – 1段 – 1段
  • 2段 – 1段
  • 1段 – 2段

の3通りです。ここで1つブレイクスルーが必要です。それは「最後に登るのが何段か」、いいかえれば「何段手前から登ってきたか」に着目するということです。
 どのような場合でも最後の登り方は1段か2段です。3段目にたどりつくには、1段目から登るかか、2段目から登るかのどちらかしかないということです。さきほどの例でいえば、
(1段 – 1段)- 1段
(2段) – 1段
1段 – 2段
のように見て、( )の部分は別途考えるということです。なぜなら、( )の部分は2段登る方法が何通りかという、言ってしまえば別の問題だからです。
 また、このように考えると何段でも同じです。 10 段目に辿り着く場合の数を数えるには、 8 段目まで登る場合の数と、 9 段目に登る場合の数を求めればよい、ということですし、その 8 段目に登る場合の数が知りたければ、 6 段登る方法と 7 段登る方法を調べればよいのです。ポイントは、連鎖的に関係しているということです。
 さて、こういうときに使うのが漸化式(高校の数学Bで勉強します)という考え方です。一般化してみましょう。 n 段登る方法を an 通りとすれば、どのような関係式が成り立つでしょうか。

解答

(2段目以上の)ある段に達するためには、その2段手前から2段登りで到達する方法と、1段手前から1段登りで到達する方法がある。(ココがポイント☆)
 つまり、( n ≧ 3 に対して、) n 段目に達する登り方が an 通りあるとすると、
   an = an-1 + an-2
とあらわされ、1段登る方法は1通り、2段登る方法は2通りなので、 a1 = 1 , a2 = 2 である。
 以後、この式で計算をすすめると、
   a3 = a2 + a1 = 3 , a4 = 3 + 2 = 5 , a5 = 5 + 3 = 8 , …… , a15 = 987
となり、987通りが正解である。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする