Ad Network

あわせて読みたい

  • あわせて読みたい

« ミネラルウォーターの謎、謎解き編 | Main | ジミー大西は世界に通じるコメディアン »

正解は一つとは限らない―だから面白い

060610_025953  昨日の「ミネラルウォーターの謎、謎解き編」で宿題として出した「線分重なり判定問題」だが、さまざまな答えをいただいた。単なる「生姜焼き定食」でも料理人によってさまざまな調理方法があるのと同じで、こんなに単純な問題にも何通りも解答方法があるところが楽しくてしかたがない。

 実際の社会では、複数の正解が存在するケースが多々あるのに、今の日本の教育システムは、一つの問題には正解が一つしかないという前提で作られている様に思えてしかたがない。もっと、一つの答えが見つかっただけで満足しない探求心の深さだとか、他人がたどり着いた自分と異なる解答にきちんと耳を傾ける謙虚さ、みたいなものを身につける機会を子供達に与えるべきではないかと思う。

 その意味でも、こうやってたくさんの人からそれぞれの個性にあふれた解答を集めるだけで、私自身にとっても、とても良い勉強になる。自分と違うものの見方をする人、私が想定もしていなかった解き方を見つけてしまう人。こんなに楽しいのなら、一度は教職についてみるのも悪くないと思ってしまう今日このごろである。

 さて、ここで宿題の正解の発表だが、集まった解答の中から合格点を与えるに値するパターンを三つ見つけることができたので、それぞれ紹介する。

【正解例1】

 図は省略させていただくが、線分AとBの関係を図に描いてみると6通りある。そのうち4通りが重なるケースで、2通りが重ならないケースである。重なるケースを式にしてみるとかなり複雑になってしまうので、重ならないケースを式にして、それを反転させる。

重ならない条件は、

  A1<B0 or B1<A0

重なる条件は、その反対なので、

  not(A1<B0 or B1<A0)

これを簡略化すると、

  A1>=B0 and B1>=A0

となる。

 これが最も一般的な解き方。ある条件が成立するかどうかをチェックする条件式を作る場合に、成立しない条件の方が簡単であれば、それを求めて反転する、というテクニックは実際にプログラムを書いているとけっこう良く使う。

【正解例2】

 それぞれの線分を正弦として含む円を書く。その二つの円が接するか交わっていれば、二つの線分は重なる。線分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

となる(|...|は絶対値の意味)。各項を2倍しても大小関係に変化はないので、

  |(A0+A1) - (B0+B1)| <= (A1-A0) + (B1-B0)

となる。

 二人ほどこの解法で答えを出してきたが、こんな答えを出してくる人は、一般的な解法を知った上で、「常識的な方法だけに囚われず、あえて他人とは違う方法も考えてみる」ことを習慣にしているタイプではないかと思う。とても良い習慣だ。

【正解例3】

 図は省略するが、A0→B1をベクトルV、A1->B0をベクトルWとした時に、VとWの向きが同じであれば重なっていない、異なっていれば重なっている、どちらかが0であれば接していることに注目する。

 直線上の二つのベクトルの方向が一致しているかどうかは、内積の正負で判別できるので、ベクトルの方向が異なる(どちらか一方、もしくは両方が0である場合も含む)条件は、

 (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に変換することはそれほど難しくない。これもまた、中学生卒業レベルの数学で可能なので、腕に自身のある人はぜひともチャレンジして欲しい。 

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d8341c4f9853ef00d8345c892069e2

Listed below are links to weblogs that reference 正解は一つとは限らない―だから面白い:

» [考察]エレガントな解法を求めてはいけない from 萌え理論Blog
問題 Life is beautiful: ミネラルウォーターの謎、謎解き編 via REVの日記 @はてな 【問題】ある直線上に線分AとBがあります。線分Aの両端の座標はそれぞれA0とA1(ただしA0A1)、線分Bの端の座標はそれぞれB0とB1(ただしB0B1)とします。そのとき、線分Aと線分Bが... [Read More]

» [日記・コラム]解答例見ましたが・・・ from yoshi--blog@hatena
さて、ここで宿題の正解の発表だが、集まった解答の中から合格点を与えるに値するパターンを三つ見つけることができたので、それぞれ紹介する。 Life is beautiful: 正解は一つとは限らない―だから面白い 何かどれもが難しすぎて、「シンプル」で「直感的」なものが「エレ... [Read More]

Comments

fmin

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を保証した上で使用する必要があります。

一

*3も、A0<A1,B0>B1(or A0>A1,B0<B1)かつ線分の一部だけが重なる場合を検出できませんね。(A0<B1<A1<B0)

Post a comment

This weblog only allows comments from registered users. To comment, please Sign In.