良いもの。悪いもの。

先日、 構造体を格納したコンテナに対してSTLのアルゴリズムを適用する方法 について記したが、今回はそれを C++0x で書き直してみた。C++0xの規格はまだきちんと定まっていないが、草案ではかなりのところまでつめられてきており、また対応するC++コンパイラも出てきていることから今のうちにC++0xに慣れておいた方が良いと思う。今回のプログラムで行う内容については前回と全く同じだが、C++0xを使うことによりかなりすっきり書くことができた。因みに現時点の最新の規格(草案)は N3000 (PDF)になる。日本語での資料は C++0xの言語拡張まとめ (Faith and Brave - C++で遊ぼう) や 本の虫 が詳しい。余談だが、2010年になっても0xから1xに変わることはないようだ。C++の生みの親であるBjarne Stroustrupによれば、 0xのxは16進数と考えて欲しい とのこと。 C++0xでは多くの便利な機能が追加されているが、今回はラムダ式、auto型指定子、初期化子リストを使用した。使用したコンパイラは Visual Studio 2010 beta2 (VS2010) 、 GCC 4.5 (snapshot 20100114) 、 Intel Compiler 11.1 だが、残念ながらVS2010とIntel Compiler 11.1では初期化子リストの機能が実装されていないので、それらを使用する場合、今回示したコードのうち素数を格納する静的メンバコンテナの初期化部分は変更しなくてはならない。また、GCCについては最新リリース版である4.4.2で ラムダ式が使えない ので、ここでは開発版の4.5を使用している。その他のコンパイラも含めてC++0xへの対応は C++0xCompilerSupport で確認できる。 初期化子リストを使用しない: static int init_primes[] = { 2, 3, 5, 7 }; vector<int> IsPrime::primes(init_primes, init_primes + 4); 初期化子リストを使用する: vector<int> IsPrime::primes = { 2, 3, 5, 7 }; 今回の...

整数の分割(integer partitions) を列挙するプログラムを書いてみた。ここでは再帰を用いた比較的単純な実装を示すが、より効率的なアルゴリズムを考えるとなると奥が深い。 整数の分割とは、ある整数を自然数の和で表したものだ。例えば分割する整数を5とすると求める自然数は以下のようになる。 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 今回のC++で書いたコードは単純で理解しやすいと思うが、高速化などは考えていない。もしよりよいアルゴリズムに興味があるのなら Antoine Zoghbiu and Ivan Stojmenovic. Fast Algorithms for Generating Integer Partitions. Intern. J. Computer Math. , 70 , 319-332 (1998) (PDF)あたりが参考になるかも。 使い方は以下の通り。 partitions 分割したい整数 [ 分割した要素の最大値 ] 分割したい整数が5であれば、 partitions 5 とする。出力は次のようになる。 5 (max 5): 7 5 4 1 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 また、分割したい整数が5で、分割した要素の最大値を3とする場合は、 partitions 5 3 で、以下のような出力を得る。 5 (max 3): 5 3 2 3 1 1 2 2 1 2 1 1 1 1 1 1 1 1 partitions.cpp #include <iostream> #include <vector> #include <algorithm> #include <cstdlib> using namespace std; void partitions(int n, int max_n, vector<int>& v, vector<vector<int> >& vv) { if (n == 0) { vv.push_back(v); return; ...

「 騎士の巡歴(Knight's Tour) 」を解くプログラムをC++で書いてみた。騎士の巡歴とはチェスボード上の駒「ナイト」を移動させてすべてのマスを一回ずつ通過させる問題だ。特に最初の駒の位置に戻ってくる解を「騎士の周遊(Closed Knight's Tour)」と呼ぶ。 一応、C++らしいコードを心掛けてみたけど、思ったより長くなってしまった。騎士の巡歴では Warnsdorffのアルゴリズム 、騎士の周遊においてはそれに加えて Schwenkの定理 を用いている。また、 Puzzle DE Programming で書かれている方法も参考にさせてもらった。 まず、ボード上のマスをNode構造体のポインタで表現し、 *node とする。その node からナイトが動けるマスを vector<Node*> next; として保持する。また、一度通った node は node->visited にそれを記録しておく。 next を順に巡っていくが、Warndorffのアルゴリズムにより、移動先となる next 内の node のうち、動けるマスの最も少ない node を移動先とする。すべてのマスを通れば探索終了だ。 また、騎士の周遊については、最初にSchwenkの定理から解があるかどうかを判断する。解があれば、騎士の巡歴と同様の手順でまず解を見つける。ここで、見つけた解の最初のマスからナイトが動けるマスをA、最後のマスからナイトが動けるマスをBとし、BからAの順となるマスがあるかどうか調べる。もしあれば、そのAのマスから最後のマスまでの順路を逆にすればそれが騎士の周遊の解となる。もし、BからAの順となるマスがなければ、動けるマスが見つかるまでバックトラックにより探索する。この手順については上記の Puzzle DE Programming が詳しい。 プログラムの使い方は以下の通り。 knight 行数 列数 [駒のスタート行=0 駒のスタート列=0 巡歴か周遊か?] スタート位置はデフォルトで(0, 0)で、何も指定がなければ騎士の巡歴を求める。騎士の周遊の場合は、コマンドラインの最後に c を付ける。 例えば、16x16マス上で騎士の周遊を解く場合は以下のようにする。 knight 16...

明けましておめでとうございます。 今年でこのブログも4年目になるなぁ。早いものだ。自分が初めてインターネットに触れたのが1994年で、それ以前はNIFTY-ServeやPC-VAN、草の根BBSなど利用していた。インターネットを利用し始めたころはメールアドレスを持っていても周りが誰も使っていなかったので全くの無用の長物だった。その頃、みんなが電子メールを持つようになれば素晴らしい世界になるのにと考えたものだが、それから数年でその「素晴らしい世界」になったわけだ。 自分のウェブサイトを作ったのが1996年から、ブログを書き始めたのは2000年2月14日からだけど、最初の頃はHTMLを直接編集していた。その後、Movable Typeに移行してしばらく使っていた。それからいくつかのサイトやブログなどに手を出し、科学情報ばかりを扱った「科学随想録」や以前ハマったMMOのEverQuestのギルド用フォーラムを作成したりしつつ、今の「良いもの。悪いもの。」に落ち着いた。 このブログはプログラミング関連情報をメインとして扱っているけど、昨年は、Google Wave、Android、Twitter、mixiアプリなどが興味深かったな。今年はどんな技術が出てくるんだろう。今からワクワクする。ブログ記事は自分が楽しめるものを書く、書きたい時が書き時というスタンスだけど、他の人にも楽しんでもらえるとしたら嬉しい。因みに自分のプログラミングスタイルの変遷は「 プログラミングができるということは、人生を楽にできるということ 」に書いてある。 これからもどうぞよろしくお願いします。