Research Space for Linear Algebra & Discrete Mathematics
您好：31.這題因為沒有詳細提到如何猜密碼，所以average 猜測次數我就當作 worst case/2。Worst case 為全部組合均猜過才得到答案：10+100+1000+...+10^6(可重複，密碼長度可能是1~6不等。)猜一次答案需要 1/1000秒，所以將其除以1000可得到：(10+100+1000+...+10^6)/1000=1111.11一半大約需要 555.55 秒，答案選C。41.這題題目提到將graph用 Strong Connected Component(SCC) 的方式分組，接著若存在一點於該集合，另一點為另一集合，則在G'中兩集合有邊相連。因此，您可以使用以下步驟找出G'：Step 1: 找出原圖G中的SCC，例如{1->2->6->1}形成SCC、另外尚有{3->7->3}，剩下均無法跟其他人形成SCC，故自行形成一集合，所以得到以下SCC：{1,2,6}、{3,7}、{4}、{5}、{8}Step 2:將這些集合連起來，因為：{1,2,6}中的6與{3,7}中的7相連，所以兩集合有邊相連，即 {1,2,6}->{3,7}{1,2,6}中的6與{8}中的8有邊相連，所以兩集合有邊相連，即 {1,2,6}->{8}{5}中的5與{1,2,6}中的1相連，所以兩集合有邊相連，即 {5}->{1,2,6}{4}中的4與{3,7}中的3有邊相連，所以兩集合有邊相連，即 {4}->{3,7}{4}中的4與{5}中的5有邊相連，所以兩集合有邊相連，即 {4}->{5}因此可得到(A)為正確答案。以上淺見..
補充：在 Step 2 中，前面說的有邊相連指的是在原圖G中有邊相連，後邊說的兩集合有邊相連是指G'中有邊相連。
張貼留言
2 則留言:
您好：
31.這題因為沒有詳細提到如何猜密碼，所以average 猜測次數我就當作 worst case/2。
Worst case 為全部組合均猜過才得到答案：
10+100+1000+...+10^6(可重複，密碼長度可能是1~6不等。)
猜一次答案需要 1/1000秒，所以將其除以1000可得到：
(10+100+1000+...+10^6)/1000=1111.11
一半大約需要 555.55 秒，答案選C。
41.這題題目提到將graph用 Strong Connected Component(SCC) 的方式分組，接著若存在一點於該集合，另一點為另一集合，則在G'中兩集合有邊相連。
因此，您可以使用以下步驟找出G'：
Step 1:
找出原圖G中的SCC，例如{1->2->6->1}形成SCC、另外尚有{3->7->3}，剩下均無法跟其他人形成SCC，故自行形成一集合，所以得到以下SCC：
{1,2,6}、{3,7}、{4}、{5}、{8}
Step 2:
將這些集合連起來，因為：
{1,2,6}中的6與{3,7}中的7相連，所以兩集合有邊相連，即 {1,2,6}->{3,7}
{1,2,6}中的6與{8}中的8有邊相連，所以兩集合有邊相連，即 {1,2,6}->{8}
{5}中的5與{1,2,6}中的1相連，所以兩集合有邊相連，即 {5}->{1,2,6}
{4}中的4與{3,7}中的3有邊相連，所以兩集合有邊相連，即 {4}->{3,7}
{4}中的4與{5}中的5有邊相連，所以兩集合有邊相連，即 {4}->{5}
因此可得到(A)為正確答案。
以上淺見..
補充：
在 Step 2 中，前面說的有邊相連指的是在原圖G中有邊相連，後邊說的兩集合有邊相連是指G'中有邊相連。
張貼留言