[核對] [軟體]-師大100-資工
看板Grad-ProbAsk作者love5566188 (I'dont kown)時間12年前 (2012/02/07 22:46)推噓0(0推 0噓 1→)留言1則, 1人參與討論串1/3 (看更多)
小弟自寫的答案,與大家核對看看,若有錯請幫提醒改正
1.
1.1 c
1.2 d
1.3 d
1.4 b
1.5 d
1.6 a
1.7 c
1.8 b
1.9 c
1.10 c
1.11 c
1.12 c
1.13 d
2.
(a)5
(b)node[5]
3.
(a)0129375468
(b)3459170268
4.
a = 1
b = 1
c = 1
d = 0
e = 0
5.
eo 0 1 e2 e1
e1 1 2 null e2
e3 0 2 null null
6.
(a)
-1 ╱ 0 1 2 ╲
A = ∣ 3 0 0 ∣
╲ 3 6 0 ／
(b)
1 ╱ 0 3 3 ╲
A = ∣ 1 0 4 ∣
╲ 2 5 0 ／
7.
(a)
╱ 1 2 3 4 ╲
A = ∣ 5 6 7 8 ∣
∣ 9 1 2 3 ∣
╲ 4 5 6 7 ／
= ╱ a11 a12 ╲
╲ a21 a22 ／
其中 a11 = ╱ 1 2 ╲
╲ 5 6 ／
a22 = ╱ 2 3 ╲
╲ 6 7 ／
╱ 8 9 1 2 ╲
B = ∣ 3 4 5 6 ∣
∣ 7 8 9 1 ∣
╲ 2 3 4 5 ／
= ╱ b11 b12 ╲
╲ b21 b22 ／
其中 b11 = ╱ 8 9 ╲
╲ 3 4 ／
b22 = ╱ 9 1 ╲
╲ 4 5 ／
代入 m1 = (a11 + a22)(b11 + b22)
(b)
2 * 2 * 2 * 7 = 56
(c)
(此recurence是參考97台大其中一題的strassen's algo)
T(n) = 7T(n/2) + O(n^2)
(d)
T(n) = O(n^log7)
(e)
4 * 4 * 4 = 64
8.
(1)自一點作BFS,最後一點稱u
(2)從u作BFS,最後一點稱v
(3)u到v即為longest simple path
9.
(i)
(j)
┌─┬─┬─┬─┐
│ │ I│ │ │
├─┼─┼─┼─┤
│ │ │ │I │
├─┼─┼─┼─┤
│I │ │ │ │
├─┼─┼─┼─┤
│ │ │ │ │
└─┴─┴─┴─┘
(k)
┌─┬─┬─┬─┐
│ │ I│ │ │
├─┼─┼─┼─┤
│ │ │ │I │
├─┼─┼─┼─┤
│I │ │ │ │
├─┼─┼─┼─┤
│X │X │I │ │
└─┴─┴─┴─┘
(ii)
┌─┬─┬─┬─┐
│ │ I│ │ │
├─┼─┼─┼─┤
│ │ │ │I │
├─┼─┼─┼─┤
│I │ │ │ │
├─┼─┼─┼─┤
│ │ │I │ │
└─┴─┴─┴─┘
┌─┬─┬─┬─┐
│ │ │ I│ │
├─┼─┼─┼─┤
│ I│ │ │ │
├─┼─┼─┼─┤
│ │ │ │ I│
├─┼─┼─┼─┤
│ │I │ │ │
└─┴─┴─┴─┘
(iii)
這題圖太難用放棄= =
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.98.50.200
→
02/09 14:44, , 1F
02/09 14:44, 1F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 3 篇)：