※ 引述《kaidi620 (萬能史哥)》之銘言:
: 小弟又來打擾了 可以請教大神三個問題嗎 就是做99台大遇到覺得最不解的問題
: https://imgur.com/vjt3WyA.jpg
: (1)這題關於題目敘述不是很懂,因為他說L1 access in one clock cycle我想說這應該是他的penalty cycle吧
: 但板上大神的解答是把L1的penalty 寫成10 然後把 L2的penalty寫成100
: https://imgur.com/9ud85V1.jpg
: https://imgur.com/sMuyqdh.jpg
: 小弟覺得這真的超難 但板上大大提供的解答
: https://imgur.com/qSen23Q.jpg
: (2)真的完全看不懂 可以請大神幫我解答一下嗎
: 最後一題是數學證明題 一樣完全看不懂 請大神降臨(跪拜
: https://imgur.com/ZJHeBkC.jpg
: 題目有點多 有點長 謝謝大神們
(1)讀取L1需要一個clock的時間,如果L1 miss了則去L2讀取,這樣的penalty是10個
cycles,如果連L2都miss則有100個cycles的penalty
(2)if((x=delete())== 0) //當Queue的頭是0代表 現在Queue裡為某列的資料
insert 0; //下一列的開頭一定是0
print("%d\n", x); //將x印出來
insert(x+peek()); //當前的Head和x組成下方的元素
0 1 t1 : Q = 0 1 // Q = 第一行
0 1 1 t2 : Q = 1 0 1
0 1 2 1 t3 : Q = 0 1 1 // Q = 第二行
0 1 3 3 1 t4 : Q = 1 1 0 1
可以看到Q的頭是0的時候,Q內容會和某行相等,所以要多insert一個0
這題一開始也覺得滿難的,後來畫出Q的內容跟圖對照就會有點靈感
其實可以畫得更清楚,不過我排版的好累,如果還是不懂我再畫給你看
(3) u - o - o - o - o - o - o - o - v
1.
只要在加上(u,v)這個edge就可以形成Hamilton Cycle,代表現在這個圖中
並沒有Hamilton Cycle,S收集和u相連的點,T收集和v相連的點,若S和T
包含了所有點,因為是Simple Graph,v不會和自己有edge,所以v一定不在T中
代表v存在S中,與u相連,則此圖有Hamilton Cycle,矛盾
2.
若S和T有交集,代表有點vi與v相連且vi+1與u相連
則必可以畫出以下的圖含有H Cycle
- - - - - - - - >
^ |
| |
| v
u - o - o - o - o - o - o - o - v
^ |
| v
< - - - - - - - - - -