Re: [閒聊] 資訊處理已哭

看板Examination作者 (malowda)時間8年前 (2015/07/16 21:59), 編輯推噓13(13推 0噓 56→)
留言69則, 10人參與, 最新討論串4/7 (看更多)
※ 引述《RedJessy (Jessy)》之銘言： : 請問這次高考的資料結構 有高手可以分享一下嗎 ? : 第一題 不太會推..只有背他們的大小關係　就掰上去 不知道有沒有同情分數ˊˋ n^2LOG(N!)<n^2(LOGN)! => log(n!)<(logn)! =>log(1*2*3*...*n)<log1*log2*...*logn =>log1+log2+...+logn<log1*log2*...*logn : 第二題 是用數學歸納法嗎 ? n=2 0--0 2個點分支度都為1得證 設n<k 至少2個點分支度都為1 當n=k 將節點為n的tree的內部節點和樹葉節點分兩個集合 得內部節點節點小於k且樹葉節點為獨立的1個點分支度為0 將內部節點和樹葉節點用1個邊連接起來，原來的樹葉節點 為分支度為1得證 (二)反證法 設每個節點分支度>=2，假設都為2則n個節點有總分支為2n 因為為無向圖所以每個節點的分支度皆算了2次所以 總分支度為2n/2=n 和(一)矛盾所以具有n個節點n>1恰好有n-1個邊 : 第三題 我是把Dijkstar演算法簡單的寫一寫 (一)假設每個邊權重都一樣，用dfs找最短路徑O(n) (二)就Dijkstar寫給他 : 第四題和第五題沒想法... 第四題 用avl tree建m個值的avltree,再給比root大向右邊找比root小向左邊找的演算法 第五題 (一)用最壞的情況說(但回家想想好像會比n/2大) (二)n分群分成m群找出中間值logn 再從這些值找中間值 : 還有程式語言最後一題 (智慧卡進出系統) : 是要將3個class的內容都寫出來嗎 ? 然後順便改寫toString()? 這是我寫的是個人的想法請多多指教謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.158.134 ※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1437055183.A.6EC.html
推
07/16 22:05, , 1F
第三的第二是求任兩點 是用Johnson 之類的吧
07/16 22:05, 1F
推
07/16 22:07, , 2F
第四題我想的是從陣列第1元素開始比，若x比較大就和
07/16 22:07, 2F
→
07/16 22:08, , 3F
題目有說可以參考dijkstar但不用和dijkstar一樣詳細
07/16 22:08, 3F
→
07/16 22:09, , 4F
第2、4、8、16、32個元素比，直到x<陣列的元素在用Bin
07/16 22:09, 4F
→
07/16 22:10, , 5F
ary search搜尋~不知此想法是否符合題目要求
07/16 22:10, 5F
→
07/16 22:13, , 6F
因為我是看到題目說大部分x的值會出現在前面m個值，就用
07/16 22:13, 6F
→
07/16 22:14, , 7F
avl tree
07/16 22:14, 7F
推
07/16 22:16, , 8F
第一小題(logn)! 是這樣拆解的嗎？我以為是logn*((logn
07/16 22:16, 8F
→
07/16 22:16, , 9F
)-1)*((logn)-2)....求解
07/16 22:16, 9F
→
07/16 22:16, , 10F
看老師接不接受了
07/16 22:16, 10F
推
07/16 22:18, , 11F
我也是認為(logn)!是樓樓上說的那樣
07/16 22:18, 11F
→
07/16 22:18, , 12F
logn算出來如果是10 那不就是10! 答案跟原po寫的會不一樣
07/16 22:18, 12F
推
07/16 22:18, , 13F
johnson就是把所有的點做一次dijkstra
07/16 22:18, 13F
推
07/16 22:24, , 14F
第四題我寫的跟2F一樣 但感覺時間複雜度會超過
07/16 22:24, 14F
→
07/16 22:25, , 15F
但也想不出其他了 只好瞎掰
07/16 22:25, 15F
推
07/16 22:27, , 16F
題目有說明可以參考Dijkstra代表說這是唯一關鍵，我覺得用
07/16 22:27, 16F
→
07/16 22:27, , 17F
其他解法只會越描越黑而已
07/16 22:27, 17F
→
07/16 22:28, , 18F
這也是個人考生看法...有更完整的打臉推文，接受打臉^^"
07/16 22:28, 18F
→
07/16 22:28, , 19F
第一小題想想好像L大的才對哈哈網路上又找不到哈
07/16 22:28, 19F
推
07/16 22:42, , 20F
又看了一次題目 好像真的寫dijkstra就好了 我以為是要
07/16 22:42, 20F
→
07/16 22:42, , 21F
算出所有點的最短距離。。囧
07/16 22:42, 21F
→
07/16 22:46, , 22F
S到其他點的最短路徑阿
07/16 22:46, 22F
推
07/16 23:03, , 23F
大家都好強 我只能瞎掰
07/16 23:03, 23F
→
07/16 23:09, , 24F
@@..第一題不是可以推 (logn)! = O(n^loglogn)
07/16 23:09, 24F
→
07/16 23:12, , 25F
如果第一題寫B比較好 但是 推論有推出來 還是一樣會很低
07/16 23:12, 25F
→
07/16 23:12, , 26F
分嗎??
07/16 23:12, 26F
→
07/16 23:33, , 27F
log(n!)=O(nlogn) 看是要用stirling還是展開求都可以
07/16 23:33, 27F
→
07/16 23:33, , 28F
令 x = (logn)!
07/16 23:33, 28F
→
07/16 23:34, , 29F
logx = log((logn)!)
07/16 23:34, 29F
→
07/16 23:35, , 30F
右邊那串 跟 log(n!) 一樣 只是n變成logn
07/16 23:35, 30F
→
07/16 23:35, , 31F
so~ => O( (logn) * (log ( logn ) ) )
07/16 23:35, 31F
→
07/16 23:35, , 32F
stirling會牽扯到定積分，根本不適合拿來解此題
07/16 23:35, 32F
→
07/16 23:36, , 33F
所以用展開求呀~
07/16 23:36, 33F
→
07/16 23:48, , 34F
看來我寫根據stirling可知O(nlogn)錯了 忽略我的解法
07/16 23:48, 34F
→
07/16 23:50, , 35F
求神人解（logn）！
07/16 23:50, 35F
→
07/16 23:52, , 36F
裡面那串前後交換 => O( (log(logn)) * (logn) )
07/16 23:52, 36F
→
07/16 23:53, , 37F
把前面那個搬上去
07/16 23:53, 37F
→
07/16 23:53, , 38F
=> O(logn ^ loglogn)
07/16 23:53, 38F
→
07/16 23:54, , 39F
寫清楚一點 => O(log (n ^ loglogn) )
07/16 23:54, 39F
→
07/16 23:55, , 40F
logx = O(log(n ^ loglogn))
07/16 23:55, 40F
→
07/16 23:59, , 41F
x => O(n ^ loglogn) , x = (logn)!
07/16 23:59, 41F
→
07/17 00:00, , 42F
所以 (logn)! = O(n ^ loglogn) ...
07/17 00:00, 42F
→
07/17 00:01, , 43F
然後各自把前面的n^2乘進來
07/17 00:01, 43F
→
07/17 00:03, , 44F
一個會是 (n^3)*logn
07/17 00:03, 44F
→
07/17 00:04, , 45F
另一個是 n^2 * n^loglogn = n^(2+loglogn)
07/17 00:04, 45F
→
07/17 00:06, , 46F
在n很大的時候 n^(2+loglogn)會遠遠大於(n^3)*logn
07/17 00:06, 46F
→
07/17 00:09, , 47F
不過我把log(n!) = O(nlogn)是用stirling代過..
07/17 00:09, 47F
→
07/17 00:09, , 48F
所以可能不太行吧..qq
07/17 00:09, 48F
推
07/17 00:17, , 49F
e大好強阿 上面也有很多神人 小弟都不知道在寫甚麼
07/17 00:17, 49F
推
07/17 00:19, , 50F
小弟國考路已走到盡頭 只能祈禱這次會有奇蹟出現了
07/17 00:19, 50F
→
07/17 00:49, , 51F
@@我專案管理可能0分呢XD 真是悲劇~
07/17 00:49, 51F
→
07/17 00:52, , 52F
我後來仔細看內聚力他要從差寫到好 我寫反了XDDD
07/17 00:52, 52F
→
07/17 00:54, , 53F
我也就內聚力那題好像可以寫些東西 其它都不會..@@
07/17 00:54, 53F
→
07/17 00:57, , 54F
8月沒考專案管理 所以我也都沒念~_~
07/17 00:57, 54F
推
07/17 01:03, , 55F
不會啦 我覺得你很有機會會上 不要太擔心
07/17 01:03, 55F
→
07/17 01:04, , 56F
我需要奇蹟才可能會上 只能先做好心理建設
07/17 01:04, 56F
→
07/17 01:18, , 57F
哀我也希望八月能考上 順利的話一定回來回報各位~_~
07/17 01:18, 57F
→
07/17 01:28, , 58F
o大你別想太多@@ 放鬆心情等放榜吧!! 搞不好會上 :)
07/17 01:28, 58F
推
07/17 03:02, , 59F
(logN)! N=10^X 代入 是不是能看出來cc ?
07/17 03:02, 59F
→
07/17 03:08, , 60F
另一邊應該小於log(N^N) = N*logN 也用 N=10^X 代入
07/17 03:08, 60F
→
07/17 06:16, , 61F
所以e大也是謝a>b嗎
07/17 06:16, 61F
→
07/17 06:17, , 62F
錯是a<b
07/17 06:17, 62F
→
07/17 06:19, , 63F
手殘要寫a<bㄧ直沒用好
07/17 06:19, 63F
→
07/17 06:20, , 64F
不是我沒寫好ptt會吃小於b
07/17 06:20, 64F
→
07/17 07:46, , 65F
恩A < B , 所以應該選A演算法
07/17 07:46, 65F
→
07/17 08:34, , 66F
謝謝e大
07/17 08:34, 66F
→
07/17 09:49, , 67F
內聚力那題看程式碼可以推得出 只是要花時間
07/17 09:49, 67F
→
07/17 09:50, , 68F
時程壓縮和CMMI都是申論形式分數難講
07/17 09:50, 68F
→
07/17 09:55, , 69F
我也只把定義寫出來再畫圖推 V MODEL定義很簡單但忘了
07/17 09:55, 69F
‣ 更多 malowda 的文章
文章代碼(AID): #1LfxZFRi (Examination)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 4 之 7 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共7篇)
‣ 更多 malowda 的文章
文章代碼(AID): #1LfxZFRi (Examination)