Python(バージョン3)で,最大値を見つけるアルゴリズム,ユークリッドの互除法,2分探索による平方根の見積もりを実装してみる.
まず,最大値を見つけるアルゴリズムを関数maximumとして以下に定義する. なお,Pythonには最大値を返す組込み関数maxがある.
def maximum(x):
y = x[0]
for i in range(1, len(x)):
if x[i] > y:
y = x[i]
return y
試しに,てきと〜に作った数値のリストを引数として関数maximumをよびだしてみる.
x = [3, 1, 4, 1, 5, 9, 2]
maximum(x)
9
確かに最大値を返してくれることを確認した.
ユークリッドの互除法を関数euclidとして以下に定義する.
def euclid(x, y):
x, y = maximum([x, y]), min(x, y)
while y > 0:
x, y = y, x % y
return x
この関数定義では,同時に複数の代入をする命令を2回使っている. 同時に複数の代入をできると入れ替え(スワップ)の際には便利である. また,せっかくなので上で定義した関数maximumを使った.
試しに,10807と10403の最大公約数を求めてみる.
euclid(10807, 10403)
101
確かに最大公約数を返してくれることを確認した.
2分探索による平方根の見積もりを関数square_root_binary_searchとして以下に定義する. なお,アルゴリズムの途中経過を観察するための表示命令も加える.
def square_root_binary_search(x, p):
a, b = 0, x
while b - a > p:
print('[a, b] = [{0:4.3f}, {1:4.3f}]'.format(a, b)) # アルゴリズムの途中経過を観察する.
m = (a + b) / 2 # このコードはPython3用なので,この商は小数部分切り捨てではない.
if m ** 2 > x:
b = m
else:
a = m
return a, b
試しに,$\sqrt{2}$を精度0.1で見積もってみる.
square_root_binary_search(2, 0.1)
[a, b] = [0.000, 2.000] [a, b] = [1.000, 2.000] [a, b] = [1.000, 1.500] [a, b] = [1.250, 1.500] [a, b] = [1.375, 1.500]
(1.375, 1.4375)
見積もりとしては甘く感じるが,$\sqrt{2}$は1.375と1.4375の間にあるとわかる.
もう少し精度を上げて,$\sqrt{2}$を精度0.0001で見積もってみる.
square_root_binary_search(2, 0.0001)
[a, b] = [0.000, 2.000] [a, b] = [1.000, 2.000] [a, b] = [1.000, 1.500] [a, b] = [1.250, 1.500] [a, b] = [1.375, 1.500] [a, b] = [1.375, 1.438] [a, b] = [1.406, 1.438] [a, b] = [1.406, 1.422] [a, b] = [1.414, 1.422] [a, b] = [1.414, 1.418] [a, b] = [1.414, 1.416] [a, b] = [1.414, 1.415] [a, b] = [1.414, 1.415] [a, b] = [1.414, 1.414] [a, b] = [1.414, 1.414]
(1.4141845703125, 1.41424560546875)
2分探索を用いると,目標を含む区間が毎回半分になる. よって探索範囲が狭まるのは意外と早い.