プログラム大公開！？・・・
Trick or Treat いいものくれなきゃいたずらするぞー！！
森博嗣の「笑わない数学者」にて使われるビリヤードの問題がある。
『…五つのビリヤードの玉を、真珠のネックレスのように、リングにつなげてみるとしよう。玉には、それぞれナンバーが書いてあるな。さて、この五つの玉のうち、幾つ取っても良いが、隣どうし連続したものしか取れないとしよう。一つでも、二つでも、五つ全部でも良い。しかし、離れているものは取れない。この条件で取った玉のナンバーを足し合わせて、１から２１までのすべての数ができるようにしたい。さあ、どのナンバーの玉をどのように並べて、ネックレスを作れば良いかな？』*1
この答えは小説内には記載されておらず、実際に考えないと答えはわからない。
さて、こんなの簡単だぜって方はぜひこの問題を考えてもらいたい。
意外に難しい。
シラミつぶしでやってみようとしても非常に大変だ。
ただ、この問題をよく考えると、いくつかの条件が出てきて絞り込みができる。
ギブアップの方は下のリンク先に行けば考え方・答えがわかるだろう。
http://tokyo.cool.ne.jp/meikyu/art96/gdu9610a.html
で、まあこいつのポイントは5個で答えは存在する。
ではこれを6個にすると・・・n個にするとどうだろうという問題。
こいつを解いた友達も6個からよくわからないという話だったので、じゃあやってみようとおもい、プログラムを作り、まわしてみた(反則)。
すると、6個の場合は答えが5つ、7個の場合は解がないことがわかった。
これ以降は実行していないが、8個の時は複数個解が存在するらしい。
プログラム(5個の場合)は以下のリンク先に掲載しておく。
ただ、これは答えが出ればいいという考えで作っており、きれいかどうかは計算していない。
なので、プログラムに関する苦情は受け付けない(ですよ、mima2氏)。
まあ、興味があったらこいつを少し改変してほかの数で試してみると面白いと思う。
やろうと思っても、作れないかなと途中諦めムードだったけど、アルゴリズムを考え付いたら結構あっさりだったな。
これくらい実験のプログラムもうまくいけたらいいのに。
プログラムリンク先：http://www.realintegrity.net/~rukideen/file/5ball.c
今日の独り言
「テレビ買ってしまったぜ。明日公開できたらしよう。」
