基本情報技術者 2012年 春期 午後 問09
次のCプログラムの説明及びプログラムを読んで、設問1，2に答えよ。
〔プログラム1の説明〕
S社では、通常勤務時間帯（8時30分〜18時）中の各社員の予定を管理している。
関数allmem_free_slotは、通常勤務時間帯に会議を計画する場合に、出席して欲しい社員（以下、出席社員という）全員の予定が入っていない時間帯を調べるプログラムである。
(1) S社では、各社員の予定を30分単位の時間帯ごとに図1に示すスケジュール表で管理している。
① スケジュール表は大きさ19の整数型配列で、各要素の添字の値は時間帯番号に対応している。
② スケジュール表の各要素には、予定が入っている場合には0以外の値が、予定が入っていない場合には0が入る。
(2) 会議時間は30分以上であり、開始時刻と終了時刻は時間帯の区切りと一致する。
(3) 関数allmem_free_slotの引数は次のとおりである。ここで、引数の値に誤りはないものとする。
num 出席社員数
time_tbl 出席社員全員のスケジュール（スケジュール表へのポインタの配列）
slot_num 会議時間（30分単位の時間帯数）
free 会議開催の候補時間帯（SLOT型の配列）
(4) 構造体を使ったSLOT型の定義は次のとおりである。
typedef struct {
int s_start; /* 開始時間帯番号 */
int s_num; /* 時間帯数 */
} SLOT;
(5) 候補時間帯freeには、出席社員全員の予定が入っていない、会議時間以上の連続する時間帯（以下、可能時間帯という）を全て格納する。最後に格納した要素の次の要素の開始時間帯番号には、−1を格納する。例えば、出席社員5名（社員A〜E）の予定が図2のとおりであった場合、会議時間が1時間（slot_num = 2）のとき、可能時間帯の一覧は表1になる。
(6) 関数allmem_free_slotで使用している関数search_free_slotの仕様は次のとおりである。
機能：スケジュール表から、予定が入っていない、時間帯数以上の連続した時間帯を全て探し出し、空き時間帯に格納する。最後に格納した空き時間帯の要素の次の要素の開始時間帯番号には、−1を格納する。
引数：sch スケジュール表
slot_num 時間帯数
free 空き時間帯（SLOT型の配列）
設問1：
問題文を見る プログラム1中のに入れる正しい答えを、解答群の中から選べ。
aに関する解答群
ア：0
イ：1
ウ：time_tbl[0][0]
エ：time_tbl[0][i]
bに関する解答群
ア：i
イ：i - cnt
ウ：i - cnt + 1
エ：i - cnt - 1
オ：NUM_DAY - cnt
cに関する解答群
ア：cnt = 0
イ：cnt++
ウ：cnt--
エ：free_num = 0
オ：free_num++
カ：free_num--
dに関する解答群
ア：cnt == 0
イ：cnt > 0
ウ：cnt >= slot_num
エ：cnt < slot_num
オ：free_num == 0
カ：free_num > 0
模範解答
a：エ、b：イ、c：ア、d：ウ
解説
解答の導き方
このプログラムは、まず出席社員全員の予定を一つにまとめ、その後、全員の予定が入っていない連続した時間帯を探します。
1. 出席社員全員の予定を一つにまとめる
スケジュール表は、時間帯ごとの予定を番号順に並べた配列です。配列の添字（各値の位置を表す番号）は、時間帯番号に対応します。
各時間帯について、まず社員の一人目の予定を配列に入れます。その後、二人目以降の社員の予定を調べ、誰か一人でも予定があればをにします。
このようにすれば、は「出席社員の中に予定がある人がいる時間帯なら以外、全員に予定がなければ」になります。
一人目の予定を取り出すには、その時間帯番号を使ってを指定します。では、常に時間帯番号の予定を参照してしまいます。また、最初からやを入れるだけでは、一人目の予定があるかどうかを正しく反映できません。したがって、空欄aにはが入ります。
2. 連続した空き時間帯を数える
次に、を時間帯番号の小さい方から順に調べます。変数は、現在続いている空き時間帯の数です。
- がなら、時間帯は空きです。を増やします。
- が以外なら、時間帯には予定があります。このとき、直前までの空き時間帯が会議時間以上なら、候補として記録します。
予定がある時間帯に到達した時点で、直前の空き時間帯はからまでです。そのため、記録する開始時間帯番号はです。空欄bはになります。
候補を記録した後は、予定がある時間帯を境に次の空き時間帯を数え始めます。そこでをに戻します。空欄cは「」です。
例として、時間帯番号、、が空きで、時間帯番号に予定がある場合を考えます。時間帯番号を調べるとき、はです。会議時間が時間帯以上なら候補にでき、開始番号はになります。その後、をに戻します。
3. 最後に続く空き時間帯を確認する
予定がある時間帯に到達すると、その直前の空き時間帯を記録できます。しかし、最後の時間帯まで空きが続いた場合は、予定がある時間帯に到達しないまま繰返し処理が終わります。そのため、繰返し処理の後にも、最後の空き時間帯を確認します。
が以上なら、会議時間を満たす空き時間帯です。空き時間帯が最後まで続く場合、その開始番号は「時間帯の総数から空き時間帯数を引いた値」です。総数はなので、開始番号はです。
例えば、最後の空き時間帯が番号からまでなら、はです。開始番号はになります。空欄dの条件はです。
候補をすべて記録した後は、次の要素の開始時間帯番号にを入れます。これは「候補の記録がここで終わる」という目印です。
誤りやすいポイント
- 空欄aをやにすると、一人目の社員の予定を正しく反映できません。さらに、時間帯番号に対応する値を使うため、とします。
- 空欄bはです。現在の時間帯は予定ありなので、その直前にある空き時間帯の先頭は、現在の番号から空き時間帯数を引いた位置です。
- 空き時間帯が予定ありの時間帯で途切れたら、をに戻します。戻さないと、途切れる前後の空き時間帯を一続きとして数えてしまいます。
- 最後の空き時間帯は、繰返し処理の中では記録されないことがあります。繰返し処理の後の確認を忘れないようにします。
- 会議時間と同じ長さの空き時間帯も候補になります。したがって、条件は「以上」のです。
FAQ
Q: なぜ予定がある時間帯に出会ったとき、空き時間帯を記録するのですか？
A: 予定がある時間帯に出会うと、その直前までの空き時間帯がそこで終わったと分かるからです。直前まで数えていたを使って、開始番号と時間帯数を記録できます。
A: 予定がある時間帯に出会うと、その直前までの空き時間帯がそこで終わったと分かるからです。直前まで数えていたを使って、開始番号と時間帯数を記録できます。
Q: 記録する時間帯数には、会議時間と同じ数を入れるのですか？
A: いいえ。条件を満たす空き時間帯の長さ全体を記録するため、にはを入れます。会議時間より長い空き時間帯も、長さをそのまま記録します。
A: いいえ。条件を満たす空き時間帯の長さ全体を記録するため、にはを入れます。会議時間より長い空き時間帯も、長さをそのまま記録します。
Q: 最後の要素にを入れるのはなぜですか？
A: 候補を記録した要素数が分からなくても、開始時間帯番号がの要素を見つければ、候補の記録が終わったと判断できるためです。
A: 候補を記録した要素数が分からなくても、開始時間帯番号がの要素を見つければ、候補の記録が終わったと判断できるためです。
関連キーワード: 配列、添字、繰返し処理、条件判定、終了位置判定
設問2：
問題文を見る 出席社員が増え、出席社員全員での会議の計画ができない（可能時間帯がない）場合がでてきた。そこで、出席社員を出席が必須の社員（以下、必須出席社員という）とそれ以外の社員（以下、任意出席社員という）に分け、必須出席社員全員が出席可能な時間帯で会議の計画をすることにした。さらに、任意出席社員について順位付けを行い、順位の高い方から最多の社員が出席可能な時間帯に絞込みを行うことにした。この条件で会議が計画できる時間帯を調べるプログラムを作成した。作成したプログラム中のに入れる正しい答えを、解答群の中から選べ。ここで、aには、設問1の正しい答えが入っているものとする。
〔プログラム2の説明〕
(1) 関数maxmem_free_slotの引数は次のとおりである。ここで、引数の値に誤りはないものとする。
num 出席社員数
must_num 必須出席社員数
time_tbl 出席社員全員のスケジュール（スケジュール表へのポインタの配列）
slot_num 会議時間（30分単位の時間帯数）
free 会議開催の候補時間帯（SLOT型の配列）
① 必須出席社員のスケジュール表へのポインタは、time_tblの先頭から人数分が格納されている。
② 任意出席社員のスケジュール表へのポインタは、time_tblの必須出席社員のスケジュールに続けて、順位の高い方から順に格納されている。
(2) 候補時間帯freeには、必須出席社員全員が出席可能な時間帯の中で、任意出席社員の順位の高い方から最多の社員が出席可能な時間帯を全て格納する。最後に格納した要素の次の要素の開始時間帯番号には、−1を格納する。
eに関する解答群
ア：j = 1; j < must_num
イ：j = 1; j < num
ウ：j = 1; j < num - must_num
エ：j = must_num; j < num
オ：j = num - must_num; j < num
fに関する解答群
ア：wk_free[1][0].s_num == 0
イ：wk_free[1][0].s_num == -1
ウ：wk_free[1][0].s_num > slot_num
エ：wk_free[1][0].s_start == 0
オ：wk_free[1][0].s_start == -1
カ：wk_free[1][0].s_start > slot_num
模範解答
e：ア、f：オ
解説
解答の導き方
まず、sch[i]が何を表すかを確認します。これは、時間帯番号iについて、対象者の中に予定が入っている社員がいるかを記録する配列です。予定がある人が一人でもいれば1、全員の予定がなければ0になります。
aでは、最初の必須出席社員の予定をsch[i]に反映します。その後の繰返しで、残りの必須出席社員の予定も調べます。
必須出席社員は、time_tblの先頭からmust_num人分です。つまり、配列の要素番号で表すと0からmust_num - 1までです。要素番号0の社員はaですでに調べているため、繰返しは要素番号1からmust_num - 1までを対象にします。したがって、eに入るのは、j = 1; j < must_numです。
次に、任意出席社員を加えていく処理を見ます。任意出席社員は、time_tblのmust_num番目から、順位の高い順に並んでいます。外側の繰返しでは、その順番に一人ずつ対象者を増やします。
対象の社員に予定がある時間帯では、sch[i]を1にします。これまでの社員について記録した1を0に戻さないため、sch[i]が0の時間帯は、必須出席社員と、そこまでに加えた任意出席社員の全員に予定がない時間帯です。search_free_slotは、そのような時間帯がslot_num以上連続する区間を探します。
search_free_slotは、見つけた時間帯の開始番号をs_start、連続する時間帯数をs_numに記録します。また、候補の最後には、次の要素のs_startに-1を入れて、候補の終わりを示します。候補が一つも見つからない場合は、先頭のwk_free[1][0].s_startが-1になります。
そこで、fでは、この値が-1かどうかを判定します。候補がなくなったら繰返しを終了し、それまでに確保できていた候補を残します。よって、fはwk_free[1][0].s_start == -1です。
誤りやすいポイント
- eの繰返しをj = 0から始めると、要素番号0の社員を二度調べます。その社員の予定はaで反映済みです。
- eの終了条件をj < numにすると、任意出席社員まで必須出席社員として扱ってしまいます。必須出席社員だけを調べるので、上限はmust_numです。
- s_startが0のときは「候補なし」ではありません。時間帯番号0から始まる候補があるという意味です。
- 候補がないときに判定するのはs_numではなくs_startです。終了を示す-1が設定されるのはs_startです。
- 候補が見つからなくなったとき、wk_free[1]の内容をwk_free[0]にコピーする前に繰返しを終了します。そのため、直前までに確保できていた候補が保たれます。
FAQ
Q: なぜ任意出席社員を順位の高い順に一人ずつ加えるのですか？
A: 順位の高い社員から順に、全員が出席できる時間帯が残るかを確かめるためです。候補がなくなった時点で、それより後の順位の社員は加えず、直前までの候補を使います。
A: 順位の高い社員から順に、全員が出席できる時間帯が残るかを確かめるためです。候補がなくなった時点で、それより後の順位の社員は加えず、直前までの候補を使います。
Q: search_free_slotが候補の最後に-1を入れるのはなぜですか？
A: 候補の数が決まっていなくても、後続の処理がどこまで読めばよいか分かるようにするためです。-1を目印にして、候補の読み取りを終えられます。
A: 候補の数が決まっていなくても、後続の処理がどこまで読めばよいか分かるようにするためです。-1を目印にして、候補の読み取りを終えられます。
Q: sch[i]を1にした後、予定がない社員を見つけても0に戻さないのはなぜですか？
A: 予定がない社員がいても、別の社員に予定があれば、その時間帯は全員が出席できる時間帯ではないからです。1を保つことで、これまでに調べた社員の予定ありを記録し続けます。
A: 予定がない社員がいても、別の社員に予定があれば、その時間帯は全員が出席できる時間帯ではないからです。1を保つことで、これまでに調べた社員の予定ありを記録し続けます。
関連キーワード: 配列、添字、ループ処理、条件判定、番兵値
