iOS プログラミング言語である swift を使って、ユークリッドの互除法による最大公約数を求めるコードを書いてみました。
 
ユークリッドの互除法:最大公約数を求める : R for Radio で確認したことは次の通りです。
優れたアルゴリズムですね。

ユークリッドの互除法は、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 の最大公約数を求めるユークリッドの互除法を図示しました。

互除法1


これをそのまま、swift の
プレイグラウンドでコーディングしてみました。最大公約数を求めるユークリッドの互除法です。

互除法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

再帰呼び出しとは、ある関数の中から自分自身、つまりその関数自身を呼び出すプログラミング技術です。無限ループにならないように留意する必要がありますが、同じ処理を連続的に行う場合に使われ、ループ処理を使うよりソースコードが単純で、きれいに見えるという特長があります。




関連記事:
最大公約数、最小公倍数 - swift programming : R for Radio

関連リンク:
アルゴリズム:最大公約数を求めるユークリッドの互除法 - GameSprit
アルゴリズム:最小公倍数と最大公約数を求めるjavascript - GameSprit