📒
応用情報技術者試験 午後問題過去問のアルゴリズムをpythonで書いてみた
平成２７年度 問３ ２分探索木の問題
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def search(k, p):
if p is None:
return None
elif k == p.key:
return p
elif k < p.key:
return search(k, p.left)
else:
return search(k, p.right)
def addNode(k, p):
if p is None:
return Node(k)
elif k != p.key:
if k < p.key:
p.left = addNode(k, p.left)
else:
p.right = addNode(k, p.right)
return p
def removeNode(k, p):
if p is not None:
if k < p.key:
p.left = removeNode(k, p.left)
elif k > p.key:
p.right = removeNode(k, p.right)
else:
if p.left is None and p.right is None:
p = None
elif p.left is None:
p = p.right
elif p.right is None:
p = p.left
else:
p.left, r = extractMaxNode(p.left)
r.left = p.left
r.right = p.right
p = r
return p
def extractMaxNode(p):
if p.right is None:
return p.left, p
else:
p.right, r = extractMaxNode(p.right)
return p, r
def inorder_traversal(node):
if node is not None:
inorder_traversal(node.left)
print(node.key) # ノードの値を表示
inorder_traversal(node.right)
root = None
root = addNode(5, root)
root = addNode(2, root)
root = addNode(7, root)
root = addNode(1, root)
root = addNode(8, root)
root = addNode(4, root)
root = addNode(3, root)
root = addNode(12, root)
root = removeNode(5, root)
root = removeNode(7, root)
inorder_traversal(root)
平成２８年度 問３ 魔法陣の問題
番兵有りVer
def syokika(N, houjin):
for y in range(N):
for x in range(N):
houjin[y][x] = 0
houjin[y][N] = SOTO_MIGI
for x in range(N):
houjin[N][x] = SOTO_SHITA
houjin[N][N] = SOTO_KADO
return houjin
def mahoujin(N, houjin):
y = N-1
x = (N+1)//2-1
suuji = 1
houjin[y][x]= suuji
while(suuji!=N**2):
yb = y
xb = x
y += 1
x += 1
if houjin[y][x] == SOTO_SHITA:
y = 0
elif houjin[y][x] == SOTO_MIGI:
x = 0
elif houjin[y][x] == SOTO_KADO:
y = 0
x = 0
if houjin[y][x] != 0:
y = yb - 1
x = xb
suuji += 1
houjin[y][x] = suuji
return houjin
N = 5
SOTO_MIGI = N**2+N
SOTO_SHITA = N**2+2*N
SOTO_KADO = N**2+3*N
houjin = [[0]*(N+1) for _ in range(N+1)]
houjin1 = syokika(N, houjin)
# for i in range(N+1):
# print(*houjin[i])
print("")
houjin2 = mahoujin(N, houjin1)
for i in range(N):
for j in range(N):
if j==N-1:
print(houjin2[i][j])
else:
print(houjin2[i][j],end =" ")
番兵無しVer
def mahoujin(N, houjin):
y = N-1
x = (N+1)//2-1
suuji = 1
houjin[y][x]= suuji
while(suuji!=N**2):
yb = y
xb = x
y += 1
x += 1
if y > N-1:
y = 0
if x > N-1:
x = 0
if houjin[y][x] != 0:
y = yb - 1
x = xb
suuji += 1
houjin[y][x] = suuji
return houjin
N = 5
houjin = [[0]*(N) for _ in range(N)]
print("")
houjin2 = mahoujin(N, houjin)
for i in range(N):
for j in range(N):
if j==N-1:
print(houjin2[i][j])
else:
print(houjin2[i][j],end =" ")
令和１年度 問３ ニューラルネットワークの問題
単純パーセプトロンVer
def simple_perceptron(X, Y):
for out in range(NC):
ytemp = BY
for i in range(NI):
ytemp += X[out][i] * WY[i]
if ytemp > 0:
Y[out] = 1
else:
Y[out] = 0
print('x1:', X[out][0], 'x2:', X[out][1], 'Y:', Y[out])
NI = 2
NC = 4
X = [[0, 0], [0, 1], [1, 0], [1, 1]]
Y = [0]*NC
WY = [0.5, 0.5]
BY = -0.2
simple_perceptron(X, Y)
３層パーセプトロンVer
def three_layer_perceptron(X, Y):
for out in range(NC):
ytemp = BY
for mid in range(NM):
mtemp = BM[mid]
for i in range(NI):
mtemp += X[out][i] * WM[mid][i]
if mtemp > 0:
M[out][mid] = 1
else:
M[out][mid] = 0
ytemp += M[out][mid] * WY[mid]
if ytemp > 0:
Y[out] = 1
else:
Y[out] = 0
print('x1:', X[out][0], 'x2:', X[out][1], 'Y:', Y[out])
NI = 2
NC = 4
NM = 2
X = [[0, 0], [0, 1], [1, 0], [1, 1]]
Y = [0]*NC
M = [[0]*NM for _ in range(NC)]
# 排他的論理和
WY = [0.5, 0.5]
WM = [[0.5, 0.5], [-0.5, -0.5]]
BY = -0.6
BM = [-0.2, 0.7]
three_layer_perceptron(X, Y)
Discussion