頭の体操入門

世界で闘うプログラミング力を鍛える150問』では、問題はいくつかのグループに分類して収録されている。たとえば、「配列と文字列」「ビット操作」といったグループが存在する。

少し毛色が違うグループに「頭の体操」がある。

このグループでは、プログラミングとは関係のないパズル的な問題が掲載されている。本には次のようにある。

頭の体操的な問題は非常に熱心に議論される問題の部類で、多くの会社では禁止の方針になってきています。それでも、この手の質問をされることは今でも十分にあり得るのです。それは、頭の体操的な問題という定義を誰もできないからです

まあ、入社試験で聞かれることは減ってきていても、こういう手合いの問題について考えることは単純に楽しい。

戯れに、本書で「古典的な問題」とされているふたつの問題を紹介しよう。

1時間で燃え尽きる2本のロープを使い、ちょうど15分間を計りなさい

簡単に思いつくのは「ロープの両端に火をつければ、30分を計測できる」ということだろう。ただ、これだけだと15分を計るには不十分だ。もうひとアイディア欲しい。

次に気づくべきは、30分で燃え尽きるロープがあれば、それの両端に火をつけることで15分を計れるということだ。

ここまで気づいてしまえば、後はこのふたつの発想を組み合わせるだけだ。

2本のロープを、それぞれロープAとロープBと呼ぼう。

  1. ロープAの両端と、もうロープBの片方に火をつける
  2. ロープAが燃え尽きたら、ロープBのもう一方にも火をつける

「2.」の時点から、ロープBが燃え尽きるまでの時間が15分だ。気づいてしまえば単純だが、気づけないと思考が沼に飲まれる。

では、次の問題に移ろう。

9個のボールがあり、8個は同じ重さで、1つだけ他より重くなっている。天秤を2回だけ使って重いボールを見つけなさい

僕たちプログラマは、こういう問題は分割統治法で解こうとしてしまう。

たとえば、9個のボールを8個のボールと1個のボールに分けて、8個のボールを4個ずつ天秤に載せる。重かった方の4個から、また2個ずつ天秤に載せる…といった具合だ。これだと、最短で1回、最悪で3回も天秤を使わなくてはならない。

では、どうすればいいのか。

「天秤を2回だけ使って」というのが条件だから、「最短で1回」のような考え方をするべきではない。

9個のボールを3個ずつのグループに分割してみよう。ボール3個ずつのグループを、それぞれグループA、グループB、グループCとしよう。次のようにすれば、天秤を2回だけ使って重いボールを見つけることができる。

  1. グループAとグループBを天秤にかける。グループAに傾けば、グループAに重いボールが存在する。グループBに傾けば、グループBに重いボールが存在する。天秤が釣り合えば、グループCに重いボールが存在する。
  2. 「重いボールが存在するグループ」から、ボールを2個、天秤に載せる。傾く場合は、傾いた方に載せたボールが重いボールとなる。釣り合う場合は、載せなかったボールが重いボールということだ。

まとめ

この手の問題が「プログラマの採用試験」として意味があるかは疑わしい。しかし、現実として問われることがあるのであれば、少し訓練をしておく方がいいかもしれない。何よりも、この手のパズルは単に問いていて楽しいし、友人と小話をするときのネタにもなるだろう。

コメントを残す

コメントを投稿するには、以下のいずれかでログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中