作者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