情報基礎「Pythonプログラミング」（番外編・『数理思考演習』）

Pythonプログラミング（番外編・Pythonコード集）

このページには、参考書『コンピュテーショナル・シンキング』に掲載されているアルゴリズムをPythonコードで表現した例をいくつか掲載しておく

２章　プログラミングの基礎知識

Algorithm 5 回文数の判定アルゴリズム

Algorithm 5: 回文数の判定

# Algorithm 5
# coding: utf-8

import math

def kaibun(n):
    if n<9:
        print("YES")
        return

    lsd=n%10
    d=int(math.log10(n)) # nの桁数-1
    k=n%(10**d)
    msd=(n-k)//(10**d)
    if lsd!=msd:
        print("NO")
        return

    m=k//10
    kaibun(m)

# メイン部

n=int(input("自然数:"))
kaibun(n)

３章　問題解決事例演習・基本編

Algorithm 6 A君へ渡すコインの枚数を求める

Algorithm 6: コインの枚数

# Algorithm 6
# coding: utf-8

n = int(input("n= "))
p = float(input("p= "))
q = 1.0-p

V=0
W=0
k=1

while True:
    W = (1.0-(q/p)**k)/(1.0-(q/p)**n)
    if W>=0.5:
        break
    V = W
    k = k+1

if 1/2-V < W-1/2:
    print(k-1)
else:
    print(k)

Algorithm 7 拡張互除法

Algorithm 7: 拡張互除法

# Algorithm 7
# coding: utf-8

def egcd(a,b):
    if b==0:
        return 1,0

    r0=a
    r1=b

    P=[[1,0], 
       [0,1]]

    while r1!=0:
        r2=r0%r1
        q1=r0//r1

        P1=[[q1,1],
            [1,0]]

        p00 = P[0][0]*P1[0][0] + P[0][1]*P1[1][0]
        p01 = P[0][0]*P1[0][1] + P[0][1]*P1[1][1]
        p10 = P[1][0]*P1[0][0] + P[1][1]*P1[1][0]
        p11 = P[1][0]*P1[0][1] + P[1][1]*P1[1][1]

        P[0][0]=p00
        P[0][1]=p01
        P[1][0]=p10
        P[1][1]=p11

        r0 = r1
        r1 = r2
        
    det = P[0][0]*P[1][1] - P[0][1]*P[1][0]
    x = P[1][1]//det
    y = -P[0][1]//det

    return x,y

# メイン部

print(egcd(120,88))

Algorithm 8 拡張互除法（再帰版）

Algorithm 8: 拡張互除法（再帰版）

# Algorithm 8 (p.71)
# coding: utf-8

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

def egcd(a,b):
    if b==0:
        return 1,0
    q=a//b
    r=a%b
    x,y=egcd(b,r)
    return y,x-q*y

# メイン部

print(egcd(120,88))

Algorithm 13 ピボット操作および Algorithm 14 ブレンドコーヒーの作り方

円による縄張り問題（線形計画法による最適化）の simplex.pyを参照のこと

Algorithm 15 マフィンとクッキーを作る個数とその売り上げ

Algorithm 15: マフィンとクッキー

# coding: utf-8

a=60  # マフィンの価格
b=15  # クッキーの価格
A=3000 # 小麦粉の量
B=1600 # 砂糖の量

x0=0
y0=0
z0=0
x=0
y=0
z=0
while 25*x <= A and 15*x <=B:
    y = min( round((A-25*x)/7) , round((B-15*x)/3) )
    z = a*x + b*y
    if z>z0:
        x0=x
        y0=y
        z0=z
    x=x+1

print("マフィンの個数:",x0," クッキーの個数:",y0," 売上げ:",z0)

４章　問題解決事例演習・発展編

Algorithm 16 巡回置換分解を求める

辞書と集合のページを参照のこと

Algorithm 18 Dijkstraの方法

最短経路探索のページを参照のこと

Algorithm 19 配属問題を解く

２部グラフのマッチングのページを参照のこと

ディジタルの傷を癒やす

アルゴリズムとしては記載されていないが、参考書で例示されているハミング符号についての検証用のコード例を示しておく。

# 『コンピュテーショナル・シンキング』p.149-
# coding: utf-8

def mul(a,A):
    ncol=len(A[0])
    nrow=len(A)
    r=[0]*ncol
    for j in range(ncol):
        for i in range(nrow):
            r[j] = (r[j] + a[i]*A[i][j])%2
    return r

def add(a,b):
    ncol=len(a)
    r=[0]*ncol
    for j in range(ncol):
        r[j]=(a[j]+b[j])%2
    return r

def distance(a,b):
    ncol=len(a)
    d=0
    for j in range(ncol):
        if a[j]!=b[j]:
            d=d+1
    return d

# 符号化行列
G = [
    [1,0,0,1,1,1,0,0],
    [0,1,0,0,1,1,1,1],
    [0,0,1,1,0,0,1,1]
    ]

# 検査行列
H = [
    [1,1,1,0,0],
    [0,1,1,1,1],
    [1,0,0,1,1],
    [1,0,0,0,0],
    [0,1,0,0,0],
    [0,0,1,0,0],
    [0,0,0,1,0],
    [0,0,0,0,1],
    ]

# 符号語のハミング距離
dmin=10000
for i in range(2**3):
    i0=i%2
    i1=(i>>1)%2
    i2=(i>>2)%2
    for j in range (2**3):
        if i==j:
            continue
        j0=j%2
        j1=(j>>1)%2
        j2=(j>>2)%2
        d = distance(mul([i2,i1,i0],G),mul([j2,j1,j0],G))
        if d<dmin:
            dmin=d

print("最小距離=",dmin)

# 送信データ
x = [1,0,0]
print(x)

# 送信符号
xp=mul(x,G)
print(xp)

# ノイズ付加
xpp=add(xp,[1,0,0,0,0,0,0,0])
print(xpp)

# シンドローム
r=mul(xpp,H)
print(r)

Algorithm 20 加算分割問題を解く

Algorithm 20: 加算分割問題を解く

# Algorithm 20: 加算分割問題を解く
# coding: utf-8

def cross_sum(n, k, d):
    if n<1:
        return [ ],0
    if d<k: 
        return [ ],0
    if k==1:
        if n<=d:
            return [[n]],1
        else:
            return [ ],0

    ell = [ ]
    c = 0
    t = min(d, n-k*(k-1)//2)
    while True:
        ellprime,cprime = cross_sum(n-t,k-1,t-1)
        for g in ellprime:
            ell.append(g + [t])

        c = c + cprime
        t = t - 1
        if k*t < n + k*(k-1)//2:
            break
    return ell,c


ell,c = cross_sum(21,4,12)
print(c)
for x in ell:
    print(x)

５章　情報の表現と文字列の操作

Algorithm 21 UTF-8からコードポイントを抽出する

Algorithm 21: UTF-8コードポイント


# Algorithm 21
# coding: utf-8
# Python 3 version

def codepoint(s):
    b = s.encode('utf-8')
    code = [ ]
    k=0
    while k < len(b):
        c0 = b[k]
        if c0 is None:
            break
        elif (c0 & 0b10000000) == 0 :
            code.append(c0)
            k=k+1
        elif (c0 & 0b11110000) == 0b11100000:
            c1 = b[k+1]
            c2 = b[k+2]
            code.append((c0 & 0x0F) * 2**12 + (c1 & 0x3F) * 2**6 + (c2 & 0x3F))
            k=k+3
        elif (c0 & 0b11111000) == 0b11110000:
            c1 = b[k+1]
            c2 = b[k+2]
            c3 = b[k+3]
            code.append((c0 & 0x07) * 2**18 + (c1 & 0x3F) * 2**12 + (c2 & 0x3F) * 2**6 + (c3 & 0x3F))
            k=k+4
    return code

# メイン部

res = codepoint("東北大学")
for c in res:
    print("u{:x}".format(c))

Algorithm 22 簡易版ボイヤー・ムーア法

Algorithm 22: 簡易版ボイヤー・ムーア法

Pythonではリストの添字が0から始まることから、リストcとsの添字が参考書とは1だけずれている

# Algorithm 22
# coding: utf-8

def search(c, s):
    n=len(c)
    m=len(s)
    i=0
    while i<=n-m+1:
        redo=False
        for j in range(1,m+1,1):
            if c[i+m-j-1] != s[m-j]:
                ell=0
                for k in range(m-j,0,-1):
                    if c[i+m-j-1]==s[k-1]:
                        ell=k
                        break
                i = i+m-j+1-ell
                redo=True
                break
        if not redo:
            return i
    return -1

# メイン部

c='PINEAPPLEJUICE'
s='APPLE'
pos=search(c,s)
if pos>=0:
    print(pos)
else:
    print('不一致')