全商情報処理検定試験プログラミング部門1級を考える
愛媛県宇和島市のプログラミング教室、みんなのパソコン教室宇和島本校の代表 松井です。
高校生より全商情報処理検定試験プログラミング部門1級の受験対策をしたいというご依頼があり、改めて過去問等確認してみました。
VB触るの久しぶりです。
高校生より全商情報処理検定試験プログラミング部門1級の受験対策をしたいというご依頼があり、改めて過去問等確認してみました。
VB触るの久しぶりです。
過去問[第72回 情報処理検定試験]
出典：令和7年1月19日 第72回 情報処理検定試験 プログラミング１級
この問題、しっかりとアルゴリズムを学習している人はすぐに気づくかもしれません。二分探索のアルゴリズムになっているということを。
実は、それがわかると簡単に解くことができる問題でした。
ポイントはこの部分ですね。
あと、気を付けないといけないところとして、この部分。
配列の一番目のインデックス(Seiza(0))が空欄なので、データの始まりはSeiza(1)からであるという点です。
そして、そもそも問題文の最初「処理内容」に
【引数で渡された配列に記憶されている文字列を「探索して」メッセージをディスプレイに表示する。】
と、はっきり「探索」って記述されてるので、探索のアルゴリズムを意識してプログラムを読むと良いでしょう。
以上を踏まえて、このソースコードを読み解いてみましょう。
・Kaに数字の１を代入
・解答(1)
・mにKa + Joを２で割った整数部を代入
となっています。
この時点で、気づいた人も多いでしょう。
Ka は配列の左端になっている。
(仮説)ということはJoは配列の右端になっていて、mは配列の中央を取っているのだろうと。
これは、二分探索の基本的な書き方ですね。
ソート済みの配列の中央の値を取って、検索対象がその中央の値より大きいのか小さいのかを比較して、検索の範囲を絞っていくのが二分探索ですから。
ソート済みになっているかどうかは、問題文の
「配列 Seiza にはデータが昇順に記憶されている。」
という記述の通りです。
ここまでわかれば、問題は簡単に解けるでしょう。
解答(1)には配列の一番右を指定したいので、解答群から選択すると
Jo = n
でしょう。
「解答不要」って何だろうって思ったけど、ここにコード入れてると解答(2)が簡単に推測できてしまうので、あえて書かなかったんでしょうね。
例として配列Seiza()が {" " , "a" , "b" , "c" , "d" , "e" , "f" , "g"}だったとします。nは配列Seiza()の要素数である、8です。（先頭の空白も要素数としてカウントします）
Ka は1、Joはnの8、mは(1 + 8) ÷ 2 の整数部の4がそれぞれの初期値になります。
以上より
If Seiza(m) > Moji Then
のところを考えます。
Seiza(m)は最初Seiza(4)ということになり、”d”です。仮にキーボードから入力された文字列 Mojiが"c"だったとします。”c”は”d”より小さいので、探索の範囲をSeiza(4)よりも左側に絞ります。すなわち範囲の右端(Jo)をmの一つ左にするということです。なので「解答不要」に入るのは、Jo = m - 1になります。
解答(2)はその逆なので、探索の範囲をSeiza(4)よりも右側に絞ります。すなわち範囲の左端(Ka)をmの一つ右にずらすということなので Ka = m + 1という回答になります。
上の処理を
Do While Ka <= Jo And Seiza(m) <> Moji
の間繰り返す。
Ka <= Jo は左端が右端と同じになるまで繰り返す。すなわち左端の数値が右端を超えたときに、繰り返しが終了し、条件に一致する文字列が配列の中になかったということになります。
上記理由により
If Ka <= Jo Then
MsgBox ("該当データあり")
Else
MsgBox ("該当データなし")
End If
で、条件に一致する文字列が見つかったかどうかの判定ができるということです。
Visual Studioでコーディングしてみた。
ExcelのVBAでは記述しづらかったので、Visual Studioを使って、コンソールで入出力できるプログラムを作って動作確認しました。
入出力のところだけが、console.WriteLine()、console.ReadLIne()になってるだけで、それ以外のコード、アルゴリズムは変わらず書けてると思います。
Module Program
Sub Program1(Seiza() As String, n As Long)
Dim Moji As String
Dim Ka As Long
Dim Jo As Long
Dim m As Long
Console.WriteLine("文字列を入力してください")
Moji = Console.ReadLine()
Ka = 1
Jo = n
m = Int((Ka + Jo) / 2)
Do While Ka <= Jo And Seiza(m) <> Moji
If Seiza(m) > Moji Then
Jo = m - 1
Else
Ka = m + 1
End If
m = Int((Ka + Jo) / 2)
Loop
If Ka <= Jo Then
Console.WriteLine("該当データあり")
Else
Console.WriteLine("該当データなし")
End If
End Sub
Sub Main(args As String())
Program1({"", "a", "b", "c", "d"}, 3)
End Sub
End Module
< /code>