[理工] 100中央(DS&ALGO)

[justbelieve (呆)]

http://ppt.cc/hjRU


因為手頭沒答案

想上來跟有寫的or有答案的問一下,順便對

1.1寫得很陽春,大致上想法是

  function Search(key x,pointer root)
  {
     if(root.key == x) then return found;

     else if(root的*left不為空){

             then root = root的*left;

                  Call function Search(x,root);
          }

          else if(root的*right不為空){

               then root = root的*right;

                    Call function Search(x,root);
               }

               else return Null;
          }
     }
  }


1.2還在想,有類似的考古嗎?

2.completion order:j1,j2,j6,j3,j9,j7,j5,j4,j8

3.2  AVL tree:    5
                /   \
              3       8
            /  \     /  \
           2    4    6   9
                      \
                       7

5和6有類似的考古or有大大可以分享一下解答嗎?

7.2 最少乘法數:5610

    (((A1A2)A3)A4)A5

    不知道有沒有計算錯,怎麼感覺越算越小?




--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.105.52.42
※ 編輯: justbelieve     來自: 112.105.52.42        (01/12 19:32)

2.因為題目說a system consists of two identical machines,X和Y

  ......for parallel execution

  所以我的想法是這2個machine是可以同時處理job的

  且一次只能處理一個job

  題目規定:這個系統使用"一個"stack來裝RSTime <= 4s的job,
                   使用"一個"queue來裝RSTime  > 4s的job

  當2個工作同時間輪到他們執行時,在stack等待的會先被選去執行

start:


AT = t         Job1到,沒有人搶,隨便選一台假設X來執行
(arrival time)
                machineX  |--J1--|---------
                     (AT) t     t+3

AT = t+1       Job2到,X在執行J1,所以Y來執行J2

               machineY   |--J2--|---------
                         t+1     t+5

AT = t+3       此時X處理完J1,在這之前到的Job有J3,J4

               因為他們的RST > 4s,所以置入queue中等待
                      __________________
               queue: J3,J4             ,J3移出queue,到X中處理

               machineX  |--J1--|--J3--|-------
                         t     t+3    t+11


AT = t+5       此時Y處理完J2,在這之前的job,除了J4,有J5,J6

               因為他們的RST <= 4,所以置入stack中等待,
               |____|        ----
               |_J6_| queue: J4,   因為stack優先權高,所以移出J6到Y執行
               |_J5_|
               stack

               machineY |--J2--|--J6--|------
                       t+1    t+5    t+9


AT = t+9       Y處理完J6,所有的Job都已進入,且皆在stack or queue中等待

               如下:   |_J9_|        ______
                       |_J7_| queue: J4,J8
                       |_J5_|
                       stack

               依照stack先執行,queue後執行的規則

               最後的  machineX |--J1--|--J3--|--J7--|--J4--|--
                                t     t+3    t+11   t+15   t+22

                       machineY |--J2--|--J6--|--J9--|--J5--|--J8--|
                               t+1    t+5    t+9    t+13   t+17   t+24

Ans:completion order = J1,J2,J6,J3,J9,J7,J5,J4,J8


如果哪邊有錯再跟小弟指正一下


※ 編輯: justbelieve     來自: 112.105.52.42        (01/12 21:38)
→ metalalive:sorry 第二題我看錯了,2 machine paralel exexcution
→ metalalive:我算的也跟你一樣, 3q
→ metalalive:哪個job進入哪個machine也一樣 @O@
推 genius945:第二題我用algo的DFS做,有grey到grey就是有cycle
→ genius945:剩下答案都相同
→ rickyccch:我有個小問題 t+5時為什麼不是J5先pop出stack給Y呢
推 bjk:stack 後進先出，所以j6先