作者taitin (小南)
看板Grad-ProbAsk
標題[理工] [資結]-96台大資工軟體設計 對答(含演算法部分)
時間Mon Jan 25 23:06:44 2010
我自己寫的答案
希望跟大家討論一下正確性
http://www.lib.ntu.edu.tw/exam/graduate/96/96419.pdf
1-a. empty(B)
1-b. !empty(A)
1-c. v=pop(A)
1-d. push(v,B)
1-e. v=pop(B)
2-a
A
/ \
C B
/ / \
F E D
\ / \
J H G
/
K
3-a index
3-b index+i-1
3-c index+1
3-d index+i-2
3-e B[j-i]+B[j-i+1]
4-a (m+1)I
4-b N(I+P)+P
(M+1)I-P
4-C N > -----------
I+P
5-a
(應該要化成兩個框框，方便起見就不畫了)
Eric->Jimmy___
^_____| (指自己....抱歉不會畫QQ)
Harry --- Adam
\ |
V V
Joe ---> Tom->Mary-->Kevin->Lucy___
George ----^ ^ ^ ^____|
John---| |
Barry__|
5-b
Mary colleages
John Tom Harry Joe George Adam Barry Kevin Lucy
6-a theta(nlgn)
6-b theta(3^n)
6-c theta(n^5)
6-d theta(lgn)
6-e theta(lgn)
7-a len[i,j]=len[i-1,j-1]+1
7-b len[i,j]=max{len[i-1,j],len[i,j-1]}
8-a 4
8-b 6
8-c -7
希望有寫這份的可以一起討論~
歡迎寄信或回(推)文
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.218.42
1F：推 nickboy0211:可以請你解說一下巴斯卡三角形那題你怎麼推出來的嗎？ 01/25 23:29
2F：→ nickboy0211:謝謝！ 01/25 23:29
3F：→ taitin:首先觀察到最後一句話 index=index+i 而i=1~n 可得知 01/25 23:45
^^剛打錯
4F：→ taitin:index為每列的列首 ex 第三列列首為4=1(初始)+1+2 01/25 23:46
5F：→ taitin:因此利用index的特性，且知道列首及列尾都是1 01/25 23:47
6F：→ taitin:因此 3a index 3b index+i-1(i為第i列故有i個數) 01/25 23:49
7F：→ taitin:因此 從第二個 到倒數第二個要加上一行的數 得 3c 3d 01/25 23:51
8F：→ taitin:而加的數為減掉該列數的數字跟下一個數字 01/25 23:52
9F：→ taitin:ex B[8]=B[8-4]+B[8-4+1] 因此可以得到3e 01/25 23:53
※ 編輯: taitin 來自: 61.230.218.42 (01/25 23:54)
10F：→ nickboy0211:感謝您的回履。 01/26 01:07
11F：推 polomoss:第一題我一直在想為何不用回復，把B的再丟回A 01/26 01:18
12F：推 polomoss:1-d push(v,B)才對吧? 還有1-a 應該B要為空才繼續做? 01/26 01:20
感謝樓上提醒..我發現我打錯XD，如果有困擾大家的，真抱歉。已修正
13F：推 polomoss:3-a 我答案只用i表達 (i^2-i)/2 +1 3-b (i^2+i)/2 01/26 01:23
應該是一樣的，我一開始也這樣寫，後來發現index比較好用
14F：推 polomoss:第4題哪裡有L，我只看到I 01/26 01:28
看來是我眼殘了....已修正
15F：→ polomoss:5-b 我覺得只有barry 01/26 01:28
因為他說同事是所有只要同一個super boss的都是同事，所以下面那整個群組的
superboss都是同事....我是這樣想的啦，包含lucy也是
16F：→ polomoss:6~8沒錯 01/26 01:29
※ 編輯: taitin 來自: 140.113.37.176 (01/26 08:56)
17F：→ polomoss:我還是覺得5-b應該只有barry 01/26 13:16
18F：→ polomoss:感覺改題老師應該不希望改那麼多名子，一個挺適當的 01/26 13:18
19F：→ polomoss:而且其他人都是MARY的下屬，感覺層級上就有差，不為同事 01/26 13:18
20F：→ polomoss:不過這大概也沒有正解@@ 01/26 13:18
哈..XD
21F：→ polomoss:1-a答案我覺得改成 !empty(A)比較好 01/26 13:19
22F：→ polomoss:B是用來輔助的，應該都是空的 01/26 13:19
可是這樣1-a不就多餘了嗎？
因為有while了阿
看一個例子 queue Q 利用這個演算法
add (1,Q) add (2,Q) delete() add(3,Q) delete() delete()
依據FIFO 應該是 1 2 3
可是如果改 !empty(A)
stack A 裡為 2 1 ，delete()時 stack B 為 1 2 ，pop(B) 輸出1
add(3,Q) stackA 裡有 3，非空，delete()時 stack 變 3 2 pop(B)輸出 3
這樣就有問題了
※ 編輯: taitin 來自: 114.44.234.233 (01/26 17:45)
23F：推 tureday:7-a 應該是len[i,j]=len[i-1,j-1]+1才對吧？ 02/03 02:46
24F：→ tureday:上一次算完串列的個數再加一..ai＝bj串列會增加一個 02/03 02:47
25F：推 yesa315:可能少打了吧 02/04 19:44
感謝樓上兩位，已修正
※ 編輯: taitin 來自: 140.113.7.249 (02/06 17:59)
26F：推 rockmanray:Eric Jimmy畫反了吧 02/05 11:35