遞迴關係－爬樓梯.

Presentation on theme: "遞迴關係－爬樓梯."— Presentation transcript:

1 遞迴關係－爬樓梯

2 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？

3 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？

4 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？

5 法1：(排列組合) 假設：1階次數為 x ，二階次數為 y 因總階數為6，所以x + 2y = 6 此方程式的非負整數解有： x 6 4 2 y 1 3 所以我們可依各階數所走次數，將所有走法分成四類。

6 法1：(排列組合) 我們可依各階數所走次數，將所有走法分成四類。 (1) 1階走的次數為 6 ，二階走的次數為 0 6個1排列方法數：1 (1, 1, 1, 1, 1, 1) (2) 1階走的次數為4 ，二階走的次數為 2 4個1及1個2的排列方法數：5 (1, 1, 1, 1, 2) (1, 1, 1, 2, 1) (1, 1, 2, 1, 1) (1, 2, 1, 1, 1) (2, 1, 1, 1, 1)

7 (3) 1階走的次數為 2 ，二階走的次數為 2 2個1及2個2的排列方法數：6 (1, 1, 2, 2) (1, 2, 1, 2) (1, 2, 2, 1) (2, 1, 1, 2) (2, 1, 2, 1) (2, 2, 1, 1) (4) 2階走的次數為 3 ，二階走的次數為 0 0個1及3個2的排列方法數：1 (2, 2, 2)

8 假設：1階次數為 x ，二階次數為 y 因總階數為6，所以x + 2y = 6 (1) x = 6, y = 0 → 方法數：1
一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？ 假設：1階次數為 x ，二階次數為 y 因總階數為6，所以x + 2y = 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 所以，總共的方法數為 = 13

9 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？
傳統解法： 設上6級樓梯，跨1級x次，跨2級y次， x＋2y＝6，其中x, y是非負整數 x y 6！ 5！ 4！1！ 4！ 2！2！ 3！ ＋ ＋ ＋ ＝13

10 法2：(遞迴方法) 問題 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？
一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有a6種，則a6之表示式為何？ 一至二樓有n級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有an種，則an之表示式為何？

11 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有a6種，則a6之表示式為何？
第一步跨1級 第一步跨2級 一至二樓有6級樓梯， 某人上樓第一步跨1級，則 接下來還有5級樓梯， 不同上樓的方法有a5種。 一至二樓有6級樓梯， 某人上樓第一步跨2級，則 接下來還有4級樓梯， 不同上樓的方法有a4種。

12 1 2 3 5 8 13 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有a6種，則a6之表示式為何？ a6＝a5＋ a4
第一步跨1級 第一步跨2級 一至二樓有6級樓梯， 某人上樓第一步跨1級，則 接下來還有5級樓梯， 不同上樓的方法有a5種。 一至二樓有6級樓梯， 某人上樓第一步跨2級，則 接下來還有4級樓梯， 不同上樓的方法有a4種。 a6＝a5＋ a4 同理 a5＝a4＋ a3 a4＝a3＋ a2 a3＝a2＋ a1 其中a2＝2, a1＝1 a1 a2 a3 a4 a5 a6 1 2 3 5 8 13

13 一至二樓有n級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有an種，則an之表示式為何？
問題 一至二樓有n級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有an種，則an之表示式為何？ an ＝ an－1＋ an－2 其中a2＝2, a1＝1 像登樓梯問題， 我們所採用的方法是： 利用前面項的某種函數關係，一項一項去推算， 這種處理問題的方法叫做遞迴方法， 它常用在計算機科學，離散數學，遊戲……等許多領域。

14 組合方法 遞迴方法 a1 a2 a3 a4 a5 a6 一至二樓有6級樓梯，某人上樓，每次可跨1級或2級，不同上樓的方法有幾種？
6！ 5！ 4！1！ 4！ 2！2！ 3！ ＋ ＋ ＋ ＝13 遞迴方法 an ＝ an－1＋ an－2 其中a2＝2, a1＝1 a1 a2 a3 a4 a5 a6 1 2 3 5 8 13