さんが熱心に聞く、という稀有な展開。2012そんなこんなで。@crashponさんから「言語オタク」の称号を頂戴致しましたw。C++のtemplate」ねた。C++マスターの面々はもっとすごいことをやっているので、マスターの方がここを見ていましたら「こいつ、またやってる」ぐらいに思って頂ければと。道順を数える残念ながら2年ぐらい前に事実上活動が停止してしまいましたが「どう書く?org」という互いにお題を出しては各種言語で実装を競い合う、コロシアムというか道場というかがありました。そこにわたしが投稿したお題のひとつが「道順を数える」。書く?org投稿した内容は次のようなものです。格子状の経路があるとします。このときPからQまでいくのに何通りの経路があるか数えてください。遠回りはせずかならずQに近づく方向に進む(右方向か下方向にだけ進む)とします。(1)と条件は同じで、図.2のように経路の一部がない(通れない)場合に、PからQまでいくのに何通りの経路があるか数えてください。経路の表現の仕方、記憶の仕方は自由とします。上記のようなキャラクタでの表現でもよいですし、最初からプログラムで扱いやすいデータとして持っていてもOKです。入力も外部からの入力でもよいですし、プログラム中にコーディングされていてもOKです。道順を数える」から拝借させて頂きました。グラフ理論の典型的な問題になると思いますが、グラフ理論はちゃんと学んでいないので、自分なりの言葉で解き方をまず解説します。4行3桁のノードとそれぞれの間をつなぐエッジを考えます。進める方向は、右方向、下方向のどちらかなので、あるノードへの経路は、上のノードからの経路のばあいと左のノードからの経路のばあいとがあります。このとき上のノードにたどり着くまでの経路の数がn、左のノードにたどり着くまでの経路がmであれば、当該ノードへの経路の数はn+mになります。左端のノードは左側にノードがないので上のノードからの経路だけになり、左端のノードの経路数は上のノードの経路数と同じになります。同様に上端のノードの経路数は左のノードの経路数と同じになります。始点のノードの経路数は1(「始点から動かない」という1通りだけ)になります。これらをすべて計算するして図にあらわすと次のようになり35通りという答えが得られます。同様に図2のばあいは次のように15通りになります。