アルゴリズムをPythonで勉強しよう〜実践編〜

「情報処理試験のアルゴリズムって具体的にどう勉強したらいいの？」
という疑問に答えます。

アルゴリズムは過去問や参考書だけ読んで理解するのは非常に難しいです。

言語はなんでもいいのでまずはプログラムを実際に作ってみましょう。
本記事ではPythonを例にしてアルゴリズムの問題を解く例を紹介します。

具体的には以下の通りです。

・アルゴリズムを勉強のために最低限必要なPythonの知識
・アルゴリズムの問題をPythonで実践する手順

あわせて読みたい
Pythonコードからフローチャートを描く方法

Table of Contents

アルゴリズムを勉強のために最低限必要なPythonの知識

Pythonでアルゴリズムを勉強する場合以下について最低でも理解しておく必要があります。

・条件分岐
・繰り返し文
・変数・関数の使い方

いずれもそれほど難しいものではありません。参考書や公式ドキュメントを読みつつプログラムをいくつか作ればすぐに理解できる内容です。

問題によっては上記以外の知識も必要になるため、都度ググるようにしましょう。
◆条件分岐
条件分岐は特定の条件に当てはまった場合の処理です。
とりあえずif・elseif・elseの使い方を覚えればOK。

◆繰り返し文
指定した回数同じ処理を繰り返す構文です。
for文の使い方について理解しておきましょう。

◆変数・関数の使い方
代入・定義・呼び出し方・リターン値などについて理解しておけばOKです。

アルゴリズムの問題をPythonで実践する手順

基本情報技術者の過去問の実践手順について、以下の順番で説明します。

・使用するアルゴリズム
・プログラムを実際に動かしてみよう
・実際に問題を解くときは？

使用するアルゴリズム

整数型関数：GeneralBitMask(文字型: Pat[], 16ビット論理型: Mask[])
整数型：i,patLen
・patLen ← Pat[]の文字数
▪i:1, i <=26, 1
| ・Mask[i] ← 【b】
▪
▪i:1, i <=patLen, 1
| ・Mask[Index(Pat[i])] ← 【c】とMask[Index(Pat[i])]の論理和
▪
return (patLen)

上記は2019年10月基本情報技術者の問8の「GeneralBitMask」というアルゴリズムです。
「問題の詳細はこちら」
上記アルゴリズムをPythonにおこしていきます。

Pythonでのアルゴリズム記述例

記述例は以下の通り。

def general_bit_mask(pat, mask):
    # patの長さを習得
    pat_len = len(pat)
    # 設問のために調整
    pat = '0' + pat
    # 初期化処理
    for i in range(1, 27):
        mask[i] = answer_b
    for i in range(1, pat_len + 1):
        mask[index(pat[i])] = answer_c | mask[index(pat[i])]
    return pat_len
def index(alphabet):
    alphabet_list = {
        'A': 1, 'B': 2, 'C': 3, 'D': 4, 'E': 5, 'F': 6, 'G': 7, 'H': 8,
        'I': 9, 'J': 10, 'K': 11, 'L': 12, 'M': 13, 'N': 14, 'O': 15,
        'P': 16, 'Q': 17, 'R': 18, 'S': 19, 'T': 20, 'U': 21, 'V': 22,
        'W': 23, 'X': 24, 'Y': 25, 'Z': 26,
    }
    return alphabet_list[alphabet]

記述はできるだけ問題文に合わせる形で作っています。
・問題のプログラムとは別にindex関数を作成
・空欄の部分はとりあえず「answer_b」,「answer_c」で記述
・文字列のインデックスは、Pythonの場合0、問題文の場合1で始まるため、ソースコード中には以下の処理を追加しています。

# 設問のために調整
pat = ‘0’ + pat

patの’0ABCD’のようになります。
‘0’の部分は参照されません。

プログラムを実際に動かしてみよう

早速プログラムを動かしてみましょう。
正解の選択肢だけでなく不正解の選択肢も動かしてみてください。
とはいえ空欄が2つあるのでb,cを同時に試そうと思うとかなりパターンが多くなります。

予め片方に正解を入れて1問ずつ実行しましょう。

「正解をいれてしまったら解く力がつかないんじゃないか」
と思うかもしれませんが、最初は問題を解くことよりも「選択肢の違いによって結果がどう変わるのか」という点を理解することが大事です。

問題を解く力はその後つけても遅くはありません。
まずはCを埋めてのBの選択肢をそれぞれ実行します。

選択肢は以下の通り。
ア：”0″B
イ：”1″B
ウ：”1″BをPatLenビットだけ論理左シフトした値
エ：”1″BをPatLen-1ビットだけ論理左シフトした値
オ:”1111111111111111″B
実行結果は以下の通り。

ア
0b10101,0b101000,0b10,0b0,0b0・・・・・
イ
0b10101,0b101001,0b11,0b1,0b1・・・・・
ウ
0b110101,0b101000,0b100010,0b100000・・・・
エ
0b1010101,0b1101000,0b1000010,0b1000000・・・・
オ
0b1111111111111111,0b1111111111111111,0b1111111111111111,0b1111111111111111・・・・

問題文中に「ACABAB」で実行した場合のA、C、Dの値が出ているのでこれと比較しましょう。
アが正しい値ですね。

イの場合、Aは合っていますがB以降が違います。
ウ〜オはAからして違います。
よって「ア」が正解です。

次にBを埋めて実行します。
選択肢は以下の通り。
ア：”1″Bを(i-1)ビットだけ論理左シフトした値
イ：”1″Bをiビットだけ論理左シフトした値
ウ：”1″BをPatLen-1ビットだけ論理左シフトした値
エ：”1″BをPatLenビットだけ論理左シフトした値
オ:”1″B
実行例は以下の通りです。

ア
0b10101,0b101000,0b10,0b0・・・・
イ
0b101010,0b1010000,0b100,0b0・・・・
ウ
0b100000,0b100000,0b100000,0b0・・・・
エ
0b1000000,0b1000000,0b1000000,0b0・・・・
オ
0b1,0b1,0b1,0b0・・・・

こちらも問題文と比較すれば一目瞭然で「ア」が正しい値です。