正解は一つとは限らない―だから面白い
2006.06.09
昨日の「ミネラルウォーターの謎、謎解き編」で宿題として出した「線分重なり判定問題」だが、さまざまな答えをいただいた。単なる「生姜焼き定食」でも料理人によってさまざまな調理方法があるのと同じで、こんなに単純な問題にも何通りも解答方法があるところが楽しくてしかたがない。
実際の社会では、複数の正解が存在するケースが多々あるのに、今の日本の教育システムは、一つの問題には正解が一つしかないという前提で作られている様に思えてしかたがない。もっと、一つの答えが見つかっただけで満足しない探求心の深さだとか、他人がたどり着いた自分と異なる解答にきちんと耳を傾ける謙虚さ、みたいなものを身につける機会を子供達に与えるべきではないかと思う。
その意味でも、こうやってたくさんの人からそれぞれの個性にあふれた解答を集めるだけで、私自身にとっても、とても良い勉強になる。自分と違うものの見方をする人、私が想定もしていなかった解き方を見つけてしまう人。こんなに楽しいのなら、一度は教職についてみるのも悪くないと思ってしまう今日このごろである。
さて、ここで宿題の正解の発表だが、集まった解答の中から合格点を与えるに値するパターンを三つ見つけることができたので、それぞれ紹介する。
【正解例１】
図は省略させていただくが、線分AとBの関係を図に描いてみると６通りある。そのうち４通りが重なるケースで、２通りが重ならないケースである。重なるケースを式にしてみるとかなり複雑になってしまうので、重ならないケースを式にして、それを反転させる。
重ならない条件は、
A1<B0 or B1<A0
重なる条件は、その反対なので、
not(A1<B0 or B1<A0)
これを簡略化すると、
A1>=B0 and B1>=A0
となる。
これが最も一般的な解き方。ある条件が成立するかどうかをチェックする条件式を作る場合に、成立しない条件の方が簡単であれば、それを求めて反転する、というテクニックは実際にプログラムを書いているとけっこう良く使う。
【正解例２】
それぞれの線分を正弦として含む円を書く。その二つの円が接するか交わっていれば、二つの線分は重なる。線分A、線分Bの中心はそれぞれ、
(A0+A1)/2、(B0+B1)/2
である。それぞれの半径は、
(A1-A0)/2、(B1-B0)/2
となるので、その二つの円が接するか交わる条件は、二つの円の中心の距離がそれぞれの半径の合計と同じか小さいときである。すなわち、
|(A0+A1)/2 - (B0+B1)/2)| <= (A1-A0)/2 + (B1-B0)/2
となる(|...|は絶対値の意味)。各項を２倍しても大小関係に変化はないので、
|(A0+A1) - (B0+B1)| <= (A1-A0) + (B1-B0)
となる。
二人ほどこの解法で答えを出してきたが、こんな答えを出してくる人は、一般的な解法を知った上で、「常識的な方法だけに囚われず、あえて他人とは違う方法も考えてみる」ことを習慣にしているタイプではないかと思う。とても良い習慣だ。
【正解例３】
図は省略するが、A0→B1をベクトルV、A1->B0をベクトルWとした時に、VとWの向きが同じであれば重なっていない、異なっていれば重なっている、どちらかが０であれば接していることに注目する。
直線上の二つのベクトルの方向が一致しているかどうかは、内積の正負で判別できるので、ベクトルの方向が異なる（どちらか一方、もしくは両方が０である場合も含む）条件は、
(A0-B1)(A1-B0)<=0
で表せ、すなわちこれが二つの線分が少なくとも一点で重なる条件となる。
この解法を提示してきた人が二人いるが、ベクトルの概念を持ち出したところが鋭い。この二つのベクトルの方向が一致するかどうかで、二つの線分が重なっているかどうかを判断できるというところに気づいた点は高く評価できる。ただし、それが誰にでも直感的に分かりやすいか、というと必ずしもそうではない点がやや難点ではある。
ちなみに、この様に三つの解法を用いて、
A1>=B0 and B1>=A0 … *1
|(A0+A1) - (B0+B1)| <= (A1-A0) + (B1-B0) … *2
(A0-B1)(A1-B0)<=0 … *3
と三つの異なる答が導かれたわけだが、ここで「解法が複数あることは分かるが、どうして同じ問題に三つの異なる答があるのだろう？」と疑問を持たれる方もいると思う。もっともである。
実は、この三つの式、全く同じ条件を別の形で表現しただけのものなのである。この問題をきちんと理解していれば、*1を*3に、*2を*3に変換することはそれほど難しくない。これもまた、中学生卒業レベルの数学で可能なので、腕に自身のある人はぜひともチャレンジして欲しい。
3つの式はA0＜A1, B0＜B1の条件においては同じ意味です。
しかし、A0＜A1, B0＜B1の条件を取り外すと意味が違ってきます。
□*2は A0＜A1, B0＜B1に限定された式
□*3は A0とA1, B0とB1の大小関係に依存しない式
□*1は*2と*3の中間で、*2に{A0＜A1,B0＞B1}かつ{線分Aが線分Bを含んでる}場合と、{A0＞A1,B0＜B1}かつ{線分Bが線分Aを含んでる}場合も含んだ式です。
すなわち、*2が一番厳しい式で、この式だけでA0＜A1, B0＜B1の判定までできます。
*3が一番汎用的で、A0とA1, B0とB1の大小関係に関係なく使える反面、A0＜A1, B0＜B1の条件に意味があるプログラムの場合には、事前にA0＜A1, B0＜B1を保証した上で使用する必要があります。
Posted by: fmin | 2006.06.12 at 07:08
*3も、A0＜A1,B0＞B1（or A0＞A1,B0＜B1）かつ線分の一部だけが重なる場合を検出できませんね。（A0＜B1＜A1＜B0）
Posted by: 一 | 2006.06.15 at 19:09