[理工] [DS]-97清大-資工系

[assassin88 (2010)]

題目：http://www.lib.nthu.edu.tw/library/department/ref/exam/eecs/cs/97/2001.pdf

想先問該年度第十題，

完全不懂他表達的意思為何...麻煩指導一下。

另外就是還想問第十一題，faliure function，

 a a  b a a b a a a b
-1 0 -1 0 1 2 3 4 X X
                  ^^^請問這兩個位置的要怎麼看....
這個時候的a不是對道由左往右數的第二個b嗎？那為什麼別人說是1..

麻煩指導一下了..感謝！

另外還想問一個問題，如果題目沒有啥條件..但問說迴圈跟遞迴哪個比較有效率，

請問是選遞迴嗎？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.57.105.163
※ 編輯: assassin88      來自: 61.57.105.163        (02/07 11:23)
推 killerjoe:直覺是迴圈比較有效率~遞迴則是可讀性較高
推 killerjoe:failure function a先與5比 失敗後再與2比失敗後再與0比
→ killerjoe:失敗後填-1
→ killerjoe:b與0比失敗後填-1
→ taitin:a下面填1，a比對失敗之後，要先查前面一個對的function
→ taitin:因此回去比對第4個(如果第一個是0的話)，若相同
→ taitin:兩個function就會相同，意思就是這兩個位置，跟位置1的狀況
→ taitin:一樣
→ taitin:10題參考http://en.wikipedia.org/wiki/XOR_linked_list
→ assassin88:所以說a因為跟b比失敗後，往前找上一個成功的a，因為這
→ assassin88:個a是1所以填1，然後b又接著比，剛好對到b(2)所以填2
→ assassin88:不知道是這樣的意思嗎？    原來是迴圈阿..XD
→ assassin88:XOR..這個好難喔看不太懂~可以略為說明一下嗎
推 polomoss:0 1
→ polomoss:這種題目不用遞迴想~就一直填就好
→ assassin88:樓上是指那兩格填0跟1嗎..怎麼三個人答案都不同= =
→ Carbunkl:failure function爬文  用trace code多練幾題就熟了
推 stevenwin:程式跑的結果是 1 2
推 crazyjoe:1  2
→ assassin88:感謝..我線在加緊練習有比較熟練一點了..