はじめに
やあ、こんにちは。今日は『最大公約数プログラム』を作成してみよう。
はい、よろしくお願いします。
ところでヒロトよ、最大公約数を求める最も強力な方法は何か知っているかな？
はい！それは『ユークリッド互除法』です。
うむ、流石だな。今回はそのユークリッド互除法をプログラムで書くことが目的だ。まずは復習として手計算で計算してみよう。168と324の最大公約数をユークリッド互除法で求めよう。
ユークリッド互除法
はい、手計算では次のようになります。
まず、小さい数を左、大きい数を右に並べて書きます。
次に324を168で割るのですが、商の1を324の右側に書きます。そして、普通の割り算のように余りの156を下図のように書きます。
次に168を余りの156で割ります。上と同様に商の1を168の左側に書きます。そして普通の割り算のように余りの12を下図のように書きます。
ここで、12と156が左右に並びました。これらに上とまったく同様の計算をしていきます。156を12で割ると、商が13で余りが0になります。今回はこの時点で余りが0になりました。
このように余りが0になったら、ユークリッド互除法はストップします。このとき、下図のように最大公約数は12ということになります。
うむ、完璧だ！
実際にプログラムを書くときは、余りを求めてくれる演算『％』や、『while文』をうまく使えばできるはずだ。では、頑張って書いてみよう！
はい、頑張ります！
今回は『file52』から書いていきます。
オリジナルの解答『最大公約数プログラム』
約20分後
できました！これはかなり考えました。結果は次のようになります。
これからプログラムの説明をします。
まず1，2行目で二つの正の整数をキーボードから入力します。上の例では24と36を入力しました。4行目から12行目までのif-else文は、変数Aに大きい方が代入され、変数Bに小さい方が必ず代入されるように細工しました。つまり、キーボードから二つの正の整数を代入するとき、大小関係を気にしなくていいということです。
なるほど、『最初に大きい整数を代入しなくてはいけない』というようなしばりがないというわけだな！うむ、素晴らしい工夫だ。
そして、14行目から21行目までがユークリッド互除法のプログラムです。while文の条件を『AとBが共に0に等しくない』としました。この条件を満たす限り処理はループします。その処理は大きい数Aを小さい数Bで割ってその余りをAに上書きするというものです。もし余りが0ならAはBで割り切れたということなので最大公約数Bを表示します。AをBで割った余りが0でないときは、今度はBを余りが代入されたAで割ってその余りをBに上書きします。もし余りが0ならBはAで割り切れたということなので最大公約数Aを表示します。余りが0でないならwhile文のループが繰り返されます。最終的に最大公約数が表示されたとき、AかBが0に等しくなったということなので、while文のループも終了します。
素晴らしい！感動をするレベルだぞ！
はい、ありがとうございます！
けっこう難しい問題も自分の力で考え、試行錯誤してプログラムを書けるようになってきたと思うぞ。ぜひ、今回作ったオリジナルのプログラムを大事にしてほしい。
はい、気づいたら自分で考えて書けるようになってきた感じです。
うむ、その調子で今後も頑張っていこう。では今日はお疲れさん。
はい、ありがとうございました。
コメント