お姉さんが実行したシンプルな数え上げプログラム。点 (0, 0) から 点 (n, n) までの経路数を求める。
$ cargo run -q --release -- 4
4 x 4 の計算を開始するわよ...(Ctrl+C で進捗表示)
4 x 4 のときは 8512 とおりね！
所要時間: 0.000 秒
$ cargo run -q --release -- 5
5 x 5 の計算を開始するわよ...(Ctrl+C で進捗表示)
5 x 5 のときは 1262816 とおりね！
所要時間: 0.068 秒
$ cargo run -q --release -- 6
6 x 6 の計算を開始するわよ...(Ctrl+C で進捗表示)
^C6 x 6 の現在の進捗: 35512526 とおり. わっしょいわっしょい. 経過時間: 2.074 秒
6 x 6 のときは 575780564 とおりね！
所要時間: 33.024 秒
- 線分 y = x での対称性を利用し、最初の一歩目は (0, 0) -> (1, 0) への移動で固定化。
- 格子の辺 (x = 0, x = n, y = 0, y = n) において、ゴールと反対向きに移動するとゴールにたどり着けなくなるため、このパターンを枝刈りしている。