第九題
在寫離散的求複雜度時，是不是要把critical path上的每一個statement都算進去?
我選的是D，因為AB顯然是錯的，C的話硬要說的話就是少一個sita(1)
老師的答案是給2sita(n)，說因為在二行的時候有一個sita(n)第三到六行又有一個巢狀結構
我的想法跟老師該題後面的註記一樣，因為sita在定義的時候就已經有＂存在一個C1C2...＂所以在他前面加上任何常數應該是沒有意義才是
如果這樣繼續推下去其實那個宣告array2和3的也是兩個sita(1)
if裡面的statement也算是一個sita(1)，那樣變成好像沒完沒了
因為這題在中央的考題中出現不止一次，所以我在想說D應該也算是答案的一種吧?
// =======================================================
第十七題
題目沒有說Q是可逆，怎麼答案裡面自己就給他AQQ-1了?
// =======================================================
拓蹼排序:
老師在書上提供了一種排法，那種排法有點感覺像是在求AOE的方法
不過我想說再寫離散題目時是不是也可以用cormen那本書上說的先做DFS後根據其finish time當作sort的根據?
7 則留言:
我沒解答耶..
我9也選D
想請問原本答案是哪個?
call B--(o(1)) // 陣列宣告
for i =1 to n (o(n))
17答案不是D?
和Q可逆有何關係?
我覺得 topological sort
和 dfs 意思不太一樣耶
雖然都可以拿來求spanning tree啦?
但是我想你應該不是這意思吧
能有例子舉例嗎?
昨天又寫了99的中央，我看全部在這篇一起問好了
1.99中央第3題
計算複雜度老師的答案變成Cn = Cn/2 + sita(n) + sita(1)和沒有sita(1)
可是我看9899兩張考卷給的code感覺上沒甚麼差別，硬要說的話就是下面的else變成if，不過理論上應該是沒差
已經對於這種題目的解法有點混亂了
// =======================
2.99中央第1題B選項：
我記得老師上課的時候是說對角線證明是在證明(0,1)區間不可數，可是有證明出|R|>|N|嗎?
(i.e.是否只要證明集合不可數就是證明了該集合比可數大?)
我知道無限有分可數不可數，但是他們的size關係我記得老師上課是說這個叫做連續統假設，所以那個大於上面打一個問號
// =======================
3.99中央第3題A選項
抱歉以下可能會有點亂，但我盡量表達出我的意思
我答案有選A，因為我這樣想
我們可把原題目的敘述
P->Q 改寫成 !P ˇ Q
所以變成
存在xy !( O(x) ^ !E(y) ) ˇ !D(x,y)
然後在"存在xy"和第一個not中間加上兩個not，變成
存在xy !! ( !( O(x) ^ !E(y) ) ˇ !D(x,y) )
然後左邊的!跟左邊合體，右邊的!跟右邊合體，變成
對所有xy O(x) ^ !E(y) ^ D(x,y)
(對所有奇數x且y為x的倍數且y不是偶數)
如果這樣的話，選項A好像也說得通吧?
// =======================
4.99中央第6題：
老師答案是寫AC，這應該是在一般的河內塔的case吧
不過讀題目第三行，＂transferring the discs only to adjacent peg＂
題目應該是說，一次只能移動到鄰近的柱子，然後，題目也沒有說是要從哪根柱子移動到哪根
假設是從最左邊到最右邊且一次只能動一步的話那好像五個都選不了，但如果要選AC的話好像又不滿足一次只動一根
所以想問問老師當初解這題的想法
// =======================
5.中央99第9題：
解答題目直接抄錯
所以答案應該是?
// =======================
6.中央99第10題：
話說B = A^2，A是集合，那B是什麼?難道是A的adjaceny matrix的平方嗎?
// =======================
7.回助教
17題我看那本解答上面是寫BD，所以想問說B是怎麼導出來的
topological sort我只是想問問寫法，因為cormen的書上提供另一種，且老師上課說excel中偏序變成全序的方法就是亂排，排序的答案顯然不唯一
所以我在想說既然演算法和離散都各出現一種求法，那我是不是只要背一個就好比較不會混淆
2.這題的B是有選的,對角論證法是一種矛盾證法來證明實數的個數比自然數多
3.應該是A,B
圖畫出來是一個開口向上的拋物線,頂點是(-7,-100),與x軸相交於2點(3,0),(-17,0)
在一個選項一個選項討論
6.那是B=AxA (A跟A做卡斯基)
98.9. 就複雜觀點來看, theta(n)前面加個常數意義不大, 所以答案選(c),(d)是OK的
98.17. 這一題有勘誤過, Q沒有給可逆, 答案只有(d)
寫離散時不用把Topological sort想得太複雜, 它只是因為partial order set沒有唯一的order, 所以希望定義一個新的唯一order
99.3. 這種題目就按照我們對於複雜度的想法, theta(n) + theta(1) = theta(n), 答案選(a)(d)
99.1. A is countable, B is uncountable, 則|A| < |B|, 這是可以證的, 不是很嚴謹說明如下, 首先|A| = |B|不可能, 如果|A| > |B|那表示B is countable, 也矛盾, 因此|A| < |B|, 所以證明了R is uncountable, 那|R| > |N|
99.2. For all x, y, O(x) ^ ~E(y) ^ D(x,y), 這句話並不是表示"沒有奇數可以整除偶數", 這句話的意思是"任取二個數x, y, x一定是奇數, y也一定是奇數而且x一定整除y", 因為它是用and連起來, 代表三句話要恆為true才會true, 也就是說這句話永遠都是false
99.6. 這題也有勘誤過, 答案是(b)(e), 因為題目說移到另一根柱子即可, 所以移到旁邊那一根所需的移動次數比移到第三格來得少
99.9. 解答一樣, f的極小值變成在-7的地方, f(-7) = -100, f(-8)=f(-6)=-99, f(-5)=f(-9)=-96, 所以一樣的說明方式, 答案仍是(b)
另外, 助教最近有些其他事, 所以暫時沒空回各位問題, 所以回您的我想應該不是助教才對, 如果還有什麼問題, 歡迎同學們一起討論, 考試也快到了, 同學們一定要依自己規劃的進度一步一步前進
99中央第9題
我想我可能沒有問得很好，就是說，如果極值在負7的地方，那麼A敘述的domain為N，N是大於等於零的整數，那麼f應該是1-1函數吧?
話說，有沒有哪個地方可以看到所有勘誤的清單?因為我手邊只有一本書然後只知道這個部落格而已
(話說我一直以為一樓的是助教...我看他每篇都回)
張貼留言