Problem 626 Ecosystem，食物鏈

輸入一 n 值後，讀入 n * n 陣列，例如： n = 3，而陣列內容如下

索引  | 1 | 2 | 3
---------------
1     | 0 | 1 | 0
---------------
2     | 0 | 0 | 1
---------------
3     | 1 | 0 | 0

這例子代表有三種動物，動物 1 吃動物 2，動物 2 吃動物 3，動物 3 吃動物 1。
所以形成一個循環 1 吃 2 吃 3 吃 1，以 1 2 3 表示，但也可以以 2 3 1、 3 1 2 表示，但這種情況只要輸出遞增或遞減的那個。

此題用一巢狀迴圈就可以找出所有食物鏈，假設動物 i 吃動物 j，動物 j 吃動物 k，動物 k 吃動物 i。首先要找尋動物 i 以及動物 j，在嘗試找尋動物 k，最後再判斷是否為遞增或遞減。
尋找動物 k 的方法，我用一函式來找尋， C 語言程式碼如下：

int system[102][102];

int n, count;
void ecosystem(int f, int m)
{
    int i, j, t;
    if (!system[f][m]) return;
    for (t = 0; t < n; t ++)
    {
        if (system[m][t] && system[t][f])
           if (( f > m && m > t ) ||( t > m && m > f ))
           { printf("%d %d %d\n", f + 1, m + 1, t + 1); count ++; }
        
    }
}

最後只須在主程式內呼叫以及輸出：

count = 0;
for (i = 0; i < n; i ++)
    for (j = 0; j < n; j ++)
    {
        ecosystem(i, j);
    }
printf("total:%d\n\n", count); 

By David.K

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