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

[YuxiWen (yu)]

第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
推 yupog2003: 第四題那種作法也是可以，只是題目要求先猜再證明，也
→ yupog2003: 許就是想考會不會數學歸納法，不然這題直接用那個作法
→ yupog2003: 簡直是秒殺又有8分，不太像是可以接受這樣的作法
     原來如此，還是要看清楚題目說什麼。謝謝!
※ 編輯: YuxiWen (122.116.253.188), 01/20/2017 10:01:33
→ w181496: 第8. dfn[u]表示u在dfs中的次序，low[u]表示u或u子樹通過
→ w181496: 非父子邊追溯到的最早祖先 題目的function就是在算這兩
→ w181496: 個
→ w181496: 而有了low和dfn 就能求關節點
原來如此，我先吸收一下，十分感謝你的解答~
推 h04mp6286: 想請教for第一輪的dfnlow(w,u);的的w是多少 u是5吧
推 h04mp6286: w=graph[5]->vertex; 那graph[5]->vertex是多少啊
→ w181496: 題目有說跑完後dfn[3]=5 所以5會先遍歷右邊完才跑3，所以
→ w181496: w可能是6或7吧
    請問我答案這樣寫對嗎？
(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
→ w181496: 8 5 5應該沒錯
     感謝!!!
※ 編輯: YuxiWen (42.73.122.147), 01/21/2017 15:35:27