作者super75927 (黃鼠狼)
看板Examination
標題Re: [閒聊] 資訊處理已哭
時間Fri Jul 17 04:32:57 2015
第一題我在考場瞪著他瞪了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: 你這樣怎麼看起來怪怪的 10000000000!這樣會大於 07/17 06:48
→ malowda: 10000000000^10*10000000000 07/17 06:49
→ APE36: 推，好一個暴力破解...但是疑惑如MAL大所提的問題 07/17 08:16
→ malowda: 不用疑惑是我看錯了 07/17 08:33
推 dogalan: 原po沒弄錯吧XD 我也是邊推邊說明可以假設10^X這樣 07/17 08:49
→ dogalan: 會比較容易看出兩者的關係差異 07/17 08:50
→ testPtt: 通常這種題目就是要考微積分 07/17 08:53
推 linklink: 選了b比較好 就真的掛了嗎？ 07/17 09:28
推 smalldulan: 看完終於惑然開朗了！謝謝分享 07/17 09:41
推 alan0204: 答案是A沒錯 只是證明過程是在考數學嗎 07/17 09:47
→ alan0204: 整張都是演算法 證明 演算法 證明 2hr根本不夠寫 07/17 09:56
→ super75927: N小時基本值少的好 N大時成長幅度小的好 考點1 07/17 11:17
→ super75927: 兩者N=多少時交會 怎比出複雜度 有多層鑑別度的神考題 07/17 11:21
→ super75927: 雖然被搞死了 但一題把複雜度內容幾乎考完 真的有點神 07/17 11:28
→ cheng9115053: 看來大家考完資料壓力真的都很大！ 07/17 11:32
推 alan0204: 因為解一題可能要40分鐘以上 時間壓力超大 07/17 11:36
→ emstarbucks: 恩@@這題(logn)!其實高點的講義有 07/17 11:41
→ emstarbucks: 不過我不知道王老師國考那本有沒有收錄 07/17 11:42
→ oklp1415: 糕點講義?不就是王老師那本課本? 在前面章節? 07/17 11:45
→ emstarbucks: 恩複雜度那章 有要你算(logn)!和另一個比較 07/17 11:46
→ emstarbucks: 推法差不多 一樣是用變數代換去比 07/17 11:46
→ emstarbucks: 但我不知道他國考那本有沒有收這題 07/17 11:46
→ emstarbucks: 我之前拿到書 翻一翻覺得跟研究所的講義差不多 07/17 11:47
→ emstarbucks: 就賣掉了-.-.. 07/17 11:47
→ emstarbucks: 只差在後面題目多寡而已 我記得前面章節內容幾乎一樣 07/17 11:55
→ RedJessy: 剛剛看到的補習班擬答 看了心情好糟 07/17 12:05
推 malowda: 最後ㄧ題和王老師的答案ㄧ樣中間值取中間值 07/17 13:24
推 dogalan: 我是覺得還是要看改考卷的老師怎麼改...大家別太氣餒 07/17 13:31
→ d12345631: 而且考上後離職的人也不少 07/18 02:07