[理工] 清大 104 計科 第4題、第8題

看板Grad-ProbAsk作者 (yu)時間9年前 (2017/01/20 00:25), 9年前編輯推噓3(3推 0噓 9→)
留言12則, 3人參與, 最新討論串1/1
第4題題目 http://i.imgur.com/l3j03jD.jpg
我看書上詳解都是用數學歸納法證明， 可以用直接帶入法帶入嗎？ 比如: An = 3*An-1 + 1 = 3*(3*An-2 + 1) + 1 : : =最後的結果 第8題題目 http://i.imgur.com/Lbl0OmQ.jpg
http://i.imgur.com/19aydly.jpg
有人能解釋一下題目dfn在做什麼嗎？ 看了好久還是沒想到在做什麼， 只知道圖示在教articulation point的時候 有拿該圖當例子而已，不知道有沒有相關? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.116.253.188 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484843146.A.C5E.html
推
01/20 07:18, , 1F
第四題那種作法也是可以，只是題目要求先猜再證明，也
01/20 07:18, 1F
→
01/20 07:18, , 2F
許就是想考會不會數學歸納法，不然這題直接用那個作法
01/20 07:18, 2F
→
01/20 07:19, , 3F
簡直是秒殺又有8分，不太像是可以接受這樣的作法
01/20 07:19, 3F
原來如此，還是要看清楚題目說什麼。謝謝! ※ 編輯: YuxiWen (122.116.253.188), 01/20/2017 10:01:33
→
01/20 11:09, , 4F
第8. dfn[u]表示u在dfs中的次序，low[u]表示u或u子樹通過
01/20 11:09, 4F
→
01/20 11:10, , 5F
非父子邊追溯到的最早祖先 題目的function就是在算這兩
01/20 11:10, 5F
→
01/20 11:10, , 6F
個
01/20 11:10, 6F
→
01/20 11:13, , 7F
而有了low和dfn 就能求關節點
01/20 11:13, 7F
原來如此，我先吸收一下，十分感謝你的解答~
推
01/20 11:29, , 8F
想請教for第一輪的dfnlow(w,u);的的w是多少 u是5吧
01/20 11:29, 8F
推
01/20 11:32, , 9F
w=graph[5]->vertex; 那graph[5]->vertex是多少啊
01/20 11:32, 9F
→
01/20 11:39, , 10F
題目有說跑完後dfn[3]=5 所以5會先遍歷右邊完才跑3，所以
01/20 11:39, 10F
→
01/20 11:39, , 11F
w可能是6或7吧
01/20 11:39, 11F
請問我答案這樣寫對嗎？ (a)dfn[1]=8 (b)low[1]=dfn[3]=5 (c)low[2]=low[1]=5 謝謝 ※ 編輯: YuxiWen (114.137.195.239), 01/20/2017 15:32:37 ※ 編輯: YuxiWen (114.137.195.239), 01/20/2017 16:42:28
→
01/21 15:05, , 12F
8 5 5應該沒錯
01/21 15:05, 12F
感謝!!! ※ 編輯: YuxiWen (42.73.122.147), 01/21/2017 15:35:27
‣ 更多 YuxiWen 的文章
文章代碼(AID): #1OWEYAnU (Grad-ProbAsk)