確率 へ戻る「 n 段ある階段を １ 段ずつ または １ 段飛ばし で昇るとき、 何通りの昇り方があるか？ n ＝ １ 〜 15 についてそれぞれ答えなさい。」 いう問題の解答は、 答えを ｆ(n) 通り とすると、 フィボナッチ数列の漸化式 ｆ(n) ＝ ｆ(n−１) ＋ ｆ(n−２) が成立することを利用します 。 では、 この問題に「 連続して １ 段飛ばしをしてはならない 」という条件を加えると、 どうなるでしょう？
n 段の階段を昇り切る １ つ前は、 第 (n−１) 段目にいるか 第 (n−２) 段目にいるか の ２つに １ つです。
n 段の階段を昇り切る １ つ前に第 (n−１) 段目にいる場合 ：
第 (n−１) 段目にいることになるすべての場合の数は ｆ(n−１) 通りです。
このすべてのケースについて、 次に n 段の階段を昇り切ることになる権利があります。
したがって、「 n 段の階段を昇り切る １ つ前に第 (n−１) 段目にいる場合 」の「 n 段の階段を昇り切るすべての場合の数 」は ｆ(n−１) 通りです。
この １ つ前は必ず第 (n−３) 段目にいます。
第 (n−３) 段目にいることになるすべての場合の数は ｆ(n−３) 通りです。
したがって、「 n 段の階段を昇り切る １ つ前に第 (n−２) 段目にいる場合 」の「 n 段の階段を昇り切るすべての場合の数 」は ｆ(n−３) 通りです。
ｆ(n) ＝ ｆ(n−１) ＋ ｆ(n−３)
そこで、 JavaScript で次のようなプログラム組んで実行し、 答えを求めます。