1、第一題 長(zhǎng)度為素?cái)?shù)的路徑個(gè)數(shù)(100 分)對(duì)于正整數(shù) n(3n30)，可以畫出 n 階的回形矩陣。下面畫出的分別是 3 階的，4 階的和 7 階的回形矩陣：n=3n=4n=7對(duì)于 n 階回形俱鎮(zhèn)，從某一格出發(fā)，每步可以向右或向下走一格，走若干步后，可以到達(dá)有下角。把這樣的路徑上所有格子中的數(shù)值之和，叫做該路徑的長(zhǎng)度。給出 n 值和出發(fā)點(diǎn)位置，求出n 階回形矩陣有多少條的長(zhǎng)度為素?cái)?shù)？如 n=3 時(shí)，出發(fā)點(diǎn)位置為左上角，路徑(用黑體標(biāo)出)及長(zhǎng)度有：長(zhǎng)度=5長(zhǎng)度=6長(zhǎng)度=6長(zhǎng)度=6長(zhǎng)度=6的長(zhǎng)度為素?cái)?shù)。長(zhǎng)度=5因此，說 3 階回形矩陣有 2 條輸入你的程序?qū)?input1.dat 中數(shù)據(jù)。輸入文件

2、可能包含多個(gè)數(shù)據(jù)，每一行代表一個(gè)獨(dú)立的測(cè)數(shù)數(shù)據(jù)，包含三個(gè)自然數(shù) n,x,y，其中 3n30。x,y 表述出發(fā)點(diǎn)位置的行和烈，一行單獨(dú)的一個(gè) 0 表示輸入的結(jié)束。輸出輸出至屏幕，每行為一個(gè)正整數(shù)，既 n 階回形矩陣中長(zhǎng)度為素?cái)?shù)的路徑的個(gè)數(shù)。樣例input1.dat3 1 10輸出：211112111111112111111112111111112111111112111111112111111111111222221123332112343211233321122222111111111111122112211111111121111第二題 并行計(jì)算(120 分)假設(shè)有 m 個(gè)處理器要并行處理某

3、個(gè)任務(wù)。該任務(wù)可被分解為 n 個(gè)不同的務(wù)，分別為 1 i n，第 i 個(gè)任務(wù)需要 1 個(gè)處理器工作ti 個(gè)時(shí)間才能完成。這些務(wù)之間有一個(gè)優(yōu)先關(guān)系，某一個(gè)務(wù)必須等待其它的某些務(wù)完成以后才能開始進(jìn)行?？捎靡豢冒?n 個(gè)節(jié)點(diǎn)的樹來表示務(wù)之間的優(yōu)先關(guān)系，樹中的每個(gè)節(jié)點(diǎn)表示一個(gè)務(wù)；對(duì)于每個(gè)節(jié)點(diǎn)所表示的務(wù)，只有當(dāng)其所有兒子節(jié)點(diǎn)都完成后才能開始進(jìn)行。當(dāng)根節(jié)點(diǎn)所表示的務(wù)被完成后，整個(gè)任務(wù)就全部被完成了。請(qǐng)你編寫一個(gè)程序，計(jì)算對(duì)于給定的 n 個(gè)其全部完成。務(wù)，m 個(gè)處理器最少需要多少時(shí)間才能將輸入輸入文件名位 input2.dat輸入文件可能包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)的第一行是兩個(gè)正整數(shù) m,n，分別表示

4、處理器的數(shù)目和不同的務(wù)的數(shù)目，其中 1m100，1n500。接下來的 n 行，每行是一個(gè)正整數(shù)，表示第 i 個(gè)務(wù)所需工作時(shí)間。再接下來的 n-1 行，每行是兩個(gè)正整數(shù) x,y，對(duì)應(yīng)于樹中一條邊，它表示任務(wù) x 必須在任務(wù) y 之前完成(即 x 時(shí) y 的兒子節(jié)點(diǎn))。一行單獨(dú)個(gè)一個(gè) 0 表示輸入文件的結(jié)束。輸出輸出至屏幕，每行只包含一個(gè)正整數(shù)，即完成所有任務(wù)所需的最短時(shí)間。樣例input2.dat1 32121 22 30輸出：5第三題 0-1 矩陣(120 分)給定一個(gè) 01 矩陣(即矩陣中的元素僅為 0 或 1)，每次操作可以選擇某一行或某一列，將其中的 1 全部刪除。問最少必須進(jìn)行多少次操

5、作，才可以將 01 矩陣中所有的 1 全部刪除。輸入輸入文件名為 input3.dat輸入文件可能包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)數(shù)據(jù)的第一行是兩個(gè)用空格隔開的正整數(shù) m,n，其中 2m,n100。接下來的 m 行是一個(gè) m*n 的 01 矩陣。一行單獨(dú)的一個(gè) 0 表示輸入的結(jié)束。輸出輸出至屏幕。每行只包含一個(gè)正整數(shù)，即刪除所有的 1 所需的最少操作次數(shù)。樣例input3.dat4 401011010010001010輸出：3第四題 寶藏(100 分)埋藏的 n 個(gè)寶庫(kù)(某個(gè)外國(guó)探險(xiǎn)隊(duì)在非洲沙漠中發(fā)現(xiàn)了二期為1n)，并且還記下了從一個(gè)寶庫(kù)走到另一個(gè)寶庫(kù)的時(shí)間(有的寶庫(kù)之間無通路，無通過時(shí)間)。幾經(jīng)知道每

6、個(gè)寶庫(kù)中藏有一定數(shù)量的寶藏，但由于德國(guó)在建造寶庫(kù)時(shí)設(shè)有保護(hù)措施，因而每個(gè)寶庫(kù)只能進(jìn)入通過一次。在第一個(gè)寶庫(kù)內(nèi)可以取得打開其它寶庫(kù)的(第一個(gè)寶庫(kù)可以不用就進(jìn)入)。另外，探險(xiǎn)隊(duì)還發(fā)現(xiàn)，在進(jìn)入第一個(gè)寶庫(kù)的同時(shí)將觸發(fā)一個(gè)裝置，因而所有的寶庫(kù)將在 tk 秒后同時(shí)。請(qǐng)你設(shè)計(jì)一種最佳的取寶藏的方案，使在寶庫(kù)前(包括時(shí))能取得最多的寶藏。例：有 4 個(gè)寶庫(kù)，如圖：其中寶藏?cái)?shù)量為：100，60，80，70通過時(shí)間(沒有給出通過時(shí)間的表示無通路)：1123234420 秒30 秒20 秒15 秒時(shí)間：50 秒124此 時(shí) 方 法計(jì) 40 秒，可取 100+60+70=230有：134計(jì) 45 秒，可取 100+8

7、0+70=250或：134可取寶藏 250則最佳方案為：1234輸入輸入文件名為 input4.dat輸入文件可能包含多個(gè)測(cè)試數(shù)據(jù)，每個(gè)測(cè)試數(shù)據(jù)的第一行有三個(gè)用空格隔開的整數(shù)n(1n20), k(1k50), tk(1tk1000)。其中 n 表示寶庫(kù)的數(shù)目，k 表示由 k 個(gè)通路，tk 表示的時(shí)間。接下來 k 行，每行有三個(gè)數(shù)據(jù)(x, y, t)，表示從xy 所需時(shí)間 t(用空格隔開)。最后一行有n 個(gè)整數(shù)，表示寶庫(kù)中的寶藏?cái)?shù)。一行單獨(dú)的一個(gè) 0 表示輸入文件的結(jié)束。輸出輸出至屏幕，每行一個(gè)數(shù)，表示能取到的最多的寶藏?cái)?shù)。樣例input4.dat4 4 501 2 20250第五題(100 分

8、)電能期間(由于缺少降雨導(dǎo)致的低水位造成的)，一個(gè)緊急預(yù)案開始啟在今年動(dòng)。它會(huì)系統(tǒng)地、有步驟地切斷我國(guó)各個(gè)地區(qū)的電源被分成n 個(gè)區(qū)域（吉林是區(qū)域 1，是區(qū)域 13）。隨便選一個(gè)數(shù) m，區(qū)域 1 的電源會(huì)被先切斷，接下來的第 m 個(gè)區(qū)域的電源會(huì)被切斷。超過 n 則轉(zhuǎn)到 1，并且跳過已經(jīng)被關(guān)了電源的區(qū)域。比如：如果 n=17，m=5，切斷電源區(qū)域的順序是：1，6，11，16，5，12，2，9，17，10，4，15，14，3，8，13，7。顯然，最后切斷電源的區(qū)域是是公平的(畢竟電源總部在那里)。所以對(duì)于給定的數(shù)n，這個(gè) m 要仔細(xì)選擇，以確保區(qū)域 13 是最后被關(guān)電源的區(qū)域。寫一個(gè)程序區(qū)域數(shù) n 并且酸出最小的 m，保證是最后一個(gè)切斷電源