[理工] 105 成大資工 遞迴

看板Grad-ProbAsk作者時間8年前 (2017/08/12 00:56), 8年前編輯推噓8(8推 0噓 14→)
留言22則, 3人參與, 最新討論串1/1
問題如圖: http://i.imgur.com/d2q0RMp.png
覺得詳解寫的還蠻奇怪的 題目說是要 奇數 有序分割 可是詳解卻有 首項為2 也就是 有偶數分割的情況... 這裡讓我很困惑 2016年有前輩大大們提出這題討論 附連結 https://www.ptt.cc/bbs/Grad-ProbAsk/M.1479731689.A.4B6.html 可是小弟不才還是看不太懂 所以問問今年的大大們對這題有沒有甚麼看法 要怎麼樣才能得出此遞迴就是費氏數列呢?? 感謝QQ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.93.59 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1502470586.A.757.html
→
08/12 01:55, , 1F
這題我會用 數字一個一個帶 然後發現遞迴是費式數列 故
08/12 01:55, 1F
→
08/12 01:55, , 2F
需要兩個初始條件 再想辦法掰出遞迴式
08/12 01:55, 2F
→
08/12 01:55, , 3F
不確定我的做法是對還錯 但我直觀會這麼做
08/12 01:55, 3F
推
08/12 08:29, , 4F
https://goo.gl/4bDDdV 所以 a8 是 6 嗎？
08/12 08:29, 4F
我也在想要不要就去先列初始值看看是不是費氏數 F大你是指維基裡面a8是6? ※ 編輯: jerry900287 (111.243.93.59), 08/12/2017 12:21:59 ※ 編輯: jerry900287 (111.243.93.59), 08/12/2017 12:22:19
推
08/12 12:57, , 5F
去年的文都冒出來了QQ
08/12 12:57, 5F
推
08/12 12:59, , 6F
假如這跟去年詳解一樣了話 這詳解覺得怪的地方就別懷
08/12 12:59, 6F
→
08/12 12:59, , 7F
疑 是錯的
08/12 12:59, 7F
是K大XD 我想問你就是 你說代2n+1和2n區別奇數和偶數 我很好奇 這樣要怎麼列式合併成一個遞迴 ※ 編輯: jerry900287 (111.243.93.59), 08/12/2017 14:07:41
推
08/12 15:23, , 8F
剛從成功嶺放出來智商還沒完全恢復 但我去年的想法
08/12 15:23, 8F
→
08/12 15:24, , 9F
應該是 第一列式為 偶數分割 + 奇數分割
08/12 15:24, 9F
→
08/12 15:25, , 10F
第二列式為 偶數分割 + 奇數分割(未知數退一數)
08/12 15:25, 10F
→
08/12 15:26, , 11F
兩式相減就可以求得 純奇數分割的遞迴式
08/12 15:26, 11F
我想超久 我懂了XD 感恩感恩
推
08/12 23:06, , 12F
我要說的是 partition into odd parts 跟
08/12 23:06, 12F
→
08/12 23:06, , 13F
partition into distinct parts 數目應該是一樣的
08/12 23:06, 13F
→
08/12 23:09, , 14F
sorry 我看錯了 這是 composition 不是 partition..
08/12 23:09, 14F
推
08/13 06:22, , 15F
如果是 composition 的話 可以這樣想
08/13 06:22, 15F
→
08/13 06:23, , 16F
最小的加數有兩個 case: 1 或是 > 1
08/13 06:23, 16F
推
08/13 06:25, , 17F
應該說首項有兩個 case: 1 或是 > 1
08/13 06:25, 17F
→
08/13 06:26, , 18F
首項是 1 時，把這個 1 拿掉 會是 n-1 的 composition
08/13 06:26, 18F
→
08/13 06:27, , 19F
首項 > 1 時，把首項扣 2 會得到 n - 2 的 composition
08/13 06:27, 19F
→
08/13 06:28, , 20F
我上面兩行 composition 是指 composition into odd parts
08/13 06:28, 20F
→
08/13 06:28, , 21F
所以就得到an = an-1 + an-2 的遞迴關係式了
08/13 06:28, 21F
F大 為什麼 首項 > 1 的時候,確定首項是 -2 ?? ※ 編輯: jerry900287 (36.227.254.205), 08/15/2017 10:24:07
推
08/15 20:16, , 22F
首項 > 1 而且又是奇數 所以至少是 3..
08/15 20:16, 22F
!!好像也行!! 感謝XD!! ※ 編輯: jerry900287 (36.227.254.205), 08/16/2017 19:15:46
‣ 更多 jerry900287 的文章
文章代碼(AID): #1PZU6wTN (Grad-ProbAsk)