Re: [解題] 高中排列組合
※ 引述《doctortwo (肅殺的十月)》之銘言：
: 題目是一題應用題，
: 「將圖中的黑棋向右移動，每次移動 1～3格，一道最右邊一格，共有幾種不同的移法？」
: 最後可以寫成方程式 x＋2y＋3z＝7（此方程式確定無誤）
: 想法：接下來應該就是
: x 7 5 3 1
: z＝0： (x＋2y＝7)
: y 0 1 2 3
: x 4 2 0
: z＝1： (x＋2y＝4)
: y 0 1 2
: x 1
: z＝2： (x＋2y＝1)
: y 0
: 所以應該共有 1 ＋ 6!/5! ＋ 5!/3!2! ＋ 4!/3! z＝0
: 5!/4!＋ 4!/2! ＋ 3!/2! z＝1
: 3!/2! z＝2
: --------------------------------------------------------------------
: 1＋6＋10＋4＋5＋6＋3＋3＝ 38種
: 可是答案是 44種...
: 想請問我還有哪裡少考慮到了？
: 謝謝！
算錯的部分已有板友推文告知，
提供利用遞迴的解法：
設a(n)為移動至第n格的方法數
由題意可推得：(1) a(1)=1 a(2)=2 a(3)=4
(2) a(n)=a(n-1)+a(n-2)+a(n-3)
移動到第n格的前一步可能在第n-1格或n第-2格或第n-3格
所以移動到第n格的方法數等於移動到前三格的方法數相加
=> a(1)=1
a(2)=2
a(3)=4
a(4)=a(1)+a(2)+a(3)=7
a(5)=a(2)+a(3)+a(4)=13
a(6)=a(3)+a(4)+a(5)=24
a(7)=a(4)+a(5)+a(6)=44 =>答案
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.232.132.69
討論串 (同標題文章)