総当たり戦スケジュール表を出力するcircle methodを以下に関数circle_methodとして定義する. 入力はチーム名の集合Tである. Circle method自体は単純なものであるが,コードにすると意外とわかりにくい.
def circle_method(T):
n = len(T)
c = [T[i] for i in range(n)]
p = {}
for t in T:
p[t] = []
for d in range(1, n):
for i in range(n):
p[c[i]].append(c[n - i - 1])
cc = ['' for i in range(n)]
for i in range(1, n - 1):
cc[i] = c[i - 1]
cc[0] = c[n - 2]
for i in range(n - 1):
c[i] = cc[i]
return p
Circle methodを関数として定義できたので,10チームの集合を作り試してみる.
T = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J']
p = circle_method(T)
各チームの各日の対戦相手がpに格納された. 見やすいように表としてpの値を表示する.
print(' | %s' % (' '.join(map(str, [i for i in range(1, len(T))]))))
print('%s' % (''.join(['-' for i in range(1+2*len(T))])))
for t in T:
print('%s | %s' % (t, ' '.join(p[t])))
| 1 2 3 4 5 6 7 8 9 --------------------- A | J H F D B I G E C B | I G E C A H F D J C | H F D B I G E J A D | G E C A H F J B I E | F D B I G J C A H F | E C A H J D B I G G | D B I J E C A H F H | C A J F D B I G E I | B J G E C A H F D J | A I H G F E D C B
アル・フアリズミーが著した本に書かれていたという乗算方法を以下に関数alkwarizumi_prodとして定義する. 以下の関数におけるzは積(の途中経過)を保存するための変数である.
def alkwarizmi_prod(x, y):
z = 0
while x >= 1:
if x % 2 == 1:
z += y
x = x // 2
y *= 2
return z
関数を定義したので,早速試してみる.
alkwarizmi_prod(34, 56)
1904
一応検算しておく.
34 * 56
1904
以下に3種類の素数列挙法をコードにしてみる.
まず,与えられた自然数xが素数か否かを単純な方法で判定する関数is_prime_simplyを以下に定義する.
def is_prime_simply(x):
for y in range(2, x):
if x % y == 0:
return False
return True
定義した関数を早速試してみる.
is_prime_simply(23)
True
is_prime_simply(24)
False
正しく定義できたようだ.
次に,素数判定アルゴリズム(関数)を利用して,素数を列挙するアルゴリズムを関数enumerate_primeとして定義する. 後々のことも考えて,素数判定関数は引数として指定できるようにしておく.
def enumerate_prime(n, is_prime):
P = []
for x in range(2, n + 1):
if is_prime(x):
P.append(x)
return P
素数判定関数としてis_prime_simplyを指定して試してみる.
enumerate_prime(100, is_prime_simply)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
確かに素数を列挙できているようだ.
さらに,平方根を素数判定に利用するアルゴリズムを関数is_prime_sqrtとして以下に定義する. 平方根の計算のために数学関数モジュールmathをimportする.
import math
def is_prime_sqrt(x):
for y in range(2, int(math.sqrt(x)) + 1):
if x % y == 0:
return False
return True
関数を早速試してみる.
is_prime_sqrt(23)
True
is_prime_sqrt(24)
False
確かに素数を判定できているようだ.
この素数判定関数を用いて再度素数を列挙してみる. 素数判定関数としてis_prime_sqrtを指定して,100までの素数を列挙する.
enumerate_prime(100, is_prime_sqrt)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
先ほどど同じ結果が得られた.
素数列挙の最後としてエラトステネスの篩を関数eratosthenesとして以下に定義する.
def eratosthenes(n):
P = []
q = [True for i in range(n + 1)]
for i in range(2, n + 1):
if q[i] == True:
P.append(i)
for j in range(2, n // i + 1):
q[i * j] = False
return P
エラトステネスの篩を試してみる.
eratosthenes(100)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
やはり先ほどと同じ結果が得られた.
実は三種の素数列挙アルゴリズムは速さ(時間複雑度)が異なる. 100までの素数列挙では実行時間の差は感じないが,100万までの素数を列挙すると実行時間の差を体感できる.