基本情報の午後試験はプログラム問題です．
科目B問題を解けるようになるにはプログラムを元に自分でコードを書いてみるのが1番良いでしょう．
今回は科目B問11「整列プログラム」の解説とそのコードを紹介します．
プログラムを元にPythonで書き直しました．
Pythonで書いてみたので是非手元で実行してみてください.
サンプル問題 科目B 問11「整列プログラム」
問題文は以下のとおりです．
リストの要素を昇順に並び替える問題です．
並び替えたあとに未定義の要素が含まれていてはいけません．
プログラムをPythonで書き直す
問11に掲載されているプログラムを元にPythonで書き直しました．
Pythonのソースコードが選択肢と比べて1小さいのはPythonの配列が0始まりのためです．
プログラムは配列の要素が1から始まっているため，Pythonに書き直すときは-1する必要があります．
ア～エを並び替えたとき昇順かつ未定義の要素がない配列はどれでしょうか？
from typing import List
def binSort(data: List[int]):
n = len(data)
bins = [None] * n
for i in range(0, n):
bins[data[i]] = data[i]
return bins
# Pythonは配列の要素が0から始まるためプログラム要素-1をする
print(f'ア{binSort([1, 5, 2, 0, 3, 4])}')
print(f'イ{binSort([2, 0, 3, 3, 4, 1])}')
print(f'ウ{binSort([3, 1, 0, 4, 5, 1])}')
print(f'エ{binSort([4, 2, 3, 2, 1, 5])}')
プログラムの結果「ア」のみ未定義がなく昇順に並び替えられました．
問題の答えも「ア」なので一致していますね．
プログラムに誤りはなさそうです．
ポイントを確認しましょう！
ポイント1 要素の数と同じ未定義の要素を持つ配列を作成する
この関数の引数は配列です．
初めの処理で配列の要素数を求めました．
要素数と [None] を掛けて引数の要素数と同じ要素数を持つ配列を作成しました．
要素はすべてNoneです．
def binSort(data: List[int]):
n = len(data) # 配列の要素数を数える
bins = [None] * n # 配列の要素数分だけNoneを作成する
引数[1, 5, 2, 0, 3, 4]の要素数は6です．
結果出力の[None, None, None, None, None, None]も要素数は6ですね．
ポイント2 要素を更新する
引数の配列を使ってNoneだけの配列を更新します．
「イ」[2, 0, 3, 3, 4, 1]を例にトレースします．
def binSort(data: List[int]):
...
for i in range(0, n): # i=0, n=6
bins[data[i]] = data[i] # bins[data[0]] = None, data[0]=2
return bins # [None, None, 2, None, None, None]def binSort(data: List[int]):
...
for i in range(0, n): # i=1, n=6
bins[data[i]] = data[i] # bins[data[1]] = None, data[1]=0
return bins # [0, None, 2, None, None, None]def binSort(data: List[int]):
...
for i in range(0, n): # i=2, n=6
bins[data[i]] = data[i] # bins[data[2]] = None, data[2]=3
return bins # [0, None, 2, 3, None, None]def binSort(data: List[int]):
...
for i in range(0, n): # i=3, n=6
bins[data[i]] = data[i] # bins[data[3]] = 3, data[3]=3
return bins # [0, None, 2, 3, None, None]def binSort(data: List[int]):
...
for i in range(0, n): # i=3, n=6
bins[data[i]] = data[i] # bins[data[4]] = None, data[4]=4
return bins # [0, None, 2, 3, 4, None]def binSort(data: List[int]):
...
for i in range(0, n): # i=3, n=6
bins[data[i]] = data[i] # bins[data[5]] = None, data[5]=1
return bins # [0, 1, 2, 3, 4, None]「イ」の選択肢では最後のNoneを更新できませんでした．
i=2, i=3のときに同じ要素を更新していましたね．
このように選択肢に同じ数字があるとすべての要素を更新できません．
以上の理由から「ウ」と「エ」も並び替えできません．
- 「ウ」[3, 1, 0, 4, 5, 1]：1が被っている
- 「エ」[4, 2, 3, 2, 1, 5]：2が被っている
よって答えは「ア」[1, 5, 2, 0, 3, 4]と分かりました．
まとめ
今回は科目B問11「整列プログラム」について紹介しました．
bins[data[i]]が2重にインデックス指定しているのでぱっと見分かりづらいですね．
「イ」を解いたときのように１度法則性に気づけが簡単でした．
この問題では配列の要素の数字が被っているとすべて更新できませんでした．
以上から「ア」のみが数字の重複がないためすべて更新できる答えだと分かりますね．
