d601: 6.計算執行路徑的可行性
標籤 :
通過比率 : 11人/17人 ( 65% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-08-30 09:30

內容

      一個程式的執行路徑關係,可以描繪成一個流程圖形(flow graph),例如左
下副程序 (subroutine) fpath(x,y,z) 從第1 行到第24 行(每一行指令左邊的
數字代表行號,行號為正整數 n,如圖所示),流程關係依照 if 與 while 的條
件真假,會執行不同的路徑。

 

例如第 3 行,若 if 條件為真(true),則執行路徑為 3 4 5,若條件不成立(false),
則執行路徑為 3 5。依此,可畫出對應之流程關係圖如上。觀察上述副程序
fpath(x,y,z),其流程關係,根據傳入參數 x, y, z 數值(假設都是32bits 的非負
整數)的不同,會有不同的執行路徑。

      以圖形 (graph)的路徑 (path) 觀點,從端點 1 為起點到終點 24,可以有不
同路徑,例如路徑 1 2 3 5 6 12 13 16 17 23 24 為一種走法,我們稱為可行路徑
(feasible path),而1 2 3 4 5 6 7 8 11 16 17 18 19 22 23 24 也是一種走法,但因為任
何零或正整數 x, y, z 的傳入參數值都無法循此路徑執行,我們稱為不可行路徑
(infeasible path)。針對上述程式範例,根據其流程關係所形成之圖形,給予任一
由起點到終點的路徑,判斷路徑是否可行。若可行,請找出一組滿足此路徑之
x, y, z,令 x + y + z 最小(其中 x,y,z 都必須大於或等於 0),並輸出。 輸入參數
x, y, z 皆為合法之 32 bits 正整數或零,測試資料中不含令運算產生 overflow 與
underflow 之情況。

輸入說明
第一行為資料筆數 N (0<N<=100)。接續 N行為路徑輸入描述,以序列的行
號表示,行號間以一個或以上的空白隔開,每一行為一個路徑描述,起點為1、
終點為24,最多包含 1000 個行號路徑(行號 L 範圍為整數 0<L<25),例如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
輸出說明
      根據上述範例程式所形成之圖形,依序判斷所給定之路徑,在「限定x, y, z
都是大於或等於零」的情況下,是否可行。若為可行路徑,輸出 min (x +y +z) 之
數值,例如min (x +y + z) = 5,則輸出
5
否則輸出:
inf
每筆路徑判定結果只以逗點相隔,每行最多輸出15 筆結果(每行最後一筆資料
無逗點與空白),超出則換行。請依照範例格式輸出。
範例輸入
輸入範例 1:
3
1 2 3 5 6 12 13 16 17 23 24
1 2 3 4 5 6 7 8 11 16 17 18 19 22 23 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

輸入範例 2:
18
1 2 3 5 6 12 13 16 17 23 24
17
1 2 3 4 5 6 7 8 11 16 17 18 19 22 23 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 22 23 17 18 19 22 23 24
範例輸出
輸出範例1:
0,inf,inf

輸出範例2:
0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf
inf,inf,inf
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1M
公開 測資點#1 (20%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 :

感谢morris1028提供图片!

標籤:
出處:
98學年度全國資訊學科能力競賽 [管理者:
swda289346 (太威啦)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」