关于沙发旋转90度角的问题

KeyTo9_Fans

小时候在【Game Boy】里玩过一个沙发旋转$90$度角的游戏。

（这个游戏和【九连环】游戏有点相似。）

游戏目标是操控小人从入口走到出口。

当沙发数为$n=3$时的大致的图是这样：



问：至少需要多少步，才能从入口走到出口？

注：当小人被沙发挡住时，如果沙发可以旋转，那么小人就会往前进方向跳$2$格，同时把沙发旋转$90$度。

例如：

走完$2$步之后是这样：



走完$3$步之后是这样：



走完$10$步之后是这样：



走完$11$步之后是这样：



依次类推，大约需要$56$步才能走到终点。

（如果对这道题还有不清楚的地方，就回贴问我哦~）

最终要求的问题是：

给定沙发的数量$n$，

问小人从入口走到出口至少需要多少步（求$f(n)$的通项公式）？

KeyTo9_Fans

这是沙发数量$n=1$的简单情形：



这是$n=2$的情况：



这样就好办了：

——————————————————————————————

已知：

$f(1)=10$、$f(2)=20$、$f(3)=56$

问：

$f(4)=?$

——————————————————————————————

《在线整数数列百科大全》(OEIS)的回答是：

http://oeis.org/search?q=10%2C20%2C56

完全不相关！

要么就是Fans算错了，要么就是前人没有关注过这个问题。

KeyTo9_Fans

经过简单的实物堆放演示：

        第0步：



        第55步：



        第119步：



我的初步结论是：

        当$n=4$时，$f(4)\approx 119$。

但是去OEIS搜索：10,20,56,119，就没结果了……



这事很奇怪。前面3项都是偶数，第4项突然变成奇数了……

有谁知道这是怎么回事吗？

dlpg070

KeyTo9_Fans 发表于 2019-2-22 07:19
经过简单的实物堆放演示：

        第0步：

我不懂，把119改为120试试看  A271512
10,20, 56, 120, 364, 560, 1140, 1540, 2600, 4960, 5984, 9880, 13244

KeyTo9_Fans

对不起，是我算错了。

当$n=2$时，需要$25$步。

这才是正确的数列：

http://oeis.org/search?q=10%2C25%2C56%2C119

风云剑

看起来确实和九连环类似，要完成高级别的，需要先完成低级别的两次。

mathe

10，25，56，119，246，501，1012，2035，4082，8177
应该可以很容易分析规律了，而且最短路径都是唯一的
$a_{n+1}-2a_n+a_{n-1}=2^{n+2}$

mathe

这个题目中每个沙发只有两个方向可用，在加上4N+5个人的位置，最多(4N+5)2^N个状态，而且每个状态最多两种转移情况，是个稀疏图，最短路径很容易计算

王守恩

KeyTo9_Fans 发表于 2019-2-22 14:35
对不起，是我算错了。

当$n=2$时，需要$25$步。

KeyTo9_Fans！
能把10，25，56 这 3 个数在空格里重新填写 1 次？谢谢！
5+2×10=25
6+2×25=56
7+2×56=119
8+2×119=246
9+2×246=501
...........

mathe

Best dist 10, totoal count 1
OO|O
P-JO
OOO
(2)=>
PO|O
O-JO
OOO
(0)=>
OP|O
O-JO
OOO
(6)=>
OOOO
O-7O
OP|
(9)=>
OOOO
O-7O
PO|
(5)=>
OOOO
P-7O
OO|
(3)=>
POOO
O-7O
OO|
(1)=>
OPOO
O-7O
OO|
(7)=>
OOPO
O-7O
OO|
(b)=>
OOOP
O-7O
OO|
(f)=>
Exit


Best dist 25, totoal count 1
OO|O|O
P-J-JO
OOOOO
(4)=>
PO|O|O
O-J-JO
OOOOO
(0)=>
OP|O|O
O-J-JO
OOOOO
(c)=>
OOOO|O
O-7-JO
OP|OO
(11)=>
OOOO|O
O-7-JO
PO|OO
(9)=>
OOOO|O
P-7-JO
OO|OO
(5)=>
POOO|O
O-7-JO
OO|OO
(1)=>
OPOO|O
O-7-JO
OO|OO
(d)=>
OOPO|O
O-7-JO
OO|OO
(15)=>
OOOP|O
O-7-JO
OO|OO
(1d)=>
OOOOOO
O-7-7O
OO|P|
(23)=>
OO|OOO
O-J-7O
OPOO|
(12)=>
OO|OOO
O-J-7O
POOO|
(a)=>
OO|OOO
P-J-7O
OOOO|
(6)=>
PO|OOO
O-J-7O
OOOO|
(2)=>
OP|OOO
O-J-7O
OOOO|
(e)=>
OOOOOO
O-7-7O
OP|O|
(13)=>
OOOOOO
O-7-7O
PO|O|
(b)=>
OOOOOO
P-7-7O
OO|O|
(7)=>
POOOOO
O-7-7O
OO|O|
(3)=>
OPOOOO
O-7-7O
OO|O|
(f)=>
OOPOOO
O-7-7O
OO|O|
(17)=>
OOOPOO
O-7-7O
OO|O|
(1f)=>
OOOOPO
O-7-7O
OO|O|
(27)=>
OOOOOP
O-7-7O
OO|O|
(2f)=>
Exit

Best dist 56, totoal count 1
OO|O|O|O
P-J-J-JO
OOOOOOO
(8)=>
PO|O|O|O
O-J-J-JO
OOOOOOO
(0)=>
OP|O|O|O
O-J-J-JO
OOOOOOO
(18)=>
OOOO|O|O
O-7-J-JO
OP|OOOO
(21)=>
OOOO|O|O
O-7-J-JO
PO|OOOO
(11)=>
OOOO|O|O
P-7-J-JO
OO|OOOO
(9)=>
POOO|O|O
O-7-J-JO
OO|OOOO
(1)=>
OPOO|O|O
O-7-J-JO
OO|OOOO
(19)=>
OOPO|O|O
O-7-J-JO
OO|OOOO
(29)=>
OOOP|O|O
O-7-J-JO
OO|OOOO
(39)=>
OOOOOO|O
O-7-7-JO
OO|P|OO
(43)=>
OO|OOO|O
O-J-7-JO
OPOO|OO
(22)=>
OO|OOO|O
O-J-7-JO
POOO|OO
(12)=>
OO|OOO|O
P-J-7-JO
OOOO|OO
(a)=>
PO|OOO|O
O-J-7-JO
OOOO|OO
(2)=>
OP|OOO|O
O-J-7-JO
OOOO|OO
(1a)=>
OOOOOO|O
O-7-7-JO
OP|O|OO
(23)=>
OOOOOO|O
O-7-7-JO
PO|O|OO
(13)=>
OOOOOO|O
P-7-7-JO
OO|O|OO
(b)=>
POOOOO|O
O-7-7-JO
OO|O|OO
(3)=>
OPOOOO|O
O-7-7-JO
OO|O|OO
(1b)=>
OOPOOO|O
O-7-7-JO
OO|O|OO
(2b)=>
OOOPOO|O
O-7-7-JO
OO|O|OO
(3b)=>
OOOOPO|O
O-7-7-JO
OO|O|OO
(4b)=>
OOOOOP|O
O-7-7-JO
OO|O|OO
(5b)=>
OOOOOOOO
O-7-7-7O
OO|O|P|
(67)=>
OOOO|OOO
O-7-J-7O
OO|POO|
(45)=>
OO|O|OOO
O-J-J-7O
OPOOOO|
(24)=>
OO|O|OOO
O-J-J-7O
POOOOO|
(14)=>
OO|O|OOO
P-J-J-7O
OOOOOO|
(c)=>
PO|O|OOO
O-J-J-7O
OOOOOO|
(4)=>
OP|O|OOO
O-J-J-7O
OOOOOO|
(1c)=>
OOOO|OOO
O-7-J-7O
OP|OOO|
(25)=>
OOOO|OOO
O-7-J-7O
PO|OOO|
(15)=>
OOOO|OOO
P-7-J-7O
OO|OOO|
(d)=>
POOO|OOO
O-7-J-7O
OO|OOO|
(5)=>
OPOO|OOO
O-7-J-7O
OO|OOO|
(1d)=>
OOPO|OOO
O-7-J-7O
OO|OOO|
(2d)=>
OOOP|OOO
O-7-J-7O
OO|OOO|
(3d)=>
OOOOOOOO
O-7-7-7O
OO|P|O|
(47)=>
OO|OOOOO
O-J-7-7O
OPOO|O|
(26)=>
OO|OOOOO
O-J-7-7O
POOO|O|
(16)=>
OO|OOOOO
P-J-7-7O
OOOO|O|
(e)=>
PO|OOOOO
O-J-7-7O
OOOO|O|
(6)=>
OP|OOOOO
O-J-7-7O
OOOO|O|
(1e)=>
OOOOOOOO
O-7-7-7O
OP|O|O|
(27)=>
OOOOOOOO
O-7-7-7O
PO|O|O|
(17)=>
OOOOOOOO
P-7-7-7O
OO|O|O|
(f)=>
POOOOOOO
O-7-7-7O
OO|O|O|
(7)=>
OPOOOOOO
O-7-7-7O
OO|O|O|
(1f)=>
OOPOOOOO
O-7-7-7O
OO|O|O|
(2f)=>
OOOPOOOO
O-7-7-7O
OO|O|O|
(3f)=>
OOOOPOOO
O-7-7-7O
OO|O|O|
(4f)=>
OOOOOPOO
O-7-7-7O
OO|O|O|
(5f)=>
OOOOOOPO
O-7-7-7O
OO|O|O|
(6f)=>
OOOOOOOP
O-7-7-7O
OO|O|O|
(7f)=>
Exit