センター入試試験の数学
朝刊にセンター試験の問題が掲載されていました。中でも目を引いたのは数学。ユークリッドの互除法がプログラムで出ていた。 高校時代は数学が嫌いで、２年間理数の勉強はしていませんでした。高校数学でユークリッドの互除法って出てくるんですか？
ユークリッドの互除法は最大公約数を引き算で求める方法。ユークリッドさんが考えました。プログラムの勉強をすると、分岐処理と繰り返し（ループ）処理の演習課題なんかでよく出ます。分岐処理というのは、条件によって処理をわけること。IF文がその代表格です。繰り返しは、与えられた条件が成り立つ間、処理を繰り返すこと。WHILE文やFOR文が代表的。
最大公約数は２つの整数の共通の約数、つまりあまりが出ない整数値を求めて、その最大の値をとることです。学校で習うやり方は掛け算や割り算を使いますよね（確か）。ですが、このユークリッドの互除法は、引き算だけで求めることができる、とっても簡単なアルゴリズム（方法）です。
原理は簡単です。２つの整数のうち、大きいほうから小さいほうを、引くほうと答えが同じになるまで引き算するだけです。
たとえば与えられた２つの整数をmとnであらわします。それらを引き算した答えをrとして、最初のmとnの関係は、mのほうが大きいものとします（m > n）。これにより以下の式が立てられます。
m - n = r
そしてこれをさらに計算するのですが、そのときに使うのはnとr。しかし、どちらが大きいかを判断しなくてはなりません。仮にこの場合、nが大きかったとすると、ユークリッドの互除法では、
n - r = s
となります。（※sは、n - rの答えを表すもの。またrが大きければ入れ替え作業をする）
この処理を、引き算の引く側と答えが一緒になるまで続けて、一緒になったらそれが答えというものです（m - n = rの式を例に取ると、nとrが一緒になるまで）。
では、実際の計算でして見ましょう。簡単にするために、今回は12と18でしてみましょう。数字の動きに注目してください。
●基本は大きいものから小さいものを引く！
18 - 12 = 6
●答えと引く数で計算する！
12 - 6 = 6
●引くほうと答えが一緒。だらか12と18の最大公約数は6。
どうですか？ 不思議でしょ？ なぜなのかは僕にもわかりません。つまり引き算さえできれば最大公約数は求めることができるということです。コンピュータの世界では、人間がしている筆算なんてものはできないので、最大公約数を求めるのもこのユークリッドの互除法を用います。
ブラウザでも動く、JavaScriptで記述すると以下のようになります。メモ帳にこれを貼り付けて、「index.html」かなんかで保存して、ダブルクリックしてみてください。12や18の部分を変更して、いろいろ試してみましょう。
<html>
<head>
<script type="text/javascript">
m = 12;
n = 18;
while (m != n){
if (m < n){
n = n - m;
}else{
m = m - n;
}
}
window.alert("最大公約数は" + n);
</script>
<title>最大公約数をプログラムで求める</title>
</head>
<body>
<h1>最大公約数をユークリッドの互除法で求める</h1>
</body>
</html>
わからない人はプログラムのわかる人にでも聞いてみてください。