数学 II・Ｂの第５問を除いて、数学Ｉ・Ａ、数学 II・Ｂを解いてみた。
さらに、「今回こそは絶対に満点を取るッ！」という意気込みの下、一旦解き終えたら必ず検算をすることに。
しかし結果は……しょーもないミスを２問やらかしました（泣）
はぁぁもぅ、なんで三角錐の体積を求めるのに 1/6 をかけちゃうのかオレは！（泣）
またも満点は持ち越し。
| 満点夢見し 飽きもせず ★ 2008. 1.24. Thu. |
オレのツメの垢を煎じたら、それはそれは甘い甘いフレグランスのお茶ができるかもしれん！
去年と同様に今回も数 II・Ｂの第６問が面白かったので、チョイとご紹介。
『ユークリッドの互除法』というヤツです。
これは何かというと、２つの整数の最大公約数を求めるための手法です。
そういえば、２つの整数の最大公約数を求める方法にこんなのがありましたね。
中学校あたりで習ったようなヤツ。
下図のように、共通して割り切れる数（共通因数）を探しては次々割り算していくという方法です。
この方法は別に難しいわけじゃぁないんだけれど、「共通因数を探す」という作業が厄介だったりするんですね。大きい数を相手に探すとなると異様に手間がかかってしまう。
まぁそりゃそうだ。「5541608 と 7107896 の最大公約数を求めよ！」とか言われても、手間を通り越して「７ケタなんぞやってられっかーッ！！」とちゃぶ台をひっくり返されて終わりだ。
ところが。
ユークリッドの互除法を使うと、多少の手間で簡単に求まってしまうんです。
しかも、小学生でもできる簡単な方法だってんだからビックリだ。
では、ユークリッドの互除法とは一体どんな手法なのか。
実は……単なる 割り算の繰り返し なんです。
下図のように、元の２数の割り算から始めて「除数を余りで割る」を数回繰り返すだけ。こんな単純な作業で最大公約数が求まってしまうんです（割り算ａ÷ｂにおいてｂのことを除数と呼びます。ちなみに、ａは被除数と呼ばれます）。
実に簡単！
しかも、この互除法のさらにスゴいところは「割り算の繰り返し回数が少ない」というところ。
なんと、小さい方の数のケタ数の５倍以内で済むんです。たとえば、上図の場合だと どんなに多くても必ず 15回以内で割り算が終わるというわけです。実際、５回で終わったしね。
これはすでに証明されていて、『ラメの定理』と呼ばれています。
ちなみに、前述の「5541608 と 7107896 の最大公約数を求める」という場合だと、とりあえず 35回以内で済むことがわかります。実際にやってみると、たった８回で終わった。早ッ！
まぁ、たった８回とはいっても、デカい数を相手に手計算で８回連続割り算する……と考えると手間はやっぱりかかるかもしれません。
でも、前述の「共通因数を探し出す」よりは格段にラクなんです。
だって、割り算するだけなんだもん。
しかも、都合のいいことに、繰り返し単純作業を大の得意とする輩がこの世の中にはいる。
それは……皆さんの目の前にある箱、パソコンだ。
チョチョッとプログラムを組んでやれば、あとはメンドウな作業はすべてパソコンがやってくれる。
コンピュータにとって数十回の繰り返しなど朝メシ前ですからね。
今となっては、十数ケタ同士の数の最大公約数なんて瞬時に求まってしまうんです。
ちなみに、この手法は『ユークリッド原論』という書物の中に記載されました。
そこから「ユークリッドの互除法」という名前がついたそうです。
ユークリッドは紀元前300年頃の古代ギリシャの数学者で、「学問に王道なし」ということわざの元になった人物でもあります。
平面や空間という意味で「２次元」「３次元」という表現が使われたりするけれど、その語源をたどっていけばこのユークリッドという人物にブチ当たります。
（平面は「２次元ユークリッド空間」、空間は「３次元ユークリッド空間」と呼ばれます）
