看板 Grad-ProbAsk 關於我們 聯絡資訊
Let A={1,2,...,9}.Then there are ____ subsets of A which do not contain consecutive numbers.(i.e.,if x belongs to A is in the subset then x-1 and x+1 must not be selected.) 這題我知道大概是要用遞迴去算,但 recurrence relation 寫不太出來 麻煩大家幫我解答了 謝謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 59.121.150.59
suhorng:求1-9選1個數字不連號的組合數 + 選2個數字的組合數 + ... 02/19 21:56
suhorng:只有 5 項 02/19 21:56
bbhands:Fibonacci 02/19 22:04
josephHPSH:記得可以用an推到一般化 從含n跟不含n討論 02/19 22:12
undefeated11:請問為什麼關係式是費氏數列 02/19 22:57
imrod:我覺得可以分成 有x就是An-2 沒x就是An-1 02/19 23:58
chiangchejnn:A={1.2....n} 考慮含n跟不含n 02/20 00:15
chiangchejnn:A={1.2..n-2} 解為An-2 {1.n} {2.n} .. {n-2.n} 02/20 00:16
chiangchejnn:解為 n-2 再來考慮不含n的 {1.2..n-1} 解為 An-1 02/20 00:18
chiangchejnn:遞迴關係式為 An=An-1+An-2 + n-2 02/20 00:19
chiangchejnn:應該是這樣 02/20 00:19
cisco:樓上正解!! 02/20 07:49
sneak: A={1.2....n https://daxiv.com 09/11 14:57