コース: 試験対策：基本情報技術者試験 データ構造とアルゴリズム
今すぐ登録して、24,700件以上登録されている、業界エキスパート指導のコースを受講しましょう。
再帰で最大公約数を求める
最大公約数を求める ユークリッドの互除法も、 再帰で記述することができます。 どのように再帰で実現するのか、 学習しましょう。 最大公約数を求める有名なアルゴリズムに、 ユークリッドの互除法があります。 ユークリッドの互除法とは、 整数 m と n があるとき、 m を n で割ったときの余りを r とすると、 m と n の最大公約数は、 n と r の最大公約数でもある という理論を、 余り r が０になるまで 繰り返すことによって、 m と n の最大公約数を求める というものです。 ユークリッドの互除法を 具体的に示してみます。 例えば 28 と 20 の最大公約数を 求める場合を考えてみます。 まず、m が 28、n が 20 なので、 余り r は８になります。 次に、m と n の関係を n と r の関係に置き換えます。 すると m が 20 で n が8になるので r は４になります。 さらに m と n の関係を n と r の関係に置き換えます。 すると m が８で n が４になるので、 r は０になります。 余り r が０になったときの除数 n が 最大公約数なので 最大公約数は４になります。 このように、 ユークリッドの互除法は 同じ処理を連続的に繰り返します。 これが、再帰で書き直せる理由です。 では、コードを見てみましょう。 このコードは、先ほどの説明を そのまま疑似言語に直したものです。 再帰は使用していません。 関数 gcd は、 整数型の引数 m と n の 最大公約数を求めて返却します。 while(true) は無限ループです。 常に真で偽になることはないので、 ループを終了することはありません。 ただし無限ループは、 必ずある条件で ループを脱出するように記述します。 m と n の余りを計算します。 なお、mod は割った余りを表します。 r が０になった場合に ループを終了します。 m に n を代入し、 n に r を代入することによって、 m と n の関係を n と r の関係に置き換えます。 r が０になった場合に ループを終了すると、 n が最大公約数なので、n を返します。 では、ユークリッドの互除法を 再帰で考えてみましょう。 最大公約数を求める関数 gcd を 引数 m と n で呼び出した場合、 m…
コースをダウンロードして学習しましょう。
ラーニングコースをダウンロードしてオフラインで視聴しましょう。ダウンロードしたコースはLinkedInラーニングのモバイルアプリ (iOSまたはAndroid) で視聴できます。