Research Space for Linear Algebra & Discrete Mathematics
1. 題目的意思他已經有舉例說明了, 譬如說取 n=2, 在長度為 n^2+1=5 的序列中, 在長度為 n+1=3 的遞增或長度為 3 的遞減序列這兩者之中我們一定可以找到其一, 例如在 15342 裡可以找到 134 為遞增子序列和 542 為遞減子序列, 你可能要說明一下是哪個地方看不懂我才比較能試著幫你理解書上的想法2. 因為我們從 S 裡得找到 2 組相加為 9 的 pair, 所以 k 至少要 5+2=7, 6 還不夠, 譬如說在 {0,1,2,3,4,5} 就找不到兩個 disjoint 且相加為 9 的 pair, 7 就 OK, 因為將 S 分為以下這 5 堆: {0,9}, {1,8}, {2,7}, {3,6}, {4,5}, 則最壞的情況就是這五堆裡每堆取到一個, 外加有兩堆被取完, 所以答案是 C
Q1: 從則1<=xk, yk<=n 所有K=1,2,3....,n^2+1 開始到最後=.=麻煩助教了
書上那一段我是覺得每一句話都寫的滿詳細的, 或許你可以先參考以下這個討論串, 看看能不能幫助你理解: http://zjhwang.blogspot.com/2009/03/blog-post_21.html
助教我今天看了一下關於那題有點懂了!!我想這樣想應該是對的就是:他說因為ai!=aj若ai < aj 則xi > xj 這句話意思是說,如果aj比ai還要大 則ai的遞增序列xi會大於xj囉!! 可是這樣的話不是應該是相等嗎? 為什麼會大於 !!還是我觀念錯了呢?
若 ai<aj, 則取由 aj 開始的最長遞增字串, 令其為 sj, 則把 sj 皆在 ai 後面可形成一更長的遞增字串, 其長度為 xj+1, i.e., xi = xj+1 > xj, 這樣會矛盾我們所取出來的那兩個pair, xi=xj; 同理, 若 ai>aj, 此時會矛盾 yi=yj, 那這樣就證完了
張貼留言
這題可否說明一下他要我們求甚麼答案 ,是要我們找最少要取幾次就有任意兩個數的和為9的嗎?
5 則留言:
1. 題目的意思他已經有舉例說明了, 譬如說取 n=2, 在長度為 n^2+1=5 的序列中, 在長度為 n+1=3 的遞增或長度為 3 的遞減序列這兩者之中我們一定可以找到其一, 例如在 15342 裡可以找到 134 為遞增子序列和 542 為遞減子序列, 你可能要說明一下是哪個地方看不懂我才比較能試著幫你理解書上的想法
2. 因為我們從 S 裡得找到 2 組相加為 9 的 pair, 所以 k 至少要 5+2=7, 6 還不夠, 譬如說在 {0,1,2,3,4,5} 就找不到兩個 disjoint 且相加為 9 的 pair, 7 就 OK, 因為將 S 分為以下這 5 堆: {0,9}, {1,8}, {2,7}, {3,6}, {4,5}, 則最壞的情況就是這五堆裡每堆取到一個, 外加有兩堆被取完, 所以答案是 C
Q1:
從則1<=xk, yk<=n 所有K=1,2,3....,n^2+1 開始到最後=.=
麻煩助教了
書上那一段我是覺得每一句話都寫的滿詳細的, 或許你可以先參考以下這個討論串, 看看能不能幫助你理解: http://zjhwang.blogspot.com/2009/03/blog-post_21.html
助教我今天看了一下關於那題有點懂了!!
我想這樣想應該是對的就是:
他說因為ai!=aj
若ai < aj 則xi > xj 這句話意思是說,如果aj比ai還要大 則ai的遞增序列xi會大於xj囉!! 可是這樣的話不是應該是相等嗎? 為什麼會大於 !!
還是我觀念錯了呢?
若 ai<aj, 則取由 aj 開始的最長遞增字串, 令其為 sj, 則把 sj 皆在 ai 後面可形成一更長的遞增字串, 其長度為 xj+1, i.e., xi = xj+1 > xj, 這樣會矛盾我們所取出來的那兩個pair, xi=xj; 同理, 若 ai>aj, 此時會矛盾 yi=yj, 那這樣就證完了
張貼留言