初歩的な数学のアルゴリズムを考えてみよう

はじめに

こんにちは。よっしーと申します。
私の趣味の一つに数学があるのですが数学の公式や定理をプログラミングで実装したりすると
アルゴリズムの勉強になったり、頭の体操になったりしますので今日はその紹介をしようと思います。
今回は最大公約数を求めるアルゴリズムを考えてみます。
素直に求めるやり方と、効率よく求める方法を考えてそれぞれコードに落とし込んでみます。

最大公約数を求める

最大公約数って何

2つの正の整数の共通の約数のうちの最大のものを最大公約数と言います。

例えば、72 と 1620 は以下で表せます。

 $ 72 = 2 \times 36 $
 $ 1620 = 45 \times 36 $

互いに36という約数を持っており、2数で共通の約数はもう持てません(2と45で共通の約数はない)。
そのため、72と1620は共通の約数で最大のものは36となります。
36は72と1620の最大公約数です。

最大公約数の求め方

愚直にやってみます。
いきなり36と出すのは難しいので、まず2数を素因数分解します。

 $ 72 = 2^3 \times 3^2 $
 $ 1620 = 2^2 \times 3^4 \times 5 $

このうち、出てきた素因数で、お互いに登場している数のうち指数が小さい数を取得し掛け算すれば最大公約数が求まります。
ここでは、2という素因数と3という素因数が2数で登場しています。
そのうち $ 2^2 $, $ 3^2 $ を取得すればそれの掛け算である36が最大公約数です。

これをプログラムで求める

先程の最大公約数の求め方を実装してみます。
実装は先程の求め方に忠実に行います(よりいいアルゴリズムがあるかもしれませんが、忠実に再現します)。
言語はC#です。

これで求めることができました。
手順としては

  1. 素因数分解に必要な素数を準備
  2. 2数を素因数分解する
  3. 素因数の中から最大公約数を見つける

という手順を用いました。

ユーグリッド互除法により最大公約数を求める

今度は少し複雑な数を考えてみましょう。
3355と11895の最大公約数を求めてくださいと言われたらどうしますか?
プログラムでやるなら今まで説明してきた方法でもすぐに解答が出ます。
しかし、人の手で計算するとなると、素因数分解がやや面倒です(2, 3, 5….で割れるかいちいち試すのは少し面倒)。

最大公約数を求める方法としてユーグリッド互除法というものがあります。

手法としては以下です

  1. 大きい数を小さい数で割る
  2. あまりが出た場合、先程割った小さい数をあまりで割る
  3. 更にあまりが出た場合、手順2で割った数をあまりで割る
  4. 手順3をあまりが0になるまで続ける
  5. 最後に割った数が最大公約数

先程あげた数で行うと以下です

 $ 11895 \div 3355 = 3 $ あまり  $ 1830 $
 $ 3355 \div 1830 = 1 $ あまり  $ 1525 $
 $ 1830 \div 1525 = 1 $ あまり  $ 305 $
 $ 1525 \div 305 = 5 $ あまり  $ 0 $

よって305が3355と11895の最大公約数となります。
この証明方法は特に解説しませんが、詳しく知りたい方はユーグリット互除法と調べていただけると出てきます。

これをプログラムに落とし込む

上記のユーグリット互除法をプログラムで書いてみましょう。
手順4あたりで同じ操作を何度も繰り返していることがわかると思います。
プログラムでは、再帰的なメソッド呼び出しになりそうという予想が立ちます。
言語はまたしてもC#です。

とてもシンプルなメソッドになりました。
それに、やってることもわかりやすいと思います。
(元々割っていた数字をあまりで割っていくという構図)

終わりに

2つの方法で最大公約数を求めるアルゴリズムを考えてみました。
後者のコードはより簡単な計算手法を考えてからコードに落としたこともあり、相当スッキリしたコードになりました。
数学の公式というのは複雑な計算を、より簡単な計算式や、容易な考え方に落とし込んだものが本質となります。
アルゴリズムを考えるときも同じようにどのような計算方法で行えば楽なコードが書けるかを考えてみると今後の開発の役に立つかもしれません。
そういうトレーニングをしたい場合は数学の公式の成り立ち等を勉強してそれをコードに落とし込んだりすると練習になるかもしれません。
ここまで読んでくださった皆様ありがとうございます!ではまた。

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP