[理工] [資結] 98交大資訊聯招-DS&algo核對

[taitin (小南)]

1
(1) -1 -1 0 1 2 0
(2)
    10
    / \
   2   15
    \    \
    9    18
   /
  4
   \
    7
   /
  6

(3)  1+2+3+4+6+7+11=34
    (圖略)

2

(1)
  error
  foo(b,5,10)
  j=5x2
  a[j]=a[10] 不存在
             (不太曉得..請高手指點)

(2)
          n
1/n *  Σ(1+(i-1)/b)
       i=1


= 1+(n-1)/2b



(3)
      0  1  2   3  4
   0  0  5  7   ∞  1
   1 ∞  0  5   ∞  ∞
   2  7  5  0   1   ∞
   3 ∞  ∞ 1   0   6
   4  6  ∞ ∞  ∞  0

  largest 7


3-(1) a,b
3-(2) b,c
3-(3) b,d
3-(4) b,d
3-(5) a,d
3-(6)            after collaps
       P
    ↗↑↑↖
   K  q  r  s                          p
 ↗                               ↗↗↑↑↖↖
 f                                i f k q  r  s
↗
i

3-(7)  X=50 Y=11

3-(8)
         H                F
        / \              / \
       B   C            B   C
      / \ / \    OR    / \ / \
     D  E F G         D  E I  G
          \ /            \    /
          I J            H    J


3-(9)

       60
       / \
      30  70
     / \   \
    20 40   80
   /   / \
  10  35 50

3-10

                (40,  )
               /    \
            (20, )  (70,  )
            /  |    /   \
         (10,)(30,)(60,)(80,)

3-11

             *
        /        \
       4          80
     /  \         / \
    8    60     6    50
   / \   / \   / \   /
  12 20 10 16 14 30 40



3-12 b,d
3-13 a,c



4

(1)
    O  o  Ω ω Θ

A   Y  Y  N  N  N
B   N  N  Y  Y  N
C   Y  N  Y  N  Y


(2) 8

(3)(A) Θ(n(logn)^2)
   (B) Θ(n^(lg3))
   (C) Θ(nlglgn)
   (D) Θ(logn)
   (E) Θ((logn)^2)


5-(1) 6
5-(2) merage sort
5-(3) 2
5-(4) 4
5-(5) 3
5-(6) │lgn!│ +1
      └    ┘
5-(7) O(nlogn)
5-(8) No
5-(9) yes
5-(10) 23,17,14,6,13,10,1,5,7,12
                |           |
                7           6
                   2 places change


6. 有請高手解之..



希望有寫這份的可以一起討論~

歡迎寄信或回(推)文





--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.236.51
※ 編輯: taitin          來自: 114.44.236.51        (02/01 20:42)
推 polomoss:後天要寫~寫完再跟你對~
推 hanbz:2-3的0到4為1  非無窮大
 喔喔打錯了，已修正感謝
※ 編輯: taitin          來自: 61.230.227.76        (02/07 00:04)
※ 編輯: taitin          來自: 61.230.220.229       (02/08 00:46)
推 qwertz:1-3我算是 1+2+3+4+6+7+11 = 34 耶
推 qwertz:5-2好像只有merge sort
我寫錯了，已修正
→ qwertz:5-3 我寫 2  ,merge sort 與 heap sort
→ qwertz:5-4 我寫 4 ,bubble insert quick selection
寫反了囧，看著打都會打錯QQ，已修正
推 qwertz:5-9 的 algo 我想不出來 可以請教一下嗎@@"
find(S,n/2);

find (S,k)
{
  假設一個數列S有n個數，將S切個成數個集合，每個集合五個數字，因此共有(n/5)個集合
  1.對每個集合排序                            n/5* O(5log5)=O(n)
  2.找到每個集合的中位數，即每個集合第3個數                 O(1)
  3.令S'=上述每個集合的中位數，m=find(S',(n/5)2)            T(n/5)
  4.則可利用M將S分成三個部份 S1(<m)  S2(=m)  S3(>m)         O(n)
  5.a. 若|S1|個數>=k，則第K數落在S1裡面，find(S1,n/2)       T(n/4)
    b. 否則若|S1|+|S2|>=k，則第K數落在S2裡面，return(m)      O(1)
    c. 否則find(s3,k-|s1|-|s2|);                            T(3n/4)
}


整體複雜度討論

  T(n)=T(n/5)+T(n/4)orT(3n/4)orO(1)+O(n)
      =T(n/5)+T(3n/4)+O(n)

由於     1/5+3/4<1
因此
   T(n)=O(n)


至於為什麼第四步是n/4

考慮下列情況


集合1  * * * * *
集合2  * * * * *
集合3  * * * * *
集合4  * * * * *
集合5  * * * * *

紅色為上述演算法中的M
而由於每個序列都被排序，而紅色點又是各集合中位數的中位數
因此可知道可以找到至少1/4的數字小於m
因此可知道|S1|最多只有n/4
而|S3|最多只有3n/4(若s2不存在)

推 hanbz:1-3  我也是算34= =
1-3我算錯了，已修正感謝樓上兩位
※ 編輯: taitin          來自: 61.230.226.58        (02/08 21:08)
※ 編輯: taitin          來自: 140.113.7.249        (02/09 13:01)
推 stevenwin:請問1-1答案是 -1 -1 0 1 2 0 嗎?
恩，是0我打錯了ˊˋ
※ 編輯: taitin          來自: 61.230.226.58        (02/09 23:20)
推 stevenwin:想問 4 (1)  A 的 big-O 和 B 的 Omega為何都是yes?
→ stevenwin:4 (2) 請問是哪8個是polynomial bounded?
推 qwertz:4 (2)我選的是從頭到尾數來 第 2 3 4 5 9 10 14 15這八個
跟我一樣
→ qwertz:4 (1) A是P(n)的絕對上界(小big-o) 所以也是P(n)的big-O
→ qwertz:4 (2) B則是P(n)的絕對下界(小omega)所以也是P(n)的大Omega
→ qwertz:  (1)  上一行打錯
推 stevenwin:常數算是polynomial bounded? 想說常數可以想成n^0
→ stevenwin:我終於瞭解了，感謝!!
推 polomoss:2(1)應該就是建立max-heap
 他程式有沒有錯阿？好像跑不出來。
推 polomoss:3(1)請問c錯在哪~?
→ polomoss:3(3)可以解釋一下a.c錯在哪嗎?
→ polomoss:4(2) 我算10個，4(3)(C)nlglgn
推 qwertz:3(1)的c 應該是theta(nlogn)而不是O(nlogn)
→ qwertz:而3(3) a錯在recursion 應是 T(n) = 2T(2/n) + (n-1)
應該還是T(n) = 2T(n/2) + cn，但是不見得balance造成best result
→ qwertz:而3(3)的 c有點像是玩文字遊戲 我是想quick sort 雖然有
→ qwertz:最高的performance 但是並不能說他是代表comparison sort中
→ qwertz:複雜度最低的
跟樓上想法大致相同，我認為不能說某個演算法是最好的，
這個問題最佳解的複雜度就是這樣，因為也許有更好的演算法只是沒被發現而已。
推 qwertz:另外4(3) 我也是算 nlglgn  polomoss請問你4(2)選哪幾個@@?
4(3)我算錯，已修正，感謝二位
※ 編輯: taitin          來自: 140.113.7.249        (02/10 18:28)
※ 編輯: taitin          來自: 140.113.7.249        (02/10 18:33)
※ 編輯: taitin          來自: 61.230.219.56        (02/15 19:26)
推 stevenwin:2(3) 我最大寫13耶
→ taitin:題目是 A1的意思是可以通過vetex number 1到達其他點
※ 編輯: taitin          來自: 220.136.209.215      (03/08 18:33)
※ 編輯: taitin          來自: 220.136.209.215      (03/08 18:34)
推 hswayne:(3) all-pairs那一題答案13吧
→ KarmaPolice:我也寫13
推 zensword:13 +1