home changes contents help options

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()

参考

ユークリッドの互除法 - Wikipedia