基本情報技術者アルゴリズムの問題をPythonでコーディングしてみた【令和元年秋】
【26日目】
Pythonの基本文法に慣れてきた今日この頃。
そろそろ参考書外で何か作ってみようと思い、
基本情報技術者試験の試験勉強も兼ねて
最も苦手とするアルゴリズムの過去問をPythonで書いてみました！
Pythonの文法の練習にもなるし
問題中に入出力の例があって、確かめやすいのも良き！
プログラムの構成も真似すればいいので、
初心者の私にはうってつけだね。
ということで、最新の問題、令和元年秋期
過去問PDF「出典：令和元年度 秋期 基本情報技術者試験 午後 問8」
プログラム1&2
import logging logging.basicConfig(level=logging.DEBUG, format='%(asctime)s - %(levelname)s - %(message)s') Mask = dict() #文字A~Zに対応するビットマスク def index(alphabet): #アルファベット→数字変換（問題文の関数Index） alpha2num = lambda c: ord(c) - ord('A') + 1 return alpha2num(alphabet) def generate_bit_mask(Pat): PatLen = len(Pat) for i in range(1,27): #range関数では,この場合27は含まない global Mask Mask[i] = 0B0 #初期化.二進数ビット表記のため、0Bをつける for i in range(0,PatLen): #pythonの要素番号は0から Mask[index(Pat[i])] = (0B1 << i)|Mask[index(Pat[i])] #"1"Bを(i-1)ビットだけ論理左シフトした値とMask[index(Pat[i])]の論理和 for i in range(1,4): print("Mask[{}]".format(i),bin(Mask[i])) #設問1-a Mask[2]確認用 return PatLen def bitap_Match(Text,Pat): TextLen = len(Text) PatLen = generate_bit_mask(Pat) Status = 0B0 Goal = 0B1 << PatLen-1 #"1"BをPatLen-1だけ論理左シフトした値 logging.debug('設問2確認用') for i in range(0,TextLen): Status = (Status << 1)|0B1 #←α Status = Status & Mask[index(Text[i])] #←β logging.debug('i = {}, Mask[index(Text[i])] = {}, Status = {}' .format(i+1, bin(Mask[index(Text[i])]),bin(Status))) #設問2用。i+1して対応付けしやすくした。 if Status & Goal != 0B0: return ( i - PatLen + 1)+1 #Text[]の要素番号に合わせるため+1する。(Pythonは0から) return (-1) Text = "AACBBAACABABAB" Pat = "ACABAB" print(bitap_Match(Text,Pat))
出力結果
Mask[1] 0b10101 Mask[2] 0b101000 Mask[3] 0b10 2020-04-17 11:47:01,858 - DEBUG - 設問2確認用 2020-04-17 11:47:01,858 - DEBUG - i = 1, Mask[index(Text[i])] = 0b10101, Status = 0b1 2020-04-17 11:47:01,874 - DEBUG - i = 2, Mask[index(Text[i])] = 0b10101, Status = 0b1 2020-04-17 11:47:01,874 - DEBUG - i = 3, Mask[index(Text[i])] = 0b10, Status = 0b10 2020-04-17 11:47:01,874 - DEBUG - i = 4, Mask[index(Text[i])] = 0b101000, Status = 0b0 2020-04-17 11:47:01,890 - DEBUG - i = 5, Mask[index(Text[i])] = 0b101000, Status = 0b0 2020-04-17 11:47:01,890 - DEBUG - i = 6, Mask[index(Text[i])] = 0b10101, Status = 0b1 2020-04-17 11:47:01,890 - DEBUG - i = 7, Mask[index(Text[i])] = 0b10101, Status = 0b1 2020-04-17 11:47:01,905 - DEBUG - i = 8, Mask[index(Text[i])] = 0b10, Status = 0b10 2020-04-17 11:47:01,905 - DEBUG - i = 9, Mask[index(Text[i])] = 0b10101, Status = 0b101 2020-04-17 11:47:01,905 - DEBUG - i = 10, Mask[index(Text[i])] = 0b101000, Status = 0b1000 2020-04-17 11:47:01,905 - DEBUG - i = 11, Mask[index(Text[i])] = 0b10101, Status = 0b10001 2020-04-17 11:47:01,921 - DEBUG - i = 12, Mask[index(Text[i])] = 0b101000, Status = 0b100000 7
過去問のプログラムと異なる点はコメントとして記載しています。
Python化による主な変更点は下記
- 二進数ビットの表記は、数字の先頭に0b(0Bでも可)を付ける。
- 要素番号が0から始まるため、ループ回数の数字も0始まり。
また、設問1、2の回答が確認できるように、PrintとloggingによるDEBUGを追加しています。
ちなみにTextとPatには過去問の値が入っていますが、変更させてみてもOKです。
プログラム3
Mask = dict() #文字A~Zに対応するビットマスク def index(alphabet): #アルファベット→数字変換（問題文の関数Index） alpha2num = lambda c: ord(c) - ord('A') + 1 return alpha2num(alphabet) def generate_bitmask_regex(Pat): OriginalPatLen = len(Pat) PatLen = 0 Mode = 0 for i in range(1,27): global Mask Mask[i] = 0B0 for i in range(0,OriginalPatLen): if Pat[i] == "[": Mode = 1 PatLen = PatLen + 1 elif Pat[i] == "]": Mode = 0 else: if Mode == 0: PatLen = PatLen + 1 Mask[index(Pat[i])] = (0B1 << (PatLen - 1))|Mask[index(Pat[i])] return(PatLen) print(generate_bitmask_regex("AC[BA]A[ABC]A")) #hの答え print(bin(Mask[1])) #gの答え print(generate_bitmask_regex("AC[B[AB]AC]A")) print(bin(Mask[1])) #iの答え
出力結果
6 0b111101 7 0b1011001
設問3の確認用でprint出力しています。
以上です。
結構時間かかったよ！
もっとこう書けばいいのに！みたいなコメント大歓迎です！！
それではまた^^
