平成28年秋期試験午後問題 問9

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】

問9 ソフトウェア開発(C)

次のCプログラムの説明及びプログラムを読んで,設問1~2に答えよ。

〔プログラム1の説明〕
 U社では,半年ごとに社内システムの見直しを行い,4月と10月に新たに開発又は改修するサブシステム(以下,対象サブシステムという)を決定し,開発又は改修作業(以下,開発作業という)を実施している。対象サブシステムは複数あり,それぞれに対して目標作業終了日が設定される。二つ以上の対象サブシステムの開発作業を同時に実施することはない。各対象サブシステムについて,開発リソースの制約があるので,必ずしも目標作業終了日までに開発作業を終了できるとは限らない。しかし,開発作業の終了が目標作業終了日よりも遅れる日数(以下,遅延日数という)の合計はできるだけ少なくしたい。そこで,対象サブシステムの開発作業順序を求める関数 job_scheduling を作成した。
  • 関数 job_scheduling の仕様は次のとおりである。ここで,引数の値に誤りはないものとする。
    機能:
    対象サブシステムの開発作業順序を求める。
    引数:
    num_s  対象サブシステム数
    job   対象サブシステム情報(JOB型の配列)
    job_sch 開発作業順序(int型の配列)
  • 構造体を使ったJOB型の定義は次のとおりである。
    pm09_1.png
    1. 開発コードは,対象サブシステムごとに一意となる長さが8の文字列
    2. 開発作業日数は,開発作業に掛かる日数
    3. 目標作業期間は,半年ごとの一連の開発作業を開始する日からこの対象サブシステムの目標作業終了日までの日数
  • 対象サブシステム情報 job には,次の①~③の順で,データが格納されている。
    1. 目標作業期間の昇順
    2. 目標作業期間が同じならば,開発作業日数の昇順
    3. 目標作業期間も開発作業日数も同じならば,開発コードの昇順
  • (5)の手順で,開発作業順序を求めると,開発作業順序 job_sch の要素 job_sch[i] には,i+1番目(i=0,1,…,num_s-1)に開発作業を実施する対象サブシステムの情報が格納された job[j] の添字の値 j (j=0,1,num_s-1)が入る。
  • 開発作業順序を求める手順は,次のとおりである。
    1. 開発作業順序 job_sch を,対象サブシステム情報 job の並び順に初期設定し,開発作業順序の添字 i に初期値 0 を設定する。
    2. i<num_s-1である間,③~⑥の処理を行う。
    3. i+1番目に開発作業を実施する対象サブシステム job[job_sch[i]] と i+2番目に開発作業を実施する対象サブシステム job[job_sch[i+1]] の開発作業を,順序どおりに実施した場合の二つの対象サブシステムの遅延日数の合計 wt_a と,順序を入れ替えて実施した場合の二つの対象サブシステムの遅延日数の合計 wt_b を求める。
    4. 開発作業の実施順序を入れ替えることによって遅延日数の合計が減る場合(wt_a>wt_b)には,開発作業の実施順序を入れ替える。
    5. 開発作業の実施順序を入れ替えた場合,i が0でなければ,i を1減らす。
    6. 入れ替えなかった場合,i を1増やす。
  • i番目の対象サブシステムの開発作業が終わるまでの開発作業日数の合計を ft としたとき,i+1番目の対象サブシステムの開発作業が終わったときの遅延日数 wt は,次式で求められる。
    pm09_2.png
    ここで,job_term と target_term は,i+1番目に開発作業を実施する対象サブシステムの開発作業日数と目標作業期間である。
pm09_3.png

設問1

プログラム1中の に入れる正しい答えを,解答群の中から選べ。
a に関する解答群
  • i + j
  • i + j - 1
  • i - j
  • i - j + 1
b に関する解答群
  • i + 1
  • i - 1
  • job_no
  • job_no + 1
  • job_no - 1
c に関する解答群
  • i + 1
  • i - 1
  • i++
  • i--
  • ++i
  • --i
d に関する解答群
  • =
  • +=
  • -=
解答選択欄
  • a:
  • b:
  • c:
  • d:
  • a=
  • b=
  • c=
  • d=

解説

aについて〕
「for j = 0; j < 2; j++) { …」のループは、2つの作業を別の順序で実施したときの遅延日数を合計する処理であり、wt_a には順序どおりに実施(i → i+1)した場合の遅延日数の合計、wt_b には順序を入れ替えて実施(i+1 → i)した場合の遅延日数の合計が格納されます。例えば i が 0 のときには、wt_a には「job_sch[0]が示す作業→job_sch[1]が示す作業」と実施した場合の遅延日数の合計、wt_b には「job_sch[1]が示す作業→job_sch[0]が示す作業」と実施した場合の遅延日数の合計が求められます。aを含む一団の処理は、wt_b を求める部分であるため、aには逆順で実施したときの作業を参照するための添字が入るとわかります。

i が 0 のときを考えると、順序どおり実施した場合と、逆順で実施した場合のそれぞれで参照すべき job_sch の要素は以下のようになります。
pm09_7.png
つまり、aに入る式は上記の逆順のときの正しい添字になる式でなければなりません。各選択肢を検証してみると、
  • i = 0, j = 0 のとき 0+0=0 となり、job_sch[0] を参照することになるため不適切です。
  • i = 0, j = 0 のとき 0+0-1=-1 となり、job_sch[-1] を参照することになるため不適切です。
  • i = 0, j = 0 のとき 0+0=0 となり、job_sch[0] を参照することになるため不適切です。
  • i = 0, j = 0 のとき 0-0+1=1 となり、job_sch[1]、
    i = 0, j = 1 のとき 0-1+1=0 となり、job_sch[0]
    両方とも正しい参照先となるため適切な式とわかります。
a=エ:i - j + 1

bについて〕
bを含む部分は、開発作業順序を求める手順中の「④ 開発作業の実施順序を入れ替えることによって遅延日数の合計が減る場合(wt_a > wt_b)に、開発作業の順序を入れ替える」処理になります。現在注目しているのは i+1 番目の作業 job_sch[i] と i+2番目の作業 job[i+1] の実施順序ですので、入れ替える対象はこの2つの作業になります。したがって入れ替え処理は以下のようになります。
//job_sch[i] と job_sch[i+1] の値を入れ替える
job_no = job_sch[i];
job_sch[i] = job_sch[i+1];
job_sch[i+1] = job_no;
b=ア:i + 1

順序は逆になりますがdから解説します。

dについて〕
dを含む1文は「開発順序を入れ替えないほうが遅延日数の合計が少なくなる場合」に行われる処理です。問題文には「⑥ 入れ替えなかった場合、i を 1 増やす」と説明されていますが、ft に関しては触れられていません。
変数 ft は「i番目の対象サブシステムの開発作業が終わるまでの開発日数の合計」であり、job[job_sch[0]] から job[job_sch[i-1]] までの job_term(※開発作業日数) の合計が格納されています。入れ替えなかった場合には、job_sch[i] が一旦確定したので ft に job[job_sch[i]](※i+1番目の開発作業) の job_term を加算することになります。よってdには「+=」が入ります。

d=イ:+=

cについて〕
cを含む部分は、開発作業順序を求める手順中の「⑤ 開発作業の実施順序を入れ替えた場合、i が 0 でなければ、i を 1 減らす」処理になります。i を 1 減らすのですから正解の候補は自ずと「i--」「--i」の2つに絞られます(「i - 1」は変数 i の値を減じるわけではないため不適切)。

ここで一応「i--(後置演算子)」と「--i(前置演算子)」の違いについて確認しておきます。どちらも変数のデクリメントですが、i-- は式の評価後に i を 1 減らす、--i は i を 1 減らした後に式を評価するという違いがあります。
int i = 5;
int j = 5;

printf(i--); //出力後に減算 → 5と出力される
printf(--j); //減算後に出力 → 4と出力される
これを踏まえてcに入る式を考えていきます。

i が 1 減ると、次に検討されるのは i番目である job[job_sch[i-1]] の作業と i+1番目である job[job_sch[i]] の作業の順序になります。ft には、i番目の作業までの合計作業日数が格納されていますが、検討対象を1つ前に戻し順序の再計算を実施するので、1回前のループで ft に加算された job[job_sch[i-1]] の job_term の値を減らす必要があります。
ft から job[job_sch[i-1]].job_term を減じつつ、i を 1 減らすには、減算後に式の評価を行う「--i」を指定しなければなりません。もし i-- を指定したならば job[job_sch[i-1] ではなく job[job_sch[i] の job_term が参照されることになり、ft が不適切な値になってしまいます。

c=カ:--i

設問2

関数 job_scheduling を実行したときに得られる対象サブシステムの開発作業順序などを出力する関数 print_schedule を作成した。次の記述中の に入れる正しい答えを,解答群の中から選ベ。
  • 関数 print_schedule の仕様は次のとおりである。ここで,引数の値に誤りはないものとする。
    機能:
    対象サブシステムの開発作業順序などを出力する。
    引数:
    num_s  対象サブシステム数
    job   対象サブシステム情報(JOB型の配列)
    job_sch  開発作業順序(int型の配列)
  • 図1に示す五つの対象サブシステムの対象サブシステム情報に対して関数 job_scheduling を実行した。このときに得られた開発作業順序を,図2に示す。
    pm09_4.png
  • 続けて,関数 print_schedule を実行した。その出力結果の3行目を図3に示す。
    pm09_5.png
pm09_6.png
e,f に関する解答群
  • 0
  • 27
  • 44
  • 46
  • 57
  • 60
  • 73
  • 86
解答選択欄
  • e:
  • f:
  • e=
  • f=

解説

for文内の処理をトレースしていくことで答えを導きます。

// i が 0 のループ
// job_sch[i] → job_sch[0] は 0
ft += job[0].job_term;
ft に job[0] の開発作業日数である 25 が加算される、ft は 25
if (ft > job[0].target_term)
ft = 25、job[0].target_term = 27 なので false と判定される
wt = 0;
printf( … );
1 APL12339 0 0 と出力される
]
// i が 1 のループ
// job_sch[i] → job_sch[1] は 2

ft += job[2].job_term;
ft に job[2] の開発作業日数である 21 が加算される、ft は 46
if (ft > job[2].target_term)
ft = 46、job[2].target_term = 30 なので true と判定される
wt = ft - job[2].target_term;
wt に 46 - 30 = 16 が格納される
wt_sum += wt;
wt_sum に 16 が加算される、wt_sum は 16
printf( … );
2 MS016101 16 0 と出力される
// i が 2 のループ
// job_sch[i] → job_sch[2] は 1
ft += job[1].job_term;
ft に job[1] の開発作業日数である 27 が加算される、ft は 73
if (ft > job[1].target_term)
ft = 73、job[1].target_term = 29 なので true と判定される
wt = ft - job[1].target_term;
wt に 73 - 29 = 44 が格納される
wt_sum += wt;
wt_sum に 44 が加算される wt_sum は 60
printf( … );
3 GGL08001 44 60 と出力される
e=ウ:44
 f=カ:60

Pagetop