Search

最大公約数のアルゴリズムを応用、今度は最小公倍数をPythonで求めてみる - ITpro

全698文字

アルゴリズムを知り、その改良テクニックを学ぶことで、プログラミングの実力を高められる。Pythonを使って「最大公約数を求めるアルゴリズム」を改良していこう。

 数学の授業では、最大公約数と一緒に最小公倍数を学んだかと思います。最大公約数を求めるアルゴリズムがわかったので、それを応用して最小公倍数を求めるアルゴリズムを考えましょう。

足し算の繰り返しで最小公倍数を求める

 「引き算を繰り返して最大公約数を求められるのだから、足し算を繰り返せば最小公倍数を求められる」と思い付いたなら、鋭いです。その手順で最小公倍数を求められます。

 2つの数(自然数)AとBの最小公倍数は、「2つの数のうち、小さい方に元の値を足すことを、両者が等しくなるまで繰り返す」という手順で求められます。等しくなった値が、最小公倍数です。この手順のフローチャートを図1-11に示します。

図1-11 最小公倍数を足し算の繰り返しで求めるフローチャート

図1-11 最小公倍数を足し算の繰り返しで求めるフローチャート

[画像のクリックで拡大表示]

 このフローチャートは、第1回の図1-1に示した最大公約数を求めるフローチャートとよく似ています。

 この手順で、876と204の最小公倍数を求めると、図1-12のようになります。

図1-12 876と204の最小公倍数を足し算の繰り返しで求める手順

図1-12 876と204の最小公倍数を足し算の繰り返しで求める手順

[画像のクリックで拡大表示]

 全部で89回の処理を行って、14892という結果が得られます。

Adblock test (Why?)



from "応用" - Google ニュース https://ift.tt/Pm7jUHD
via IFTTT

Bagikan Berita Ini

0 Response to "最大公約数のアルゴリズムを応用、今度は最小公倍数をPythonで求めてみる - ITpro"

Post a Comment

Powered by Blogger.