AT's Blog

趣味のプログラミングに関する技術メモがメインです。

ユークリッドの互除法で最大公約数を求めるアルゴリズムをPython3で実装してみた

尿管結石になった件

GWからこっち不摂生を続けていたせいか、尿管結石を発症してしまいました。

結石が体外に排出されるまでの四日間、文字通り七転八倒するような痛みにもがき苦しむことになりました。 噂には聞いていましたが、本当に救急車を呼ぼうかと思ったほどでした。 病院に駆け込んでもレントゲンやらCTスキャンをたらい回しにされた挙句、結局痛み止めの座薬(アッー!)を打たれるだけで、 石が出るまで耐えるしかないと医者に言われる始末。

せっかくひどい目にあったので、これを機に生活習慣を見直していこうと思います(とりあえずコーヒー断ち中)。

アルゴリズムの勉強

最終章から、ユークリッドの互除法を用いた最大公約数の計算プログラムです。

コード自体はかなり前に書き上げていたのですが、今回はpylintとpep8をPASSするまでコードを修正してみました。 こんな過疎ブログとはいえ、世間様に自分の書いたコードを晒すわけですから、それなりに体裁は整えないと・・・。

gcd.py

# coding: utf-8

"""
GCD -- Greatest common divisor
Usage : python3 gcd.py [Integer1] [Integer2]
"""

import sys


def euclid(i, j):
    """
    Euclidean Algorithm
    >>> euclid(12, 18)
    6
    """

    if i > j:
        if i % j == 0:
            return j
        else:
            return euclid(j, i % j)
    else:
        if j % i == 0:
            return i
        else:
            return euclid(i, j % i)


def main():
    """
    Entry point
    """

    print(euclid(int(sys.argv[1]), int(sys.argv[2])))

if __name__ == '__main__':
    main()

Aizu Online Judge

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

アルゴリズムを、はじめよう」を読み終えたので、今度はこちらに取り掛かっています。 プロコン向けに書かれた本ですが、基礎から応用までアルゴリズムとデータ構造が網羅されています。

オンラインプロコンのAizu Online Judgeと連携しているので、自分で書いたコードをテストしながら勉強できます。 プロコン参加自体は目的ではありませんが、モチベーション維持にはいい感じです。