就活ぶろぐ » Blog Archive » Webテスト・SPI対策【タイリング問題】

Webテスト・SPI対策【タイリング問題】

Posted by yama3 2009年 03月 09日. 筆記試験

久しぶりにWebテスト、SPI対策の記事でも書いてみます。というのも、ここ最近、Webテストやら筆記試験やらがちょっと多くなってきたんで、復習も兼ねて、ということです。

というか、土曜に受けた筆記試験と、昨日の朝受けたWebテストの問題で同じやつが半分くらいあってちょっとビックリ。志望度的には、逆の順番だったらよかったのに。。。とWebテストを早く受けなかったことをちょっと後悔。

ということで、タイトルにあるように今回の記事は、タイリング問題。
タイリング問題と言われて、どんな問題かが頭に浮かんでくる人は少ないかもしれません。が、これは実は、私の研究室テーマのグラフ理論と離散最適化の離散最適化部分に関わってくる問題だったりします。

そして、この問題が昨日受けたWebテストで出てきたとき、ちょっと懐かしくおもったりしました。

タイリング問題の問題例は、下のような図形に対し、１×２の長方形で敷き詰めることができるかどうか？というものがあります。

当然、元の図形を色々変えた問題例も考えられますし、１×２の長方形ではなく、１×３の長方形にしたり、正三角形にしたり・・・といった問題例もあります。

こういった応用を考えるのは、研究者に任せるとして・・・昨日出てきたのが、ちょうど上の図形に対し、１×２の長方形で敷き詰めることができるかどうか。という問題です。

答えを言ってしまうと、できないです。しかし、このできないということを論理的に示すのは難しかったりします。

ということで、これを知るための方法は続きにて

上の図のように、図形に対して、白と黒で交互にマークをつけていきます。こうしたときに、白と黒の隣り合った1ペアが敷き詰める１×２の長方形になります。

ここで、白の個数と黒の個数を数えてみると・・・白は10個、黒は12個。ということは、敷き詰められません。

もし、白と黒の個数が同じであれば、敷き詰めることは可能でしょう。

こういうのはその場で気づくのは難しいです。ということで、試行錯誤が一番でしょう。

http://workship.info/2009/03/09-223000.php/trackback