はじめに
基本情報技術者試験にアルゴリズム問題と呼ばれるものがあります。
これは、情報処理推進機構（IPA）が定めた疑似言語でアルゴリズムのプログラムが示され、受験者はプログラムの穴埋めや変数の推移などを解答するものです。
試験中はプログラムを脳内でシミュレートして解答しなければならず、なかなかしんどいです。
ほとんどの人が、基本情報技術者試験で一番苦労するところです。
また、基本情報技術者試験は令和2年度秋期からソフトウェア開発として、新たにPythonが選択できるようになりました。
一方で令和2年度秋期からCBT試験（予約した日に試験会場に行ってモニターに示された問題に解答する）が導入され、それとともに試験問題が公開されなくなりました。
Pythonについては、サンプル問題しか公開されておらず、過去問を用いた試験対策にはハンデがあります。
でも、試験合格後に「ソフトウェア開発で何を選択したの？」と聞かれて、「最近はやりのPythonで合格しました」と言えたらかっこいいじゃないですか？
そこで私は考えました。
疑似言語で書かれた過去のアルゴリズム問題をPythonで実装してみれば、アルゴリズムを自分でシミュレートでき、Pythonの勉強にもなって、一石二鳥ではないか。と
以下は、その実践例です。
実装
-
平成25年春期のアルゴリズム問題（食料品店の値引き処理）を対象とします。
- ご興味があるようなら、ぜひ問題にチャレンジしてみてください（所要時間30分）。
- この問題では、構造体型の変数が用いられています。Pythonには構造体がないので、クラスを使用しています。
- 実はクラスを自分で作ったのはこれが初めてです。クラスの理解には、Udemyの現役シリコンバレーエンジニアが教えるPython入門のセクション7が役に立ちました。
- 漢字の変数名（
購入[].単価等）はアルファベット（kounyu[].tanka等）に置き換えています。 - クラスで共通の変数(
prt_kiten等)はクラス変数に、インスタンスごとの変数（kounyu[].tanka等）はインスタンス変数にしています。 - 問題の配列は添え字が1から始まっているので、Pythonのリストの最初に空データを入れて添え字0を飛ばしています。
- 設問2でプログラムを修正するので、変数
testmodeを定義し、1の場合は設問１のプログラム、2の場合は設問2のプログラムが流れるようにしています。 -
test01、test02、test03を定義しました。 -
test01：設問1対応 特売のレコードの追加処理を実施 -
test02：設問2対応(1) 購入に品番223を追加して、特売のレコードの更新処理を実施 -
test03：設問2対応(2) 購入の品番221,222,223を削除して、特売のレコードの削除処理を実施- 品番221,222,223の削除処理と特売のレコードの削除処理は、 該当する特売のレコードを格納していた配列の要素はそのまま残し， ポインタの付替えによってレコードを無効にする。
h25s.py
# グローバル変数の設定
testmode = 1 # テストモード 1:設問１、2:設問2
class Kounyu: # 購入クラス
ptr_kiten = 2 # ptr起点
kounyu_gyousu = 5 # 購入行数
def __init__(self, ptr, hinban, hinmei, tanka, suuryo, kingaku):
self.ptr = ptr # prt
self.hinban = hinban # 品番
self.hinmei = hinmei # 品名
self.tanka = tanka # 単価
self.suuryo = suuryo # 数量
self.kingaku = kingaku # 金額
class Taisyo: # 対象クラス
shitei_suuryo = 3 # 指定数量
taisyo_gyousu = 3 # 対象行数
def __init__(self, hinban, suuryo):
self.hinban = hinban # 品番
self.suuryo = suuryo # 数量
class Tokubai: # 特売クラス
def __init__(self, hinban, hinmei, tanka, suuryo):
self.hinban = hinban # 品番
self.hinmei = hinmei # 品名
self.tanka = tanka # 単価
self.suuryo = suuryo # 数量
# 購入リストの初期値設定
kounyu = ["", # kounyu[0]は空データ
Kounyu(4,222,"B社緑茶500ml ",140,5,700),
Kounyu(1,111,"A社牛乳1000ml ",200,2,400),
Kounyu(0,335,"C社めんつゆ300g ",150,1,150),
Kounyu(5,224,"B社麦茶500ml ",140,2,280),
Kounyu(3,333,"C社うどん2食入り",180,2,360),
Kounyu(0,0,"",0,0,0) # 行追加用にkounyu[6]をもっておく
]
# 対象リストの初期値設定
taisyo = ["", # taisyo[0]は空データ
Taisyo(222, 0),
Taisyo(223, 0),
Taisyo(224, 0)
]
# 特売の初期値設定
tokubai = Tokubai(229,"B社お茶3本100円引",-100,0)
# 本体プログラム(問題文に記載されているものと同じ)
def register_program():
global testmode
# 検索部
K = Kounyu.ptr_kiten
T = 1
while (K > 0) and (T <= Taisyo.taisyo_gyousu):
if kounyu[K].hinban == taisyo[T].hinban:
taisyo[T].suuryo = kounyu[K].suuryo
K = kounyu[K].ptr # a
T += 1 # b
elif kounyu[K].hinban < taisyo[T].hinban:
K = kounyu[K].ptr # a
else:
T += 1 # b
# 計算部
W = 0
for T in range(1, Taisyo.taisyo_gyousu+1):
W += taisyo[T].suuryo
tokubai.suuryo = W // Taisyo.shitei_suuryo
# 更新部
Kp = 0
K = Kounyu.ptr_kiten
while (K > 0) and (kounyu[K].hinban < tokubai.hinban):
Kp = K
K = kounyu[K].ptr
# 破線囲み部（上行：設問1用、下行：設問2用）
if (testmode == 1 and tokubai.suuryo > 0) or \
(testmode == 2 and (K == 0 or kounyu[K].hinban > tokubai.hinban)):
Kounyu.kounyu_gyousu += 1
if Kp > 0:
kounyu[Kp].ptr = Kounyu.kounyu_gyousu # c
else:
Kounyu.ptr_kiten = Kounyu.kounyu_gyousu # c
kounyu[Kounyu.kounyu_gyousu].ptr = K # d
kounyu[Kounyu.kounyu_gyousu].hinban = tokubai.hinban
kounyu[Kounyu.kounyu_gyousu].hinmei = tokubai.hinmei
kounyu[Kounyu.kounyu_gyousu].tanka = tokubai.tanka
kounyu[Kounyu.kounyu_gyousu].suuryo = tokubai.suuryo
kounyu[Kounyu.kounyu_gyousu].kingaku = tokubai.tanka * tokubai.suuryo
if testmode == 2: # 設問2用
if (tokubai.suuryo > 0) and (K > 0 and kounyu[K].hinban == tokubai.hinban):
kounyu[K].suuryo = tokubai.suuryo
kounyu[K].kingaku = tokubai.tanka * tokubai.suuryo
if (tokubai.suuryo == 0) and (K > 0 and kounyu[K].hinban == tokubai.hinban):
if Kp > 0:
kounyu[Kp].ptr = kounyu[K].ptr # g
else:
Kounyu.ptr_kiten = kounyu[K].ptr # g
# 結果表示用関数
def result_show():
print(f"ptr起点={Kounyu.ptr_kiten}")
print(f"購入行数={Kounyu.kounyu_gyousu}")
print("ptr\t品番\t品名 \t単価\t数量\t金額")
for num in range(1,Kounyu.kounyu_gyousu+1):
print(f"{kounyu[num].ptr}\t{kounyu[num].hinban}\t{kounyu[num].hinmei}\t \
{kounyu[num].tanka}\t{kounyu[num].suuryo}\t{kounyu[num].kingaku}")
def test01():
"""
設問1対応
"""
global testmode
testmode = 1
print("=========更新前=========")
result_show()
register_program()
print("=========更新後=========")
result_show()
def test02():
"""
設問2対応(1)
購入に品番223を追加して、特売のレコードの更新処理を実施
"""
global testmode
testmode = 2
for T in range(1, Taisyo.taisyo_gyousu+1): # 対象[*].数量を初期化する
taisyo[T].suuryo = 0
Kounyu.kounyu_gyousu += 1
kounyu.append(Kounyu(4,223,"B社ウーロン茶500ml",140,2,280)) # 品番223を追加
kounyu[1].ptr = Kounyu.kounyu_gyousu # 品番222のptrを品番223につなぐ
print("=========更新前=========")
result_show()
register_program()
print("=========更新後=========")
result_show()
def test03():
"""
設問2対応(2)
購入の品番221,222,223を削除して、特売のレコードの削除処理を実施
品番221,222,223の削除処理と特売のレコードの削除処理は、
該当する特売のレコードを格納していた配列の要素はそのまま残し，
ポインタの付替えによってレコードを無効にする。
"""
global testmode
testmode = 2
for T in range(1, Taisyo.taisyo_gyousu+1): # 対象[*].数量を初期化する
taisyo[T].suuryo = 0
kounyu[2].ptr = 6 # 品番111のptrを品番229につないで、品番221,222,223を削除
print("=========更新前=========")
result_show()
register_program()
print("=========更新後=========")
result_show()
print("==================TEST01==================")
test01()
print("==================TEST02==================")
test02()
print("==================TEST03==================")
test03()
実行結果
==================TEST01==================
=========更新前=========
ptr起点=2
購入行数=5
ptr 品番 品名 単価 数量 金額
4 222 B社緑茶500ml 140 5 700
1 111 A社牛乳1000ml 200 2 400
0 335 C社めんつゆ300g 150 1 150
5 224 B社麦茶500ml 140 2 280
3 333 C社うどん2食入り 180 2 360
=========更新後=========
ptr起点=2
購入行数=6
ptr 品番 品名 単価 数量 金額
4 222 B社緑茶500ml 140 5 700
1 111 A社牛乳1000ml 200 2 400
0 335 C社めんつゆ300g 150 1 150
6 224 B社麦茶500ml 140 2 280
3 333 C社うどん2食入り 180 2 360
5 229 B社お茶3本100円引 -100 2 -200
==================TEST02==================
=========更新前=========
ptr起点=2
購入行数=7
ptr 品番 品名 単価 数量 金額
7 222 B社緑茶500ml 140 5 700
1 111 A社牛乳1000ml 200 2 400
0 335 C社めんつゆ300g 150 1 150
6 224 B社麦茶500ml 140 2 280
3 333 C社うどん2食入り 180 2 360
5 229 B社お茶3本100円引 -100 2 -200
4 223 B社ウーロン茶500ml 140 2 280
=========更新後=========
ptr起点=2
購入行数=7
ptr 品番 品名 単価 数量 金額
7 222 B社緑茶500ml 140 5 700
1 111 A社牛乳1000ml 200 2 400
0 335 C社めんつゆ300g 150 1 150
6 224 B社麦茶500ml 140 2 280
3 333 C社うどん2食入り 180 2 360
5 229 B社お茶3本100円引 -100 3 -300
4 223 B社ウーロン茶500ml 140 2 280
==================TEST03==================
=========更新前=========
ptr起点=2
購入行数=7
ptr 品番 品名 単価 数量 金額
7 222 B社緑茶500ml 140 5 700
6 111 A社牛乳1000ml 200 2 400
0 335 C社めんつゆ300g 150 1 150
6 224 B社麦茶500ml 140 2 280
3 333 C社うどん2食入り 180 2 360
5 229 B社お茶3本100円引 -100 3 -300
4 223 B社ウーロン茶500ml 140 2 280
=========更新後=========
ptr起点=2
購入行数=7
ptr 品番 品名 単価 数量 金額
7 222 B社緑茶500ml 140 5 700
5 111 A社牛乳1000ml 200 2 400
0 335 C社めんつゆ300g 150 1 150
6 224 B社麦茶500ml 140 2 280
3 333 C社うどん2食入り 180 2 360
5 229 B社お茶3本100円引 -100 3 -300
4 223 B社ウーロン茶500ml 140 2 280
- TEST01は、更新後に特売のレコード(B社お茶3本100円引)が追加されています。
- TEST02は、更新後に特売のレコード(B社お茶3本100円引)の数量が3に更新されています。
- TEST03は、更新後に特売のレコード(B社お茶3本100円引)が、ポインタ(ptr)の付け替えによって削除されています。
一応、思い通りに動いているようです。
疑問点等
- 上にも書いたとおり、今回初めてクラスを作ったのでよくわからない箇所があります。
- クラスを構造体の代替として使用しているんですが、空のメモリを確保するために、以下の通りダミーのインスタンス
Kounyu(0,0,"",0,0,0)をあらかじめ割り当てています。
# 購入リストの初期値設定
kounyu = ["", # kounyu[0]は空データ
Kounyu(4,222,"B社緑茶500ml ",140,5,700),
Kounyu(1,111,"A社牛乳1000ml ",200,2,400),
Kounyu(0,335,"C社めんつゆ300g ",150,1,150),
Kounyu(5,224,"B社麦茶500ml ",140,2,280),
Kounyu(3,333,"C社うどん2食入り",180,2,360),
Kounyu(0,0,"",0,0,0) # 行追加用にkounyu[6]をもっておく
]
なんかダサいんですが、良い方法はないのでしょうか。
-
test02とtest03で、以下の通り対象[*].数量の初期化をしています。
for T in range(1, Taisyo.taisyo_gyousu+1): # 対象[*].数量を初期化する
taisyo[T].suuryo = 0
これも冴えないんですが、良い方法はないのでしょうか。
- 他にもここはおかしい、こうしたほうが良いという箇所があれば、ご指摘いただけますと幸いです。
- サンプル問題、過去問のリンクに基本情報技術者試験ドットコムを利用しました。これまでの勉強でもお世話になっています。感謝申し上げます。