Re: [理工] [DS]99師大 軟體基礎(自寫版)

[DavyBlue (Nothing at all)]

※ 引述《justbelieve (呆)》之銘言：
: 3.  (1+2+...n)/n
怎麼不寫(n+1)/2就好
: 4.  (1+2+...n)/n
: 5.  n/n = 1
其實這個我很納悶 關鍵在有沒有tail的pointer
如果有就只要O(1) 否則複雜度就變成O(n)
: 6.  (1+2+...n)/n
這式子只有搜尋位置 沒算插入
可能會被刁
寫個(n+1)/2 + 2可能會比較好?
: 12. a.  計算n個點的complete binary tree的高度
:     b.  log n
:     c.
小弟寫的破程式
程式重寫 剛剛看有問題...
再看看有沒有bug吧!
ALGORITHM Mystery(n)
        i <- 1 //代表現在的level
        j <- 1 //當前level的最大node數
        if (n>1) do
            repeat
                n <- n - j//剩下的node
                i <- i + 1//level+1
                j <- j * 2
            until (n/j=0)//整數除法 等於0就是未滿
        else if(n<1) do
            i <- 0
最後i值就是答案
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.36.211.210
→ DavyBlue:忘記寫Time complexity 也是O(logn)
→ privatewind:通常link list如果沒特別講，請以單向去解
→ DavyBlue:是單向沒錯 可是有時single link list也會提供頭尾的指標
→ privatewind:不用去想特例吧XD 如果真的怕就把定義加上去
→ privatewind:那通常是程序員方便自己coding加上去的
→ privatewind:不然以single link list最general的定義去想的話 不會
→ privatewind:特別提到尾端的操作
→ DavyBlue:修正一下 while裡面應該是>0
→ DavyBlue:整個重寫 想法錯了
※ 編輯: DavyBlue        來自: 114.36.211.210       (03/18 09:19)
推 h88488848:為何我的第10題的44是在左子樹= =