资源描述：
《递回关系-爬楼梯.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、遞迴關係－爬樓梯一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？法1：(排列組合)假設：1階次數為x，二階次數為y因總階數為6，所以x+2y=6x6420y0123此方程式的非負整數解有：所以我們可依各階數所走次數，將所有走法分成四類。(1)1階走的次數為6，二階走的次數為06個1排列方法數：1(2)1階走的次數為4，二階走的次數為24個1及1個2的排列方法數：5(1,1,1,1,1,1)(1,1,1,1,
2、2)(1,1,1,2,1)(1,1,2,1,1)(1,2,1,1,1)(2,1,1,1,1)我們可依各階數所走次數，將所有走法分成四類。法1：(排列組合)(4)2階走的次數為3，二階走的次數為00個1及3個2的排列方法數：1(2,2,2)(1,1,2,2)(1,2,1,2)(1,2,2,1)(2,1,1,2)(2,1,2,1)(2,2,1,1)(3)1階走的次數為2，二階走的次數為22個1及2個2的排列方法數：6(1)x=6,y=0→方法數：1(2)x=4,y=1→方法數：5(3)x=2,y=2→方法數：6(4)x=0,y=3→方法數：1所以，總共的方法數為1+5+6+1
3、=13假設：1階次數為x，二階次數為y因總階數為6，所以x+2y=6一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？設上6級樓梯，跨1級x次，跨2級y次，x＋2y＝6，其中x,y是非負整數傳統解法：x6420y01235！4！1！4！2！2！3！3！＋＋＋＝136！6！一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有a6種，則a6之表示式為何？問題一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？一至二樓有n級樓梯，某人上樓，每次可跨1級
4、或2級，不同上樓的方法有an種，則an之表示式為何？法2：(遞迴方法)一至二樓有6級樓梯，某人上樓第一步跨1級，則 接下來還有5級樓梯， 不同上樓的方法有a5種。一至二樓有6級樓梯，某人上樓第一步跨2級，則 接下來還有4級樓梯， 不同上樓的方法有a4種。第一步跨1級第一步跨2級一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有a6種，則a6之表示式為何？一至二樓有6級樓梯，某人上樓第一步跨1級，則 接下來還有5級樓梯， 不同上樓的方法有a5種。一至二樓有6級樓梯，某人上樓第一步跨2級，則 接下來還有4級樓梯， 不同上樓的方法有a4種。第一步跨1級第一步跨2
5、級一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有a6種，則a6之表示式為何？a6＝a5＋a4同理a5＝a4＋a3a4＝a3＋a2a3＝a2＋a1其中a2＝2,a1＝1a1a2a3a4a5a61235813一至二樓有n級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有an種，則an之表示式為何？問題an＝an－1＋an－2其中a2＝2,a1＝1像登樓梯問題， 我們所採用的方法是：利用前面項的某種函數關係，一項一項去推算， 這種處理問題的方法叫做遞迴方法， 它常用在計算機科學，離散數學，遊戲……等許多領域。組合方法一至二樓有6級樓梯，某人上樓，每次可跨
6、1級或2級，不同上樓的方法有幾種？遞迴方法an＝an－1＋an－2其中a2＝2,a1＝15！4！1！4！2！2！3！3！＋＋＋＝136！6！a1a2a3a4a5a61235813
