« プログラマーになりたい人向きの頭の柔軟体操 | Main | Wオフ会 »

June 10, 2006

プログラマーになりたい人向きの頭の柔軟体操 (解答編)

答え合わせ編「正解は一つとは限らない―だから面白い」
「合格点を与えるに値するパターン」の一つとして私の式も紹介していただいたけど、そこに至る経緯が私が書いたものより整然と書かれていました(^_^;

【正解例3】

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

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

 (A0-B1)(A1-B0)<=0

で表せ、すなわちこれが二つの線分が少なくとも一点で重なる条件となる。

 この解法を提示してきた人が二人いるが、ベクトルの概念を持ち出したところが鋭い。この二つのベクトルの方向が一致するかどうかで、二つの線分が重なっているかどうかを判断できるというところに気づいた点は高く評価できる。ただし、それが誰にでも直感的に分かりやすいか、というと必ずしもそうではない点がやや難点ではある。


自分でも、あの式を見て「そういえばどこかでこんな式見たことあるなぁ」とは思っていたんですよ。そうそう、それそれ((C)仮面ライダードレイクの人) ベクトルの内積でしたね(^_^; 私は半ば偶然にその式にたどり着きましたけど、内積の定義を「車輪の再発明」していたのかも...(?) 3Dグラフィックのプログラムとかでベクトル演算はいろいろやりましたけど、あまりよく分かっていなかったのがバレてしまいましたかね(^_^;

向こうのコメント欄にはさっぱりとしたことしか書いていないから「最初から内積を使いましたよー」とも見えるけど、こっちではそうじゃない過程をバッチリ書いてしまったので、書き直したい気分です(苦笑)

結果だけじゃなくて過程もエレガントに考えられるようになるには、まだまだ精進が必要だなぁ...。


ちなみに今回の問題はこれ(「ビル・ゲイツの面接試験-私の場合」)の簡易版で、今回の問題を拡張して考えれば難しくないものですね。3次元にも対応できるでしょう。
3次元になるとポリゴンのコリジョン(衝突)判定で同様の計算をやるんですよ。それを「いかに高速に演算させるか」って最適化させると、やっぱり今回のようなベクトルの演算が「速くていいぞ」という話だったような記憶があります。それを頭の片隅に憶えていた、ということにしておいてください(^_^;

|

« プログラマーになりたい人向きの頭の柔軟体操 | Main | Wオフ会 »

Comments

Post a comment



(Not displayed with comment.)


Comments are moderated, and will not appear on this weblog until the author has approved them.



TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/6718/10463676

Listed below are links to weblogs that reference プログラマーになりたい人向きの頭の柔軟体操 (解答編):

« プログラマーになりたい人向きの頭の柔軟体操 | Main | Wオフ会 »