優れたアルゴリズムですね。
ユークリッドの互除法は、2つの自然数 m, n (m ≧ n) について、m の n による剰余を r とすると、 m と n との最大公約数は n と r との最大公約数に等しいという性質を利用して、2つの自然数の最大公約数を求める方法です。
m を n で割った余りを r とし、次に
n を r で割った余りを s とし、
r を s で割った余りを t とし、、、、を続けて
余りが 0 となった場合に、割った数が m とn の最大公約数です。
例として、510 と 357 の最大公約数を求めるユークリッドの互除法を図示しました。
これをそのまま、swift のプレイグラウンドでコーディングしてみました。最大公約数を求めるユークリッドの互除法です。
ところで、変数A に格納した値と、変数B に格納した値を交換する場合は、第3の変数C をテンポラリーに使います。例えば、次の通りです。
変数A 変数B 変数C
1071 1029 -
1071 1029 1071 ※ 変数A「1071」→変数C・・・「1071」
1029 1029 1071 ※ 変数B「1029」→変数A・・・「1029」
1029 1071 1071 ※ 変数C「1071」→変数B・・・「1071」
次に再帰呼び出しを使っての最大公約数を求めるユークリッドの互除法の swift コーディングです。
再帰呼び出しとは、ある関数の中から自分自身、つまりその関数自身を呼び出すプログラミング技術です。無限ループにならないように留意する必要がありますが、同じ処理を連続的に行う場合に使われ、ループ処理を使うよりソースコードが単純で、きれいに見えるという特長があります。
関連記事:
最大公約数、最小公倍数 - swift programming : R for Radio
関連リンク:
アルゴリズム:最大公約数を求めるユークリッドの互除法 - GameSprit
アルゴリズム:最小公倍数と最大公約数を求めるjavascript - GameSprit