私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「同心円をつなぐ橋」（CodeIQ）を参照してください。
問題を引用します。
ここでは、同心円上に等間隔に並んだ場所を結ぶ橋を架けることにします。
橋は交差することはできないものとします。
標準入力から、等分する数が与えられるとき、考えられる橋の架け方が何通りあるかを標準出力に出力してください。
JavaScript(Node.js)で解答しています。
process.stdin.resume();
process.stdin.setEncoding('utf8');
var Points = 0;
process.stdin.on('data', function (chunk) {
var lines = chunk.toString().split('\n');
for(var i=0; i<lines.length; i++) {
var input = lines[i].trim();
if(!input){
continue;
}
Points = parseInt(input);
}
});
process.stdin.on('end', function () {
var ret;
if(Points % 2){
ret = 0;
}
else{
switch(Points){
case 0:
ret = 0;
break;
default:
// 線の数は点の数の1/2のカタラン数に等しい
ret = CN(Math.floor(Points/2));
break;
}
}
console.log(ret);
});
// カタラン数を求める
function CN(n){
var a = 1;
var b = 1;
for(var i=2*n; i>n+1; i--){
a *= i;
}
for(var j=n; j>1; j--){
b *= j;
}
return a/b;
}
解答のプログラムは非常に簡単です。
ですが、これはかなり難しい問題です。
解答のプログラムではやっていませんが、真面目にパターンを生成して数えるのはかなり難しいです。
まず、組み合わせ数ですがO(n!)になります。単純に数え上げていたのではまともな時間ではできないことは明らかです。
次に、並び順のチェックの難しさがあります。
円周上の2点を交差しない直線で結んだ場合はプログラムでは次のように表現できます。（結ばれる2点をa、a'のように表します）
とりあえず、6点あるとします。
[a,a',b,b',c,c']
[a,b,b',a',c,c']
[a,b,c,c',b',a']
こういう風に対になるものが入れ子になるようになっていれば円周上の点を結んだ線は交差しません。
[a,b,a',b',c,c']
こちらのように入れ子の対応が取れない場合はダメです。
HTMLのタグが正しいかをチェックするのと同じようにスタックを使うなどしてチェックすることは簡単に思いつきますが、結構時間がかかりそうです。
円周上の点なので先頭はAに固定して構いませんが、裏返しになるパターンは同じと判断しなければなりません。
この問題に挑戦したのはCodeIQの問題をやり始めて割と初期の頃でここまで考えなかったのですが、今考えても難解です。
当時は自分でパターンを列挙するうまい方法を考えつけず、漸化式も自分で導けなかったのでやり方を調べました。もちろん、問題の題名や文章から直接解答が見つかるわけではありませんが、この問題はいかにも数学の問題にありそうです。
私は問題を次のような文章に変換し、そのキーワードで検索しました。
「円周上の任意の2点を結ぶ直線が互いに交差しない点の組み合わせの数を求めよ」
これがうまくいって、円周上の点の数の1/2の「カタラン数」が解であることがわかりました。あとはWikipediaで「カタラン数」を調べて漸化式をそのままコード化して出来上がりです。CN()がそのコードです。
あと、入力値が奇数の場合は線を引けない点があるので最初にエラーチェックで弾いて全てのパターンについて結果を求めることができます。
この問題を今やり直したら全部自力で解けるかというとなかなか難しい気がします。
しかし、CodeIQは問題に正解すると解答した言語の難易度によって上級スキルに認定されますが、この手の数学的に難しい問題（これの場合は★★★）で「言語の上級」はどうでしょうか？ 「アルゴリズム上級」ならなんの文句もないですけど。