Re: [理工] [離散]-中山96-資工所
※ 引述《cakeboy ()》之銘言:
: ※ 引述《mqazz1 (無法顯示)》之銘言:
: : http://www.lib.nsysu.edu.tw/exam/master/eng/infoe/infoe_96.pdf
: : 第七頁的第七題
: : 請問這題的題目是在問什麼?
: : 應該要怎麼列遞迴式呢?
: : 謝謝
: a1=0 a2=1 a3=1 a4=2
: 對n>=4
: 對 n分解
: 首項為2 則後段剩下n-2欲分解成每項至少為2的有 an-2種
: 首項為3 則後段剩下n-3欲分解成每項至少為2的有 an-3種
: 首項為4 則後段剩下n-4欲分解成每項至少為2的有 an-4種
: 首項為n-2 則後段剩下2欲分解成每項至少為2的有 a2種
: 首項為n 則為一種
: 故得 an= an-2 + an-1 + ...+a3+ a2+1
: an+1= an-1 + ...+a3+ a2 + 1
: 所以 an+1=an-1 + an
: an+1=an-1 + an n>=4
: a1=0 a2=1 a3=1 a4=2
: 接下來就Fn套下去啦
: an=fn-1
直接往回想會不會比較簡單阿?
(可先看下方的例子)
(i)
n 比 n-1 多了 1
而因為最小項至少是2 所以這個1一定是加到an-1各組合中的某一項
(ii)
n 比 n-2 多了 2
這就讓 an-2 中的各項組合中多了2這項
不可加到an-2各組合中的某一項 因為會和an-1形成的重複
好像有點複雜 = =
舉個例子好了
n = 4 : 2 2 , 4 => a4 = 2
n = 5 : 2 3 , 3 2 , 5 => a5 = 3
n = 6 : (i) 2 (3+1), 3 (2+1), (5+1) -> 2 4, 3 3, 6
(ii) (2) 2 2, 4 (2) -> 2 2 2, 4 2
=> a6 = 5
提供大家另一個想法 不過解釋的好像有點糟糕= =
這想法應該沒錯吧@@"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.243.152.161
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 3 篇):