3136

急～爬樓梯～幾種爬法？？？

小明爬樓梯一次最多可以爬3階(1次1階

1次2階或1次3階)..請問他可用幾種不同的走法爬上15階的階梯?
另 f(n) 為爬到 n階的方法總數f(1) = 1 (走一步)f(2) = 2 (跨兩步 or 單階走兩次)f(3) = 4 (111

12

21

3)用一次動作到 第n 階有幾種方法呢?1. 可由 第n-3階 跨三步2. 可由 第n-2階 跨兩步3. 可由 第n-1階 跨一步所以.. f(n) = f(n-1)*1 f(n-2)*1 f(n-3)*1 f(n) = f(n-1) f(n-2) f(n-3)f(1) = 1f(2) = 2f(3) = 4f(4) = 7f(5) = 13f(6) = 24f(7) = 44f(8) = 81f(9) = 149f(10) = 274f(11) = 504f(12) = 927f(13) = 1705f(14) = 3136f(15) = 5768所以用指定的方法可以用 f(15) =5768 種方法如果問題改成只能走 1 or 2階f(n) = f(n-1) f(n-2)這就變成了有名的fibonnacci numbersf(1) = F2 = 1f(2) = F3 = 2走道 n 階共有 f(n) = Fn 1

第n 1 個 fibonnacci number例如..走道11階共有 F12 = 144 種方法
假設1階X次

2階Y次

3階Z次則可列X 2Y 3Z=15

求非負整數解1、Z=0

X 2Y=15

(15

0)=1(13

1)=14!/13!=14(11

2)=13!/(11!*2!)=78(9

3)=12!/(9!*3!)=220(7

4)=11!/(7!*4!)=330(5

5)=10!/(5!*5!)=252(3

6)=9!/(3!*6!)=84(1

7)=8!/(1!*7!)=8共有1 14 78 220 330 252 84 8=987種走法2、Z=1

X 2Y=12

(12

0)=1(10

1)=11!/10!=11(8

2)=10!/8!*2!=45(6

3)=9!/6!*3!=84(4

4)=8!/4!*4!=70(2

5)=7!/2!*5!=21(0

6)=6!/6!=1共1 11 45 84 70 21 1=233種走法3、Z=2

X 2Y=9

(9

0)=9!/9!=1(7

1)=8!/7!1!=8(5

2)=7!/5!*2!=21(3

3)6!/3!*3!=20(1

4)=5!/1!*4!=5共1 8 21 20 5=55種走法4、Z=3

X 2Y=6

(6

0)=6!/6!=1(4

1)=5!/4!*1!=5(2

2)=4!/2!*2!=6(0

3)=3!/3!=1共1 5 6 1=13種走法5、Z=4

X 2Y=3

(3

0)=3!/3!=1(1

1)=2!/1!*1!=2共有1 2=3種走法6、Z=5

X 2Y=0

(0

0)=1種走法BY1、2、3、4、5、6共有987 233 55 13 3 1=1292種走法
解法一假設一階爬a次

二階爬b次

三階爬c次

則a 2b 3c=15直接列舉(先鎖定係數較大者)c=0

0

0b=0

1

2a=15

13

11

.......每一組解還要考慮順序的變化例如: c=2

b=3

a=3其排列為: 8!/2!3!3!這個方法最基本

但比較煩.....計算結果共有5768種方法
令 f(n) 為 n 階時的走法總數f(1) = 1   // 一階時

只有一種: 1f(2) = 2   // 二階時

只有二種: 1 1

2f(3) = 4   // 三階時

只有四種: 1 1 1

1 2

2 1

3f(n) = f(n-1) f(n-2) f(n-3)// n 階時// 若第一步走1階 則接下來有 f(n-1) 種走法// 若第一步走2階 則接下來有 f(n-2) 種走法// 若第一步走3階 則接下來有 f(n-3) 種走法// 此走法三種互斥 所以加起來就是 n 階的走法// 類似費式數列 一直加到第 15 項即為所求1______12______23______44______75_____136_____247_____448_____819____14910___27411___50412___92713__170514__313615__5768所以答案就是 5768 種
1F的大大 你的過程有誤喔! 例如: z=2

x=5

y=3 應該有 10!/2!5!3!才對啊
看到您花了納麼多時間把情形全部列出來

我認為您只要修正即可.
不用選我

給數學同好

減肥方法,賺錢最快方法,讀書方法,自衛方法,長高的方法,咳嗽治療方法,痔瘡治療方法,研究方法,失眠解決方法,墮胎方法方法,927,274,1705,共有,階梯,動作,問題,變成

心算|開根號|複數|微積分|代數|商高定理|矩陣|面積換算|離散數學|多項式|機率|統計學|演算法|對角線|平均數|向量|質數|雙曲線|小數|畢氏定理|數獨|方程式|分解式|因數|三角函數|長度換算|進位法|拋物線|體積換算|內角和|幾何|負數|倍數|不等式|分數|等比級數|證明題|圓周率|

3136
參考:http://tw.knowledge.yahoo.com/question/question?qid=1406011802626如有不適當的文章於本部落格，請留言給我，將移除本文。謝謝！