平成７年度 秋期 第二種 午後 問13 ［更新日］1995.10.25 問13 次のFORTRANプログラムの説明及びプログラムを読んで、設問1、2 に答えよ。 〔プログラムの説明〕 処理時間と納期が与えられたn個の仕事に対し、納期遅れ時間の総 和をできるだけ小さくするような処理順序を求めるプログラムである。 (1) n個の仕事には、表に示すような処理時間と納期が与えられている。 表 処理時間と納期のデータ ┌─────┬─────┬─────┬─────┬─────┐ │仕事の番号│ １ │ ２ │ … │ ｎ │ ├─────┼─────┼─────┼─────┼─────┤ │処理時間 │ＰＴ（１）│ＰＴ（２）│ … │ＰＴ（ｎ）│ ├─────┼─────┼─────┼─────┼─────┤ │ 納期 │ＤＴ（１）│ＤＴ（２）│ … │ＤＴ（ｎ）│ └─────┴─────┴─────┴─────┴─────┘ 納期については、DT(1)≦DT(2)≦…≦DT(n)の関係がある。 (2) 仕事の数が多くなると、処理順序の組合せは急激に増加するが、 ここでは、すべての隣接する二つの仕事について、その処理順序 を交換したときに、納期遅れ時間の総和が減少するか否かを調べ ることにする。 (3) k番目に処理される仕事の番号はSN(k)に格納する。 (4) k番目に処理される仕事の処理完了時刻をFTkで表す。このとき、 FTkは次の式で定義される。FT0＝0とする。 FTk＝FTk-1＋PT(SN(k)) (k＝1,2,…,n) この関係を図1に示す。 (5) k番目に処理される仕事の納期遅れ時間WTkは、次の式で計算する。 WTk ＝ FTk-DT(SN(k)), FTk＞DT(SN(k))のとき 0, FTk≦DT(SN(k))のとき このとき、納期遅れ時間の総和は、次の式で計算する。 WT1 ＋ WT2 ＋ … ＋ WTn (6) 任意のk番目とk+1番目にある二つの仕事の処理順序を交換した とき、納期遅れ時間の総和が減少すれば、新しい処理順序を採択 する。この様子を図2に示す。 処理順序が交換されたときには、新しくk番目になった仕事と k-1番目の仕事(k＞2の場合)が隣接し、その交換について検討する 必要がある。 (7) 処理順序を求める手順を、次の1.〜4.に示す。 1. k＝1 2. 処理順序がk番目とk+1番目である仕事の順序を交換したとき、 納期遅れ時間の和 WTk＋WTk+1 が減少すれば、新しい処理順序を採択し、k＞1ならば、k-1→k として2.を繰り返す。k＝1、又は減少しない場合、3.に進む。 3. k+1→kとし、k＜nならば2.に戻る。k＝nならば処理順序の交換を 終了し、4.に進む。 4. 得られた各仕事の処理順序のもとでの納期遅れ時間と納期遅れ 時間の累計を計算して印字する。 (8) 入力データとプログラムを実行した印字結果の例は、図3のとお りである。 入力データ 仕事の数 ↓ ［ 10 ］ 仕事の番号 処理時間 納期 ↓ ↓ ↓ ┌───────────────┐ │ １ ７５ ８２ │ │ ２ ５１ １００ │ │ ３ ７９ １３７ │ │ ４ ６２ １３９ │ │ ５ ８２ ２８１ │ │ ６ ３５ ３３０ │ │ ７ ４２ ３４９ │ │ ８ ６６ ３５０ │ │ ９ １３ ３７１ │ │ １０ ８５ ４３６ │ └───────────────┘ 印字結果 処理順序 仕事の番号 納期遅れ時間 累積納期遅れ時間 ↓ ↓ ↓ ↓ ┌──────────────────────────┐ │ １ １ ０ ０ │ │ ２ ２ ２６ ２６ │ │ ３ ４ ４９ ７５ │ │ ４ ３ １３０ ２０５ │ │ ５ ６ ０ ２０５ │ │ ６ ７ ０ ２０５ │ │ ７ ９ ０ ２０５ │ │ ８ ８ ７３ ２７８ │ │ ９ ５ ２２４ ５０２ │ │ １０ １０ １５４ ＊６５６ │ └──────────────────────────┘ ↑ 総納期遅れ時間 図3 入力データと印字結果の例 〔プログラム〕 01 INTEGER SN(50),PT(50),DT(50),XN(50) 02 INTEGER FT,ST,XT,WTS,WTX,WT 03 READ(5,*)N,(SN(J),PT(J),DT(J),J=1,N) 04 FT=0 05 K=1 06 DO WHILE(K.LT.N) ! KとK+1番目の仕事の順序交換ループ 07 XN(K)=SN(K+1) 08 XN(K+1)=SN(K) 09 WTS=0 10 WTX=0 11 ST=FT 12 ［ ａ ］ 13 DO J=K,K+1 ! 納期遅れ時間の計算ループ 14 ST=ST+PT(SN(J)) 15 IF(ST.GT.DT(SN(J))) WTS=WTS+(ST-DT(SN(J))) 16 ［ ｂ ］ 17 IF(XT.GT.DT(XN(J))) WTX=WTX+(XT-DT(XN(J))) 18 END DO 19 IF(WTX.LT.WTS) THEN ! 納期遅れ時間の比較 20 SN(K)=XN(K) 21 SN(K+1)=XN(K+1) 22 IF(K.GT.1) THEN 23 K=K-1 24 FT=FT-PT(SN(K)) 25 END IF 26 ELSE ! 納期遅れ時間が減少しない場合 27 FT=FT+PT(SN(K)) 28 K=K+1 29 END IF 30 END DO 31 FT=0 32 WTS=0 33 DO J=1,N ! 納期遅れ時間の計算と印字のループ 34 FT=FT+PT(SN(J)) 35 IF(FT.GT.DT(SN(J))) THEN ! 処理完了時刻と納期の比較 36 WT=FT-DT(SN(J)) 37 WTS=WTS+WT 38 ELSE ! 納期遅れにならない場合 39 ［ ｃ ］ 40 END IF 41 WRITE(*,*) J,SN(J),WT,WTS 42 END DO 43 END 設問1 入力データ、印字結果を分析し、プログラム中の［ ］に 入れる正しい答えを、解答群の中から選べ。 a 答カ b 答ウ c 答ウ 解答群 ア FT=FT+PT(XN(J)) イ FT=FT+PT(SN(J)) ウ XT=XT+PT(XN(J)) エ XT=XT+PT(SN(J)) オ XT=0 カ XT=FT キ XT=XT+WT ク WT=0 ケ WT=FT-PT(SN(J)) 設問2 プログラムを分析し、次の文章の［ ］に入れる正しい答 えを解答群の中から選べ。 19行目の記述 19 IF(WTX.LT.WTS) THEN において、判定 .LT. を誤って等号を含む記述 19 IF(WTX.LE.WTS) THEN にしてしまった。 図3の入力データに対してプログラムを実行すると、［ ］。 答ア 解答群 ア 図3とすべて同じ結果が印字される イ 図3と処理順序は異なるが、総納期遅れ時間は等しい結果が印字さ れる ウ 図3と処理順序も総納期遅れ時間も異なる結果が印字される エ 無限ループに陥る 戻る次頁：問14