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

看板Examination作者super75927 (黃鼠狼)時間10年前 (2015/07/17 04:33)推噓7(7推 0噓 23→)

留言30則, 13人參與討論串5/7 (看更多)

第一題我在考場瞪著他瞪了20分鐘以上後面寫不完可惡怒回這題請多包涵關鍵1: N 用 10^X 代入 log(n!) <= log N^N = N*logN = 10^X * X (關鍵2) (logn)! = (log10^X)! = X! 這樣就差不多了關鍵3: X 再用 10^10 代入 10,000,000,000^10 * 10,000,000,000 <====原logN! 10,000,000,000! <======原(logN)! 開始來數0的個數: logN! 大概有 110個 (logN)! 一項大概多10個贏定了這樣有算得證了嗎? 想了很久但題目的確出的很妙 (logN)! 忽然發現並不是N項相乘關鍵1再想到可以把較小的變大來比大小關鍵23最後再把N弄到足夠大一邊整理出易判讀形式思考過程滿好玩的但可惜考試並不是在玩花了好多年值得嗎 ※ 引述《malowda (malowda)》之銘言： : ※ 引述《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.160.25.204 ※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1437078780.A.7FA.html

→

malowda

07/17 06:48, , 1^F

07/17 06:48, 1^F

→

malowda

07/17 06:49, , 2^F

07/17 06:49, 2^F

→

APE36

07/17 08:16, , 3^F

07/17 08:16, 3^F