AMC 8 2010 Problem 25
AMC8 2010 年第 25 题
递推★★★★☆
Everyday at school, Jo climbs a flight of 6 stairs. Jo can take the stairs 1 , 2 , or 3 at a time. For example, Jo could climb 3 , then 1 , then 2 . In how many ways can Jo climb the stairs?
Jo 每天在学校里都要爬 6 节楼梯。Jo 可以一次爬 1 节，2 节或者 3 节。例如，J0 可以先一次爬 3 节，然后 1 节，然后 2 节。则 Jo 爬楼梯一共有多少种可能的方法？
- A.13
- B.18
- C.20
- D.22
- E.24
正确答案 · Correct Answer
E
解析 · Solution
解法1
常规解法 · 递推
设 为登 级台阶的方法数。最后一步可迈 1、2 或 3 级，故 f(n)=f(n-1)+f(n-2)+f(n-3)。由 f(1)=1、f(2)=2、f(3)=4 递推：f(4)=7、f(5)=13、f(6)=24。
巧解 · 按所含 2、3 个数枚举
把 6 拆成若干 1、2、3 的有序和，按 2 和 3 的个数分类，用排列数计每类顺序：全 1（1 种）；一个 2（5 种）；两个 2（6 种）；三个 2（1 种）；3+1+1+1（4 种）；3+2+1（6 种）；3+3（1 种）。合计 1+5+6+1+4+6+1=24。
Solution 1
Elementary · recursion
Let be the number of ways to climb stairs. The last move is 1, 2, or 3 stairs, so f(n)=f(n-1)+f(n-2)+f(n-3). With f(1)=1, f(2)=2, f(3)=4, we get f(4)=7, f(5)=13, f(6)=24.
Slick · enumerate by how many 2s and 3s
Count ordered sums of 6 using parts 1, 2, 3 by type: all 1's (1); one 2 (5); two 2's (6); three 2's (1); 3+1+1+1 (4); 3+2+1 (6); 3+3 (1). The total is 1+5+6+1+4+6+1=24.
继续练习