アルゴリズム – 低レイヤーでテレ屋です

内容と感想

目次などは著者のページで公開されているとおりです。

プログラミングの基本となる数学をとても平易な文章で書かれていて読みやすいです。最近、ちゃんと本を読んでいなかったので読みやすいものと思って本棚から取り出して読んだのですが、正解でした。
※私は大学では一応理系だったので、数学が全くできないわけではないですが、それほど得意だったわけではありません。

最後の計算不可能な問題のところが不完全な理解のまま読み進めてしまったので、別の機会に改めて読み直した方が良いかも、という気がしています。

論理や数学的帰納法、再帰などはプログラミングする上で理解しているのとそうでないのとでは、だいぶ違ってくる気がします。そのあたりの理解の導入にぴったりな本だと思います。

最後に、読書案内がついているので、そこから何を読むと良いかもわかり安心ですね。ちなみに何冊かはすでに読んだものもありました。

ちなみに

これで結城さんの著書を読んだのは6冊目です。どれもとても良い本ばかりです。今までに読んだ本は以下のとおりです。

増補改訂版　Java言語で学ぶデザインパターン入門

増補改訂版　Java言語で学ぶデザインパターン入門　マルチスレッド編

新版　C言語プログラミングレッスン文法編

暗号技術入門　第3版

数学ガール

はじめに

夏休みの旅行中に、うちの子がペグソリティアをやっているのを見て、「これ解けたらドヤ顔できるな」と思ってチャレンジしたものの、意外に大変でした、というお話です。

いろんなパターンがあるようですが、一番スタンダードっぽいやつということで。

最初は、何回かチャレンジしてれば解けるやろ、と思っていたが全然できないです。マジですか？？ヤバイという気持ちになり、PCに解いてもらおうと考えたわけです。

しかし、これも意外に難しい。というか全然意外ではなく、難しいことが知られていたらしいです。私が知らないだけでした。

こういうのとか（英語なので半分も読めてないですけど）、こういうのとか見ると、現実的な時間で解の全部を解くことはかなり困難そうだ、という印象を受けました。

とはいえ、仕事のあとでちょびちょびやるだけだとそこまでのエネルギーはないというわけで、とりあえず、簡単な感じで書いてみました。

なんと！時間はものすごーくかかったものの、一応、解の一つが得られました。夜寝る前に走らせて、翌朝には解けていたので、とりあえず良しとします。
（時間を計測するのを仕込むのを忘れてしまったのが残念。）

このあとは、性能を改善するのみ！現実的な時間でちゃんと解けるようになりたいなぁ。

あのあとも少し工夫を続けた結果、解の一つであれば、数分で得られるようになりました。7時間くらい雨後し続けると50,000超の解を得ることができましたが、まだまだ探索空間が広すぎて全体を把握できていないようです。

対称性や回転で同一となるペグの配置ができたら解決済みとする、とかの工夫が必要だなぁと思いつつ、まだ解決できていません。