この記事は応用情報技術者が監修しています。
- 基本情報技術者試験の科目Bのアルゴリズムの解き方
- 全ての素数だけを格納した配列を返す関数に関する問題
- 手続procに関する問題
- 関数sort内で出力される配列dataに関する問題
- 関数addで配列hashArrayに値がどのように代入されるかに関する問題
- コサイン類似度を求める式をプログラムで表す問題
アルゴリズムが全く分からない、初めて学ぶという人は以下の記事でアルゴリズムの基礎を学ぶことができます。
基本情報技術者試験の科目Bのアルゴリズム問題ができない、難しい、苦手という人向けに解き方を分かりやすく解説します。
どういう考え方で解くのかに焦点を当てた解説になっているので、覚え方が分からない人でも解けるようになります。
問題文を見ると難しそうに見えるけど、実は考え方次第で簡単に解くことが可能です。
試験前の対策などに活用してください。
令和5年度の過去問を対象にしています。
基本情報技術者令和5年度過去問の問1の解き方
全ての素数だけを格納した配列を返す関数に関する問題
次のプログラム中のaとbに入れる正しい答えの組合せを， 解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
関数 findPrimeNumbers は，引数で与えられた整数以下の，全ての素数だけを格納
した配列を返す関数である。ここで，引数に与える整数は 2 以上である。
ア
出典：出典：令和５年度 基本情報技術者試験 科目B 公開問題 問1
まずは、簡単な考えで答えを求める方法を解説します。
問題文に「関数 findPrimeNumbers は，引数で与えられた整数以下の，全ての素数だけを格納
した配列を返す関数である。」とあるので、2つのことが分かります。
①素数を判定する必要がある
②引数で与えられた整数以下の値で判定する
プログラムを見てみると、forが2回あるので、外側のforで i が引数で与えられた整数まで1ずつ増えて、内側のforで i が素数かを判定するんだろうということが分かります。
空欄aには「maxNum」または「maxNum + 1」が入るので、「②引数で与えられた整数以下の値で判定する」から「maxNum」だろうと考えられます。
内側のループでは素数ではないことを判定したいんだろうと分かるので、解答群の「i ÷ j の商は1に等しくない」場合は素数である可能性があるので、答えになりません。
よって空欄bには「i ÷ j の余り が 0 と等しい」が当てはまることが分かります。
以下、詳しい解説です。
まずは条件を整理しましょう。
・配列の要素番号は1から始まる
・引数で与えられた整数以下の，全ての素数だけを格納した配列を返す関数
→素数とは、1または自らの数字でしか割り切れない値のこと。例えば、2,3,5,7,11,13が素数です。
・引数に与える整数は 2 以上
プログラムを1つずつ確認していきます。
まず問題文に、for(i を 2から空欄 a まで１ずつ増やす)とあり、解答群を見ると「maxNum」または「maxNum + 1」まで増えることが分かるので、仮に空欄aには「maxNum」が入るとして考えてみましょう。
仮にmaxNumの値が9であるなら、最初 i は2でループするごとに3、4、5、6、7、8、9と増えていきます。
1つ目のfor文ではdivideFlgにtrueが入ります。
次に問題文に「 i の正の平方根の整数部分が2未満のときは，繰返し処理を実行しない」とあります。
まずは平方根について簡単に説明します。
ある数字を2乗すると、なんらかの数字Xになりますが、このある数字というのが平方根です。
上記の文に当てはめて例文を作ります。
2(ある数字)を2乗すると、4(X)になりますが、この2(ある数字)というのが平方根です。つまり、4の「平方根は2」です。
1.73205…(ある数字)を2乗すると、3(X)になりますが、この1.73205…(ある数字)というのが平方根です。つまり、3の「平方根は1.73205」です。
正の平方根の整数部分とは、1.73205であれば1のことを指しています。
それぞれの平方根は次のようになります。()内の数字が平方根です。
2(1.414)、3(1.732)、4(2)、5(2.236)、6(2.449)、7(2.645)、8(2.828)、9(3)
外側のfor文が実行されると内側のfor文が実行されるので、1回目のループでは i は2です。
問題文に「 i の正の平方根の整数部分が2未満のときは，繰返し処理を実行しない」とあります。上に書いてある、平方根を見ると、2(1.414)、3(1.732)であることが分かるため、内側のfor文は i が4になるまで実行されません。
内側のfor文が実行されない場合、divideFlgにtrueが入ったままなので、pnListの末尾にiの値が追加されます。
pnListの末尾に2と3が追加されました。
i の正の平方根の整数部分が2以上の場合は、内側のfor文が実行されるので、i が4以上の場合はfor文が実行されます。
内側のfor文の中のif文では、i が素数かを判断し、素数でなければdivideFlgにfalseを入れることで、pnListの末尾に値を入れないようにしたいのだろうと予想が出来ます。
つまり、素数ではないと判定する条件が必要になります。
i が4から8の場合を考えてみます。
for(j を 2 から i の正の平方根の整数部分 まで 1 ずつ増やす)とあります。
4の「平方根は2」
5の「平方根は2.236」
6の「平方根は2.449」
7の「平方根は2.645」
8の「平方根は2.828」
9の「平方根は3」
i が4～8の場合 i の正の平方根の整数部分は２のままなので、jは増えません。
そのため、ループは1回だけ実施され、1回だけ空欄bの条件判定が実施されます。
素数とは、1または自らの数字でしか割り切れない値のことでした。
解答群の「i ÷ j の余りが0と等しい」を試してみます。
4 ÷ 2 = 2;余り0(割り切れているので素数ではない)
5 ÷ 2 = 2;余り1(素数)
6 ÷ 2 = 3;余り0(割り切れているので素数ではない)
7 ÷ 2 = 3;余り1(素数)
8 ÷ 2 = 4;余り0(割り切れているので素数ではない)
素数を判定できています。
素数でない場合にdivideFlgにfalseを入れたいので、空欄bには「i ÷ j の余り が 0 と等しい」が当てはまります。
空欄aについては、「引数で与えられた整数以下の，全ての素数だけを格納した配列を返す」とあるのことから、「maxNum」以下の整数が素数かを判定すれば良いと分かるので、空欄aは「maxNum」です。
答えはアです。
基本情報技術者令和5年度過去問の問2の解き方
手続procに関する問題
次の記述中の に入れる正しい答えを，解答群の中から選べ。
次のプログラムにおいて，手続proc2を呼び出すと， の順に出力される。
ク
出典：出典：令和５年度 基本情報技術者試験 科目B 公開問題 問2
proc3()は”C”を出力します。
proc1は”A”を出力してからproc3()を実行するので”C”を出力します。
これらを踏まえてproc2()を考えます。
proc2()を実行。
①proc3()は”C”を出力。
②”B”を出力。
③proc1は”A”、”C”を出力。
CBAC
答えはクになります。
基本情報技術者令和5年度過去問の問3の解き方
関数sort内で出力される配列dataに関する問題
次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
次の手続 sort は，大域の整数型の配列 data の，引数 first で与えられた要素番号から引数 last で与えられた要素番号までの要素を昇順に整列する。
ここで，first ＜ last とする。手続 sort を sort(1, 5) として呼び出すと，/*** α ***/ の行を最初に実行したときの出力は“ ”となる。
エ
出典：出典：令和５年度 基本情報技術者試験 科目B 公開問題 問3
手続 sort を sort(1, 5) として呼び出すと問題文中にあるので、1がfirst、5がlastになります。
pivot ← data[(first + last) ÷ 2 の商]とあるので、[(1 + 5) ÷ 2 の商]は3です。
data[3]になるので、配列dataの3番目の値は3なので、pivotには3が入ります。
data ← {2, 1, 3, 5, 4}とあるので、配列dataには、左の数字から順番に格納されています。
data[1]は2を表します。
data[2]は1を表します。
ここまでを整理します。
pivot = 3
i = 1
j = 5
次に while(data[i] < pivot) は while(data[i] < 3) という意味(data[i]の値が3より小さい間ループする)なので、data[i]の値が3になるまでループをし、iの値が3まで加算されます。
i = 3
次に while(pivot < data[j]) は while(3 < data[j]) という意味(data[j]の値が3より大きい間ループする)なので、data[j]の値が3になるまでループをし、jの値が3まで減算されます。
j = 3
次に if(i ≧ j)とは i が j 以上の場合という意味なので、i と j は共に3なので条件に一致します。
繰り返し処理を終了するとあるので、「dataの全要素の値を要素番号の順に空白区切りで出力する」が実行されます。
2 1 3 5 4
「data[i] と dats[j]の値を入れ替える」という処理は行われない為、配列の順番は最初のままなので、答えはエです。
基本情報技術者令和5年度過去問の問4の解き方
関数addで配列hashArrayに値がどのように代入されるかに関する問題
次の記述中の に入れる正しい答えを，解答群の中から選べ。ここで，
配列の要素番号は 1 から始まる。
関数 add は，引数で指定された正の整数 value を大域の整数型の配列 hashArray に
格納する。格納できた場合は true を返し，格納できなかった場合は false を返す。
ここで，整数 value を hashArray のどの要素に格納すべきかを，関数 calcHash1 及び
calcHash2 を利用して決める。
手続 test は，関数 add を呼び出して，hashArray に正の整数を格納する。手続
test の処理が終了した直後の hashArray の内容は， である。
エ
出典：出典：令和５年度 基本情報技術者試験 科目B 公開問題 問4
処理はtest()から始まります。
配列hashArrayは要素数5と初期値-1で初期化されます。
add(3)とあるので、関数addのvalueは3となり、関数calcHash1が実行されます。
calcHash1は return (value mod hashArrayの要素数) + 1とあるので、(3 % 5)+1を計算します。
modは剰余算のことで記号は%を使います。
剰余算とは、割った余りを求める計算です。
余りの3と1を足すと4になるので、4を関数addに返して、変数 i に代入します。
hashArray[4]は-1なので、hashArray[4]に3を代入します。
もしhashArray[i]の値が-1でなければ、関数calcHash2が実行され、配列hashArrayの他の要素に値が代入されるという仕組みになっています。
次はadd(18)ですが、関数calcHash1の結果4になり、hashArray[4]には3が入っているため、関数calcHash2が実行され2が返されるので、hashArray[2]に18が代入されます。
次はadd(11)ですが、関数calcHash1の結果2になり、hashArray[2]には18が入っているため、関数calcHash2が実行され5が返されるので、hashArray[5]に11が代入されます。
配列の値は-1, 18, -1, 3, 11となるため、答えはエです。
基本情報技術者令和5年度過去問の問5の解き方
コサイン類似度を求める式をプログラムで表す問題
次のプログラム中のaとbに入れる正しい答えの組合せを，解答群の中から選べ。ここで，配列の要素番号は 1 から始まる。
コサイン類似度は，二つのベクトルの向きの類似性を測る尺度である。関数calcCosineSimilarity は，いずれも要素数が n(n≧1) である実数型の配列 vector1 と vector2 を受け取り，二つの配列のコサイン類似度を返す。配列 vector1 が {a1, a2, …, an}，配列 vector2 が {b1, b2, …, bn} のとき，コサイン類似度は次の数式で計算される。ここで，配列 vector1 と配列 vector2 のいずれも，全ての要素に 0 が格納されていることはないものとする。
エ
出典：出典：令和５年度 基本情報技術者試験 科目B 公開問題 問5
この問題は、「コサイン類似度」，「二つのベクトルの向きの類似性を測る尺度」などの言葉が出てきますが、無視して大丈夫です。
このプログラムは、問題文中の式を表しているので、式の内容を空欄に当てはめるだけで解くことが出来ます。
問題文中に「配列 vector1 が {a1, a2, …, an}，配列 vector2 が {b1, b2, …, bn} のとき」とあるので、配列vector1と2は式の要素を表していることが分かります。
変数numeratorにはnumeraterに何かを足したものが入ります。
連続して足し算したいことが分かるので、分子と同じことをしていると分かります。
まず、空欄 a はvector1[i] × vector2[i]になります。
次に、similarity ← numerator ÷ denominatorからdenominatorが式の分母であることが分かります。
分母の左側をdenominatorに代入してから、denominatorとvector2[i]の2乗を足していったtempの正平方根を掛け算する必要があるので。
空欄 b はdenominator × (tempの正の平方根)になることが分かります。
答えはエです。
