【解題】送愛心到肯大亞 - Care

台北市95學年度高中資訊學科能力競賽 - 送愛心到肯大亞 (Care)


問題描述

　　在非洲的友邦肯大亞由於久經乾旱、傳染病、戰亂等天災人禍摧殘，民不聊生、亟待外界物資救援，遠在台北的承緒與智鈴發起送愛心到肯大亞活動，已經募集一些文具用品準備分送到肯大亞各地城鎮的小朋友就學使用。但是肯大亞的交通建設非常落後，僅部分城鎮間有單方向可行駛的道路連結，並且在軍事管制下不是隨時都可通行，已知肯大亞所有省的鄉鎮數皆不超過 20 個。下圖是肯大亞某一省的鄉鎮道路地圖，簡單起見城鎮名稱用數字(1 ~ 20)來編號：



　　其中每一點代表一個城鎮，每一個方向線代表城鎮間的道路連結與車輛通行方向。線上數值代表某天可以通行的機率。像是城鎮6 到8 的通行路徑僅有一種選擇，即是一條單方向可行駛道路連結 6 到 7 到 8，所以至少有一條路徑可通行的機率是 0.3 * 0.7 = 0.21。而城鎮 1 到 4 則有兩條路徑分別是：（1）先行經連結 1 到 2 道路(可通行的機率是0.7)再行駛連結 2 到 4 道路(可通行的機率是0.8)；（2）或是直接行駛連結 1 到 4 道路(可通行的機率是0.8)，所以至少有一條路徑可通行的機率是1 - (1 - 0.7 * 0.8)(1 - 0.8) = 0.912。

　　已知送愛心到肯大亞活動每天會從某一省的一個城鎮出發運送救援物資的同一個省的另一個城鎮，車輛沿途最多僅會經過某一個城鎮一次。聰明的各位，請幫富有愛心的承緒與智鈴計算看看，在給定某一省的鄉鎮地圖與每條道路通行的機率情況下，任意兩城鎮間至少有一條路徑可通行的機率為何。


輸入檔格式(C:\area\input.txt)

　　第 1 行為某一省城鎮數目N；接下來第 2 行到第 N + 1 行為一個 N * N 陣列，陣列的第 k 列 (row) (即輸入檔的第 k + 1 行)的每一個數值代表某一標號為 k 的城鎮到其它城鎮(1 至 N)間道路可通行的機率；輸入檔的最後一行(第 N + 2 行)有兩個數值分別(由左至右)代表起始城鎮編號與目的地城鎮編號。任一兩個數字之間都用一個空白隔開。


輸出檔格式 (C:\area\output.txt)

　　從起始城鎮到目的地城鎮至少有一條路徑可通行的機率值(準確到小數點以後第五位)。


輸入檔範例1

1
1.0
1 1


輸出檔範例2

1.00000


輸入檔範例2

2
1.0 0.1
0.0 1.0
1 2


輸出檔範例3

0.10000


輸入檔範例3

8
1.0 0.7 0.9 0.8 0.0 0.0 0.0 0.0
0.0 1.0 0.0 0.8 0.6 0.0 0.0 0.0
0.0 0.0 1.0 0.0 0.0 0.8 0.0 0.0
0.0 0.0 0.0 1.0 0.0 0.7 0.0 0.6
0.0 0.0 0.0 0.0 1.0 0.0 0.0 0.5
0.0 0.0 0.0 0.0 0.0 1.0 0.3 0.0
0.0 0.0 0.0 0.0 0.0 0.0 1.0 0.7
0.0 0.0 0.0 0.0 0.0 0.0 0.0 1.0
1 4


輸出檔範例1

0.91200


解題思考

　　首先，從題目看來，我們需要用程式"走"過每一條由起始點到終點可能路徑，並計算出該路徑的通行機率。由於需要試著走過每條路徑，所以我採用遞迴的方式進行。每遞迴一層，就像是往下一個城鎮走。

　　至於機率值怎麼計算呢？我們以一個變數值儲存"走某路線到當前節點"的機率，並設定初始值為 1 (由起點出發，在起點的機率當然就是 100% 囉)。每往下一個節點走(即呼叫一次遞迴)時，就乘上兩節點間的通行機率。反之，假如要往前回朔，則除以兩點間的機率。

　　此外，仔細看題目，同一個城鎮不可以走第二次。因此，我們還需要紀錄哪些路徑已經走過了，在程式"走"的時候不要重複經過同一城鎮。

　　最後再使用題目提供的，在有 n 條可行路徑的情況下：機率 = 1 - (1 - 路徑 1 的機率) * (1 - 路徑 2 的機率) * ... * (1 - 路徑 n 的機率)，就能夠計算出結果。


參考解答(C)

#include <stdio.h>
#include <stdlib.h>

float **city, chance = 1, num = 1;
void care(int);
int *gone, start, end, n;

int main(void)
{
    int i, j;

    // 宣告檔案串流
    FILE *in, *out = fopen("C:/care/output.txt", "w+");
    if (!(in = fopen("C:/care/input.txt","r")))
    {
        printf("找不到 input.txt\n");
        system("pause");
        exit(1);
    }

    fscanf(in, "%d", &n);
    printf("%d\n", n);

    // 動態配置記憶體空間
    city = (float**)malloc(sizeof(float*) * n);
    gone = (int*)malloc(sizeof(int) * n);

    for (i = 0; i < n; i++)
    {
        city[i] = (float*)malloc(sizeof(float) * n);
        gone[i] = 0;

        for (j = 0; j < n; j++)
        {
            fscanf(in, "%f", &city[i][j]);
            printf("%.1f ", city[i][j]);
        }

        printf("\n");
    }

    fscanf(in, "%d%d", &start, &end);
    printf("%d %d\n", start, end);

    // 呼叫遞迴函式
    care(start - 1);

    // 釋放記憶體空間
    for (i = 0; i < n; i++) { free(city[i]); }
    free(city);
    free(gone);

    printf("%.5f\n", (1 - num));
    fprintf(out, "%.5f\n", (1 - num));

    system("pause");
}

void care(int now)
{
    int i;

    // 假如走到終點則加總機率後返回
    if (now + 1 == end)
    {
        num *= 1 - chance;
        return;
    }

    // 標記走過的城鎮
    gone[now] = 1;

    for (i = 0; i < n; i++)
    {
        // 跳過機率為零的路徑及走過的城鎮
        if (!city[now][i] || gone[i]){ continue; }

        // 呼叫遞迴計算機率
        chance *= city[now][i];
        care(i);
        chance /= city[now][i];
    }

    gone[now] = 0;
}