跳蚱蜢

hujunhua

感觉7#的那个策略（如下图）具有通用性，在规模较大时。

我们的任务是将环排列 {0, 1, 2, 3, ..., -3, -2, -1} 变换到环排列 {0, -1, -2, -3..., 3, 2,1}
按上述策略，任务被转化成将开环排列 {2, 3, ..., -3, 0} 变换到开环排列 {0, -3, ..., 3, 2}
规模减小了3个。记闭环任务次数为b(n), 开环为k(n), 猜想
b(n)=5+k(n-3)

hujunhua

计算了一下9只蚱蜢，需要跳26次。
但k(6)=25, 5+k(6)=30, 远远超过了26

7只蚱蜢也有这种情况，k(4)=12, k(4)+5=17大于15.

所以上楼的策略似乎对于奇数只蚱蜢不成立，可能是有一个中数不动的缘故。
9只26次的一条路径如下：
{{0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
{1, 0, 2, 3, 4, 5, 6, 7, 8, 9},
{1, 2, 0, 3, 4, 5, 6, 7, 8, 9},
{0, 2, 1, 3, 4, 5, 6, 7, 8, 9},
{8, 2, 1, 3, 4, 5, 6, 7, 0, 9},
{8, 2, 1, 3, 4, 5, 0, 7, 6, 9},
{8, 2, 1, 3, 0, 5, 4, 7, 6, 9},
{8, 2, 0, 3, 1, 5, 4, 7, 6, 9},
{0, 2, 8, 3, 1, 5, 4, 7, 6, 9},
{2, 0, 8, 3, 1, 5, 4, 7, 6, 9},
{2, 3, 8, 0, 1, 5, 4, 7, 6, 9},
{2, 3, 8, 1, 0, 5, 4, 7, 6, 9},
{2, 3, 8, 1, 5, 0, 4, 7, 6, 9},
{2, 3, 8, 1, 5, 7, 4, 0, 6, 9},
{2, 3, 8, 1, 5, 7, 0, 4, 6, 9},
{2, 3, 8, 1, 5, 7, 6, 4, 0, 9},
{0, 3, 8, 1, 5, 7, 6, 4, 2, 9},
{9, 3, 8, 1, 5, 7, 6, 4, 2, 0},
{9, 0, 8, 1, 5, 7, 6, 4, 2, 3},
{9, 1, 8, 0, 5, 7, 6, 4, 2, 3},
{9, 1, 8, 7, 5, 0, 6, 4, 2, 3},
{9, 1, 8, 7, 0, 5, 6, 4, 2, 3},
{9, 1, 8, 7, 6, 5, 0, 4, 2, 3},
{9, 1, 8, 7, 6, 5, 4, 0, 2, 3},
{9, 1, 8, 7, 6, 5, 4, 3, 2, 0},
{9, 0, 8, 7, 6, 5, 4, 3, 2, 1},
{0, 9, 8, 7, 6, 5, 4, 3, 2, 1}}

hujunhua

上楼9只蚱蜢差点把我的机子蹦垮了，10只就不作全图搜索了，按11#策略，k(7)=28, 所以猜想 b(10)=33.

且慢！ k(3)=6, k(5)=15, k(7)=28, 似乎有 k(n)=C(n+1, 2).（为嘛是n+1, 盘子数啊）。

好在我还算得动k(9), 赶紧验算一下，果然k(9)=45. 所以b(12)=50?


但是，如果k(n)是二次增长而不是线性增长的，那11楼的策略就该有问题了。

aimisiyou

hujunhua 发表于 2020-8-27 00:20
上楼9只蚱蜢差点把我的机子蹦垮了，10只就不作全图搜索了，按11#策略，k(7)=28, 所以猜想 b(10)=33.

且 ...

如果空盘的位置可变，但数字仍是逆时针顺序，是否步数比空盘位置固定时的步数少呢？