はじめに
5/3に基本情報技術者試験を受けました。
結果は
- A問題 免除
- B問題 770/1000
でしたので無事合格できました。
去年の7月に午前免除を取得していてその後も情報セキュリティマネジメント、応用情報（試験当日は欠席）の勉強をしていましたが、アルゴリズムやプログラムを書いたりは殆どしておらずここ2ヶ月になって始めたので、アルゴリズムは殆ど勉強時間を取れない状態で午後試験に当日挑みました。
試験を解いてみた感想はセキュリティの問題は完全に情報セキュリティマネジメントの問題だったので、そちらの参考書過去問を理解できたら４問全て答えられると思います。逆に基本情報受かったらそのまま情報セキュリティマネジメント申し込んでいいと思いますw
アルゴリズムはサンプル問題と難易度が変わらないのでサンプル問題のif文やfor文while等を自分でフローチャートを書く、疑似言語で書いてみるをやると解きやすくなると思います。
今回の試験は午前免除を使いましたが、お陰で午後から試験に挑めて頭がスッキリな状態でB問題を解けたのがとても嬉しかったです。
無事に合格できましたが、元々アルゴリズムは特に苦手で人に教えられるほど殆ど理解できていません。また、参考書等でサンプル問題の解説を見なかったので今回IPAが公式で公開してるサンプル問題の解説を書きながら深く理解していこうと思います。
紹介する問題は全て下記URLから引用しています。
サンプル問題
今年から問題の傾向が変わり、よりプログラムに似た形式になりました。
去年までの問題は日本語を丁寧に読み解く力が必要で自分は全くわかりませんでしたが、今年からは実際のプログラムに似た形式に変わったので対策すれば誰でも必ず受かるものとなったので安心しました。
実際の試験問題は多少マニアックなことが聞かれたとしても毎月試験受けれるのでサンプルで６割超えたらいつでも試験申し込んでいいと思います。
可能な限りわかり易く言葉でまとめるので最後までお付き合いいただけたらありがたいです。
問題文には説明するためにプログラムの実行文に行数を振っています。
問1
次の記述中の⬜︎に入れる正しい答えを，解答群の中から選べ。
プログラムを実行すると，“⬜︎”と出力される
〔プログラム〕
- 整数型: x ← 1
- 整数型: y ← 2
- 整数型: z ← 3
- x ← y
- y ← z
- z ← x
- yの値 と zの値 をこの順にコンマ区切りで出力する
解説
1〜3行目までで変数x,y,zを整数型と宣言し整数1,2,3を代入しています。
↓3行目までの処理工程
| 行数 | x | y | z |
|---|---|---|---|
| 1 | 1 | ||
| 2 | 1 | 2 | |
| 3 | 1 | 2 | 3 |
4行目からは 元々数字の入っていた変数xに変数yの値を代入して上書きするという作業をしていますので x＝2になります。
同様に5行目では 変数yにzの値を代入して上書きしているので、y＝3。
今度6行目では、変数zにxの値を代入して上書きしようとしていますが、変数xは4行目で上書きされているのでxの値は元々の1ではなく2になります。よってzにxの値を代入するとz＝2になります。
↓6行目までの処理
| 行数 | x | y | z |
|---|---|---|---|
| 1 | 1 | ||
| 2 | 1 | 2 | |
| 3 | 1 | 2 | 3 |
| 4 | 2 | 2 | 3 |
| 5 | 2 | 3 | 3 |
| 6 | 2 | 3 | 2 |
よって7行目でyとzで出力されるのは
y＝3
z＝2 になります。
問2
問２ 次のプログラム中の a ～ c に入れる正しい答えの組合せを，
解答群の中から選べ。
関数 fizzBuzz は，引数で与えられた値が，3 で割り切れて 5 で割り切れない場合
は“3 で割り切れる”を，5 で割り切れて 3 で割り切れない場合は“5 で割り切れ
る”を，3 と 5 で割り切れる場合は“3 と 5 で割り切れる”を返す。それ以外の場合
は“3 でも 5 でも割り切れない”を返す。
〔プログラム〕
1. ○文字列型: fizzBuzz(整数型: num)
2. 文字列型: result
3. if (num が a で割り切れる)
4. result ←” a で割り切れる"
5. elseif (num が b で割り切れる)
6. result ←” b で割り切れる"
7. elseif (num が c で割り切れる)
8. result ←” c で割り切れる"
9. else
10. result ←"3 でも 5 でも割り切れない"
11. endif
12. return result
解説
この問題はプログラムが上から下に実行されることを意識すれば困らない問題だと思います。
3で割り切れて5で割り切れない数字は 3の倍数
3で割り切れず5で割り切れる数字は 5の倍数
3で割り切れてかつ5でも割り切れる数字は 3の倍数であり5の倍数でもあるので15（3×5）の倍数になります
例えば、18は3で割り切れて5で割り切れないので3の倍数になります。25は3で割り切れず5で割り切れるので5の倍数。45は3で割り切れてかつ5でも割り切れるので15の倍数になります。
プログラムではnumに上記のような数字を代入したと想定して、ifの条件ごとに別のresultを代入しています。
仮に4行目でa=3 num=45を代入したとして、45は3でも5でも割り切れる数なのにプログラムは上から下へ処理を行うため「3で割り切れる数」とresultに返してしまいます。
またa=5を代入した場合でも「5で割り切れる数」とresultに返してしまいます。
よって4行目のif文の最初の結果は全ての条件が成立した場合を入れないといけません。よってa
には3と5で割り切れるを答えに入れなければいけません。
b、cはどちらに3か5を入れても問題ないので選択肢を見て選べば問題ありません。
問3
問３ 次の記述中の⬜︎に入れる正しい答えを，解答群の中から選べ。ここで，
配列の要素番号は 1 から始まる。
関数 makeNewArray は，要素数 2 以上の整数型の配列を引数にとり，整数型の配列
を返す関数である。関数 makeNewArray を makeNewArray({3, 2, 1, 6, 5, 4})として
呼び出したとき，戻り値の配列の要素番号 5 の値は となる。
〔プログラム〕
1. 整数型の配列: makeNewArray(整数型の配列: in)
2. 整数型の配列: out ← {} // 要素数0の配列
3. 整数型: i, tail
4. outの末尾 に in[1]の値 を追加する
5. for (i を 2 から inの要素数 まで 1 ずつ増やす)
6. tail ← out[outの要素数]
7. outの末尾 に (tail ＋ in[i]) の結果を追加する
8. endfor
9. return out
解説
まずは引数と戻り値の解説をします
関数は引数(今回だと配列[3, 2, 1, 6, 5, 4]の値)を使うことで結果（戻り値）が違うものになります。例えば自販機で缶ジュース150円のものを購入する際に1000円（引数）入れるとお釣りは850円（戻り値）帰ってきますし、200円（引数）を入れればお釣りは50円（戻り値）になります。
このように引数に入れる値によって戻り値は違う結果を返すことができます。
今回の場合関数makeNewArrayの引数として配列in{3, 2, 1, 6, 5, 4}を利用して戻り値out[]の配列の5番目の値は何かという問題です。
1行目で関数makeNewArrayでは引数としてin[]の配列を使うという宣言をしています。今回のプログラムでは{3, 2, 1, 6, 5, 4}を引数として関数を呼び出すとしているのでin{3, 2, 1, 6, 5, 4}の配列として扱うことができます。
2行目で結果として返される戻り値のout[]の配列を宣言しています。
3行目ではi, tailは整数型のデータを格納する変数であることを宣言しています
。
4行目では配列outの一番後ろにin[1]の値を追加しなさいと書いてあります。プログラミング言語では配列要素の順番は一番前の要素から0、1、2、3...と0から数えるのが一般的でしたが、この問題では丁寧に「配列の要素番号は 1 から始まる。」と書いてあります。要素番号は配列内の順番のことです。ここで0番目から数えるか1番目から数えるのかというのは出席番号を1番目から割り振るのか0番目から割り振るのかと同じ話です。
なのでin[1]の意味は「配列in[]の1番目の要素（中身）」のことです。in[]の配列はin{3, 2, 1, 6, 5, 4}となっているので一番目の要素は3になります。よってoutの末尾に3を追加します。 現在はout{3}の状態です。
5行目はfor文内でiを2からinの要素数まで1つずつ増やす間、6〜7行目の処理をループ処理するというものです。今回は要素数は6つあるのでiは2〜6の間処理を繰り返し行います。
6行目では、tailにout[outの要素数]の値を代入する処理です。1周目ではoutの中身は{3}のみなので要素数は1になります。配列outの1番目の要素は3なのでtailに3を代入します。
7行目では、outの一番後ろにtail＋in[i]の数字を追加しなさいと書いてあります。
現在tailは3が代入されていて、iは2が代入されているので配列inの2番目の要素は2になります。
よって、tail+in[2]=3+2=5がoutの末尾に追加されます。 なので、out{3,5}の状態になります。
i＝2の際の処理は終了したので同じようにiに1を足したi=3の処理を行います。
5行目、tailには配列outの2番目の配列の5を代入します。6行目ではtail+in[3]の結果を配列outの一番後ろに追加します。
tail+in[3]=5+1=6を配列outの一番後ろに追加します。 なのでout{3,5,6}の状態になります。
ここから先はトレース表を載せますので気になる方は計算してみてください。
処理番号は上から順に処理をするごとに1増えています。
↓for文の処理（4〜7行目の繰り返し処理）
| 処理番号 | 行数 | i | tail | in[i] | out{} |
|---|---|---|---|---|---|
| 1 | 4 | out{3} | |||
| 2 | 5 | 2 | 2 | out{3} | |
| 3 | 6 | 2 | 3 | 2 | out{3} |
| 4 | 7 | 2 | 3 | 2 | out{3,5} |
| 5 | 5 | 3 | 3 | 1 | out{3,5} |
| 6 | 6 | 3 | 5 | 1 | out{3,5} |
| 7 | 7 | 3 | 5 | 1 | out{3,5,6} |
| 8 | 5 | 4 | 5 | 6 | out{3,5,6} |
| 9 | 6 | 4 | 6 | 6 | out{3,5,6} |
| 10 | 7 | 4 | 6 | 6 | out{3,5,6,12} |
| 11 | 5 | 5 | 6 | 5 | out{3,5,6,12} |
| 12 | 6 | 5 | 12 | 5 | out{3,5,6,12} |
| 13 | 7 | 5 | 12 | 5 | out{3,5,6,12,17} |
| 14 | 5 | 6 | 12 | 4 | out{3,5,6,12,17} |
| 15 | 6 | 6 | 17 | 4 | out{3,5,6,12,17} |
| 16 | 7 | 6 | 17 | 4 | out{3,5,6,12,21} |
よって9行目で配列outを戻り値として返しているので、関数makeNewArrayはout{3,5,6,12,17,21}を返します。
そして問題文では、戻り値の配列の要素番号5の値を聞いているので、out[5]=17となります。
問4
問４ 次のプログラム中の(a) ～ (c) に入れる正しい答えの組合せを，
解答群の中から選べ
関数 gcd は，引数で与えられた二つの正の整数 num1 と num2 の最大公約数を，次
の(1)～(3) の性質を利用して求める。
(1) num1 と num2 が等しいとき，num1 と num2 の最大公約数は num1 である。
(2) num1 が num2 より大きいとき，num1 と num2 の最大公約数は，(num1 － num2)
と num2 の最大公約数と等しい。
(3) num2 が num1 より大きいとき，num1 と num2 の最大公約数は，(num2 － num1)
と num1 の最大公約数と等しい。
〔プログラム〕
1. ○整数型: gcd(整数型: num1, 整数型: num2)
2. 整数型: x ← num1
3. 整数型: y ← num2
4. （a）
5. if (b)
6. x ← x － y
7. else
8. y ← y － x
9. endif
10. (c)
11. return x
解説
これはユークリッドの互除法をプログラムにする問題ですね。主は数学a覚えていないので久しぶりにこの単語聞きました。
二つの数a、bの差が0の時はbが最大公約数になるが、差が0以外の時はa-b(a>b)またはb-a(a<b)を繰り返し行う手法です。
ユークリッドの互除法がわからなくてもaとbに適当な数字を代入して試すとこれは最大公約数を求めるプログラムだと実際に確かめることができます。
今回は2、3行目で二つの数字num1,num2をx,yに代入しています。
まずプログラムで気になるのは(b)です。ifの条件式がtrueだったらx←xーy、ifの条件式がfalseだったらy←y-xの処理を行います。
問題文で二つの数字の処理を行う記述がされているのは性質(2)(3)になります。 num1-num2の処理を行っているのは(2)になります。
文章を見ると、「(2) num1 が num2 より大きいとき，num1 と num2 の最大公約数は，(num1 － num2)と num2 の最大公約数と等しい」と書いてあるのでnum1>num2がtrueの際に処理を行うということになります。よって、num1=x、num2=yなので(b)はx＞yとなります。
(a)について考えてみます。選択肢ではif文かwhlie文のどちらになるかを聞いていますが、実際にnum1、num2に数字を代入してみるとわかりやすいです。
例として x←24、y←8を代入してみます。
x>yよりx-y=16になります。ただ(2)(3)より16と8では二つの数字が等しくないので処理を継続しなければなりません。よって、x>yよりx-y=8になります。ここで二つの数字が等しくなるので24と8の最大公約数は8となります。
上記より二つの数字が等しくなるまで繰り返し引き算をしなければならないので繰り返し処理を行うwhile(x≠y)が(a)に入ります。
(c)は疑似言語の書き方からwhile文ではendwhileで閉じるように指定がされているので(c)はendwhileになります。
問5
問５ 次のプログラム中の に入れる正しい答えを，解答群の中から選べ。
関数 calc は，正の実数 x と y を受け取り， √x^2＋y^2
の計算結果を返す。関数 calcが使う関数 pow は，第 1 引数として正の実数 a を，第 2 引数として実数 b を受け取り，a の b 乗の値を実数型で返す。
〔プログラム〕
○実数型: calc(実数型: x, 実数型: y)
return
解答群
ア (pow(x, 2) ＋ pow(y, 2)) ÷ pow(2, 0.5)
イ (pow(x, 2) ＋ pow(y, 2)) ÷ pow(x, y)
ウ pow(2, pow(x, 0.5)) ＋ pow(2, pow(y, 0.5))
エ pow(pow(pow(2, x), y), 0.5)
オ pow(pow(x, 2) ＋ pow(y, 2), 0.5)
カ pow(x, 2) × pow(y, 2) ÷ pow(x, y)
キ pow(x, y) ÷ pow(2, 0.5)
解説
この問題は4^0.5が2であることを知らないと解けません。
また、関数powはSQLやExcelではPOWER関数としてよく知られているので知っている方は想像しやすかったと思います。
問題文の関数powの引数を仮に第一引数a、第二引数bとして扱うとき、a^bする値を結果として返す関数としています。
この二つの引数にa=3、b=2とすると3^2より9を結果として返すということになるます。
今回は√x^2+y^2と同じ結果を返す、関数powを使った関数calc（caluclateの略）のプログラムはどれかを問う問題です。
自分はx=3、y=4を代入して考えました。
√3^2+4^2＝√9＋16＝√25＝±5になります。よって±5になるプログラムを探せばいいことになります。
(ア)は、(9+16)/√2より25√2/2(二分の25√2)になりますので違います。
(イ)は、(9+16)/(3^4)より25/81になりますので違います。
(ウ)は、pow(2, √3) ＋ pow(2,2)と計算途中で5にならないと気づけるので違います。
(エ)は、pow(pow(8, 4), 0.5)より64になりますので違います。
(オ)は、pow(9 ＋ 16, 0.5)より±5になりますの正しい選択肢になります。
(カ)は、9×16÷81より16/9になりますので違います。
(キ)は、81÷√2より81√2/2になりますので違います。
⚠️全部計算する必要はないですww
よって答えは(オ)になります。
問6
問６ 次のプログラム中の に入れる正しい答えを，解答群の中から選べ。
関数 rev は 8 ビット型の引数 byte を受け取り，ビットの並びを逆にした値を返す。
例えば，関数 rev を rev(01001011) として呼び出すと，戻り値は 11010010 となる。
なお，演算子 ∧ はビット単位の論理積，演算子 ∨ はビット単位の論理和，演算
子 >> は論理右シフト，演算子 << は論理左シフトを表す。例えば，value >> n は
value の値を n ビットだけ右に論理シフトし，value << n は value の値を n ビット
だけ左に論理シフトする。
〔プログラム〕
- ○8 ビット型: rev(8 ビット型: byte)
- 8 ビット型: rbyte ← byte
- 8 ビット型: r ← 00000000
- 整数型: i
- for (i を 1 から 8 まで 1 ずつ増やす)
- ⬜︎
- endfor
- return r
解答群
ア r ← (r << 1) ∨ (rbyte ∧ 00000001)
rbyte ← rbyte >> 1
イ r ← (r << 7) ∨ (rbyte ∧ 00000001)
rbyte ← rbyte >> 7
ウ r ← (rbyte << 1) ∨ (rbyte >> 7)
rbyte ← r
エ r ← (rbyte >> 1) ∨ (rbyte << 7)
rbyte ← r
解説
この問題は2進数やビット列の論理シフトと論理演算（論理積や論理和）を理解していないと解けないので先に軽く解説します。基礎理論は難しいので、参考書やYouTube等の教材動画で基本情報の午前対策の基礎理論を丁寧に学習してもらえたらすんなり入ります。
00001000（2）は10進数では16ですが、
00010000（2）は10進数では32になります。
2進数のある桁から見て、一つ左の桁はその桁の2倍の数、一つ右の桁は1/2倍の数です。このことから二進数（ビット列）を左に1ビットずらすともとの数の2倍となり、右に1ビットずらすと元の数の1/2になるます。ビット列を左または右にずらすことをシフトといい、左にずらすことを左シフト、右にずらすことを右シフトといいいます。そして問題文でもあるように最上位ビット（一番前）も含めてシフトすることを論理シフトと言います。 他にもオーバーフローや算術シフトの用語がありますが、ここでは解説を省略します。
また、論理積はAND演算のことで論理和はOR演算のことを指します。（二つの用語の解説も省略します）
問題は、rbyteに代入したビット列の並びを逆にしてrにして返す関数revのプログラムに入る処理を入れる選択肢を選ぶものです。 例:01001011→1101001
今回は反転したいビット列rbyteには01001011を代入して考えます。
選択肢を一つずつ見ていきます。
(ア)ではi=1の一周目では、左側の(r << 1)によりr（00000000）を左に1ビットずらしています。
右側の(rbyte ∧ 00000001)では、一番右側のビット列のみを取り出すAND演算を行おうとしています。
（ア）は、r ← (r << 1) ∨ (rbyte ∧ 00000001)なのでOR演算を行います。
rは3行目で初期化された00000000が入っているので左に1ビットずらしても00000000になります。rbyteには01001011が入っていますので一番右側のビットのみを取り出すためにAND演算を行なっています。
01001011
AND 00000001
＝＝＝＝＝＝＝＝＝
00000001 が取り出されます。
なので r ← (00000000) or (00000001)によりOR演算で求めたものをrに代入します。
00000000
OR 00000001
＝＝＝＝＝＝＝＝＝
00000001 がrに代入されます。
そして rbyte ← rbyte >> 1ではrbyteのビット列を右に論理シフトすると言っています。ので
論理右シフト（1ビット）
01001011
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
1ビット右にずれる → 00100101 がrbyteに代入されます
これを繰り返した作業を下記のトレース表に載せますので試してみてください。
| i | r | rbyte |
|---|---|---|
| 00000000 | 01001011 | |
| 1 | 00000001 | 00100101 |
| 2 | 00000011 | 00010010 |
| 3 | 00000110 | 00001001 |
| 4 | 00001101 | 00000100 |
| 5 | 00011010 | 00000010 |
| 6 | 00110100 | 00000001 |
| 7 | 01101001 | 00000000 |
| 8 | 11010010 | 00000000 |
よって、rbyteのビットの並びが逆になっているので、答えは（ア）になります。
念の為、他の選択肢も試しておきます。
（イ）は、2行目の rbyte ← rbyte >> 7により 1周目の処理で7ビット右に論理シフト指定しまうので、一番左以外の全てのビットが0になってしまいます。
01001011
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
7ビット右にずれる → 00000000
よってrbyteが保持していたビット列が消されてしまうので違います。
（ウ）と（エ）はビットを取り出している作業はいいのですが、最終的にrbyteと結果として出力されるrが同じビット列になり、逆になりませんので違います。
問7
問７ 次のプログラム中の⬜︎に入れる正しい答えを，解答群の中から選べ。
関数 factorial は非負の整数 n を引数にとり，その階乗を返す関数である。非負
の整数 n の階乗は n が 0 のときに 1 になり，それ以外の場合は 1 から n までの整数
を全て掛け合わせた数となる。
1. 〔プログラム〕
2. ○整数型: factorial(整数型: n)
3. if (n ＝ 0)
4. return 1
5. endif
6. return ⬜︎
解説
再帰関数の話なので自分の定義に自分自身を呼び出して使用して決して無限ループはしてはいけないことだけ覚えてたら、最悪答え覚えてもいいかなと思ってますw
再帰関数で一番有名なのが、階乗関数です。
どんなものかというと
4！＝4x（4-1）！
3！＝3x（3-1）！
2！＝2x（2-1）！
1！＝1
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
2！＝2x1
3！＝3x2x1
4！＝4x3x2x1
4！＝24
というものです。
そのため必ずfunc=n * func(n-1) というようにn-1で呼び出されます。
仮に、func=n * func(n）として、n=4にすると
4！＝4x4！
4！＝4x4！
4！＝4x4！
4！＝4x4！
4！＝4x4！
4！＝4x4！
4！＝4x4！
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
4！＝4x4x4x4x4x4x...
となり無限ループになりますのでもしプログラムを組んで起動したらPCを壊すほどのリソースを食いますw
なのでこの問題は解説しませんが、階乗を求めるプログラムなので、答えはfunc=n * func(n-1)になります。
問8
問８ 次の記述中の に入れる正しい答えを，解答群の中から選べ。
優先度付きキューを操作するプログラムである。優先度付きキューとは扱う要素に優先度を付けたキューであり，要素を取り出す際には優先度の高いものから順番に取り出される。クラス PrioQueue は優先度付きキューを表すクラスである。クラス PrioQueue の説明を図に示す。ここで，優先度は整数型の値 1，2，3 のいずれかであり，小さい値ほど優先度が高いものとする。手続 prioSched を呼び出したとき，出力は の順となる。
| コンストラクタ | 説明 |
|---|---|
| PrioQueue() | 空の優先度付きキューを生成する。 |
| メソッド | 戻り値 | 説明 |
|---|---|---|
| enqueue(文字列型: s,整数型: prio) | なし | 優先度付きキューに，文字列 s を要素として，優先度 prio で追加する。 |
| dequeue() | 文字列型 | 優先度付きキューからキュー内で最も優先度の高い要素を取り出して返す。最も優先度が高い要素が複数あるときは，そのうちの最初に追加された要素を一つ取り出して返す。 |
| size() | 整数型 | 優先度付きキューに格納されている要素の個数を返す。 |
図 クラス PrioQueue の説明
〔プログラム〕
1. ○prioSched()
2. PrioQueue: prioQueue ← PrioQueue()
3. prioQueue.enqueue("A", 1)
4. prioQueue.enqueue("B", 2)
5. prioQueue.enqueue("C", 2)
6. prioQueue.enqueue("D", 3)
7. prioQueue.dequeue() /* 戻り値は使用しない /
8. prioQueue.dequeue() / 戻り値は使用しない /
9. prioQueue.enqueue("D", 3)
10. prioQueue.enqueue("B", 2)
11. prioQueue.dequeue() / 戻り値は使用しない /
12. prioQueue.dequeue() / 戻り値は使用しない */
13. prioQueue.enqueue("C", 2)
14. prioQueue.enqueue("A", 1)
15. while (prioQueue.size() が 0 と等しくない)
16. prioQueue.dequeue() の戻り値を出力
17. endwhile
解説
キューに優先度がついた問題です。
キューは最初に格納した要素を一番最初に取り出すデータ構造のことです。イメージしやすいのはレジ待ちのお客様の並び順です。一番最初に並んだ人が順番通り最初にレジに通されます。
ただ何を出力するかが分からず自分は初見で解いた際にすごく時間がかかりました。
プログラムを見ると
1行目で関数prioSched()の定義
2行目でPrioQueue()の中身を初期化しています
3行目〜14行目までで処理をしています。ただし /* 戻り値は使用しない */ という記述があるので、この間での処理では結果に戻り値が渡されませんので出力されません。
そして15行目〜16行目の繰り返し処理で出力をしていますので、ここで出力されます。問題はこの15〜16行目の出力結果を求めなさいと言っています。
次にメソッドについて解説します
enqueue(s,prio)では、（）内の文字列型の第一引数sを優先度prioで紐づけて優先度月キューに追加します。
dequeue()では、優先度月キューからキュー内で最も優先度の高い要素を取り出すものです。ただし、最も優先度の高い要素が複数あるときは，先に追加された要素を一つ取り出して返します。
ただし、問題文に「小さい値ほど優先度が高いものとする」と書いてあるので1が最も優先度が高いです。
size()は、キューに格納されている要素の個数を返します。キュー内に三つの要素が格納されていれば3を返します。
次にプログラムを一つずつ見ていきます。
3行目〜6行目でenqueue()により優先度つき要素が追加されました
↓6行目時点でのキューの中身の状態
prioQueue{("A", 1),("B", 2),("C", 2),("D", 3)}
7行目では、dequeue()により最も優先度の高いキューが取り出されますので("A", 1)が取り出されます。ここで/* 戻り値は使用しない */ と書いてあるのでデータがキューからなくなるだけとなります。
↓7行目時点でのキューの中身の状態
prioQueue{("B", 2),("C", 2),("D", 3)}
8行目でもdequeue()が行われますが、現在の優先度は優先度が同じ2の("B", 2),("C", 2)がありますので、先に追加された("B", 2)が取り出されます。
↓8行目時点でのキューの中身の状態
prioQueue{("C", 2),("D", 3)}
9〜10行目ではenqueue()により新たに二つ追加されました。
↓10行目時点でのキューの中身の状態
prioQueue{("C", 2),("D", 3),("D", 3),("B", 2)}
11〜12行目ではdequeue()により、優先度2の("C", 2)と("B", 2)が取り出されます。 /* 戻り値は使用しない */ と書いてあるのでここでもデータがキューからなくなるだけとなります。
↓12行目時点でのキューの中身の状態
prioQueue{("D", 3),("D", 3)}
13〜14行目でenqueue()によりまた新たに二つ追加されました。
↓14行目時点でのキューの中身の状態
prioQueue{("D", 3),("D", 3),("C", 2),("A", 1)}
15〜16行目で問題文で問われている出力結果の繰り返し処理が行われます。
prioQueue.size() が0になるまでdequeue()が行われますので
| prioQueue.size() | prioQueue.dequeue() の戻り値 |
|---|---|
| 4 | "A" |
| 3 | "C" |
| 2 | "D" |
| 1 | "D" |
の順で出力されます。
よって、手続 prioSched を呼び出したとき，出力は “A”，“C”，“D”，“D”の順となる。
問9
問９ 次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，
配列の要素番号は 1 から始まる。
手続 order は，図の 2 分木の，引数で指定した節を根とする部分木をたどりなが
ら，全ての節番号を出力する。大域の配列 tree が図の 2 分木を表している。配列
tree の要素は，対応する節の子の節番号を，左の子，右の子の順に格納した配列で
ある。例えば，配列 tree の要素番号 1 の要素は，節番号 1 の子の節番号から成る配
列であり，左の子の節番号 2，右の子の節番号 3 を配列｛2，3｝として格納する。
手続 order を order(1)として呼び出すと、⬜︎の順に出力される。
図 プログラムが扱う 2 分木
注記 1 ○の中の値は節番号である。
注記 2 子の節が一つの場合は，左の子の節とする。
〔プログラム〕
大域: 整数型配列の配列: tree ← {{2, 3}, {4, 5}, {6, 7}, {8, 9},
{10, 11}, {12, 13}, {14}, {}, {}, {},
{}, {}, {}, {}} // {}は要素数0の配列
1. ○order(整数型: n)
2. if (tree[n]の要素数 が 2 と等しい)
3. order(tree[n][1])
4. nを出力
5. order(tree[n][2])
6. elseif (tree[n]の要素数 が 1 と等しい)
7. order(tree[n][1])
8. nを出力
9. else
10. nを出力
11. endif
解答群
ア 1，2，3，4，5，6，7，8，9，10，11，12，13，14
イ 1，2，4，8，9，5，10，11，3，6，12，13，7，14
ウ 8，4，9，2，10，5，11，1，12，6，13，3，14，7
エ 8，9，4，10，11，5，2，12，13，6，14，7，3，1
解説
個人的にはかなり難しく初見で解いて間違えましたが、ゆっくり時間かけて解いたらわかりましたので解説書いていきます。
まず問題文に手続 order を order(1)として呼び出すと書いてありますので、最初はn＝1が格納されます。
2行目ではtree[1]の要素数が問われています。問題文に書いてあるようにtree[1]は親の節1に対して、子の要素2と3を持っています。よってtree[1]={2,3}が格納されています。よって、tree[1]の要素数は2つとなります。
2行目の条件式を満たすので order(tree[1][1]) が実行されます。これは上記の大域を確認します。帯域よりtreeの要素番号tree[1]＝tree{2,3}なのでtree{2,3}[1]と書き換えられます。これはtree{2,3}のうちの要素番号1番目の要素を取得するということなので、
order(tree[1][1])＝order(2)になります。
先ほど解説をはしょった再帰関数になります。order(1)内でorder(2)が呼ばれましたので1行目から処理を開始します。
2行目でtree[2]の要素数が問われています。tree[2]は親の節2に対して、子の要素4と5を持っています。よってtree[2]={4,5}が格納されています。よってtree[2]の要素数は2つとなります。
2行目の条件式を満たすので order(tree[2][1]) が実行されます。先ほどと同じように、tree{4,5}[1]と書き換えられるのでorder(tree[2][1])＝order(4)になります。
order(2)内でorder(4)が呼ばれましたので、また1行目から処理を開始します。
2行目でtree[4]の要素数が問われています。tree[4]は親の節4に対して子の要素8と9を持っていますので、tree[2]の要素数は2つとなります。
2行目の条件式を満たすので order(tree[4][1]) が実行され、order(tree[4][1])＝order(8)になります。
order(4)内でorder(8)が呼ばれましたので、もう一度1行目から処理を開始します。
2行目でtree[8]の要素数が問われています。しかし、tree[8]は子の要素を持っていませんので、要素数は0になります。2行目のif文の条件式にも6行目のelseifの条件式も満たさないので、9行目のelseに飛びます。
そして10行目より、nを出力するので 8 が最初に出力されます。
よって、少し処理が戻るので頭が困惑しやすいので気をつけますが、
この再帰処理は、order[1]からorder[2]へいきまたorder[4]が呼び出されそしてまた、order[8]が呼び出されたものなので、現在はorder[8]の処理が終了して呼び出し元のorder[4]になってます。
order[1]=order[2]呼び出し ↓
order[2]＝order[4] ↓
order[4]=order[8]⭐︎今ｺｺ ↓
order[8]=8出力 ↑ ←
なので、現在はn＝4となっています。
そして4行目のnを出力より 4が出力されます。
よって、回答群で8,4の順で出力されるのは一つしかないので答えは(エ)になります。
この後もorder(1)からの出力は終わりませんが、気になる方いたら計算してみてください。
問10
問10 次のプログラム中の に入れる正しい答えを，解答群の中から選べ。
手続 delNode は，単方向リストから，引数 pos で指定された位置の要素を削除する手続である。引数 pos は，リストの要素数以下の正の整数とする。リストの先頭の位置を 1 とする。
クラス ListElement は，単方向リストの要素を表す。クラス ListElement のメンバ変数の説明を表に示す。ListElement 型の変数はクラス ListElement のインスタンスの参照を格納するものとする。大域変数 listHead には，リストの先頭要素の参照があらかじめ格納されている。
表 クラス ListElement のメンバ変数の説明
| メンバ変数 | 型 | 説明 |
|---|---|---|
| val | 文字型 | 要素の値 |
| next | ListElement | 次の要素の参照 次の要素がないときの状態は未定義 |
〔プログラム〕
0. 大域: ListElement: listHead // リストの先頭要素が格納されている
1. ○delNode(整数型: pos) /* posは，リストの要素数以下の正の整数 /
2. ListElement: prev
3. 整数型: i
4. if (pos が 1 と等しい)
5. listHead ← listHead.next
6. else
7. prev ← listHead
8. / posが2と等しいときは繰返し処理を実行しない */
9. for (i を 2 から pos － 1 まで 1 ずつ増やす)
10. prev ← prev.next
11. endfor
12. prev.next ←⬜︎
13. endif
解説
単方向リストで要素を削除した際にどのようなデータの動きをするかイメージできるとわかりやすいので先に線形リストの中の一つである単方向リストについて説明します。
単方向リストとは、データを入れる部分と次のデータの場所を指すポインタを指す情報を持つデータ構造です。例えば
| 10 | 20 | 30 | 40 | 50 | 60 |
|---|
というデータ構造があったとします。前からデータを参照する用途で使っています。もし、20のデータを削除したとき、後ろのデータの場所を全て書き換えないといけません。
| 10 | 30 | 40 | 50 | 60 | |
|---|---|---|---|---|---|
| そのまま | ←に動かす | ←に動かす | ←に動かす | ←に動かす |
という形で、五つのデータ枠を書き換えないといけません。
しかし、単方向リストでポインタを持っていると20を削除した際に前（10）のポインタのみを書き換えれば済みます。
| データ | 10 | 30 | 40 | 50 | 60 | |
|---|---|---|---|---|---|---|
| 次のデータ先へのポインタ | 30の場所 | 40の場所 | 50の場所 | 60の場所 |
このようなポインタを持つ線形リストは他にもありますが今回はこのまま行きます。
問題文を見ると、手続 delNodeは、引数posで指定された位置の要素を削除する手続である。と書いてあるので、posで指定されたデータを別のデータで上書きすれば削除することができるとわかる。
プログラム4行目のもしposで指定されている場所が1番目ならば、5行目の処理でlistHeadをlistHead.nextで 問題文より、listHeadにはリストの先頭要素の参照（ポインタ）が格納されていると書いてあるので、lisHead.nextは2番目である。つまり、1番目に格納されている要素を2番目の要素で上書きしなさいという意味になります。
6〜7行目で、posが1以外ならばprevにlistHeadを代入しなさいとあります。よって、ここからはlistHeadはprevで代用することができます。
9〜11行目ではfor文で繰り返しデータを上書きする処理が行われていますが、仮にpos=2であったと仮定して話を進めます。
その場合はfor文は無視して12行目に飛びます。
単方向リストでは次のデータ先へのポインタしか持たないのでデータを削除する際は次のデータを使用します。よって、prev.nextを上書きする際はprev.nextの次のデータ先であるprev.next.nextが答えになります。
問11
問11 次の記述中の に入れる正しい答えを，解答群の中から選べ。
ここで，配列の要素番号は 1 から始まる。
関数 binSort を binSort( ) として呼び出すと，戻り値の配列には未定義の要素は含まれておらず，値は昇順に並んでいる。
〔プログラム〕
1. ○整数型の配列: binSort(整数型の配列: data)
2. 整数型: n ← dataの要素数
3. 整数型の配列: bins ← {n個の未定義の値}
4. 整数型: i
5. for (i を 1 から n まで 1 ずつ増やす)
6. bins[data[i]] ← data[i]
7. endfor
8. return bins
解答群
ア {2, 6, 3, 1, 4, 5} イ {3, 1, 4, 4, 5, 2}
ウ {4, 2, 1, 5, 6, 2} エ {5, 3, 4, 3, 2, 6}
解説
この問題は8行目で戻り値として返されるbinsの配列はどれかを問う問題です。
プログラムを見てみると、2行目のnには（ア）〜（エ）のどれもが6つの要素を持っているので6が代入されます。
3行目で、配列bins[]にn個の未定義の値を代入しなさいと書いてあります。この場合は3や5のようなものではなく ””の中には何も入っていない要素を６つ定義しなさいと言う一文です。
よって配列binsはbins{ , , , , , }の状態になります。
5〜7行目でfor文で要素番号1番目から6までの、data[i]の要素をdata[i]番目に代入しなさいと言っています。
（ア）の選択肢で実際にトレースして試してみます。
| 実行順序 | 行数 | i | data[i] | bins{} |
|---|---|---|---|---|
| 1 | 5 | 1 | 2 | bins{ , , , , , } |
| 2 | 6 | 1 | 2 | bins{ ,2, , , , } |
| 3 | 5 | 2 | 6 | bins{ ,2, , , , } |
| 4 | 6 | 2 | 6 | bins{ ,2, , , ,6} |
| 5 | 5 | 3 | 3 | bins{ ,2, , , ,6} |
| 6 | 6 | 3 | 3 | bins{ ,2,3, , ,6} |
| 7 | 5 | 4 | 1 | bins{ ,2,3, , ,6} |
| 8 | 6 | 4 | 1 | bins{1,2,3, , ,6} |
| 9 | 5 | 5 | 4 | bins{1,2,3, , ,6} |
| 10 | 6 | 5 | 4 | bins{1,2,3,4, ,6} |
| 11 | 5 | 6 | 5 | bins{1,2,3,4, ,6} |
| 12 | 6 | 6 | 5 | bins{1,2,3,4,5,6} |
よって、答えは（ア）になります。
仮に（イ）の場合、i=3の時に、bins[data[3]]に要素を代入しますが、 data[3]＝4の時はbins[4]より配列binsの4番目の場所に4を代入します。
そして、i=5の際にbins[data[4]]に要素を代入しますが、 data[4]＝4の時はbins[4]より先ほど代入した配列binsの4番目の場所に4を上書きします。そうすると、配列binsの要素は{1,2,3,4,5, }になりますが、問題文より、戻り値の配列には未定義の要素は含まれていないとされているので条件に合いませんでした。
（ウ）（エ）も同様に数字がかぶっているので、配列bins内に未定義の要素が含まれてしまいます。
問12
問12 次のプログラム中の⬜︎に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
関数 simRatio は，引数として与えられた要素数 1 以上の二つの文字型の配列 s1と s2 を比較し，要素数が等しい場合は，配列の並びがどの程度似ているかの指標として，（要素番号が同じ要素の文字同士が一致する要素の組みの個数 ÷ s1の要素数）を実数型で返す。例えば，配列の全ての要素が一致する場合の戻り値は 1，いずれの要素も一致しない場合の戻り値は 0 である。
なお，二つの配列の要素数が等しくない場合は，－1 を返す。関数 simRatio に与える s1，s2 及び戻り値の例を表に示す。プログラムでは，配列の領域外を参照してはならないものとする。
表 関数 simRatio に与える s1，s2 及び戻り値の例
| s1 | s2 | 戻り値 |
|---|---|---|
| {"a", "p", "p", "l", "e"} | {"a", "p", "p", "l", "e"} | 1 |
| {"a", "p", "p", "l", "e"} | {"a", "p", "r", "i", "l"} | 0.4 |
| {"a", "p", "p", "l", "e"} | {"m", "e", "l", "o", "n"} | 0 |
| {"a", "p", "p", "l", "e"} | {"p", "e", "n"} | -1 |
〔プログラム〕
1. ○実数型: simRatio(文字型の配列: s1, 文字型の配列: s2)
2. 整数型: i, cnt ← 0
3. if (s1の要素数 ≠ s2の要素数)
4. return －1
5. endif
6. for (i を 1 から s1の要素数 まで 1 ずつ増やす)
7. if ( ⬜︎ )
8. cnt ← cnt ＋ 1
9. endif
10. endfor
11. return cnt ÷ s1の要素数 /* 実数として計算する */
解答群
ア s1[i] ≠ s2[cnt] イ s1[i] ≠ s2[i]
ウ s1[i] ＝ s2[cnt] エ s1[i] ＝ s2[i]
解説
この問題の関数simRatioは、二つの配列s1,s2の要素の文字と位置が同じ場合の割合を計算して戻り値として返すプログラムです。
例えば、表1つ目の、s1{"a", "p", "p", "l", "e"}とs2{"a", "p", "p", "l", "e"}の際は要素数が同じなので、-1ではなくそのまま比較をしていきます。配列内の要素と並びが全て同じなので戻り値は1を返します。
次に、表2つ目のs1{"a", "p", "p", "l", "e"}とs2{"a", "p", "r", "i", "l"}を比較していきます。要素数は同じですが、要素の文字と並びが同じ要素は要素番号1、2のみとなります。
よって一致する要素の組みの個数は2つとなりますのでs1の要素数5で割ると、2÷5＝0.4となります。
表三つ目のs1{"a", "p", "p", "l", "e"}とs2{"m", "e", "l", "o", "n"}は全ての要素番号が同じ要素の文字同士が一致しないので0を戻り値として返します。
表四つ目の{"a", "p", "p", "l", "e"}とs2{"p", "e", "n"}は要素数が違うので比較をしないで、-1を返します。
プログラムを見ていきます。
1行目で、関数simRatioで使用する引数の配列s1、s2を定義しています。
2行目で、for文で繰り返し処理を行うための前から順に比較する要素番号iと、比較した結果同じ文字列同じ並び方をしている要素の個数を数えるcntを宣言します。
3行目で、s1とs2の要素数が違うかどうかを確認しています。もし違った場合はtrueなので4行目で戻り値-1を返して関数simRatioは終了します。
6行目〜10行目で、要素数が同じだった場合に限り配列s1とs2の要素がどの要素番号が同じ要素の文字同士が等しいかどうか比較していきます。forでは要素番号がs1になるまで前から順に比較する繰り返し処理です。
そして7行目ではifの条件式がtrueだった場合、cntを一つ増やすと言っているのでifの条件式には問題文の要素番号が同じ要素の文字同士が一致するの部分の式が入ります。
選択肢を見てみると、配列の同じ要素番号を比較しているのは(イ)(エ)のみになります。(イ)の場合、配列s1とs2の要素番号1の要素同士が違う時、trueを返してcntを一つ増やすと言っているので違います。
よって答えは(エ)のs1[i] ＝ s2[i]になります。
問13
問13 次の記述中の⬜︎に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
関数 search は，引数 data で指定された配列に，引数 target で指定された値が含まれていればその要素番号を返し，含まれていなければ －1 を返す。data は昇順に整列されており，値に重複はない。
関数 search には不具合がある。例えば，dataの ⬜︎ 場合は，無限ループになる。
〔プログラム〕
1. ○整数型: search(整数型の配列: data, 整数型: target)
2. 整数型: low, high, middle
3. low ← 1
4. high ← dataの要素数
5. while (low ≦ high)
6. middle ← (low ＋ high) ÷ 2 の商
7. if (data[middle] ＜ target)
8. low ← middle
9. elseif (data[middle] ＞ target)
10. high ← middle
11. else
12. return middle
13. endif
14. endwhile
15. return －1
解答群
ア 要素数が 1 で，target がその要素の値と等しい
イ 要素数が 2 で，target が data の先頭要素の値と等しい
ウ 要素数が 2 で，target が data の末尾要素の値と等しい
エ 要素に－1 が含まれている
二分探索について説明
この問題は、二分探索を行うプログラムの中に不具合があるのでそれを直しなさいと言うものです。
先に二分探索について解説します。二分探索を知ってる方は下の解説の方まで読み飛ばしてください。
例えば配列のデータdata{1,2,3,4,5,6,7,8,9,10}を用意します。この中から見つけたいデータデータであるtarget＝1を探そうとします。
配列のデータの先頭から一つずつ探した場合は1回目の要素番号1を確認した時にtarget=1が見つかるので比較回数は1回になります。
しかし、target=10の場合は前から順に一つずつ比較した場合、10回目の比較でtarget=10を見つけることができます。このようにデータの先頭から順に一つずつ比較して目的のデータを探す方法を線型探索法と言います。少ないデータ配列から探す場合は線型探索法でも問題はないのですが、データの母数が1000、1万になると沢山の比較をしなければならないので非効率です。
そこで前から一つずつ比較するのではなく整列された（昇順、降順どちらでもOK）データの並びにおいて探索範囲の中央の値と探索データを比較することで、探索範囲の前半あるいは後半を切り捨て、次に探索する範囲を1／2ずつ狭めていくことで、探索データを探す方法を二分探索法と言います。
例として配列の降順に並ぶデータdata{1,2,3,4,5}を用意し、探索したいデータtargetは2とします。(探索範囲には下線部を引いておきます。)
この際に探索範囲の下限lowと上限highをそれぞれ設定します。今回のデータ配列では下限は1、上限は5なのでlow=1、high=5にします。二分探索法では探索範囲の中央値を求めてから探してるデータtargetが探索範囲の前半にあるか後半にあるかを調べます。ですので、探索範囲lowとhighの中央値middleを求めます。
計算式はmidddle = (low + high) ÷ 2
＝ 3 になります。
middleは探してるデータtargetとは等しくないので、範囲を狭めてもう一度探索していきます。
data{1,2,3,4,5}の中央値から見てtarget=2は前半にあるか後半にあるかを確認します。
2 > 3より前半にあることがわかります。よって後半にはtargetがないことがわかりましたので、以降後半を切り捨てます。
探索範囲はdata{1,2,3,4,5}の1〜3になりましたのでもう一度二分探索を行います。探索範囲の下限は1、上限は3なのでlow=1、high=3とします。
中央値middleを求めたいので、( low + high ) ÷ 2 ＝2より targetとmiddleが等しくなったのでtarget=2を見つけられました。
二分探索法での平均比較回数はデータがn個の時、log[2]nで求められます。データが1024(2^10)個あっても平均比較回数は10回で済みます。
解説
上記のように二分探索法はデータを探す上で便利なのですが、問題の関数search()のプログラムではある一定の条件のときに無限ループが発生すると言っています。
今回の場合はあらゆる可能性がありますので、選択肢の(ア)〜(エ)を実際に検証していくのが一番早く解くことができます。
前提として、3行目で先頭データは必ず1としていますのでlow=1で固定になります。また4行目で上限highには配列のdata[]の要素数と同じ数字が入るとしているので要素数が1ならばhigh=1、要素数が2ならばhigh=2が入ります。
まず(ア)の場合、「要素数が1でtargetと要素数の値が等しい時」と書いてあるのでtarget=1になります。プログラムを見てみます。この場合配列には要素数が一つだけのdata{1}のみなので、探索範囲の上限下限はlow=1、high=1とします。
5行目は、low=high=1なのでtrueになるので、6行目に進みます。
6行目で、middle=(low + high)/ 2よりmiddle＝1となります。
7行目は、data[1]がtargetより小さいかどうかを判定しますが、1<1なのでfalseになります。
9行目でも、data[1]がtargetより大きいかどうかを判定しますが、1>1なのでfalseになります。
11、12行目でどの条件にも当てはまらなかったのでmiddleを戻り値として返して関数search()は終わります。 よって無限ループにならないので(ア)は違います。
次に(イ)の場合、要素数2の時にtargetがdataの先頭要素の値と等しいと言っているのでlow=1より、target=1になります。要素数が2なのでhigh=2になります。
5行目で、low < highよりtrueなので6行目に移ります。
6行目で、middle ＝ (low ＋ high) ÷ 2の商 よりmiddle = 1が入ります。
7行目で、data[1]がtargetより小さいか判定します。1<1より、falseになります。
9行目で、data[1]がtargetより大きいか判定します。1>1より、falseになります。
11、12行目で11、12行目でどの条件にも当てはまらなかったのでmiddleを戻り値として返して関数search()は終わります。 よって無限ループにならないので(イ)は違います。
今度は(ウ)を試してみます。要素数2の時にtargetがdataの末尾要素の値と等しいと言っているので、要素数が2でhigh=2なのでtarget=2になります。
5行目で、low<highよりtrueなので6行目に移ります。
6行目で、middle ＝ (low ＋ high) ÷ 2の商 よりmiddle = 1が入ります。
7行目で、data[1]がtargetより小さいか判定します。1<2より、trueになりますので、8行目に移ります。
8行目では、middle=1をlowに代入するように言っていますのでlow=1とします。
そして13行目で、if文が終了しましたが5〜14行目まではlow <= highの間繰り返し処理を実行しなさいと書いてあるのでもう一度6〜13行目の上記と同じ処理を行います。このように(ウ)ではループ処理が行われるので答えは(ウ)になります。
ちなみに(エ)の場合は要素に何が含まれていても（ウ）の条件を満たさない限りはループ処理にはなりませんので、問題なく探索できます。
問14
問14 次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。（問題文少し変えています）
要素数が 1 以上で，昇順に整列済みの配列を基に，配列を特徴づける五つの値を返すプログラムである。
関数 summarize を summarize({0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1})として呼び出すと，戻り値は である。
〔プログラム〕
1. ○実数型: findRank(実数型の配列: sortedData, 実数型: p)
2. 整数型: n
3. n ← (p × (sortedDataの要素数 － 1)) の小数点以下を切り上げた値
4. return sortedData[n ＋ 1]
5. ○実数型の配列: summarize(実数型の配列: sortedData)
6. 実数型の配列: rankData ← {} /* 要素数0の配列 */
7. 実数型の配列: p ← {0, 0.25, 0.5, 0.75, 1}
8. 整数型: i
9. for (i を 1 から pの要素数 まで 1 ずつ増やす)
10. rankDataの末尾 に findRank(sortedData, p[i])の戻り値 を追加する
11. endfor
12. return rankData
解答群
ア {0.1, 0.3, 0.5, 0.7, 1}
イ {0.1, 0.3, 0.5, 0.8, 1}
ウ {0.1, 0.3, 0.6, 0.7, 1}
エ {0.1, 0.3, 0.6, 0.8, 1}
オ {0.1, 0.4, 0.5, 0.7, 1}
カ {0.1, 0.4, 0.5, 0.8, 1}
キ {0.1, 0.4, 0.6, 0.7, 1}
ク {0.1, 0.4, 0.6, 0.8, 1}
解説
この問題は関数summarizeが何をやっているのかを理解することが大切です。問題文より引数sortedData{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1}を引数として渡した時にrankData{}がどのような値を返すかを選択肢の中から選べと言うものです。
5行目〜12行目の関数summarizeの中には10行目関数findRankが引数として配列sortedDataと配列pを渡されて処理しています。ですのでまずは1〜4行目の関数findRankの定義部分を見ていきます。
3行目では sortedDataの要素から1引いた数にpを掛けた値をiに代入しなさいと書いてあります。sortedDataには{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1}が渡されていますので要素数は10個でなります。そしてその要素数から1引いた値なので(sortedDataの要素数 － 1)は常に9になります。そして3行目はn ← (p × 9)の小数点以下を切り上げた値と書いてあるのでpに渡される値を探します。そうすると7行目にpは{0, 0.25, 0.5, 0.75, 1}の配列のデータを持つと書いてあるのでこの五つの値を参照して先ほどの3行目のnを求めることになります。
そして4行目で、sortedDataの先ほど求めたi+1番目のデータをfindRank関数に戻り値として返すと言うことになります。
関数sumarrize内ではfor文内で、findRankで返されたデータを要素数0の配列rankDataに繰り返し格納していきその中身がどのような値を返すかをこの問題は求めています。よってこの上記の手順で実際にやっていきます。
まず、8行目でfor文はi=1からスタートします。よって、findRank関数に渡される引数はsortedData{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1}とp[1]=0になります。
3行目のfindRank関数の定義に戻ります。
(p × (sortedDataの要素数 － 1))より、0 x 9＝ 0がiに代入されます。
4行目でi+1番目の要素番号のsortedDataの値を戻り値として返すので1番目の0.1を返します。
10行目に戻ります。よって、配列rankDataの末尾に0.1が追加されます。そしてfor文内で繰り返し処理が続きます。
i=2でまた処理が実行されますのでfindRank関数に渡される引数はsortedData{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1}とp[2]=0.25になります。
3行目のfindRank関数の定義に戻ります。
(p × (sortedDataの要素数 － 1))の小数点以下を切り上げた値より、0.25 x 9＝2.25になります。ただし下線部より小数点以下切り上げなので2.25を切り上げた3がiに代入されます。
4行目でi+1番目の要素番号のsortedDataの値を戻り値として返すので4番目の0.4を返します。
10行目に戻ります。よって、配列rankDataの末尾に0.4が追加されます。そしてfor文内で繰り返し処理が続きます。
i=3でまた処理が実行されますのでfindRank関数に渡される引数はsortedData{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1}とp[3]=0.5になります。
3行目のfindRank関数の定義に戻ります。
(p × (sortedDataの要素数 － 1))の小数点以下を切り上げた値よりi=5が代入されます。
4行目でi+1番目の要素番号のsortedDataの値を戻り値として返すので6番目の0.6を返します。
10行目に戻ります。よって、配列rankDataの末尾に0.6が追加されます。そしてfor文内で繰り返し処理が続きます。
i=4でまた処理が実行されますのでfindRank関数に渡される引数はsortedData{0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9,1}とp[4]=0.75になります。
3行目のfindRank関数の定義に戻ります。
(p × (sortedDataの要素数 － 1))の小数点以下を切り上げた値よりi=7が代入されます。
4行目でi+1番目の要素番号のsortedDataの値を戻り値として返すので6番目の0.8を返します。
10行目に戻ります。よって、配列rankDataの末尾に0.8が追加されます。
選択肢を見てみるとP{0.1, 0.4, 0.6, 0.8}の順で要素が追加されているのは(ク)しかないので答えは(ク)になります。
問15
問15 次の記述中の a と b に入れる正しい答えの組合せを，解答群の中から選べ。
三目並べにおいて自分が勝利する可能性が最も高い手を決定する。次の手順で，ゲームの状態遷移を木構造として表現し，根以外の各節の評価値を求める。その結果，根の子の中で最も評価値が高い手を，最も勝利する可能性が高い手とする。自分が選択した手を○で表し，相手が選択した手を×で表す。
〔手順〕
(1) 現在の盤面の状態を根とし，勝敗がつくか，引き分けとなるまでの考えられる
全ての手を木構造で表現する。
(2) 葉の状態を次のように評価する。
① 自分が勝ちの場合は 10
② 自分が負けの場合は－10
③ 引き分けの場合は 0
(3) 葉以外の節の評価値は，その節の全ての子の評価値を基に決定する。
① 自分の手番の節である場合，子の評価値で最大の評価値を節の評価値とする。
② 相手の手番の節である場合，子の評価値で最小の評価値を節の評価値とする。
ゲームが図の最上部にある根の状態のとき，自分が選択できる手は三つある。そのうち A が指す子の評価値は a であり，B が指す子の評価値はで b ある。
解説
図の根の状態からA、真ん中、Bの3種類の指す方法があるが真ん中を刺したら確定で勝てるけど、AかBを指した場合は勝敗の評価値はどうなるかを聞いています。
Aを指した場合、(3)②より評価値は最小の評価値が節の評価値となると書いてあります。相手も勝ちたいので自分に有利にわざと打ったりはしませんwですのでAの場合は結末が評価値0か10の引き分けか自分が勝つ未来のどちらかになります。よって相手は引き分けの方を選択するのでAを選んだ場合は評価値0になります。
Bを指した場合も同様に、結末が-10か0の相手が勝つか引き分けにするかのどちらかの未来があるので、(3)②より-10を選択します。よってBを選んだ場合は評価値-10になります。
選択肢より二つを満たすのは(ア)なので、答えは(ア)になります。
問16
問16 次のプログラム中の に入れる正しい答えを，解答群の中から選べ。二つの ⬜︎ には，同じ答えが入る。ここで，配列の要素番号は 1 から始まる。
Unicode の符号位置を，UTF-8 の符号に変換するプログラムである。本問で数値の後に“(16)”と記載した場合は，その数値が 16 進数であることを表すUnicode の各文字には，符号位置と呼ばれる整数値が与えられている。UTF-8 は，Unicode の文字を符号化する方式の一つであり，符号位置が 800(16) 以上 FFFF(16)以下の文字は，次のように 3 バイトの値に符号化する。
3 バイトの長さのビットパターンを 1110xxxx 10xxxxxx 10xxxxxx とする。ビットパターンの下線の付いた“x”の箇所に，符号位置を 2 進数で表した値を右詰めで格納し，余った“x”の箇所に0 を格納する。この 3 バイトの値が UTF-8 の符号である。
例えば，ひらがなの“あ”の符号位置である 3042(16) を 2 進数で表すと11000001000010 である。これを，上に示したビットパターンの“x”の箇所に右詰めで格納すると，1110xx11 10000001 10000010 となる。余った二つの“x”の箇所に 0 を格納すると，“あ”の UTF-8 の符号 11100011 10000001 10000010 が得られる。関数 encode は，引数で渡された Unicode の符号位置をUTF-8 の符号に変換し，先頭から順に 1 バイトずつ要素に格納した整数型の配列を返す。encodeには，引数として，800(16) 以上 FFFF(16) 以下の整数値だけが渡されるものとする。
〔プログラム〕
- ○整数型の配列: encode(整数型: codePoint)
- /* utf8Bytesの初期値は，ビットパターンの“x”を全て0に置き換え，
- 8桁ごとに区切って，それぞれを2進数とみなしたときの値 */
- 整数型の配列: utf8Bytes ← {224, 128, 128}
- 整数型: cp ← codePoint
- 整数型: i
- for (i を utf8Bytesの要素数 から 1 まで 1 ずつ減らす)
- utf8Bytes[i] ← utf8Bytes[i] ＋ (cp ÷ ⬜︎ の余り)
- cp ← cp ÷ ⬜︎ の商
- endfor
- return utf8Bytes
解答群
ア ((4 － i) × 2) イ (2 の (4 － i)乗) ウ (2 の i 乗)
エ (i × 2) オ 2 カ 6
キ 16 ク 64 ケ 256
解説
この問題は初見は全く分かりませんでしたw実際の試験でもこれくらい難しい問題出ましたが、自分は捨て問にして他の問題の見直しやメモ用紙に直接トレース表を書いたりと時間配分を変えたのでどこから手をつけていいか困った方は諦めていいと思ってます。
まずはこの問題文が何をやっているのかを見ていきます。問題文より、「Unicode の符号位置を，UTF-8 の符号に変換するプログラムである。」と書いてあるので、ビット列を変換するプログラムなんだなぁとイメージできます。そしてUTFー8では、3バイトの長さのビットパターンを 1110xxxx 10xxxxxx 10xxxxxxとして符号化するとしています。なのでUTFー8は全て1110xxxx 10xxxxxx 10xxxxxxの並び順でなければならないと言うことになります。xの位置には何が入るかというとUnicodeの文字を右詰めで格納して余ったら0埋めすると言うことになる。問題文の例を使うと
ひらがなの“あ”の符号位置である 3042(16) を 2 進数で表すと11000001000010 である。
これを右詰めで格納するにはまず、1110xxxx 10xxxxxx 10xxxxxxの下線部分を埋めていきます。下線部分には6ビット入るので“あ”の符号位置である 3042(16)の11000001000010の部分を格納します。よって、1110xxxx 10xxxxxx 10000010となります。まだ埋められてないビットが8個ありますので先ほどの6つのビットは消した11000001を格納していきます。1110xxxx 10xxxxxx 10xxxxxxの下線部分に右詰めで11000001の下線部分を入れていきます。よって1110xxxx 10000001 10000010になります。まだ残りの2ビット分である11を1110xxxx 10000001 10000010部分に入れていきます。結果、1110xx11 1000000
1 10000010となりますが残り2ビット分の下線部のxが残ってしまいました。問題文を見ると「余った二つの“x”の箇所に 0 を格納する」と書いてあるので、“あ”の UTF-8 の符号 11100011 10000001 10000010 が得られます。
したがって、この問題のプログラムencode()は 1110xxxx 10xxxxxx 10xxxxxxのx部分に引数(codePoint)を右詰めで埋める処理であることが分からないと解けません。
プログラムを見てみます。 プログラムでは変換したいUnicodeの文字を2進数で引数codePointとして扱い、変換したUTF-8の2進数の符号はutf8Bytesとして戻り値にして返します。
4行目、では1110xxxx 10xxxxxx 10xxxxxxの3ビットの長さのビットパターンで表すために8ビットごとに分けられたutf8Bytesに2進数として代入しています。
＜参考程度に＞
* 1110xxxxのビットパターン
128+64+32+0+0+0+0+0+0=224(10進数表記)
1 1 1 0 0 0 0 0(2進数表記)
* 10xxxxxxのビットパターン
128+0+0+0+0+0+0+0+0=128(10進数表記)
1 0 0 0 0 0 0 0(2進数表記)
* 10xxxxxxのビットパターン
128+0+0+0+0+0+0+0+0=128(10進数表記)
1 0 0 0 0 0 0 0(2進数表記)
〆
5行目では変換したいUnicodeの二進数表記codePointをcpに代入しています。
7行目〜10行目で utf8Bytesの要素数（今回は3つの10進数の要素が追加されているので3）が1になるまで右詰めで引数を埋める処理を繰り返し行います。
8行目で (cp ÷ ⬜︎ の余り) とありますが、問題文の例で挙げるとUnicode"あ"の2進数表記である11000001000010の余りを計算しなさいと言っています。右詰めをする際にはまず1110xxxx 10xxxxxx 10xxxxxxでどこからどこまでを埋めるかを確認します。最初は1110xxxx 10xxxxxx 10xxxxxxの下線部分を埋めていきますので6ビットを埋めていきます。そのためには引数が代入されたcpから右から6ビットを取り出さなければなりません。
そしてutf8Bytes[i] ← utf8Bytes[i] ＋ (cp ÷ ⬜︎ の余り)より取り出したビット列をutf8Bytesに格納しようとしています。
つまり、8行目は引数から取り出したビット列をutf8Bytesに格納する作業をしています。
6ビットの列を余りとして取り出すには2^6で割ることでできます。よって⬜︎に入るのは2^6である64です。
ちなみに9行目ではcpから右から6ビット引き出されたので6ビット右に論理シフトすることで残りの格納しなければならないビット列を特定してcpに格納する処理をしています。
最後に
初めて疑似言語について詳しく解説を書いていきましたが、深く理解できる一方でまだうまく言語化できていないことが多く周りに上手く伝えられるか怪しいので授業や普段のコードを書くときにコード一つ一つの意味合いを深く考えて知識や考え方を再利用できるように頭の中を整理していきます。
かなりの長文で誤字脱字、間違えた解説多々あると思いますので、気づいた方いましたらコメントで優しく教えていただけるとありがたいです。
最後まで読んでいただきありがとうございました。次に記事を書くのは果たしていつなんだろうか...