【C言語入門の次】 第02回 最大公約数と最小公倍数

https://youtu.be/LHQ5IhgL-M8

$\textcolor{pink}{四国めたん: }$教師役ですわ

$\textcolor{lime}{ずんだもん: }$生徒役なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ こんにちは。四国めたんです

$\footnotesize \textcolor{lime}{ずんだもん:}$ ずんだもんなのだ。こんにちはなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は最大公約数と最小公倍数の求め方についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 小学校で習ったのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、でも今回はコンピューターで求める方法をお話ししますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

最大公約数

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、最初は自然数に対する 最大公約数 についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 2つの自然数nとmについて、両方に共通する約数の内、最大の整数が 最大公約数 なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 最大公約数 の求め方は幾つもありますが、今回は、プログラムと相性のいい ユークリッドの互除法 を使いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ユーグリッドの互除法 について詳しく教えて欲しいのだ

ユークリッドの互除法

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 ユークリッドの互除法 では、このようにして 最大公約数 を求めますわ

1. 2つの自然数nとmについて $n > m$ とする
2. nをmで割った余りをrとする
3. mとrの 最大公約数 が、nとmの 最大公約数 となる

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、$n > m$となる自然数nとmを考えますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そしてnをmで割った余りをrとしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 余剰計算なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後にmとrの 最大公約数 がnとmの 最大公約数 となりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ いまいちピンと来ないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 数学的には 最大公約数 を求める関数"gcd"はこのようになりますわ

$$r = n \mod m \\ gcd(n, m) = gcd(m, r)$$

$\footnotesize \textcolor{pink}{四国めたん:}$ これを繰り返して、$r = 0$ となった時のmが最大公約数ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 再帰関数 を使うと判り易いプログラムになりそうなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに ユークリッド は紀元前3世紀頃の数学者、天文学者ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、ユークリッド幾何学の方が有名かもしれませんわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ しかし2300年程前の数学者が、コンピューターも無い時代に、このようなアルゴリズムを考案するのは凄いと思いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしかにその通りなのだ

ユークリッドの互除法の証明のようなもの

まず、2つの自然数nとmがあるとします

ここで $n > m$ とします

$n = m$の場合には、剰余が0なのでm(= n)が 最大公約数 です

ここでnをmで割った商をq、余りをrとすると $n = qm + r$ となります

nとmの 最大公約数 をgとすると、

$$\frac{n}{g} = \frac{qm + r}{g} \\ \frac{n}{g} = \frac{qm}{g} + \frac{r}{g}$$

となります

$n / g$ は自然数なので、$qm/g + r/g$ も自然数です

mはgで割り切れますので、$qm / g$も自然数となります

つまり、$r / g$ も自然数でなければなりません

結果としてmとrの 最大公約数 はgとなります

最大公約数の計算をやってみよう

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは 最大公約数 を求める関数を実装してみましょう

#include <conio.h>
#include <stdio.h>

int greatest_common_divisor(int n, int m) {
  int rc = -1;
  if ((n >= 0) && (m >= 0)) {
    if (m == 0) {
      rc = n;
    } else {
      rc = greatest_common_divisor(m, (n % m));
    }
  }
  return rc;
}

int main(int argc, char* argv[]) {
  int c0 = 0;
  int c1 = 0;
  do {
    printf("数値を2つ入力して下さい(ESC:終了)\n");
    c0 = _getch();
    if ((c0 <= '9') && (c0 >= '0')) {
      c1 = _getch();
      if ((c1 <= '9') && (c1 >= '0')) {
        int n = c0 - '0';
        int m = c1 - '0';
        int gcd = greatest_common_divisor(n, m);
        printf("%dと%dの最大公約数は%dです。\n", n, m, gcd);
      }
    }
  } while ((c0 != 27) && (c1 != 27));  // ESCの入力
}

最大公約数の関数

$\footnotesize \textcolor{lime}{ずんだもん:}$ まず 最大公約数 の関数greatest_common_divisorの説明をお願いするのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、引数に2つの負ではない整数を指定すると、その 最大公約数 を返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ どちらかが負の整数の場合は、負数(-1)が返りますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最初に戻り値"rc"を-1、つまり引数のどちらかが負の整数の場合の戻り値で初期化していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に引数のどちらも負ではない整数であることをチェックしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ どちらも0か正の整数である必要があるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ その次に、2番目の引数mが0の場合には、1番目の引数nをそのまま戻り値"rc"としますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ これが 再帰関数 greatest_common_divisorの終了条件となるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ その通りですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なお、どちらの引数も0の場合には、0が返るのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、終了条件に該当しない場合は ユークリッドの互除法 を適用しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ つまり2番目の引数と、引数同士の割り算の余りで、再度greatest_common_divisorを呼び出すのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに2回目以降のgreatest_common_divisor関数の呼び出しでは、引数が負の整数ではないことが保証されますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ ですので、2回目以降は最初の引数の負数チェックは必要ありませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ですので、メイン関数で最初にgreatest_common_divisor関数を呼び出す前にチェックすれば、この部分は省けますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

メイン関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、メイン関数ではdo～whileループを使用しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最初にキーボードから「2つの数値の入力」を促すと共に、_getch()関数で1文字の入力を2つ待ちますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ キーボードからの入力は、最初に宣言している変数"c0"と"c1"に代入するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そしてif文でキーボードからの入力が0～9の数値なのを確認しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 確認はだいじなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 確認できたらc0 - '0'やc1 - '0'で入力された'0'～'9'の文字を整数の0～9に変更しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よく使われるテクニックなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、変換された0～9の整数を引数にgreatest_common_divisor関数を呼び出して 最大公約数 の計算をおこないますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 得られた値はコンソールに出力するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、whileの条件式で、キーボードの入力のどちらかが$\fcolorbox{blue}{lightgray}{ESC}$かどうかをチェックしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしか、27と比較しているのは、ASCIIコード表で$\fcolorbox{blue}{lightgray}{ESC}$に相当する整数値が27だからなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、キーボードの入力のどちらかが$\fcolorbox{blue}{lightgray}{ESC}$ならwhileループを抜け、プログラムを終了しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実行してキーボードから9と3、8と4を入力した後、$\fcolorbox{blue}{lightgray}{ESC}$で終了してみましょう

最大公約数の計算はループでもできます

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回 最大公約数 の計算は 再帰関数 になっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 当然、ループに変えることができるのだ

int greatest_common_divisor(int n, int m) {
  int rc = -1;
  if ((n >= 0) && (m >= 0)) {
    while (m > 0) {
      int t = n % m;
      n = m;
      m = t;
    }
    rc = n;
  }
  return rc;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ 最初に戻り値"rc"を-1、つまり引数のどちらかが負の整数の場合の戻り値で初期化していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に引数のどちらも負ではない整数であることをチェックしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ チェックは大事なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ その次に、whileループ中で ユークリッドの互除法 をおこなっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ メイン関数は同じなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実行してキーボードから9と3、8と4を入力した後、$\fcolorbox{blue}{lightgray}{ESC}$で終了してみましょう

最小公倍数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に自然数に対する 最小公倍数 についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 2つの自然数nとmについて、両方に共通する 倍数 の内、最小の整数が 最小公倍数 ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ その通りなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 2つの自然数nとmの 最小公倍数 "lcm"は、 最大公約数 "gcd"を用いて、このように求めることができますわ

$$lcm = \frac{nm}{gcd}$$

$\footnotesize \textcolor{lime}{ずんだもん:}$ 意外に簡単なのだ

最小公倍数を最大公約数から求めることができることの理由

2つの自然数nとmについて、 最大公約数 "gcd"に対して以下のような自然数aとbがあります

$$n = gcd \times a \\ m = gcd \times b$$

ここで、aとbは互いに素、つまり公約数が1の関係にあります

公約数が1以外に存在すると、nとmの 最大公約数 が"gcd"ではなくなってしますからです

ここで、nとmの公倍数をlとすると、$l = i \times n = j \times m$ のような自然数iとjが存在します

nとmを"gcd"を使って置き換えると、$l = i \times gcd \times a = j \times gcd \times b$ となります

gcdで割ると $l / gcd = i \times a = j \times b$ となります

ここで、aとbは互いに素であるため、iはbの倍数、jはaの倍数である必要があります

つまり、$i = p \times b$ や $j = p \times a$ のような自然数pが存在します

このiとjを用いると、nとmの公倍数lは $l = p \times b \times gcd \times a = p \times a \times gcd \times b$ となります

最小公倍数 "lcm"は公倍数の内の最小の値なので、$p = 1$として、$lcm = gcd \times a \times b$ となります

両辺に 最大公約数 "gcd"を掛けると$lcm \times gcd = gcd^2 \times a \times b$となります

これを変形して、$lcm \times gcd = (gcd \times a) \times (gcd \times b) = n \times m$ です

つまり $lcm = \frac{nm}{gcd}$ となります

最小公倍数の計算をやってみよう

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは 最小公倍数 を求める関数を実装してみましょう

#include <conio.h>
#include <stdio.h>

int greatest_common_divisor(int n, int m) {
  int rc = -1;
  if ((n >= 0) && (m >= 0)) {
    while (m > 0) {
      int t = n % m;
      n = m;
      m = t;
    }
    rc = n;
  }
  return rc;
}

int least_common_multiple(int n, int m) {
  int rc = greatest_common_divisor(n, m);
  if (rc > 0) {
    rc = n / rc * m;
  }
  return rc;
}

int main(int argc, char* argv[]) {
  int c0 = 0;
  int c1 = 0;
  do {
    printf("数値を2つ入力して下さい(ESC:終了)\n");
    c0 = _getch();
    if ((c0 <= '9') && (c0 >= '0')) {
      c1 = _getch();
      if ((c1 <= '9') && (c1 >= '0')) {
        int n = c0 - '0';
        int m = c1 - '0';
        int lcm = least_common_multiple(n, m);
        printf("%dと%dの最小公倍数は%dです。\n", n, m, lcm);
      }
    }
  } while ((c0 != 27) && (c1 != 27));  // ESCの入力
}

最小公倍数の関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 最大公約数 の関数greatest_common_divisorはそのままで、 最小公倍数 の関数least_common_multipleを追加しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 引数に2つの負ではない整数を指定すると、その 最小公倍数 を返す関数なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ どちらかが負の整数の場合は、負数(-1)が返りますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、0を含む数値の 最小公倍数 は0としていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ まず最初に戻り値"rc"を 最大公約数 の関数greatest_common_divisorの戻り値で初期化していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 引数が負の整数かどうかのチェックはどうするのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 引数が負の整数かどうかのチェックは、greatest_common_divisor関数でおこなわれるので不要ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ わかったのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、greatest_common_divisor関数の戻り値が0ならば、引数に0が含まれていることを意味しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ もし、greatest_common_divisor関数の戻り値が自然数であれば、引数同士を掛けて 最大公約数 、つまりgreatest_common_divisor関数の戻り値"rc"で割ることで 最小公倍数 を得られますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なぜ $n \times m / rc$ ではなく、$n / rc \times m$ としているのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ $n \times m$ が大きな値となる場合、計算できなくなる可能性があるので、先に割り算をしているのですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数は 最大公約数 の場合と概ね同じですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 関数の呼び出しと出力する文章が変わっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、実行してキーボードから9と3、8と4を入力した後、$\fcolorbox{blue}{lightgray}{ESC}$で終了してみましょう

まとめ

$\footnotesize \textcolor{pink}{四国めたん:}$ お疲れさまでした

$\footnotesize \textcolor{lime}{ずんだもん:}$ おつかれさまなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 以上で 最大公約数と最小公倍数 を終了しますわ