理系母の趣味はプログラミング

理系院卒、メーカー技術職の二児の母が、PythonやVBAで色々と作ってアップしていくブログです。

基本情報技術者アルゴリズムの問題をPythonでコーディングしてみた【平成31年春】

FEアルゴリズム実装

前回からアルゴリズム過去問のコーディングをやっておりまして
私のレベルでコーディングが一日でできるわけがなく
以前のように毎日記事をアップすることができなくなりました。
これからはのんびりペースです。

さて、今回はハフマン符号化を用いた文字列圧縮のプログラムです。

過去問PDF「出典：平成31年度 春期 基本情報技術者試験 午後 問8」


プログラム1&2

import collections
#符号化する文字列を設定
Text = "AAAABBCDCDDACCAAAAA" #過去問の文字列
#Text = "ABBBBBBBCCCDD"　#設問1確認用

#出現回数をもとめる①
count_dic=collections.Counter(Text)
character = list(count_dic.keys())
freq =list(count_dic.values())
character_num = len(freq) #

#初期化②
parent=[-1]*len(freq)
left = [-1]*len(freq)
right = [-1]*len(freq)
node = list()
size = len(freq)
nsize = 0

#副プログラム：Huffman
def huffman():
    global size,parent,left,right,freq
    
    sort_node()
    while nsize >= 2:
        i = node[0] #最も小さい値をもつ要素組の要素番号
        j = node[1] #二番目に小さい値をもつ要素組の要素番号
        left.append(i)
        right.append(j)
        freq.append(freq[i] + freq[j]) #子の値の合計
        parent.append(-1)
        parent[i] = size #子に親の節の要素番号を格納
        parent[j] = size #子に親の節の要素番号を格納
        size = size + 1
        sort_node()

#副プログラム：SortNode
def sort_node():
    
    global nsize,node
    #初期化
    nsize = 0 
    node = list()
    
    for i in range(0,size):
        if parent[i] < 0 : #親がまだいない場合
            node.append(i)
            nsize = nsize + 1
    sort()

#副プログラムSort③
def sort():

    global node
    freq_node = []
    #nodeに対応する要素番号の要素だけを抽出し、同時ソートのための新リスト作成
    for i in node:
        freq_node.append((freq[i],i))
    freq_node.sort()
    #分解して別々のリストに戻す
    sfreq,node = zip(*freq_node)

#副プログラムencode
def encode(k,parent,left):
    global b  
    if parent[k] >= 0:
        encode(parent[k],parent,left)
        if left[parent[k]] == k:
            b = b + "0" #④
        else:
            b = b + "1" #④
#実行
            
huffman()

#ハフマン符号化結果を表示⑤
bit_list=[]
for k in range(0,character_num):
    b = ""
    encode(k,parent,left)
    bit_list.append(b)

bit_dic = {key:val for key,val in zip(character,bit_list)}
print(bit_dic)

出力結果

{'A': '1', 'B': '010', 'C': '00', 'D': '011'}

過去問との主な相違点は下記
①文字の出現回数を求めるコードを追加
②各リストを初期化するコードを追加
③副プログラムSortを追加
④副プログラムencodeのprint出力部分を変数に格納する仕様に変更
⑤結果の表示形式を辞書式（文字：ハフマン符号）に変更

何気に副プログラムSortに苦労しました。
問題文では省略してあり、ヒントが乏しかったうえ、
プログラムの説明文の
”節を表す要素組の要素番号の配列nodeを受けとり、要素番号に対応する要素組が表す節の値が昇順になるように整列する。”
という説明の意味が分かりにくくて…。

にしてもこれ、最初に考えた人天才。

今回は以上です。
もっとこうすればいいのに、といったご意見ご指摘ありましたら教えてくださるとうれしいです！！

それではまた^^

基本情報技術者アルゴリズムの問題をPythonでコーディングしてみた【令和元年秋】

FEアルゴリズム実装

【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出力しています。

以上です。
結構時間かかったよ！

もっとこう書けばいいのに！みたいなコメント大歓迎です！！

それではまた^^

【25日目】オブジェクト指向プログラミング⑨isで同一オブジェクトを判定する

独学プログラマー

こんばんは、
今回は参考書の順番的に特殊メソッドをやろうと思ったのですが、
内容が腑に落ちなかったので、isをやります。
特殊メソッドのことは、おいおいってことで。

isキーワードは前後のオブジェクトが同一ならTrue,違う場合Falseを返します。
英語と同じです。
例えば
This Note is a pen.（このノートはペンです。）
と言われたら
嘘やん！(False)って言いたくなります。
これと同じです。

書きます。

class Mono:
    def __init__(self,n):
        self.name = n

note = Mono("note")
pen = Mono("pen")
penA = pen
print(note is pen)
print(pen is penA)

#出力結果
False
True

isキーワードは、変数がNoneかどうかを調べるときにも使えるそうです。

a = None
print(a is None)

b = "hogeee"
print(b is None)
#出力結果
True
False

何この作業感...！

今日は以上です。
特殊メソッド理解するのあきらめたら記事の最短記録更新！

そしてオブジェクト指向プログラミングも以上です。
参考書では学びのまとめとしてwarというカードゲームをプログラミングする課題が出てきますが、
まとめなので、記事としては割愛します。

さて、ここまでPythonの基礎文法を学んできました。
そろそろ、習得した知識を使って、何かコーディングしたい！ということで、
基本情報技術者試験のアルゴリズム過去問をPythonでコーディングしたいと思います。

独学プログラマー文法編終了。
次回、FE過去問コーディング編突入。

参考書はこちらです。
「独学プログラマー」

独学プログラマー Python言語の基本から仕事のやり方まで

独学プログラマー Python言語の基本から仕事のやり方まで

それではまた^^

【24日目】オブジェクト指向プログラミング⑧クラス変数を定義する

独学プログラマー

こんばんは、なぺです。

まだまだオブジェクト指向プログラミングです。
今回は、クラス変数です。

さて、今までインスタンス変数は扱ってきましたが、クラス変数とは、
その名の通りクラスオブジェクトに属する変数です。

クラスもオブジェクトなのですね。
定義の仕方もいたってシンプル、クラス定義の中に普通に定義すればいいのです。

家族の構成員をインスタンスオブジェクトとして生成し、
家族の名前を家族リストに格納するプログラムを作ります。
ここで、家族リストはどのインスタンスからもアクセスできるよう、クラス変数として定義します。

class Family:

    fam = [] #クラス変数としてFamリストを定義
    
    def __init__(self,n,m):
        self.name = n
        self.mother = m
        self.fam.append(self.name)
        #インスタンス生成の度に、nameをfamリストに追加

P1 = Family("umeko","takeko")
P2 = Family("takeko","matsuko")
P3 = Family("matsuko","kikuko")
P4 = Family("ichiro","kikuko")
P5 = Family("jiro","matsuko")

print(Family.fam)
#出力結果
['umeko', 'takeko', 'matsuko', 'ichiro', 'jiro']

できました！

オブジェクト指向にも慣れてきたかも^^
今回はここまで。
だんだん記事が短くなってきましたね！

まあ、そんな時期もある。

参考書はこちらです
「独学プログラマー」

独学プログラマー Python言語の基本から仕事のやり方まで

独学プログラマー Python言語の基本から仕事のやり方まで


コロナで引きこもりでもパソコンとネットがあれば快適生活^^

それではまた^^

【23日目】オブジェクト指向プログラミング⑦コンポジションな関係を作る

独学プログラマー

こんばんは、なぺです。

前回までで、オブジェクト指向プログラミングの4大要素を学びました。
今回は、もうひとつ重要なコンセプト、コンポジションについて学びます。

さて、
コンポジション？

本にはこう書いてあります。

コンポジション：別クラスのオブジェクトを変数として持たせること。「has-a関係」


ふむふむ
変数にオブジェクトを入れることができるのね！

ちょっとやってみます。
前回作った親子クラスのコードを使って、子のインスタンス変数に親を入れます。

class Parent:
    def __init__(self,n,o):
        self.name = n
        self.old = o

class Child:
    def __init__(self,n,p):
        self.name = n
        self.parent = p

takeko = Parent('takeko',50)
umeko = Child('hanako',takeko) #Childクラスの変数にParentクラスのオブジェクトを入れる
print(umeko.parent.name)
#出力結果
takeko

Childクラスのオブジェクト（umeko）の親としてParentクラスのオブジェクト（takeko）を入れました。
よしよし。

次は前回の継承とコンポジションの合わせ技！

class Parent:
    def __init__(self,n,o,p):
        self.name = n
        self.old = o
        self.parent = p

class Child(Parent):　#継承
    pass

takeko = Parent('takeko',50,'matsuko')
umeko = Child('hanako',15,takeko) #コンポジション
print(takeko.parent)
print(umeko.parent)
print(umeko.parent.name)
#出力結果
matsuko　#takekoのparentは文字列で入力したので、そのまま出力される。
<__main__.Parent object at 0x000001C80A322688> #umekoのparentはオブジェクトを渡したので、.parentだけだとメモリ上の場所が表示されてしまう。
takeko #parent.nameと指定したので、takekoオブジェクトのname変数が表示された。

できたっぽい。
継承もコンポジションも、コードを少なくできるのはいいですね。（多分）

今日は以上です！

まだまだ続くよオブジェクト指向！


参考書はこちらです
「独学プログラマー」

独学プログラマー Python言語の基本から仕事のやり方まで

独学プログラマー Python言語の基本から仕事のやり方まで

それではまた^^

【22日目】オブジェクト指向プログラミング⑥継承させる

独学プログラマー

こんばんは、なぺです。
今日はオブジェクト指向プログラミングの4大要素のうちの4つ目、継承です。

さて、継承とは
ja.wikipedia.org

主にクラスベースのオブジェクト指向言語で、既存クラスの機能、構造を共有する新たなクラス（派生クラス、派生型）を定義すること（subclassing、サブクラス化）ができる。またそのような派生クラスは「親クラス（スーパークラス）を継承した」という。具体的には変数定義（フィールド）や操作（メソッド）などが引き継がれる。

ふむふむ。
クラスを作るときにほかのクラスから変数やメソッドを引きつぐことができるのか。
親から髪質とか目の色とか肌の色を引きつぐのと同様ですね。
継承元のクラスを親クラス、継承先を子クラスというみたいです。

本のコードをもとに、子クラスに変数とメソッドを継承させてみます。

class Parent:
    def __init__(self,o):
        self.old = o

    def print_old(self):
        print('私は{}歳です'.format(self.old))

class Child(Parent):
    pass

hanako = Child(7)
hanako.print_old()
#実行結果
私は7歳です

Parentクラスの変数とメソッドを、Childクラスに継承しました。
Childクラスは継承するだけなので、passと書くことで何もしないことをPython先輩に伝えています。
Childクラスには何も定義していないのに、継承によってself.oldのインスタンス変数と、print_oldというメソッドを使うことができました。

ちなみに、メソッドは受け取るだけはなく、子のほうで上書きもできます。
子クラスが親クラスのメソッドを上書きすることを、メソッドオーバーライドといいます。
やってみます。

class Parent:
    def __init__(self,o):
        self.old = o

    def print_old(self):
        print('私は{}歳です'.format(self.old))

class Child(Parent):
    def print_old(self): #ここで上書き
        print('私の年齢は{}歳でーっす！Yeah!!'.format(self.old)) #文を少し変更

mama = Parent(40)
mama.print_old()
hanako = Child(7)
hanako.print_old()
#出力結果
私は40歳です
私の年齢は7歳でーっす！Yeah!!

できた！けどこれでいいのか？
結局コード書いてるから継承とか関係なくなりそうだけども。

今日はここまで！
最近寝不足気味でつらいです。

参考書はこちらです
「独学プログラマー」

独学プログラマー Python言語の基本から仕事のやり方まで

独学プログラマー Python言語の基本から仕事のやり方まで

それではまた^^

【21日目】オブジェクト指向プログラミング⑤ポリモーフィズム

独学プログラマー

こんばんは、なぺです。
今日はオブジェクト指向プログラミングの4大要素のうちの一つ、ポリモーフィズムについて学びます。
今日も概念の理解回なので、短くなりそうです。

さて

ポリモーフィズムってなんぞ。

ポリモーフィズムは、「同じインターフェースでありながらデータ型に合わせて異なる動作をする機能」をプログラミングで提供します。

ここで、インターフェース＝関数、メソッドのことらしい。
どうやら、一つの関数とかメソッドで、複数のデータ型を扱える機能はポリモーフィズムらしい。

例えばprint関数は下記のように

>>> print("やあこんにちは")
やあこんにちは
>>> print(123)
123
>>> print(3.14)
3.14

どんなデータ型であろうと同じprint関数で出力してくれます。
もし、ポリモーフィズムが使えなかったら、
文字列を扱うときはprint_string()
整数を扱うときはprint_int()
浮動小数点数を扱うときはprint_float()
のように、データ型専用print関数を用意しないといけなくなります。

なるほど、ポリモーフィズムがないと面倒です。

ポリモーフィズム、ありがとう。

今日はここまでです。
今日は娘のお昼寝がほぼ皆無だったため、進みが悪いですが、自分を許すことにします。

参考書はこちらです。

独学プログラマー Python言語の基本から仕事のやり方まで

独学プログラマー Python言語の基本から仕事のやり方まで

それではまた^^