ぽよぽよぽよ

ヒモになりたい

乳首の探索アルゴリズム(理論編)

人間一度は遊んだ遊びがある。

 

f:id:otama_jaccy:20130824234530p:plain

f:id:otama_jaccy:20130824234711p:plain

 

そう、乳首あてげーむである

 

人は古来より乳首を当てることにより、文明を発展させてきた。

 

だがそこには、勘・経験などといった要素が絡んでくる。

 

人によっては乳首の場所を当てれないなどといった悲しみに包まれる人も出てくる。

 

では、どのようにすれば人間の乳首に高速に触れることができるのであろうか。

 

この問題は以下のようにして考える事が可能である。

 

N*Mのフィールドに乳首が2個存在する。この2つの乳首の位置を当てろ。また、フィールド上に手を当てた場合、その手の座標から乳首がどの方向にあるかが出力される。なお、乳首を触られる人は服を着ているため乳首が見えないとし、男であるとする。

f:id:otama_jaccy:20130825000456p:plain

 

この問題は男として考える。

 

理由は、アクセス拒否される(その人との関係による)・3次元の問題になる(人による)からである。

 

このように問題を設定することにより、以下3つのアルゴリズムでこの問題を解くことができる。

 

1:勘

 

最も人間らしいアルゴリズムである。

 

だが、このアルゴリズムを用いた場合最悪の場合いつまでも乳首を当てられずに、計算量が、O(∞)になってしまう。

 

これではよろしくない。

 

次のアルゴリズムを考えてみる。

 

2:2分探索

「にぶたん」などといった愛称で愛されるアルゴリズムである。

 

まず、乳首のx座標を2分探索で探り当て、次にy座標の乳首の位置を探り当てる。

 

この場合、計算量は、O(log2 N)となる。

 

早いがこれよりも高速なアルゴリズムが存在する。

 

 

 3:服を脱がせる

乳首を触られる人は服を着ている(脱がせていけないとは書いてない)。

 

見えないなら脱がせる。当たり前だよなぁ

 

この場合の計算量はO(1)となる。神アルゴリズムである。

 

 

 

以上の3つを検証する「実践編」は気が向いたら行う。