[理工][離散]遞迴

看板Grad-ProbAsk作者 (Carmelo)時間12年前 (2012/02/19 21:42), 編輯推噓5(5推 0噓 8→)
留言13則, 8人參與, 最新討論串1/1
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
→
02/19 21:56, , 1F
求1-9選1個數字不連號的組合數 + 選2個數字的組合數 + ...
02/19 21:56, 1F
→
02/19 21:56, , 2F
只有 5 項
02/19 21:56, 2F
推
02/19 22:04, , 3F
Fibonacci
02/19 22:04, 3F
推
02/19 22:12, , 4F
記得可以用an推到一般化 從含n跟不含n討論
02/19 22:12, 4F
→
02/19 22:57, , 5F
請問為什麼關係式是費氏數列
02/19 22:57, 5F
推
02/19 23:58, , 6F
我覺得可以分成 有x就是An-2 沒x就是An-1
02/19 23:58, 6F
推
02/20 00:15, , 7F
A={1.2....n} 考慮含n跟不含n
02/20 00:15, 7F
→
02/20 00:16, , 8F
A={1.2..n-2} 解為An-2 {1.n} {2.n} .. {n-2.n}
02/20 00:16, 8F
→
02/20 00:18, , 9F
解為 n-2 再來考慮不含n的 {1.2..n-1} 解為 An-1
02/20 00:18, 9F
→
02/20 00:19, , 10F
遞迴關係式為 An=An-1+An-2 + n-2
02/20 00:19, 10F
→
02/20 00:19, , 11F
應該是這樣
02/20 00:19, 11F
推
02/20 07:49, , 12F
樓上正解!!
02/20 07:49, 12F
→
09/11 14:57, , 13F
A={1.2....n https://daxiv.com
09/11 14:57, 13F
‣ 更多 undefeated11 的文章
文章代碼(AID): #1FGFnXUK (Grad-ProbAsk)