论坛 › 开心茶馆 › 有几种不同走法？

王守恩 发表于 2020-5-19 10:40:02

有几种不同走法？

本帖最后由 王守恩 于 2020-5-19 12:39 编辑

从 B 点出发，最后回到 A 点，所有点不能重复走，有几种不同走法？
1 步到达，有 1 种走法。
2 步到达，有 1 种走法。
3 步到达，有 1 种走法。
4 步到达，有 2 种走法。
5 步到达，有 3 种走法。
6 步到达，有 7 种走法。

下面的三角形没画全，请玩者自行添加。

lsr314 发表于 2020-5-19 15:44:18

本帖最后由 lsr314 于 2020-5-19 20:08 编辑

1,1,1,2,3,7,16,37,96,253,691,1963,5693,16912

lsr314 发表于 2020-5-19 16:45:52

本帖最后由 lsr314 于 2020-5-19 17:01 编辑

将最左边的作为x轴，最右边的作为y轴，最上面的顶点A标记为{0,0},B标记为{1,0},B右边的为{0,1},以此类推。
8步有37种，路径如下：
序号        路径
1        {{1,0},{2,0},{3,0},{4,0},{3,1},{2,1},{1,1},{0,1},{0,0}}
2        {{1,0},{2,0},{3,0},{3,1},{2,1},{1,1},{0,2},{0,1},{0,0}}
3        {{1,0},{2,0},{3,0},{3,1},{2,1},{1,2},{0,2},{0,1},{0,0}}
4        {{1,0},{2,0},{3,0},{3,1},{2,1},{1,2},{1,1},{0,1},{0,0}}
5        {{1,0},{2,0},{3,0},{3,1},{2,2},{1,2},{0,2},{0,1},{0,0}}
6        {{1,0},{2,0},{3,0},{3,1},{2,2},{1,2},{1,1},{0,1},{0,0}}
7        {{1,0},{2,0},{3,0},{3,1},{2,2},{2,1},{1,1},{0,1},{0,0}}
8        {{1,0},{2,0},{3,0},{2,1},{1,1},{1,2},{0,2},{0,1},{0,0}}
9        {{1,0},{2,0},{3,0},{2,1},{2,2},{1,2},{0,2},{0,1},{0,0}}
10        {{1,0},{2,0},{3,0},{2,1},{2,2},{1,2},{1,1},{0,1},{0,0}}
11        {{1,0},{2,0},{3,0},{2,1},{1,2},{0,2},{1,1},{0,1},{0,0}}
12        {{1,0},{2,0},{3,0},{2,1},{1,2},{1,1},{0,2},{0,1},{0,0}}
13        {{1,0},{2,0},{3,0},{2,1},{1,2},{0,3},{0,2},{0,1},{0,0}}
14        {{1,0},{2,0},{2,1},{3,1},{2,2},{1,2},{0,2},{0,1},{0,0}}
15        {{1,0},{2,0},{2,1},{3,1},{2,2},{1,2},{1,1},{0,1},{0,0}}
16        {{1,0},{2,0},{2,1},{1,1},{1,2},{0,3},{0,2},{0,1},{0,0}}
17        {{1,0},{2,0},{2,1},{2,2},{1,2},{0,2},{1,1},{0,1},{0,0}}
18        {{1,0},{2,0},{2,1},{2,2},{1,2},{1,1},{0,2},{0,1},{0,0}}
19        {{1,0},{2,0},{2,1},{2,2},{1,2},{0,3},{0,2},{0,1},{0,0}}
20        {{1,0},{2,0},{2,1},{2,2},{1,3},{0,3},{0,2},{0,1},{0,0}}
21        {{1,0},{2,0},{2,1},{2,2},{1,3},{1,2},{0,2},{0,1},{0,0}}
22        {{1,0},{2,0},{2,1},{2,2},{1,3},{1,2},{1,1},{0,1},{0,0}}
23        {{1,0},{2,0},{2,1},{1,2},{1,3},{0,3},{0,2},{0,1},{0,0}}
24        {{1,0},{2,0},{2,1},{1,2},{0,3},{0,2},{1,1},{0,1},{0,0}}
25        {{1,0},{2,0},{1,1},{2,1},{2,2},{1,2},{0,2},{0,1},{0,0}}
26        {{1,0},{2,0},{1,1},{2,1},{1,2},{0,3},{0,2},{0,1},{0,0}}
27        {{1,0},{2,0},{1,1},{1,2},{1,3},{0,3},{0,2},{0,1},{0,0}}
28        {{1,0},{1,1},{2,1},{3,1},{2,2},{1,2},{0,2},{0,1},{0,0}}
29        {{1,0},{1,1},{2,1},{2,2},{1,2},{0,3},{0,2},{0,1},{0,0}}
30        {{1,0},{1,1},{2,1},{2,2},{1,3},{0,3},{0,2},{0,1},{0,0}}
31        {{1,0},{1,1},{2,1},{2,2},{1,3},{1,2},{0,2},{0,1},{0,0}}
32        {{1,0},{1,1},{2,1},{1,2},{1,3},{0,3},{0,2},{0,1},{0,0}}
33        {{1,0},{1,1},{1,2},{2,2},{1,3},{0,3},{0,2},{0,1},{0,0}}
34        {{1,0},{1,1},{1,2},{1,3},{0,4},{0,3},{0,2},{0,1},{0,0}}
35        {{1,0},{1,1},{2,0},{3,0},{2,1},{1,2},{0,2},{0,1},{0,0}}
36        {{1,0},{1,1},{2,0},{2,1},{2,2},{1,2},{0,2},{0,1},{0,0}}
37        {{1,0},{1,1},{2,0},{2,1},{1,2},{0,3},{0,2},{0,1},{0,0}}

王守恩 发表于 2020-5-20 08:59:39

本帖最后由 王守恩 于 2020-5-20 09:06 编辑

lsr314 发表于 2020-5-19 16:45
将最左边的作为x轴，最右边的作为y轴，最上面的顶点A标记为{0,0},B标记为{1,0},B右边的为{0,1},以此类推。
...
把我的算法晒一晒，欢迎批评。
去掉顶点 A，记第 1 排：起点，终点
第 2 排：1,2,1。第 3 排：1,2,2,1。第 4 排：1,2,3,2,1
第 5 排：1,2,3,3,2,1。以此类推。
起点出来有2种可能：1，2。回归终点有2种可能：1，2
即：起点出来到回归终点有3种可能：1,1，1,2，2,1
第 1 种可能 1,1，记从左往右比从右往左小
第 3 种可能 2,1，合并记在第2种 1,2
据此，8 步 37 种走法合并成 12 种
01={1,1,1,2,2,2}*2(1,34)
02={1,1,2,2,1,1}*1(13)
03={1,1,2,2,1,2}*2(11,37)
04={1,1,2,2,2,1}*8(2,3,8,12,16,23,26,27)
05={1,1,2,2,2,2}*2(4,32)
06={1,1,2,3,2,1}*4(5,9,19,20)
07={1,1,2,3,2,2}*6(6,7,10,29,30,33)
08={1,2,2,1,1,2}*2(24,35)
09={1,2,2,3,2,1}*4(14,18,21,25)
10={1,2,2,3,2,2}*2(15,31)
11={1,2,3,2,1,2}*2(17,36)
12={1,2,3,2,2,2}*2(22,28)

lsr314 发表于 2020-5-20 11:40:28

王守恩 发表于 2020-5-20 08:59
把我的算法晒一晒，欢迎批评。
去掉顶点 A，记第 1 排：起点，终点
第 2 排：1,2,1。第 3 排：1,2,2,1 ...

{}里的数字怎么区分是第几行的？

王守恩 发表于 2020-5-22 06:57:51

lsr314 发表于 2020-5-19 15:44
1,1,1,2,3,7,16,37,96,253,691,1963,5693,16912
   lsr314!再添几个？谢谢！
1,1,1,2,3,7,16,37,96,253,691,1963,5693,16912,....
没有规律。我的方法不行，添几个再试试。

lsr314 发表于 2020-5-22 09:20:45

王守恩 发表于 2020-5-22 06:57
lsr314!再添几个？谢谢！
1,1,1,2,3,7,16,37,96,253,691,1963,5693,16912,....
没有规律。我的 ...

目前的算法已经到极限了，运算量是指数级增长的，下一个要算好几天

王守恩 发表于 2020-5-22 09:58:06

本帖最后由 王守恩 于 2020-5-22 09:59 编辑

lsr314 发表于 2020-5-22 09:20
目前的算法已经到极限了，运算量是指数级增长的，下一个要算好几天

原来的题目是这样的(1楼的图)
从 A 出发，先走 B，最后回到 A，不重复地走遍所有路段，有几种不同走法？
答案说是4032。我就是想用手工的方法重新算一下。
答案对么？电脑能出来4032？

lsr314 发表于 2020-5-22 10:51:07

王守恩 发表于 2020-5-22 09:58
原来的题目是这样的(1楼的图)
从 A 出发，先走 B，最后回到 A，不重复地走遍所有路段，有几种不同走法 ...

我的算法是假设下面的三角形可以一直增加下去（一楼说下面的自行添加，所以默认有无限个三角形），如果只要求图中的这几个三角形，那么算出来是很简单的。

lsr314 发表于 2020-5-22 10:55:19

王守恩 发表于 2020-5-22 09:58
原来的题目是这样的(1楼的图)
从 A 出发，先走 B，最后回到 A，不重复地走遍所有路段，有几种不同走法 ...

你把题目里的路径不重复改成顶点不重复了，意思完全变了

查看完整版本: 有几种不同走法？