高校数学10分プログラミング(48日目、2024年8月7日)
おはようございます。
今日は、高校数学10分プログラミングの48日目です。
本日の課題は、ユークリッドの互除法を用いて最大公約数を求めるプログラムを作成することです。
ユークリッドの互除法
a. 2つの自然数$${a,b}$$について、$${a}$$を$${b}$$で割ったときの商を$${q}$$、余りを$${r}$$とすると、$${a}$$と$${b}$$の最大公約数は、$${b}$$と$${r}$$の最大公約数に等しい。
b. aの性質を利用すると、2つの自然数$${a,b}$$の最大公約数を求めるには、次の手順を繰り返す。
i. $${a}$$を$${b}$$で割ったときの余りを$${r}$$とする。
ii. $${r=0}$$ならば、$${b}$$が$${a}$$と$${b}$$の最大公約数である。
$${r>0}$$ならば、$${a}$$を$${b}$$で、$${b}$$を$${r}$$でおきかえて、iに戻る。
この手順を繰り返すと余り$${r}$$が小さくなり、$${r}$$が$${0}$$になって必ず終了する。
課題
$${72}$$と$${15}$$の最大公約数をユークリッドの互除法を用いて算出して、結果をコンソールに出力するプログラムを作成してください。
ヒント
今回の課題は、上記ユークリッドの互除法bをそのまま実装することで実現することができます。
それでは、よろしくお願いします。
MK's papa
この記事が気に入ったらサポートをしてみませんか?