LoginSignup
2
3

More than 1 year has passed since last update.

データ構造とアルゴリズムAdvent Calendar 2021Day 25
@sylphy(シルフィー)

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

Last updated at Posted at 2021-12-25

はじめに

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

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

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

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

実装

  • 平成24年秋期のアルゴリズム問題（駅間の最短距離を求めるプログラム）を対象とします。
    • ご興味があるようなら、ぜひ問題にチャレンジしてみてください（所要時間30分）。
  • 問題では、駅番号等の配列の添え字が１から始まっていますが、今回の実装では0から始まるようにしています。
  • また、問題図3,4では、2駅間の距離が一部しか示されていないので、今回自分で適当に定めました。
  • 結果として、問題図1、図3、図4は以下のとおり変更されます。

図1
図3 鉄道の路線例（2）改、　図4 鉄道の路線例（2）の基幹駅と区間名 改

  • 初期プログラムCalcDistについて、問題中で計算量を削減する改良をするので、変数testmodeを定義し、1の場合は初期プログラム、2の場合は計算量削減プログラムが流れるようにしています。
  • CalcDistは、計算量を調べるために、計算回数を出力する機能を追加しています。
  • 問題中のPrint(N，Dist)は定義せず、CalcDist中に同じ機能を追加しています。
  • メモリ使用量削減プログラムは、CalcStoSという名前で定義しています。CalcStoSは、Dist、StaInfo、i,j(最短距離を求める2駅の駅番号）を入力とし、計算された最短距離を返します。
  • 表１の駅情報表は、辞書型のStaInfoで定義し、keyをSec、KL、ToKL、KH、ToKHとし、valueをリストにしました。
    • たとえば、問題のToKL[i]は、実装したプログラムではStaInfo['ToKL'][i]であらわされます。
  • test01、test02、test03を定義しました。
  • test01：初期プログラムによる計算
  • test02：計算量削減プログラムによる計算
  • test03：メモリ削減プログラムによる計算
h24f.py
# グローバル変数の設定
testmode = 1        # テストモード　1:初期プログラム、2:計算量削減プログラム

# 初期プログラム & 計算量削減プログラム
def CalcDist(N, Dist):
    global testmode         # グローバル変数の宣言 
    calc_order = 0          # 計算回数算出用
    print("初期値")         # タイトル出力
    for num in range(N):    # 設問のPrint(N,Dist)は関数にせずそのまま記載
        print(Dist[num])
    for Via in range(0, N):
        if testmode == 1:           # 初期プログラム 設問の破線部
            for From in range(0, N):
                for To in range(0, N):
                    if Dist[From][To] > Dist[From][Via] + Dist[Via][To]:
                        Dist[From][To] = Dist[From][Via] + Dist[Via][To]
                    calc_order += 1
        if testmode == 2:           # 計算量削減プログラム 設問の破線部置き換え後
            for From in range(0, N-1):
                for To in range(From+1, N):     # e
                    if Dist[From][To] > Dist[From][Via] + Dist[Via][To]:
                        Dist[From][To] = Dist[From][Via] + Dist[Via][To]
                        Dist[To][From] = Dist[From][Via] + Dist[Via][To]
                    calc_order += 1
        print(f"Via={Via}")     # タイトル出力
        for num in range(N):    # 設問のPrint(N,Dist)は関数にせずそのまま記載
            print(Dist[num])
    print(f"計算回数={calc_order}") # 計算回数出力

def CalcStoS(Dist,StaInfo,i,j):
    """
    メモリ使用量削減プログラム
    ・Dist(入力)：基幹駅間の最短距離表
    ・StaInfo(入力)：駅情報表 辞書型でvalueがリスト
    ・i,j(入力)：最短距離を求める2駅の駅番号
    ・Res(出力)：計算された最短距離
    """
    D1 = StaInfo['ToKL'][i] + Dist[StaInfo['KL'][i]][StaInfo['KL'][j]] + StaInfo['ToKL'][j]
    D2 = StaInfo['ToKL'][i] + Dist[StaInfo['KL'][i]][StaInfo['KH'][j]] + StaInfo['ToKH'][j]
    D3 = StaInfo['ToKH'][i] + Dist[StaInfo['KH'][i]][StaInfo['KL'][j]] + StaInfo['ToKL'][j]
    D4 = StaInfo['ToKH'][i] + Dist[StaInfo['KH'][i]][StaInfo['KH'][j]] + StaInfo['ToKH'][j]
    if StaInfo['Sec'][i] == StaInfo['Sec'][j]:  # f
        Res = min(abs(StaInfo['ToKL'][i]-StaInfo['ToKL'][j]),D1,D2,D3,D4)
    else:
        Res = min(D1,D2,D3,D4)
    return Res

def test01():
    """
    初期プログラム対応
    """
    global testmode
    testmode = 1            # テストモード　1:初期プログラム
    N = 5
    Dist = [                # Dist行列初期値設定
        [0,18,999,14,999],
        [18,0,17,999,16],
        [999,17,0,13,999],
        [14,999,13,0,12],
        [999,16,999,12,0]
    ]
    CalcDist(N, Dist)

def test02():
    """
    計算量削減プログラム対応
    """
    global testmode
    testmode = 2            # テストモード2:計算量削減プログラム
    N = 5
    Dist = [                # Dist行列初期値設定
        [0,18,999,14,999],
        [18,0,17,999,16],
        [999,17,0,13,999],
        [14,999,13,0,12],
        [999,16,999,12,0]
    ]
    CalcDist(N, Dist)

def test03():
    """
    メモリ削減プログラム対応
    まず、CalcDistで基幹駅間の最短距離表Distを計算
    次に、駅情報表から２駅間の最短距離Resを計算
    """
    global testmode
    testmode = 2            # テストモード2:計算量削減プログラム
    N = 4
    Dist = [                # Dist行列初期値設定(メモリ使用量削減時)
        [0,20,45,999],
        [20,0,20,25],
        [45,20,0,999],
        [999,25,999,0]
    ]
    StaInfo ={              # 駅情報表StaInfo 辞書型でvalueをリストにした。
        'Sec':["0","1","2","3","B","B","C","C","C","E"],
        'KL':[0,1,2,3,0,0,0,0,0,1],
        'ToKL':[0,0,0,0,15,25,15,25,35,15],
        'KH':[0,1,2,3,2,2,2,2,2,3],
        'ToKH':[0,0,0,0,30,20,40,30,20,10]
    }
    CalcDist(N, Dist)   # 基幹駅間の最短距離表Distを計算
    From = 9            # 出発駅(0～9)
    To = 8              # 到着駅(0～9)
    Res = CalcStoS(Dist,StaInfo,From,To)        # From-To間の最短距離計算
    print(f"From={From} To={To} Dist={Res}")    # 距離出力 

print("==================TEST01==================")
test01()
print("==================TEST02==================")
test02()
print("==================TEST03==================")
test03()

実行結果

==================TEST01==================
初期値
[0, 18, 999, 14, 999]
[18, 0, 17, 999, 16] 
[999, 17, 0, 13, 999]
[14, 999, 13, 0, 12] 
[999, 16, 999, 12, 0]
Via=0
[0, 18, 999, 14, 999]
[18, 0, 17, 32, 16]  
[999, 17, 0, 13, 999]
[14, 32, 13, 0, 12]  
[999, 16, 999, 12, 0]
Via=1
[0, 18, 35, 14, 34]  
[18, 0, 17, 32, 16]  
[35, 17, 0, 13, 33]  
[14, 32, 13, 0, 12]  
[34, 16, 33, 12, 0]  
Via=2
[0, 18, 35, 14, 34]  
[18, 0, 17, 30, 16]  
[35, 17, 0, 13, 33]  
[14, 30, 13, 0, 12]  
[34, 16, 33, 12, 0]  
Via=3
[0, 18, 27, 14, 26]  
[18, 0, 17, 30, 16]  
[27, 17, 0, 13, 25]  
[14, 30, 13, 0, 12]  
[26, 16, 25, 12, 0]  
Via=4
[0, 18, 27, 14, 26]
[18, 0, 17, 28, 16]
[27, 17, 0, 13, 25]
[14, 28, 13, 0, 12]
[26, 16, 25, 12, 0]
計算回数=125
==================TEST02==================
初期値
[0, 18, 999, 14, 999]
[18, 0, 17, 999, 16]
[999, 17, 0, 13, 999]
[14, 999, 13, 0, 12]
[999, 16, 999, 12, 0]
Via=0
[0, 18, 999, 14, 999]
[18, 0, 17, 32, 16]
[999, 17, 0, 13, 999]
[14, 32, 13, 0, 12]
[999, 16, 999, 12, 0]
Via=1
[0, 18, 35, 14, 34]
[18, 0, 17, 32, 16]
[35, 17, 0, 13, 33]
[14, 32, 13, 0, 12]
[34, 16, 33, 12, 0]
Via=2
[0, 18, 35, 14, 34]
[18, 0, 17, 30, 16]
[35, 17, 0, 13, 33]
[14, 30, 13, 0, 12]
[34, 16, 33, 12, 0]
Via=3
[0, 18, 27, 14, 26]
[18, 0, 17, 30, 16]
[27, 17, 0, 13, 25]
[14, 30, 13, 0, 12]
[26, 16, 25, 12, 0]
Via=4
[0, 18, 27, 14, 26]
[18, 0, 17, 28, 16]
[27, 17, 0, 13, 25]
[14, 28, 13, 0, 12]
[26, 16, 25, 12, 0]
計算回数=50
==================TEST03==================
初期値
[0, 20, 45, 999]
[20, 0, 20, 25]
[45, 20, 0, 999]
[999, 25, 999, 0]
Via=0
[0, 20, 45, 999]
[20, 0, 20, 25]
[45, 20, 0, 999]
[999, 25, 999, 0]
Via=1
[0, 20, 40, 45]
[20, 0, 20, 25]
[40, 20, 0, 45]
[45, 25, 45, 0]
Via=2
[0, 20, 40, 45]
[20, 0, 20, 25]
[40, 20, 0, 45]
[45, 25, 45, 0]
Via=3
[0, 20, 40, 45]
[20, 0, 20, 25]
[40, 20, 0, 45]
[45, 25, 45, 0]
計算回数=24
From=9 To=8 Dist=55
  • TEST01では、Via=2で設問aが35、設問bが33であることがわかります。また、計算回数が125回であり、設問cの通り計算量が5^3オーダーであることがわかります。
  • TEST02では、計算回数が50回であり、TEST01の約半分に減っていることがわかります。
  • TEST03は、例として駅8,9の最短距離を求めており、55と正しい値が算出されています。

補足

  • ここはおかしい、こうしたほうが良いという箇所があれば、ご指摘いただけますと幸いです。
  • サンプル問題、過去問のリンクに基本情報技術者試験ドットコムを利用しました。これまでの勉強でもお世話になっています。感謝申し上げます。
  • データ構造とアルゴリズム Advent Calendar 2021 の25日が開いていたので投稿しました。学術的なプログラムではありませんが、このような問題が、IT技術者の基本装備である基本情報技術者試験で出題されていることに、興味を持ってもらえればと思います。
2
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
3