高校数学をプログラミングで解く（数学A編）「3-6 ユークリッドの互除法」

マガジンリスト　＞　数学A編 3.整数の性質　＞　3-6 ユークリッドの互除法

はじめに

今回は、数学Aで学ぶ「ユークリッドの互除法」について、互除法を用いて最大公約数を求めるプログラムと互除法を応用して長方形を正方形で分割するプログラムを作成します。

ユークリッドの互除法

ユークリッドの互除法について、解説しておきます。

ユークリッドの互除法
a. 2つの自然数$${a,b}$$について、$${a}$$を$${b}$$で割ったときの商を$${q}$$、余りを$${r}$$とすると、$${a}$$と$${b}$$の最大公約数は、$${b}$$と$${r}$$の最大公約数に等しい。
b. aの性質を利用すると、２つの自然数$${a,b}$$の最大公約数を求めるには、次の手順を繰り返す。
i. $${a}$$を$${b}$$で割ったときの余りを$${r}$$とする。
ii. $${r=0}$$ならば、$${b}$$が$${a}$$と$${b}$$の最大公約数である。
   $${r>0}$$ならば、$${a}$$を$${b}$$で、$${b}$$を$${r}$$でおきかえて、iに戻る。
この手順を繰り返すと余り$${r}$$が小さくなり、$${r}$$が$${0}$$になって必ず終了する。

ユークリッドの互除法を用いた最大公約数の算出

今回は、72と15の最大公約数をユークリッドの互除法を用いて算出するプログラムを書きます。

アルゴリズム設計（解法）

今回の問題の解法は先ほど解説したユークリッドの互除法 b を単純に実装すればよいです。

プログラム

ユークリッドの互除法を用いて最大公約数を求め、その結果をコンソールに出力するプログラムを作成します。

// 2つの整数の最大公約数を互除法を用いて計算する
void setup(){

  int a = 72; // 1つ目の整数
  int b = 15; // 2つ目の整数
  
  int remainder = 1; // aをbで割った余り
  // 余りが0になるまで、ユークリッドの互除法を繰り返す
  while( remainder > 0 ){
    remainder = a%b; // 余り
    a = b; // aを更新
    b = remainder; // bを更新
  }
  // 最大公約数をコンソールに出力
  println(a);
}

ソースコード1　ユークリッドの互除法を用いて最大公約数を求めるプログラム

ソースコード1を、Processingの開発環境ウィンドウを開いて（スケッチ名を「calcbyEuclideanAlgorithm」としています）、テキストエディタ部分に書いて実行すると、図1のように、コンソールに72と15の最大公約数である「3」を出力します。

図1　スケッチ名「calcbyEuclideanAlgorithm」の実行結果

長方形を正方形で分割する

次に、ユークリッドの互除法の応用例として、長方形を正方形で分割する、次のような問題を考えてみます。

問題
縦306ピクセル、横135ピクセルの長方形をできるだけ大きな正方形に分割する。次に残った長方形に対して同じようにできるだけ大きな正方形に分割し、これを繰り返す。結果として、最初の長方形を正方形に分割することができる。

アルゴリズム設計（解法）

長方形の縦の長さを$${a}$$ 、横の長さを$${b}$$とします。ただし、$${a > b}$$とします。
①長方形をできるだけ大きな正方形で分割するので、その正方形は一辺の長さが$${b}$$の正方形だということがわかります。そして、この正方形は最初の長方形から、$${a}$$を$${b}$$で割ったときの商$${q}$$の値だけ分割することができます。$${a}$$を$${b}$$で割ったときの余り$${r}$$とすると、残った長方形は縦の長さが$${r}$$、横の長さが$${b}$$となります（図2）。

図2　長方形を正方形で分割する（最初のステップ）

② 次に残った縦の長さが$${r}$$、横の長さが$${b}$$の長方形に対して同じようにできるだけ大きな正方形に分割していきます。これは、$${a}$$を$${b}$$で、$${b}$$を$${r}$$でおきかえると、①の処理を再度行うことになります。

図3　長方形を正方形で分割する（2つ目のステップ）

③あとは、②の処理を$${r}$$が0になるまで繰り返すことになります。

これらの一連の処理はまさにユークリッドの互除法 b と同じものです。

プログラム

それでは、上記で説明した解法をもとに、長方形を正方形に分割していくプログラムを作成していきます。なお、長方形を正方形に分割する際に、図2のように最初のステップでは縦の方向に分割し、図3のように次のステップでは横の方向に分割する、というように長方形の分割は長方形の辺の長さが長い方向に分割していくことに注意が必要です。これに対処するために、変数の置き換えを行う際、分割する方向（縦か横か）を指定するようにしています。

// ユークリッドの互除法を用いて長方形を正方形に分割していく
void setup(){

  size(135, 306); // 最初の長方形のサイズ
  
  int a = height; // 縦方向の大きさ
  int b = width; // 横方向の大きさ
  
  int x, y; // 正方形の左上座標
  x = 0;
  y = 0;
  
  int quotient; // aをbで割ったときの商
  int remainder = 1; // aをbで割った余り
  int flag = 0; // flagが0であれば縦方向、1であれば横方向
  // 余りが0になるまで、ユークリッドの互除法を繰り返す
  while( remainder > 0 ){
    quotient = a/b; // 商
    remainder = a%b; // 余り
    for(int i=0; i<quotient; i++){ // 商の値だけ正方形を描く
      rect(x, y, b, b); // 左上の座標が(x,y)の位置にある一辺の長さbの正方形を描く
      if(flag == 0){
        y += b; // 正方形の左上座標を縦方向にbだけずらす
      } else {
        x += b; // 正方形の左上座標を横方向にbだけずらす
      } 
    }
    a = b; // aを更新
    b = remainder; // bを更新
    flag = (flag+1)%2; // flagを更新
  }
}

ソースコード2　ユークリッドの互除法を用いて長方形を正方形に分割するプログラム

ソースコード2を、Processingの開発環境ウィンドウを開いて（スケッチ名を「divideRectintoSquares」としています）、テキストエディタ部分に書いて実行すると、図4のように、実行ウィンドウのキャンバスに長方形をできるだけ大きな正方形で分割した結果の図形が得られます。

図4　スケッチ「divideRectintoSquares」の実行結果

まとめ

今回は、数学Aで学ぶ「ユークリッドの互除法」について、互除法を用いて最大公約数を求めるプログラムと互除法を応用して長方形を正方形で分割するプログラムを作成しました。
２つの自然数の最大公約数を求めるプログラムは記事『高校数学をプログラミングで解く（数学A編）「3-2 最大公約数と最小公倍数」』で紹介しています。その際は、２つの自然数についてそれぞれ素因数分解を行い、各冪の指数の小さい方を選んで掛け合わせるとそれが最大公約数となることを用いてプログラムを作成しました。そのプログラムと比べると、今回作成したユークリッドの互除法を用いて最大公約数を求めるプログラム（ソースコード1）はかなりシンプルになっています。このように、同じ結果を得るものでも計算手法が変わるとプログラムの大きさは変わってきます。そのため、プログラミングをする人はいろいろな計算手法を知っておいた方がよいです。

読んだ感想などをお寄せください

本記事を読んだ感想や質問などを以下のお問い合せフォームからお寄せください。感想、質問をいただいた方には本記事の演習問題の解答をプレゼントします。（お問合せフォームの本文に、本記事のタイトルを入れてください。）

お問い合わせ | note（ノート）

参考文献

改訂版 教科書傍用 スタンダード 数学A（数研出版、ISBN9784410209277）

数学から創るジェネラティブアート（巴山竜来著、技術評論社、ISBN9784297104634）

演習問題

次の２つの整数について、これらが互いに素の関係にあるか確かめるプログラムを作成してください。
(1) $${72, 35}$$
(2) $${72, 45}$$

演習問題の解答例