資訊處理已哭 - 考試

第一題我在考場瞪著他瞪了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()?
: 這是我寫的是個人的想法請多多指教謝謝

--