新卒や転職でエンジニアを目指す方で,コーディングテスト対策に取り組んでいますか?
この記事では,コーディングテストでも使うことのあるユークリッドの互除法についてSwiftを用いて解説します!
ユークリッドの互除法は,高校の数学の授業で出てくるあれですね笑
コーディングテスト対策になれば幸いです.
また,Swiftの勉強を頑張っている方の励みになると嬉しいです!
ユークリッドの互除法とは?
ユークリッドの互除法とは,
2つの自然数の最大公約数(Greatest Common Divisor, GCD)を効率的に求めるためのアルゴリズムです.
高校の数学で習ったやつですね笑
手順としては下記の通りになります・
- a と b を用意する.
ただし、 a ≧ b であると仮定する(もしa < b ならば a と b を入れ替える) - a を b で割り、商 q と余り r を求める.
つまり、次のように表されます:
a = b × q + r 余り r が 0 であれば、 b が最大公約数となる.
もし r ≠ 0 であれば、 a を b に、 b を r に置き換えて
手順2を繰り返
す.
手順を書くと上記の通りですが,少し分かりづらいと思います..
よくわからないという方は以下の例を見ると思い出すのではないでしょうか??
a = 252 と b = 105 の最大公約数を求めるとする.
- 252 ÷ 105 = 2 余り 42 (つまり、 252 = 105 × 2 + 42 )
- 105 ÷ 42 = 2 余り 21 (つまり、 105 = 42 ×2 + 21 )
- 42 ÷ 21 = 2 余り 0 (つまり、 42 = 21 ×2 + 0 )
余りが0になったので、この時点で最大公約数は21と求まる.
なぜこの手順で最大公約数が求まるのかアルゴリズム・証明の部分までは解説しませんが,
やり方を思い出せたでしょうか.
それでは実際にSwiftを用いてどのようにユークリッドの互除法を実装するのかを続いて解説していきます!
Swiftを用いたユークリッドの互除法
Swiftでのコード解説
Swiftを用いてユークリッドの互除法は以下のコードになります.
func gcd(_ x: Int, _ y: Int) -> Int { if y == 0 { return x; } else { return gcd(y, x % y); } } let num1 = 15 let num2 = 5 let gcd = gcd(num1, num2)
あまりが0となるまで繰り返すことでユークリッドの互除法を実装することができます.
ちなみに,num1≧num2を判別する必要があるのでは?と考えた方もいるのではないでしょうか?
このコードでは実は,その必要がありません.
実際に計算してみると,5÷15=0あまり5 → 15÷5=…のように勝手に入れ替わってくれます.
ただ明示的に表したい場合は.以下のコードに変更すると良いと思います!
func gcd(_ x: Int, _ y: Int) -> Int { if x < y { return gcd(y, x) // 入れ替える } if y == 0 { return x } else { return gcd(y, x % y) } } let num1 = 15 let num2 = 5 let gcd = gcd(num1, num2)
こちらのコードのほうが,
直感的にはアルゴリズムのミスがないことがわかりやすくなりますね!
ちなみに,こういったわかりやすいコードを書くための技を身につけることができる
コーディング界における良書:リーダブルコードは非常におすすめです!
(私自身もこの本を読んでから,リーダブルコード内に紹介されたルールに則ってコーディングをするように心がけ始めました!)
ユークリッドの互除法の活用事例
今回紹介したユークリッドの互除法は
- 単純に最大公約数を求める問題だけでなく
- 他のアルゴリズムの中で,最大公約数を必要とする問題
(文字列の最大の共通文字列を見つける問題 etc.
で応用することができます.
他のコーディングテストに関するアルゴリズムについても紹介していく予定なので,ぜひお楽しみに!
ちなみに私は無料でコーディングテスト対策を行えるLeetCodeを用いて,コーディングテスト対策をしています!
皆さんのコーディングテスト対策の方法についても,教えてくれると嬉しいです!
SNSやお問い合わせから気軽にご連絡下さい!
おわりに
このブログでは,SwiftやFlutterなどの日々学びつつアウトプットしています.
また,間違いや改善点があれば,ご指摘いただけますと幸いです!