推 hsheng: 專業推。私下問一下，現在高中數學出類似這題難度會難嗎? 10/17 20:38
推 lp33506: 不難 學測之前出過 10/17 22:14
推 RaventheCrow: 之前中區模擬考也出過走階梯走法的遞迴式 10/17 23:44
※ 引述《dddd5477 (旗美地區第一帥哥)》之銘言：
: 標題: [問題] 棋盤排列組合
: 時間: Fri Oct 16 15:54:00 2015
:
: 是一個2*7的格子
:
: 任意選兩格以上
:
: 每格不能相鄰
:
: 求算法 跟答案
:
: 感謝
:
: 推 disjoint126: 先用遞迴算可取任意格數的方法 設2*n格的取法為a_n 10/16 23:03
: → disjoint126: 可推得 a_(n+2)=2a_(n+1)+a_n 10/16 23:04
: → disjoint126: 再由a_1=3、a_2=7 得到 a_7=577 10/16 23:05
: → disjoint126: 最後把兩格以下的取法(15種)扣掉就是答案 10/16 23:05
解法如這位高手所說
但我覺得個題目比較困難的部分在於 如何求出遞迴關係式
所以(ry
首先看這張圖 http://imgur.com/s5PSxUi
這張圖代表相鄰兩排之間所有可能的選擇情形
假設題目是一個高度為 7 格 ，寬度為 2 格的長方形
由上往下著色
可以由圖中觀察到，如果上一排有著色，則下一排只有兩種可能的選擇：
1.著色在不同於上一排的一側
2.不著色
而如果上一排沒有著色，則下一排可有三種選擇：
1.左側著色
2.右側著色
3.不著色
所以，n排所有組合 = 2*(n-1排且底排有著色) + 3*(n-1排且底排無著色)
= 2*(n-1排所有組合) + (n-1排且底排無著色)
而「n-1排且底排無著色」的組合數量，等同於「n-2排所有組合」，
即為n-2排的任何一種情形加上一排沒有上色的格子。
得
n排所有組合 = 2*(n-1排所有組合) + (n-2排所有組合) 當 n > 2
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.18.98
※ 文章網址: https://www.ptt.cc/bbs/SENIORHIGH/M.1445056422.A.642.html