182：最大公約数と最小公倍数を求める
組み込み関数、ライブラリとしては用意されていないので作成しました。
- gcd(x, y)
- x と y の最大公約数を返します。 x, y が負の数の場合 Ruby にあわせて正の数に変換してから計算します。 int, long 以外を渡すと TypeError? となります。内部で _gcd(x, y), _is_integer(x) を使用しています。
- lcm(x, y)
- x と y の最小公倍数を返します。 x, y が負の数の場合 Ruby にあわせて正の数に変換してから計算します。 int, long 以外を渡すと TypeError? となります。内部で _lcm(x, y), _is_integer(x) を使用しています。
- _gcd(x, y)
- x と y の最大公約数を返します。 x, y が負の数の場合 Ruby にあわせて正の数に変換してから計算します。 型チェックしていません。
- _lcm(x, y)
- x と y の最小公倍数を返します。 x, y が負の数の場合 Ruby にあわせて正の数に変換してから計算します。 型チェックしていません。
- _is_integer(x)
- x が int 型もしくは long 型ならば True を返します。それ以外ならば False を返します。
- _gcd2(x, y)
- _gcd(x, y) を再帰を使って実装しなおしたものです。 x, y が負の数でもそのまま計算し、最終結果の絶対値を取っています。
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
import unittest
def _gcd(x, y):
u"""
最大公約数を求める。型チェック無し。
x, y が負の数の場合は正に変換してから計算する。
ユークリッドの互除法にて。
y が 0 ならば終了。最大公約数は x 。
x に y を代入。 y に x を y で割った余りを代入。繰り返し。
"""
x = abs(x)
y = abs(y)
while y:
x, y = y, x % y
return x
def _lcm(x, y):
u"""
最小公倍数を求める。型チェック無し。
x, y が負の数の場合は正に変換してから計算する。
最小公倍数は x と y の積を最大公約数で割ったものに等しい。
"""
x = abs(x)
y = abs(y)
return x * y / _gcd(x, y)
def gcd(x, y):
u"""
最大公約数を求める。型チェックあり。
x, y が負の数の場合は正に変換してから計算する。
ユークリッドの互除法にて。
"""
if _is_integer(x) and _is_integer(y):
return _gcd(x, y)
raise TypeError("unsupported types: '%s' and '%s'" % (type(x).__name__, type(y).__name__))
def lcm(x, y):
u"""
最小公倍数を求める。型チェックあり。
x, y が負の数の場合は正に変換してから計算する。
最小公倍数は x と y の積を最大公約数で割ったものに等しい。
"""
if _is_integer(x) and _is_integer(y):
return _lcm(x, y)
raise TypeError("unsupported types: '%s' and '%s'" % (type(x).__name__, type(y).__name__))
def _is_integer(x):
u"""
引数が int もしくは long 型であるかどうか確認する。
"""
if isinstance(x, int) or isinstance(x, long):
return True
return False
def _gcd2(x, y):
u"""
ユークリッドの互除法にて最大公約数を求める。
再帰版。
型チェック無し。
"""
if not y:
return abs(x)
return _gcd2(y, x % y)
class TestFunctions(unittest.TestCase):
def testGcd(self):
self.assertEqual(gcd(12, 15), 3)
self.assertEqual(_gcd(12, 15), 3)
self.assertEqual(_gcd2(12, 15), 3)
self.assertRaises(TypeError, gcd, 'a', 15)
self.assertEqual(gcd(-12, 15), 3)
self.assertEqual(gcd(12, -15), 3)
self.assertEqual(gcd(-12, -15), 3)
for i in range(-500, 500):
for j in range(-500, 500):
self.assertEqual(_gcd(i, j), _gcd2(i, j))
def testLcm(self):
self.assertEqual(lcm(12, 15), 60)
self.assertEqual(_lcm(12, 15), 60)
self.assertRaises(TypeError, lcm, 'a', 15)
self.assertEqual(lcm(-12, 15), 60)
self.assertEqual(lcm(12, -15), 60)
self.assertEqual(lcm(-12, -15), 60)
if __name__ == '__main__':
unittest.main()
参考