高校数学の窓LaTeX版: 最大公約数と最小公倍数

さて、最大公約数と最小公倍数、です。
実はこれらの計算アルゴリズムもLisp系では「再帰の例」として良く使われる例、です。
ほらね、このセンセ、やっぱ「Lispっぽいネタ」が大好きなのです(多分、東工大の情報工学系の学生は皆やらされます・笑)。
しかし、これらの「再帰だったら簡単に書ける計算アルゴリズム」を「反復」で書かなければならないとしたらどうなるか?
これは非常に大変、です。そして説明が大変になる。従って読んでる読者はもっと大変になる、って事です。
以下はその典型例だ、って事を含んで始めましょうか。

[課題2・1]　　２つの正の整数が与えられたとき、その最大公約数を求めよ。

プログラム作成の第1段階として上の問題を次のように分解しましょう。

2つの正整数m、nを入力する

mとnの最大公約数GCDを求める

最大公約数を出力する

1番目の入力部分については、非正値の入力があればプログラムを強制終了することにし、次のように分解します。

正整数m、nを読み込む

mとnのどちらか一方が非正値であればプログラムを強制終了する

2番目の命令について、後からその手順を詳細に考えることにし、いまはそれを実行してくれる手続き"最大公約数(m、n、GCD)"があるものとします。この手続きは、2つの正整数m、nを与えると、その最大公約数GCDを返すものとします。
最後の出力は、前節と同様にこれ以上詳細に考えません。
これから、メインプログラムは次のように書かれます。

プログラム　　「最大公約数を求める」

変数　m, n, GCD : 整数型

{

m、nを入力する

もし　　(m≦0またはn≦0)
　　　　ならば　プログラムを終了

最大公約数(m, n, GCD)

GCDの値を出力する

}

ここから、最大公約数を求める具体的な手順を考えていきましょう。数学的には、最大公約数を求める方法はいくつかあります。ここではユークリッドの互除法によって最大公約数を求めてみます。
ユークリッドの互除法が拠り所とするのが、次の定理です。

[定理]　　2つの正の整数m、n　(m≧n)　があるとき、mをnで割った余りをr　(0≦r<n)とすれば、

r = 0ならば、mとnの最大公約数はnである

r ≠ 0ならば、mとnの最大公約数は、nとrの最大公約数に等しい

上の1.はあきらかですし、2.も簡単ですからこの証明は省略します。演習問題として自分で考えてください。

下線部:亀田

はいはいはいはいはい、ストップストップストップ。
ここで、世界最古のアルゴリズム、と呼ばれる「ユークリッドの互除法」が表れました。そして、実はこの「ユークリッドの互除法」自体が数学的に言えば「帰納」、プログラミング用語で言うと「再帰」の構造である、ってのが分かるでしょうか?
ここで、mとnの最大公約数を取り合えずGCD(m、n)と置いてみて、また、mとnの剰余をm mod nと書き表す事とします。
そうすると、下線部の部分に注視すると、次の「たった」3ステップで「ユークリッドの互除法」を表現出来るんです。

正整数m、nを読み込む。mとnのどちらか一方が非正値であればエラーを返す

m mod n = 0ならば、GCD(m, n)はnである

m mod n ≠ 0ならば、CCD(m, n)は、GCD(n, m mod n)である

ここまで分かれば早速実装です。んで、不思議に思うかもしれませんが「これで上手く動く」んですよ(笑)。



# -*- coding: utf-8 -*-
# Pythonの場合

def GreatestCommonDivisor(m, n):
   if m <= 0 or n <= 0:
       raise ValueError
   elif m % n == 0:
       return n
   else:
       return GreatestCommonDivisor(n, m % n) # ここで再帰

# Rubyの場合

def GreatestCommonDivisor m, n
 if m <= 0 || n <= 0
   raise
 elsif m % n == 0
   n
 else
   GreatestCommonDivisor(n, m % n) # ここで再帰
 end
end

;; Schemeの場合

(define (GreatestCommonDivisor m n)
 (cond ((or (<= m 0) (<= n 0))
        (error m n))
       ((zero? (modulo m n))
        n)
       (else
        (GreatestCommonDivisor n (modulo m n))) ;ここで再帰
       ))

## Rの場合

GreatestCommonDivisor <- function(m, n) {
 if (m <= 0 || n <= 0) {
   return(NA)
 }
 else if (m %% n == 0) {
   return(n)
 }
 else {
   return(GreatestCommonDivisor(n, m %% n))    #ここで再帰
 }
}

不思議でしょ(笑)?単に「数学的定義」を「そのまま」置き換えれば良いのです。「反復」なんて影も形も出てきませんし、「それでも動く」のは、元々数学自体が「そう言う風に」作られている、って事なんです。一旦枠組みさえ大まかに設定してしまえば、「個々の細かい計算」は全然考えなくって良い。あとはコンピュータ(と言うか、プログラミング言語)任せで良い、んです。
そろそろ「再帰」と言うプログラミングに於ける数学的手法が如何に強力なのか、分かってきたでしょ(笑)?「再帰」が使えないプログラミング言語なんて学ぶに値しない、って言った意味を。
ちなみに、「再帰が難しい」とか思うんだったら、数学が分からん、って意味です。数列や漸化式、数学的帰納法が全くわかっていない、って事なんで、「数学教員免許取得」なんて諦めた方が良い、です。あるいは、一旦プログラミングの学習を中止して、通大のテキストで良いんで、解析をもう一度やり直してください。その理論は数学の範疇なんで、プログラムをやる前に数学で押えておくべきネタです。
いずれにせよ、これを「再帰」ではなく「反復」で実装するのはなかなか骨が折れる仕事です。まあ、練習代わりにはやっても良いでしょうが、基本的にコードは「長く」なりがちですね。
以下の通大テキストの抜粋は「反復」を使う場合のコードの書き方、になります。

この命題から、2つの正整数m、nがあるとし、わり算を続けて行い

$$n > r_1 > r_2 > r_3 > r_4 > \ldots \ge 0$$

という整数で各わり算の余りを実現したとき、

r₁ = mをnで割った余り

r₂ = nをr₁で割った余り

r₃ = r₁をr₂で割った余り

r₄ = r₂をr₃で割った余り

・・・

・・・

であるとすれば、この演算の繰り返しは必ず有限回で終了します。最後のわり算は割り切れて

0=r_kをr_k+1で割った余り

となります。このときr_k+1が、mとnの最大公約数となります。これが、ユークリッドの互除法と呼ばれる方法です。ここで、定理の仮定にあるようにm≧nを確かめていませんが、m<nのときは、

r₁=mをnで割った余り＝m

r₂=nをr₁で割った余り＝nをmで割った余り

と考えられますから、手順としてその確認は必要ありません。この数学的手順を、これからプログラムとして書かなくてはなりません。
数学的表現では添え字を使って、すべての余りを区別しています。これにより、なにを数学的にやっているのか分かりやすい表現となります。では、プログラム上も配列等を使って、それらを区別して記憶しなくてはならないのかというと、その必要はありません。ここでは、最大公約数として最後のr_k+1だけが必要です。したがって、1つの変数rを用意して、新たな余りが得られるたびにその値を変数rに代入すればよいことになります。これは、数学では変数はなにか具体的な値そのものを表しており、時間的に変化しません。そこで、添え字を使って、別の変数として記述することによりその変化を表現します。しかし、コンピュータプログラムにおいては、変数の中身は時間(処理が進むにつれてという意味です)によってダイナミックに変化していきます。
ユークリッド互除法による最大公約数を求めるプログラムを手続きの形で書いてみましょう。
手続き　最大公約数(m:整数, n:整数, GCD:整数型変数)

局所変数　　d, r, t : 整数型


{

d←m

r←n

(r≠0)であるかぎり次を繰り返す
{

t←dをrで割った余り

d←r

r←t


}

GCD←d


}
この手続きが呼び出されると、仮引き数mとnの最大公約数が変数GCDの中に格納されます。mとnは、値だけをサブプログラムに渡す引数ですが、GCDは呼び出し先に値を返さなければならないため変数の仮引数となります。

局所変数dとrは、1つ前に実行されたわり算における除数divisorと剰余residueの値を格納するための変数です。

n＝○○をmで割った余り

と解釈すれば、このわり算において、除数はmで余りはnとなります。そこで、dにmを代入、rにnを代入します。ユークリッドの互除法は、余りが0になるまで1つ前に実行されたわり算における除数を被除数に、また、余りを除数にした新たなわり算をおこない余りを求めていきます。それが

l←dをrで割った余り

の部分です。ここでは、余りをすぐにrに代入せずに一時的に変数tに代入しています。ここで実行されたわり算の除数であるrの値を、後のためにdとして保存しておかなければならないからです。

r←dをrで割った余り

と、すぐに余りを求めてそれをrに代入したのでは、次のわり算に必要な代入前のrの値が失われてしまいます。プログラムを書くとき、このように一時変数に値を保存しておき、後で必要となる値を失わないようにします。代入の順序に注意してください。
先ほどのメインプログラムの後に、この手続きを書けば課題に対するプログラムとなります。

極めて長ったらしい説明ですよね(笑)。さすがに読んでる途中で嫌になってきます。
もう一度繰り返しますが、元々「ユークリッドの互除法」と言うアルゴリズム自体が「再帰」的、なんです。従って、再帰的アルゴリズムを「反復」に直す事は極めて「不自然」で、上のように「長ったらしく」考えないと「反復」に変換出来ない、って事を意味しています。
91年当時のパソコンの「テクノロジー」ってのは、こう言う風に「再帰を楽々扱えない」限界が存在してた、って言い方も出来るのです。

[課題2・2]　　２つの正の整数が与えられたとき、その最小公倍数をもとめよ。

この課題のメインプログラムは、前の課題のプログラムにおける最大公約数を求める手続きを最小公倍数を求める手続きに変えるだけです。
2つの正整数mとnが与えられたとして、その最小公倍数を求める手順を考えてみましょう。このための数学的手順もいくつかありますが、上で作った最大公約数を求めるプログラムを利用することを考えてみます。

m×n＝(mとnの最小公倍数)×(mとnの最小公約数)

が成立することは、よく知られた事実です。これから、すでに作成してある最大公約数を求める手続きを使って、最小公倍数を求める手続きは次のようになります。
手続き　最小公倍数(m : 整数, n : 整数, LCM : 整数型変数)

局所変数　GCD整数型


{

最大公約数(m, n, GCD)

LCM←(m×n)/GCD


}
これから、課題のプログラムを完成させることは容易ですから省略します。

<演習問題>

ユークリッドの互除法の拠り所となる定理を示せ。

3つの正整数a、b、cの最大公約数と最小公倍数を求めるプログラムを作成せよ。

まずは課題2・2を解いてしまいましょう。
基本的には全然難しくないんですが、ある「流儀」を説明しておこうと思います。
それは別ファイルに保存した「プログラム」を呼び出したりする方法です。

課題2・2自体は全然難しくないんですが、このプログラムでは先に作ったプログラム「GreatestCommonDivisor」を呼び出さなければなりません。そしてその「呼び出し方法」にはプログラミング言語毎に流儀があります。
まずは、プログラムを書いたテキストファイルを保存するには「拡張子」と言うものを保存するテキストファイルの名前に付けないとなりません。一般にOS(オペレーティングシステム)はこの「拡張子」によって、そのテキストファイルが何のプログラムなのか識別するようになっているから、です。

Pythonプログラムの拡張子は".py"である。

Rubyプログラムの拡張子は".rb"である。

Schemeプログラムの拡張子は".scm"である。

Rプログラムの拡張子は".R"である。

ここでは、先ほど作ったGreatestCommonDivisorを記述したテキストファイルをそれぞれ

Pythonの場合は"GCD.py"として保存。

Rubyの場合は"GCD.rb"として保存。

Schemeの場合は"GCD.scm"として保存。

Rの場合は"GCD.R"として保存。

したとして、それぞれのコードがどうなるか見てみます。
なお、プログラムの保存場所はどこにすべきか?と言う問題がありますが、一般に、デフォルト指定されている場所(フォルダ/ディレクトリ)に保存すれば大丈夫、です。その辺にはデフォルトでパスが通ってるでしょうから。



# -*- coding: utf-8 -*-
# Pythonの場合

import GCD                              # これが呼び出し方

def LeastCommonMultiple(m, n):
    return (m * n) / GCD.GreatestCommonDivisor(m, n)
# Pythonではドット(.)は〜の、と言う意味

# Rubyの場合

load "GCD.rb"                   # "GCD.rb"をロード

def LeastCommonMultiple m, n
  (m * n) / GreatestCommonDivisor(m, n)
end

;; Schemeの場合

(load "GCD.scm")                        ;"GCD.scm"をロード

(define (LeastCommonMultiple m n)
  (/ (* m n) (GreatestCommonDivisor m n))
  )

## Rの場合

source("GCD.R")                         #これが呼び出し方

LeastCommonMultiple <- function(m, n) {
  return((m * n) / GreatestCommonDivisor(m, n))
}

<演習問題解答例>

Phaos氏が数学的に説明してるんで、それをパクります(笑)。

まずは作っておいたLeastCommonMultipleと言う関数(あるいは手続き/メソッド)を
- Pythonの場合は"LCM.py"として保存
- Rubyの場合は"LCM.rb"として保存
- Schemeの場合は"LCM.scm"として保存
- Rの場合は"LCM.scm"として保存
します。こうやって保存した"GCM.*"と"LCM.*"を再利用して演習問題を解きます(これが、通大のテキストに書かれてある「分割」「統合」の例だ、と言う事を忘れないように!!!)。
なお、これは問題としては単純で、一般に3変数a、b、cの最大公約数、最小公倍数を求める場合、最大公約数のアルゴリズムをGCM、最小公倍数のアルゴリズムをLCMとすると、
- 3変数a、b、cの最大公約数＝GCM(a, GCM(b, c))
- 3変数a、b、cの最小公倍数＝LCM(a, GCM(b, c))
となります。こう言う表記を入れ子(あるいはネスト)と呼ぶのです。
つまり、上の「入れ子表現」をそのまま書けば解答としては一丁上がり、って事なんです。
なお、通大のテキストだと一々出力命令を噛ましていますが、一般に、出力命令を噛ますと再利用がしにくい、と言う欠点が生じます(これはC言語でも同様です)。
従って、ここでは2つの計算結果を返す為、リスト(配列)を用いて計算結果を返すようにしてみました。
```
# -*- coding: utf-8 -*-
# Pythonの場合

import GCD, LCM                         # 二つのファイルをインポート

def GCDandLCM(a, b, c):
    return [GCD.GreatestCommonDivisor(a, GCD.GreatestCommonDivisor(b, c)),
            LCM.LeastCommonMultiple(a, LCM.LeastCommonMultiple(b, c))]

# Rubyの場合

load "GCD.rb"                   # "GCD.rb"をロード
load "LCM.rb"                   # "LCM.rb"をロード

def GCDandLCM a, b, c
  [GreatestCommonDivisor(a, GreatestCommonDivisor(b, c)),
   LeastCommonMultiple(a, LeastCommonMultiple(b, c))]
end

;; Schemeの場合

(load "GCD.scm")                        ;"GCD.scm"をロード
(load "LCM.scm")                        ;"LCM.scm"をロード

(define (GCDandLCM a b c)
  (list
   (GreatestCommonDivisor a (GreatestCommonDivisor b c))
   (LeastCommonMultiple a (LeastCommonMultiple b c))
   ))

## Rの場合

source("GCD.R")                         #"GCD.R"をロード
source("LCM.R")                         #"LCM.R"をロード

GCDandLCM <- function(a, b, c) {
  return(list(GreatestCommonDivisor(a, GreatestCommonDivisor(b, c)),
              LeastCommonMultiple(a, LeastCommonMultiple(b, c))))
}
```
はい、問題無いですね。
以上です。

高校数学の窓LaTeX版

高校数学の窓過去問検索

最大公約数と最小公倍数

0 コメント:

New

分類

ツール

数学ガール

たけしのコマ大数学科

ガスコン研究所

数学系ブログ記事