[理工][資結]台大資工99軟體設計-核對
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
→
02/12 00:51, , 1F
02/12 00:51, 1F
MM 我知道我哪裡錯了~"~ 我一直把題目看成
Delete 會返回第二個元素
推
02/12 02:26, , 2F
02/12 02:26, 2F
→
02/12 02:27, , 3F
02/12 02:27, 3F
→
02/12 02:27, , 4F
02/12 02:27, 4F
→
02/12 07:57, , 5F
02/12 07:57, 5F
→
02/12 08:04, , 6F
02/12 08:04, 6F
※ 編輯: charliejack 來自: 61.231.68.229 (02/12 08:09)
※ 編輯: charliejack 來自: 61.231.68.229 (02/12 08:11)
推
02/12 19:14, , 7F
02/12 19:14, 7F
抱歉 我Key in Key 錯@@
以更正~
→
02/12 19:53, , 8F
02/12 19:53, 8F
推
02/12 22:19, , 9F
02/12 22:19, 9F
你可以從 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第一~三行 輸出都對了 通常答案就對了
→
02/12 22:20, , 10F
02/12 22:20, 10F
推
02/12 23:59, , 11F
02/12 23:59, 11F
推
02/13 00:44, , 12F
02/13 00:44, 12F
推
02/13 10:47, , 13F
02/13 10:47, 13F
※ 編輯: 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)
推
02/13 22:19, , 14F
02/13 22:19, 14F
哈哈 你說的對 這樣看的確是{Ci}才是答案~
恩恩 我確認過網路答案 謝謝糾正
※ 編輯: charliejack 來自: 61.231.71.224 (02/14 10:49)
※ 編輯: charliejack 來自: 61.231.71.224 (02/14 10:50)
推
12/09 03:05, , 15F
12/09 03:05, 15F
→
09/11 14:14, , 16F
09/11 14:14, 16F