Algorithm - Python - 基礎概念 - アルゴリズム

The Art of Computer Programming
Volume 1
原著

開発環境

• macOS Sierra - Apple (OS)
• Emacs (Text Editor)
• Python 3.6 (プログラミング言語)

The Art of Computer Programming　Volume 1 Fundamental Algorithms Third Edition 日本語版(Donald E. Knuth (著)、青木 孝 (著)、筧 一彦 (著)、鈴木 健一 (著)、長尾 高弘 (著)、有澤 誠 (その他)、和田 英一 (その他)、ドワンゴ)の第1章(基礎概念)、1.1(アルゴリズム)、演習問題1、2、3、4を取り組んでみる。

1.

コード(Emacs)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 1.
a, b, c, d = 1, 2, 3, 4
print(b, c, d, a)

t = a
a = b
b = c
c = d
d = t

print(a, b, c, d)

入出力結果(Terminal, IPython)

$ ./sample1.py
2 3 4 1
2 3 4 1
$

2.

$\begin{array}{l}m=nq+r\left(0\le n<r\right)\\ m\leftarrow n\\ n\leftarrow r\\ m<n\end{array}$

3、4.

コード(Emacs)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-


# 3.
def e(m, n):
    if m <= 0 or n <= 0:
        raise Exception()
    while True:
        # E1.
        r = m % n
        # E2.
        if r == 0:
            return n
        # E3.
        m = n
        n = r


def f(m, n):
    while True:
        # F1.
        m = m % n
        # F2.
        if m == 0:
            return n
        # F3.
        n = n % m
        # F4.
        if n == 0:
            return m


# 4.
import timeit

m = 2166
n = 6099
print(e(m, n), f(m, n), sep='\n')

t1 = timeit.timeit('e(m, n)', globals=globals())
t2 = timeit.timeit('f(m, n)', globals=globals())
print(t1, t2, t1 / t2, sep='\n')

入出力結果(Terminal, IPython)

$ ./sample3.py
57
57
0.5657923950348049
0.4853711019968614
1.165690319648374
$