Question

らむ

試行のヒント①が何を言っているかわかりません。
再起的な構造とは何回かすると最初の状態に戻るこうぞうをもつもの　らしいです

880
30 確率 ⑩0
題30
★★☆ 15分
1歩で1段または2段のいずれかで階段を昇るとき1歩で2段昇
ることは連続しないものとする。 15段の階段を昇る昇り方は何通り
あるか。
(京大・理系・07)
0
(理解
試行のヒント①
1段昇りでも2段昇りでも1歩進むと「“階段の一番
下の段”という状態にリセットされる」と見ることができるので,再
帰的な構造です。n段の昇り方を an 通りとして漸化式を立てましょ
う。
･･･(*) の条件がなけ
「1歩で2段昇ることは連続しないものとする」
れば有名問題なので,一度くらいやった経験があるのではないでしょう
か? まずはこれを考えてみましょう。
試行のヒント② 再帰的な構造をもつ問題の場合,最初の操作で場合
分けするか,最後の操作で場合分けします。最初の操作を「1段昇
り」と「2段昇り」で場合分けしてみてください。
ように
遷移的な構造をもつ問題で漸化式を立てるときは、 28 29でやった
遷移的な構造をもつ
問題の漸化式の立て方
n番目の状態で場合分けをして,
n+1番目の状態との関係を考える
ということになりますが、 再帰的な構造をもつ問題では, 「n番目の状態
で場合分け」が難しいことが多いです。 このようなときは,
確率 ⑩ 195

Answer 1

✨ ベストアンサー ✨

きらうる

例えば組み合わせの公式に
nCr＝n-1Cr-1+n-1Cr
という公式があります。

これは、n個の要素からr個の要素を取り出す組み合わせと、ある1つの要素を除いたn-1個の要素からr-1個の要素を取り出し、最後に除いていた1個を含める組み合わせと、ある1つの要素を除いたn-1個の要素からr個の要素を選ぶ組み合わせの和であることを言っています。

これも再帰的な構造の一種と言えます。

何が言いたいかというと、今回の問題では。
1歩目で1段登ると、次は1段か2段登る
1歩目で2段登ると、次は1段登る
事になっているので、
n段目に登るには、
①n-1段から1歩でn段に登る
②n-3段から1歩でn-2段に登って、2歩でn段に登る
の2パターンが考えられるので、
n段に登る総数をa[n]とすると、
a[n]＝a[n-1]+a{n-3}
という式で表すことができるのです。

質問の返答になっていますでしょうか。