2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

Pythonでユークリッドの互除法を再現

Last updated at Posted at 2019-12-14

## はじめに
###これは超初心者による備忘録です
今回は初めての投稿です。
pythonをやり始めて一週間。まだまだヒヨッコなので、ネットで見つけた問題集で練習しております。

その時に見つけた問題がうまく解決できなかったので備忘録として記事を残します。

超初心者の方は必見です!!!

###ユークリッドの互除法とは
簡単にいえば、最大公約数を機械的に求めることができる計算方法。

計算方法
①調べたい2つの自然数を用意する
②大÷小をする
③余りが出たら、小さいほうの数字とそのあまりの最大公約数が元の2数の最大公約数と一致している。
④これを繰り返すことで、簡単な数字で最大公約数がわかる

まあこんな感じです。わかりにくくてすいません。

実際にやってみる

それではコードを書いていきます。
まずは新しい関数gcd()を定義します

def gcd(a,b) #関数を定義

関数を自分で定義するのはdefを使います。

次に、この関数が行う処理を書いていきます。
ユークリッドの互除法では、何度も計算を繰り返さなくてはなりません。
そのため、次のような条件分岐が必要になります。

①余りが出なくなったとき(割り切れた時)、そこで計算終了
②余りが出れば、計算を継続

2つの場合に合わせて、処理が分かれるわけですね。
つまり、ifをつかえばよさそうです!

よって、下のようなコードになると思います。

def gcd(a,b) #関数を定義
#①のとき
    if b == 0
        return a
#②のとき
    else:
        return gcd(b,a%b)

これで、書き終わりました!!!
あとは、自分の好きな2数を自由に入力できるように、input関数を使い、結果を出力するためにprint関数をつければよさそうです
↓が完成形となります。

a,b = input(),input()

#整数に変換
a,b = int(a),int(b)

#関数を定義
def gcd(a,b) 
#①のとき
    if b == 0
        return a
#②のとき
    else:
        return gcd(b,a%b)
#結果を出力
print(gcd(a,b))

これで完成です!!

##まとめ
今回はユークリッドの互除法をpythonであらわしました。

最初は、inputがうまくいかずエラーが出てたんですけど、intをくっつけたらうまくいきました。
なんでかはよくわかんないので、その辺を教えていただけたら嬉しいです。
※追記
コメントで教えていただきました!
理由は、型の違いだそうです。
inputはユーザーの入力した”文字列”を受け取る関数なので、strです。
一方、gcd関数で想定している型はintなので、型が合わず、エラーが発生するとのこと。
つまり、int関数で整数に変換すると、うまくいくわけですね。

※さらに追記
再びコメントで教えていただきました!
python 3.5以降であれば、mathライブラリに私が作ったような機能があるそうです!

最後まで読んでいただきありがとうございました!!!
なにかアドバイスなどあれば気軽にお願いします!

2
3
5

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?