Problem 821 Page Hopping，翻頁

題目輸入整數 i 和整數 j，意思是說第 i 頁翻到第 j 頁需要一次，數量不等，讀到 0 0 結束讀取，若一開始就輸入 0 0 程式就會結束，當我們翻書時，會產生一書的「拍打聲」，所以我們要輸出此書平均會「拍打」幾聲。

此題要先紀錄最大的頁數，並且將所有第 i 頁翻到第 j 頁的資料在索引內的值變為 1，例如：
1 2 2 4 1 3 3 1 4 3 0 0
而陣列內的所有狀態如下：
0 1 1 0
0 0 0 1
1 0 0 0
0 0 1 0
而陣列狀態定義好後，使用「最短路徑演算法」後，再將陣列內的值總合起來除以陣列內有值的個數，答案就會出來了。C 語言程式碼如下：

count = 0, sum = 0; 
for(k = 1; k <= max; k++)
r(i = 1; i <= max; i++)
or(j = 1; j <= max; j++)
        {
            if (i != j && page[i][k] != 0 && page[k][j] != 0)
            {
                int t = page[i][k] + page[k][j];
                if (page[i][j] == 0) page[i][j] = t;
                else if (t < page[i][j]) page[i][j] = t;
            }
        }
or(i = 1; i <= max; i ++)
   for(j = 1; j <= max; j ++)
   {
       int t = page[i][j];
       if (page[i][j] > 0) sum += t, count ++;
   }
printf("Case %d: average length between pages = %.3f clicks\n", caseNum ++,(float)sum / (float)count);

By David.K

p821題目連結
回ACM題庫目錄
回首頁