1.不大懂題目的意思P1,P2是向量,向量連成的線段是??這題感覺像是高中的題目......
b跟c題也不會
4.題目裡只說(G,*)是群,如果沒定義*的運算,這題可以確定答案嗎?
另外還有一題,求其bigO
k=0
for (i=0 to n-1)
for (j=0 to i^2 -1)
if (j%i==0)
for(z=0 to j-1)
k++;
這題該怎麼解?
問題有點多 麻煩解答了 謝謝
Research Space for Linear Algebra & Discrete Mathematics
4 則留言:
1. 大概就形容一下那些形狀是由哪些線段所圍成的, 譬如像是p2-p1, etc.
(b) 先考慮前 k 個數為 decreasing, 這相當於由 n 個數中取 k 個數出來, 再將它們做decreasing的排列, 然後剩下的n-k個數隨便排, 所以總數就是c(n,k)(n-k)!, 同理如果考慮前 k+1 個數為decreasing的話, 則總數為c(n,k+1)(n-k-1)!, 所以機率就是
[c(n,k)(n-k)!-c(n,k+1)(n-k-1)!]/n!
= 1/k! - 1/(k+1)!
(c) 由(b),
Σ[k=1~n-1] k(n!/k! - n!/(k+1)!) + n(n!/n!)
= ... = Σ[k=1~n] 1/k!
4. 這問題的敘述簡單來說就是問子群的關係是否為一個partial order, 而子群的關係雖然具有transitive和antisymmetric, 但因為沒有reflexive (譬如任取一個 G 中的元素, 除了單位元素以外, 所形成的集合都不能形成group), 所以答案是no
5. (algorithm) 我們可以先觀察出每當執行到最後一個for迴圈時, 總共就會在裡面跑 j 次, 接著就來看甚麼時候會執行到最後一個for迴圈: 因為j%i=-0時才會進到最後一個for迴圈, 也就是當 j 為 i 的倍數, j=i,2i,3i,...,floor((i^2-1)/i)*i 時會進去, 所以這些 j 的加總就是 i+2i+...+floor((i^2-1)/i)*i
= (i+floor((i^2-1)/i)*i) * floor((i^2-1)/i) /2
= O(i^3 + i^2), 再把所有的 i 做加總, 結果就是 O(n^4)
上面(c)的左式要整個再除以 n!, 我忘記打了
關於第一題可以麻煩助教解題一下嗎?
還有第四題,但因為沒有reflexive (譬如任取一個 G 中的元素, 除了單位元素以外, 所形成的集合都不能形成group), 所以答案是no
可再說的詳細一點?
麻煩了,感謝
1.
(1) ||P2-P1||
(2) parallelogram為包含四個頂點座標為 O,P1,P1+P2,P2 所連的四邊形
(3) 由 O,P1,P2 所連成的三邊形
(4) 由 P1,P2,P3 所連成的三邊形
(5) convex n-sided polygon 為一個由n個點所圍成的平面, 其中任兩點所連成的直線都會在polygon中
4. 譬如 G = Z_2 在加法, 若取 {1} in 2^G-{}, 因為 {1} 不是群, 所以{1}也就不會是{1}的subgroup, 所以 R 不具 reflexive
張貼留言