Help us understand the problem. What is going on with this article?

アルゴリズム入門[最大公約数]

[追記]
@il9437 さんに標準入力が負数だった場合、無限ループになってしまっていたので、修正を加えました。コメントまでお読みください

まずアルゴリズムの学習を始めるにあたって最初に考え方をインプットしておきましょう
まずコンピューターの処理の種類は四つしかありません
入力記憶演算出力のみです

アルゴリズムと聞くと難しいと思うかもしれませんが、この4つを組み合わせて最高の処理の形を探すだけです

同様にして処理の流れも三つしかありません
順次分岐繰り返しのみです

次に問題を解くコツ4つを見ていきましょう

  • 処理の区切りを考える
  • キリの悪い数字を疑う
  • 数値の変化を追う
  • 計算量は無視してとりあえず動くようにしてみる
  • より良い処理を考える

こんな感じですね

ここを抑えてユークリッドの互除法を考えていきましょう
そもそもユークリッドの互除法とは二つの最大公約数を求めるアルゴリズムです

二つの整数の大きい方から小さい方を引くことを二つの整数が等しくなるまで繰り返す
等しくなった値が最大公約数

ではまずなぜそうなるのかを考えましょう

10025の最大公約数を求めていきましょう
100=5^2*2^2
25=5^2ですね
つまり共通している5^2最大公約数
これを上のアルゴリズムで計算すると

100>25なので
100-25=75
75>25なので
75-25=50
50>25なので
50-25=25
25=25
なので最大公約数は25

ではなぜこうなるのかを解説していきます
縦25、横100の長方形から縦25、横25の正方形を取り除くことができるのでユークリッドの互除法です

* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *

しかしこれだと数が大きくなれば大きくなるほど、計算回数が増えてしまうため、
剰余を求めてやるのが先ほど紹介したコツにある、より良い処理を考えるというところになります

function euclidean(int $x, int $y) {
    if ($x < $y) return euclidean($y, $x); 
    if ($y == 0) return $x;
    return euclidean(abs($y), intval($x % $y));
}

まず$x >= $yの状態を作りたいので$xの方が$yよりも小さい場合は数値を入れ替えて計算しなおします
また$y0の場合も必ず$xになる上に割る数のエラーが出てしまうので$xを返しています

satorunooshie
経済学を学んでいる大学三年生です PHP, Kotlinを中心に学習しています 役に立てそうな英語の記事や詰まったところを共有していきます
https://satorunooshie.net
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away