ユークリッドの互除法
ナビゲーションに移動
検索に移動
ユークリッドの互除法（ゆーくりっどのごじょほう）とは、「二つの自然数の最大公約数を求めるための効率のよい高速なアルゴリズム」であるとされるが、「効率のよい、高速な」というところに問題があり、「自然数のペアがあり、どちらかがもう一方よりも大きい場合は、大きいほうから小さいほうを引く」という素朴な定義が忘れられていて問題化している。
これを「高効率化」「高速化」するために「割った余り」で説明したのが「互除法」であるが、ユークリッド自身が『原論』で述べたのは「引き算」のほうであった。
概要[編集]
かつてはIT企業の新人研修におけるプログラミング研修において新人いじめのためによく課題として出された。遠山啓による水道方式における「タイルのシェーマ」が頭に入っていれば小学生にも解るのだが、受験勉強漬けで頭の中からすっからかんに「理解」というものが抜けている新卒は「顧客」がいるということが理解できないために、危なっかしくて現場には出せない。反面、ろくにプログラムも書けない奴をマネージャーとして現場に送りこんでカスっているタチの悪い企業もいるため、両刃の刃ではある。
要するに、「m × n （m < n）の長方形から m × m の長方形を齧り取っていって、正方形になったら、それが m と n の最大公約数である」という話である。