おはようございます.
今日もいまいち寝れないので,整数をいじくろうと思います.
今回は「はじめての数論」から,Euclidの互除法のコードを実際に書きなさいという問題をやっていきます.
問題文
演習問題 5.2 ですね.
2つの整数 $a,b$ の最大公約数 $\mathrm{gcd}(a,b)$ を計算するプログラムを書け.プログラムは $a,b$ のいずれか1つが $0$ であってもうまく働くようにせよ.
よく知られたEuclidの互除法を実際にコードで書きなさいという問題です.
どうせググったら答えが出てきますが,まあ自分でやってみましょう.
回答
最終的には特定の言語で実装したいですが,まずはプログラミング言語に依存しないレベルの話をしたいので,疑似コードで書くことにします.
$a$ を $b$ で割って余りを求める時に,$b=0$ だと多分困るんですよね.だからまず最初に $b=0$ かどうかで条件分岐を入れて…….あと変数が $x,y,r$ の3つ必要なはずだから最初にそれを定義して……とやっていったらこんな感じになりました.
いいんじゃないかな,たぶん.
具体的に値を代入してテストした感じではいけそうです.
$a,b$ は0以上だと勝手に仮定していますが,別に問題ないと思います.負の数だったら絶対値をとって置き換えればいいだけです.
ただ,ちょっとパッと見て意味がわかりづらいコードになってしまっている気がします.
while ループの外側と内側でそれぞれ $r$ を計算していますが,実質的に同じことをやっているので1行でまとめた方がきれいですね.
また,while ループを抜ける条件が $r = 0$ なんですけど,Euclidの互除法の手続きって, $\mathrm{gcd}(x,y)$ の引数をどんどん小さくしていってどちらかがゼロになったら停止するというものなので,ループを抜ける条件を $y=0$ にしたいんですよね.
また $r$ という変数は,手続きを記述するための補助的な変数で,$x,y$ がメインなんだという感じを出したいので,$r$ の出現範囲を while ループの中に限定したいところです.
以上,もろもろの不満点を考えて修正したものがこちらのコードです.
赤文字で書いてあるのはコメントです.//
が付いてるとコメントっぽいかなと思ってつけました.
$\mathrm{gcd}(a,b) = \mathrm{gcd}(x,y)$ という条件を保ちながら,$x,y$ をガンガン小さくしていくアルゴリズムなのだということを明確にしています.
ちゃんと動くかどうかあんまりテストしていませんが,まあそれは後で実装して確かめることにしましょう.
感想とまとめ
今回は疑似コードを用いて遊んでいただけですが,なんだかプログラミングをしている気分になりました.
書いてる時すごく思ったんですけど,コードってすごく見づらいんですね!
変数がどういう意味なのかとか,while ループを回している間に何が変化しなくて何が変化するのかとか,自分で書いてても全然わからない.
プログラムの正しさを検証する,プログラミング意味論という分野がありますが,ちょっと勉強してみたくなりました.
今回,「while ループを回しても普遍な条件をコメントとして書く」みたいなことは自分でおもいついてやったことですけど,そういう我流ではなくてきちんと勉強してみたいなと.