基本情報【科目B】令和6年度サンプル問題問4(複数while):｢完成形｣で楽しよう

基本情報技術者試験科目Bの「令和6年度サンプル問題問4」(2つの整列済み配列のマージ・複数の while)を、図解トレースで解説します。完成形を描いて比べながら解くと､楽できます｡

動画で見たい方はこちら▼

index

問題(令和6年度サンプル問題問4)
解説
まとめ
関連リンク
関連動画

問題(令和6年度サンプル問題問4)

次の記述中の【　】に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。

関数 merge は，昇順に整列された整数型の配列 data1 及び data2 を受け取り，これらを併合してできる昇順に整列された整数型の配列を返す。関数 merge を merge({2, 3}, {1, 4}) として呼び出すと，α の行は【　】。

○ 整数型の配列: merge(整数型の配列: data1, 整数型の配列: data2)
    整数型: n1 ← data1 の要素数
    整数型: n2 ← data2 の要素数
    整数型の配列: work ← { (n1 + n2) 個の未定義の値 }
    整数型: i ← 1
    整数型: j ← 1
    整数型: k ← 1

    while ((i ≤ n1) and (j ≤ n2))
        if (data1[i] ≤ data2[j])
            work[k] ← data1[i]
            i ← i + 1
        else
            work[k] ← data2[j]
            j ← j + 1
        endif
            k ← k + 1
    endwhile

    while (i ≤ n1)
        work[k] ← data1[i]
        i ← i + 1
        k ← k + 1
    endwhile

    while (j ≤ n2)
        work[k] ← data2[j]  /***α***/
        j ← j + 1
        k ← k + 1
    endwhile

    return work

解答群

ア　実行されない　イ　１回実行される　ウ　２回実行される　エ　３回実行される

本番さながらの環境で解いてみたい方はこちら↓

⛶ 全画面表示で解く

解説

正解は イ（1回実行される） です。

⓪まず「完成形」を書く

問題文の「関数 merge は，昇順に整列された整数型の配列 data1 及び data2 を受け取り，これらを併合してできる昇順に整列された整数型の配列を返す」がポイントです。{2, 3} と {1, 4} を併合して昇順に並べるので、work は最終的に {1, 2, 3, 4} です。完成形がわかっていると、トレース中の確認に使える上、より早く正解にたどり着けます。

work（完成形）

1	2	3	4
1	2	3	4

このように、「何を返す関数なのか（ここでは『併合して昇順に整列した配列』）」は問題文から必ず確認し､最終形が分かる場合は書いてしましょう。

①トレース表を作成

data1

1	2
2	3

data2

1	2
1	4

work

1	2	3	4
ミ	ミ	ミ	ミ

(`整数型の配列: work ← { (n1 + n2) 個の未定義の値 }` を反映。「ミ」＝未定義)

トレース表（初期値 n1=2, n2=2, i=1, j=1, k=1 を反映）

n1	n2	i	j	k	while((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])	while(i ≤ n1)	while(j ≤ n2)
2	2	1	1	1

while() は w()、if は i() と略せます。ただし何の処理の条件なのか分かるよう、() だけでは書かないようにしましょう。

②while ((i ≤ n1) and (j ≤ n2)) の1周目

繰り返し w((i ≤ n1) and (j ≤ n2)) が○なので、if (data1[i] ≤ data2[j]) を判定します。

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])
2	2	1	1	1	(1≤2) and (1≤2) ○	data1[1]≤data2[1] 2≤1 ×

③(if判定は×なので)elseの処理を行う

work[k] ← data2[j]

work

1	2	3	4
ミ	ミ	ミ	ミ
~~data2[j]~~ ~~data2[1]~~ 1

以下の2ステップで反映しましょう。 1. work[k] を処理する … k は1なので、配列表の work[1] に `data2[j]` を記入。 2. data2[j] の値を読み取る … j は1なので、data2[1] の値を work[1] に上書き。

都度、完成形と見比べましょう。どちらも1番目に1が入っており一致するので、正しくトレースできていることがわかります。

④j ← j + 1 と k ← k + 1 を反映

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])	w(i ≤ n1)	w(j ≤ n2)
2	2	1	1	1
			2	2	(1≤2) and (1≤2) ○	data1[1]≤data2[1] 2≤1 ×

⑤(2周目)

(i ≤ n1) and (j ≤ n2) は○なので、if (data1[i] ≤ data2[j]) を判定します。

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])
2	2	1	1	1
			2	2	○	×
					(1≤2) and (2≤2) ○	data1[1]≤data2[2] 2≤4 ○

⑥(○なので)true時の処理

work[k] ← data1[i]

work

1	2	3	4
ミ	ミ	ミ	ミ
~~data2[j]~~ ~~data2[1]~~ 1	~~data1[i]~~ ~~data1[1]~~ 2

i ← i + 1、k ← k + 1

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])
2	2	1	1	1
			2	2	○	×
		2		3	(1≤2) and (2≤2) ○	data1[1]≤data2[2] 2≤4 ○

⑦3周目以降も同様に繰り返す

このwhileは、if が○なら data1 を、×なら data2 を work に入れるという分岐です（1周目が×＝data2、2周目が○＝data1）。1つ目の while が×になるまで繰り返すと、次のようになります。

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])
2	2	1	1	1
			2	2	○	×
		2		3	(1≤2) and (2≤2) ○	data1[1]≤data2[2] 2≤4 ○
		3		4	(2≤2) and (2≤2) ○	data1[2]≤data2[2] 3≤4 ○
					(3≤2) and (2≤2) ×

⑧完成形と比べる

work

1	2	3	4
1	2	3	ミ

この時点で work は {1, 2, 3, ミ} で、あと必要なのは data2[2]＝4 を work[4] に入れることだけです。残り2つの while の中身を見てみましょう。

    while (i ≤ n1)
        work[k] ← data1[i]
        i ← i + 1
        k ← k + 1
    endwhile

    while (j ≤ n2)
        work[k] ← data2[j]  /***α***/
        j ← j + 1
        k ← k + 1
    endwhile

2つ目の while では data1 の値を、3つ目（α のある while）は data2 の値を work に入れています。よって「data2 を入れる」3つ目の while（α）を1回実行すれば完成するので、答えは イ（1回） だと推測できます。

j と n2 は共に2なので、あと1回の繰り返しで `w(j ≤ n2)` が×になることからも、1回だとわかります。

あとは、時間があればトレースして確認しましょう。

⑨ while (i ≤ n1) の判定

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])	w(i ≤ n1)	w(j ≤ n2)
2	2	3	2	4			3≤2 ×

i ≤ n1（3≤2）が×なので、1回も実行せずに終了します。

⑩ while (j ≤ n2) の判定

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])	w(i ≤ n1)	w(j ≤ n2)
2	2	3	2	4			×	2≤2 ○

⑪ work[k] ← data2[j]（α の部分）

work

1	2	3	4
ミ	ミ	ミ	ミ
~~data2[j]~~ ~~data2[1]~~ 1	~~data1[i]~~ ~~data1[1]~~ 2	~~data1[i]~~ ~~data1[2]~~ 3	~~data2[j]~~ ~~data2[2]~~ 4

j ← j + 1、k ← k + 1

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])	w(i ≤ n1)	w(j ≤ n2)
2	2	3	2	4
			3	5				○

⑫(2周目) while (j ≤ n2) の判定

n1	n2	i	j	k	w(j ≤ n2)
2	2	3	2	4
			3	5	○
					3≤2 ×

α を実行したのは1回だけなので、答えは イ（1回実行される） です。

Memo: 何回か実行される場合、回数は「✓をつけて数える」

「α の行が何回実行されるか」のように回数を問う問題では、トレース表に α の列を作り、α を実行するたびにチェック印(✓)をつけていきましょう。最後にチェックの数を数えれば実行回数です。（今回は1回だけで、途中で1回だと推測できたため別途は数えていません。）

例えば α の列を足すと、こうなります。

n1	n2	i	j	k	w((i ≤ n1) and (j ≤ n2))	if(data1[i] ≤ data2[j])	w(i ≤ n1)	w(j ≤ n2)	α
2	2	3	2	4
			3	5				○	✓

別の場所に「正」の字で数えてもOKですが、✓ の方が後から見直してカウント漏れに気づきやすいです。

まとめ

複数の while がつながる問題は、まず 完成形（ここでは併合後の {1, 2, 3, 4}）を先に書いて確認に使う のがコツ。1つ目の while は × なら data2、○ なら data1 を work に入れる 分岐で、1周ずつ「判定→処理」を追います。残り2つの while は「余った要素をそのまま入れる」だけなので、α が何回実行されるかは残りを見れば推測できます。回数を問われたら、その行を通るたびに ✓ を打って最後に数えるのが確実です。