[理工][資結]台大資工99軟體設計-核對

[charliejack (charliejack)]

1.
count[0]=34
count[1]=55
count[2]=34
count[3]=21
count[4]=13
count[5]=8
count[6]=5
count[7]=3
count[8]=2
count[9]=1
count[10]=1

Reason:
if i>= 1 fab(i) 只會被 fab(i+1) & fab(i+2) 呼叫
所以 count[i]= count[i+1] + count[i+2]

i=0時 因遞迴的結束條件包含n=1;
所以 count[0] = count[2]

2.

for(i=0; i<20; i++){
 if((x = peek())==0)
    insert(0)
 printf("%d\n", x);
 insert(delete() + peak());
}

3.
Build d-heap 和 max-heap 很像
可以用的Array 的Data Structure 儲存Data
Bottom-up方法 Construct d-heap

First-step Build d-heap:
將Input 放在 陣列裡面
在d-heap之中 還是能經過數學式子導出Parent的所在
然後用遞迴的方式 從最下面 最右邊 的Subtree開始做

遞迴中 將 node 和 d個Child 做比較
將最大元素和node swap.
持續做到 root層
這樣就Build 出 d-heap tree

Second-step removing the largest element
A:
移除root
將最尾端的Element Replace root
這次從Root 沿著 被Replace 的 Element方向
開始做遞迴 直到 Replace 結束 或 到達最大Level

重複A步驟 直到最後一點被移除

(b)
我先睡了~"~

4.

(a) (A1( ( (A2A3) A4) A5))

(b)146000

5.
用遞迴DFS 去dicover node
如果node 有重複 表示必有迴圈存在

V: Vertex Set
D <-ψ

function DFS-cycle
  for each vε (V-D)
        if(DFS(v) = true) then return ture;
  return false

function DFS(v)
   for each uεAdj(v)
       D <- D ∪ v;
       if ( (Adj(u)-{v} = ψ)) //假如是尾端的 Vertex
                  return false;
       else if ( (Adj(u)-{v}) ∩ D = ψ) //DFS
                  if(DFS(u) = true) return true;
       else return true;
   return false;



6.
(6-a)  (1)|R ∩ Ci|
  (2) {Ci}               **要加括號

(6-b)
  U={1,2,3,4,5,6,7,8,9,10}
  C1={1,2,6,7,8}
  C2={3,4,9}
  C3={1,2,3,4,5}
  C4={6,7,8,9,10}

Greedy Algorithm 找尋的順序 可能會是 C1->C2->C3->C4

而optimal solution is C3->C4

So Greedy Algorithm找到的Subset會是Optimal solution 的兩倍



有問題可以交流一下~

(3b) 還沒寫完 感冒有點想睡了...... 明晚在努力

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.231.68.229
→ ybite:第二題最後是insert(delete() + peak());
MM 我知道我哪裡錯了~"~ 我一直把題目看成
Delete 會返回第二個元素
推 ai305428d:我對6.(b)一直有個疑問
→ ai305428d:為什麼greedy第一個會挑c1而不是c4
→ ai305428d:題目上也沒有表明一定要從c1開始檢查
→ charliejack:要假設呀 冏 他只是要一個Example~ 他要一種情況
→ charliejack:因為你Greedy 通常要嗎是FCFS 不然就是 LCFS
※ 編輯: charliejack     來自: 61.231.68.229        (02/12 08:09)
※ 編輯: charliejack     來自: 61.231.68.229        (02/12 08:11)
推 boy5548:6(1)是R交集Ci吧??
抱歉 我Key in Key 錯@@

以更正~
→ owen78:寫|C'聯集Ci|感覺也可以?????
推 wolfswolfs:想問一下第二題那code到底是怎麼去思考然後追出來的?
你可以從 Pascal's triangle

每個Element會跟他上層Level的兩個值"相依(加)"去思考

然後在這 你可以把他的0 看成要換行的意思

和 當Pascal 最左邊 和 最右邊的元素的 identity

Example: 1+0=0 0+1=0 //Pascal最左邊最右邊皆為1

他先Insert(0) Insert(1);

第一層他預設先形成 表示要換行了

So x==peek() == 0 要 insert(0); //一個換行符號

再來程式 不難發現 他每次一定要Print("%d\n",x);

所以一定要輸出一個元素

So 你必定要在元素Output之後 把他下一層的相依元素 Insert();

你要做的有兩件事情

Insert(一是刪除此元素 並取出他的值 +_ 下一個元素的值);

Answer: Insert(delete() + peek());

你Trace第一~三行 輸出都對了 通常答案就對了
→ wolfswolfs:6-a覺得是交集+1
推 cksh3300110:是交集我在COREMEN上有看過這個演算法
推 ai305428d:可以請問樓上是在哪個章節嗎??
推 cksh3300110:最後面35章好像  就近似演算法那裡
※ 編輯: charliejack     來自: 61.231.68.229        (02/13 11:33)
※ 編輯: charliejack     來自: 61.231.68.229        (02/13 11:46)
※ 編輯: charliejack     來自: 61.231.68.229        (02/13 11:50)
推 rnbjacky:6.B  {Ci}   C'應該是蒐集集合?  否則最後C' = U
哈哈 你說的對 這樣看的確是{Ci}才是答案~

恩恩 我確認過網路答案 謝謝糾正
※ 編輯: charliejack     來自: 61.231.71.224        (02/14 10:49)
※ 編輯: charliejack     來自: 61.231.71.224        (02/14 10:50)
推 RdMax:推一個
→ sneak: 6-a覺得是交集+1 https://daxiv.com