走格子的路线数统计问题

mathe

百度吧贴中有个 KeyTo9のFans的计算题感觉不错,特此转贴过来, 大家可以思考一下其可行的算法.我基本上可以猜测出来KeyTo9のFans在那里使用的算法(虽然他没有公布),有空时和大家一起详细分析一下: http://tieba.baidu.com/f?kz=395424512 国际象棋棋盘上，一只車从左下角格走到右上角格一共有多少条简单路径？ 简单指不自交，即每个格子最多经过一次。 一般化为n×n棋盘，可以从比较小的n算起，然后尝试寻找通项公式. 同类问题： 2. n×n的棋盘，从左下角走到右下角一共有多少条简单路径？ 3. n*n的棋盘，从左下角走到右上角一共有多少条简单路径？ 4. n*n的棋盘，从左下角走到右下角，遍历所有格子一共有多少条简单路径？ 而且KeyTo9のFans特别提到了这个题目他所用的算法非常有意思的竟然同另外一个关于围棋问题的算法基本相同: http://tieba.baidu.com/f?kz=372248697 在19路棋盘上，共有多少种可能的局面？ 在n×n的棋盘上，共有多少种可能的局面？ 两问完成一问即可。

mathe

贴一下他的计算结果: 问题1的路径条数： n s 1 1 2 2 3 12 4 184 5 8512 6 1262816 7 575780564 8 789360053252 9 3266598486981642 10 41044208702632496804 11 1568758030464750013214100 12 182413291514248049241470885236 13 64528039343270018963357185158482118 14 69450664761521361664274701548907358996488 15 227449714676812739631826459327989863387613323440 16 2266745568862672746374567396713098934866324885408319028 17 68745445609149931587631563132489232824587945968099457285419306 程序运行时间： n t 10 0.7s 11 2.2s 12 7.8s 13 28s 14 106s 15 7min 16 28min 17 2h 问题4的路径条数： n s 1 1 2 1 3 2 4 8 5 86 6 1770 7 88418 8 8934966 9 2087813834 10 1013346943033 11 1111598871478668 12 2568944901392936854 13 13251059359839620127088 14 145194816279817259193401518 15 3524171261632305641165676374930 16 182653259988707123426135593460533473 17 20867537601324146829127267814319046730462 18 5108466695838037792668155733045329910045302167 程序运行时间： n t 11 0.9s 12 3.5s 13 12s 14 51s 15 3min 16 13min 17 47min 18 3.5h 围棋可能局面数的计算结果: n=12: 2h n s 1 1 2 57 3 12675 4 24318165 5 414295148741 6 62567386502084877 7 83677847847984287628595 8 990966953618170260281935463385 9 103919148791293834318983090438798793469 10 96498428501909654589630887978835098088148177857 11 793474866816582266820936671790189132321673383112185151899 12 57774258489513238998237970307483999327287210756991189655942651331169

mathe

关于围棋问题,找到了一个源代码,用pike写的(呵呵,我不知道这是什么语言): http://www.lysator.liu.se/~gunnar/legal.pike.txt 不过前面部分的注释介绍了所用的算法的思想,应该基本就是KeyTo9のFans所用的算法了.

无心人

Pike语言官方网站 作者：牛魔王 — 上次修改时间: 2007-01-09 13:52 Pike是一种解释性的，面向对象的编程语言。它看起来有点象C和C++，但更容易学习和使用。既适用于小型脚本语言应用，也适用于大型程序。Pike是很巧妙的语言，它是纯面向对象的，但形式上你也可以把它当成面向过程的语言来应用，并且Pike提供了lambda函数。在理念上，Pike是为了让程序员舒服而被设计的。 这个链接地址是： http://pike.ida.liu.se/

shshsh_0510

这类问题应该被深入研究过的，所以搜资料是最好的办法

shshsh_0510

如：http://arxiv.org/PS_cache/cond-mat/pdf/0506/0506341v2.pdf http://mathworld.wolfram.com/Self-AvoidingWalk.html

medie2005

问题1： n s 1 1 2 2 3 12 4 184 5 8512 6 1262816 7 575780564 8 789360053252 9 3266598486981642 10 41044208702632496804 11 1568758030464750013214100 12 182413291514248049241470885236 13 64528039343270018963357185158482118 14 69450664761521361664274701548907358996488 15 227449714676812739631826459327989863387613323440 16 2266745568862672746374567396713098934866324885408319028 17 68745445609149931587631563132489232824587945968099457285419306 18 6344814611237963971310297540795524400449443986866480693646369387855336 19 1782112840842065129893384946652325275167838065704767655931452474605826692782532 20 1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844

无心人

晕，光解的文字的形状就是个快速增长的曲线

shshsh_0510

自己算的？贴一下运行时间比较一下。