基本情報技術者試験　アルゴリズム問題をPythonで実装してみた　平成25年春期

# はじめに
基本情報技術者試験にアルゴリズム問題と呼ばれるものがあります。
これは、情報処理推進機構（IPA）が定めた疑似言語でアルゴリズムのプログラムが示され、受験者はプログラムの穴埋めや変数の推移などを解答するものです。
試験中はプログラムを脳内でシミュレートして解答しなければならず、なかなかしんどいです。
ほとんどの人が、基本情報技術者試験で一番苦労するところです。

また、基本情報技術者試験は令和2年度秋期からソフトウェア開発として、新たにPythonが選択できるようになりました。
一方で令和2年度秋期からCBT試験（予約した日に試験会場に行ってモニターに示された問題に解答する）が導入され、それとともに試験問題が公開されなくなりました。
Pythonについては、[サンプル問題](https://www.fe-siken.com/kakomon/sample/python_sample.html)しか公開されておらず、過去問を用いた試験対策にはハンデがあります。
でも、試験合格後に「ソフトウェア開発で何を選択したの？」と聞かれて、「**最近はやりのPythonで合格しました**」と言えたらかっこいいじゃないですか？

そこで私は考えました。
**疑似言語で書かれた過去のアルゴリズム問題をPythonで実装してみれば、アルゴリズムを自分でシミュレートでき、Pythonの勉強にもなって、一石二鳥ではないか。**と

以下は、その実践例です。

# 実装
- [平成25年春期のアルゴリズム問題（食料品店の値引き処理）](https://www.fe-siken.com/kakomon/25_haru/pm08.html)を対象とします。
    - **ご興味があるようなら、ぜひ問題にチャレンジしてみてください（所要時間30分）。**
- この問題では、構造体型の変数が用いられています。Pythonには構造体がないので、クラスを使用しています。
    - 実はクラスを自分で作ったのはこれが初めてです。クラスの理解には、Udemyの**[現役シリコンバレーエンジニアが教えるPython入門](https://www.udemy.com/course/python-beginner/)**のセクション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
```
これも冴えないんですが、良い方法はないのでしょうか。

- 他にもここはおかしい、こうしたほうが良いという箇所があれば、ご指摘いただけますと幸いです。
- サンプル問題、過去問のリンクに[基本情報技術者試験ドットコム](https://www.fe-siken.com/)を利用しました。これまでの勉強でもお世話になっています。感謝申し上げます。