魔方吧·中文魔方俱乐部

 找回密码
 注册
搜索
热搜: 魔方
楼主: 西北天狼

百度贴吧推箱子关卡移动步数推算 [复制链接]

Rank: 3Rank: 3

积分
816
帖子
181
精华
0
UID
1319509
性别
保密
兴趣爱好
推箱
发表于 2013-7-5 14:18:35 |显示全部楼层
本帖最后由 shamy 于 2013-7-5 14:27 编辑
西北天狼 发表于 2013-7-5 12:18
接楼上,图A是B8(八个箱子)的初始状态,图B是大约移动M6(六个箱子的最佳移动步数)步后的状态,图C是B8 ...


太棒了,有公式。感谢天狼兄推导。
哦,是N的一次函数。

请问推动数量能否计算呢?

还有,不知道有没有3次函数的?
二次函数的在版主的博客里好像有。

使用道具 举报

Rank: 5Rank: 5

积分
3378
帖子
535
精华
1
UID
1238171
性别
保密

超级搬运工

发表于 2013-7-5 14:53:03 |显示全部楼层
shamy 发表于 2013-7-5 14:18
太棒了,有公式。感谢天狼兄推导。
哦,是N的一次函数。

推动数当然可以计算,只要依葫芦画瓢就能做出。有兴趣的可以当作习题来做。
注意,这是递推函数,相当于3的指数函数小一点:M(2n)≈a×3^n。

使用道具 举报

Rank: 3Rank: 3

积分
816
帖子
181
精华
0
UID
1319509
性别
保密
兴趣爱好
推箱
发表于 2013-7-5 15:47:15 |显示全部楼层
西北天狼 发表于 2013-7-5 14:53
推动数当然可以计算,只要依葫芦画瓢就能做出。有兴趣的可以当作习题来做。
注意,这是递推函数,相当于 ...

哦,原来是这样,感谢天狼兄了。

使用道具 举报

Rank: 3Rank: 3

积分
816
帖子
181
精华
0
UID
1319509
性别
保密
兴趣爱好
推箱
发表于 2013-7-8 11:17:24 |显示全部楼层
看样子多加些箱子,步数增大的越多。100个箱子估计就天文数字了。60个箱子步数就多的离谱了。

使用道具 举报

Rank: 4

积分
1131
帖子
201
精华
0
UID
1256908
性别
保密

四年元老

发表于 2013-7-8 11:34:17 |显示全部楼层
这关步数太吓人,我只作为关卡收藏的。

使用道具 举报

Rank: 5Rank: 5

积分
3378
帖子
535
精华
1
UID
1238171
性别
保密

超级搬运工

发表于 2013-7-10 11:32:31 |显示全部楼层
本帖最后由 西北天狼 于 2013-7-10 11:57 编辑

箱子数        移动步数        推动步数
4         48         15
6         170         57
8         494         167
10         1346         455
12         3580         1209
14         9432         3183
16         24756         8351
18         64878         21881
20         169922         57303
22         444934         150039
24         1164928         392825
26         3049900         1028447
28         7984824         2692527
30         20904626         7049145
32         54729110         18454919
34         143282762         48315623
36         375119236         126491961
38         982075008         331160271
40         2571105852         866988863
42         6731242614         2269806329
44         17622622058         5942430135
46         46136623630         15557484087
总步数        415229612726         140017356783
Excel计算60个箱子还是够用的,再大就超出15位整数的有效范围了,需要编程实现。

使用道具 举报

Rank: 3Rank: 3

积分
816
帖子
181
精华
0
UID
1319509
性别
保密
兴趣爱好
推箱
发表于 2013-7-10 14:45:50 |显示全部楼层
西北天狼 发表于 2013-7-10 11:32
箱子数        移动步数        推动步数
4         48         15
6         170         57

多谢天狼兄讲解啊。想不到这关能有这么厉害。

使用道具 举报

Rank: 7Rank: 7Rank: 7

积分
5262
帖子
3216
精华
19
UID
13140
性别

论坛建设奖 八年元老

发表于 2013-7-13 18:33:12 |显示全部楼层
本帖最后由 sokoban 于 2013-7-13 18:41 编辑

我分析过这关的一个变形,写在博客中:http://sokoban.ws/blog/?p=430

正如天狼兄指出,原关有个特点,只有偶数个箱子有解。我把这个关卡做了很小的改动,使得奇数的时候也有解,这是一个好处。第二个好处是更容易建立递归关系。缺点就是不如原关卡美观。在经过变形后我给出了变形后关卡的通项公式。

原关和变形关的关系是:当箱子数n是偶数的时候,原关卡移动少11步,推动少3步。

fibo.png

使用道具 举报

Rank: 5Rank: 5

积分
3378
帖子
535
精华
1
UID
1238171
性别
保密

超级搬运工

发表于 2013-7-14 15:26:11 |显示全部楼层
本帖最后由 西北天狼 于 2013-7-23 22:50 编辑
sokoban 发表于 2013-7-13 18:33
我分析过这关的一个变形,写在博客中:http://sokoban.ws/blog/?p=430

正如天狼兄指出,原关有个特点,只 ...

还可以变形为:







公式跟箱子数的奇偶无关。
MnPn1.png

使用道具 举报

Rank: 5Rank: 5

积分
3378
帖子
535
精华
1
UID
1238171
性别
保密

超级搬运工

发表于 2013-7-14 23:19:42 |显示全部楼层
本帖最后由 西北天狼 于 2013-7-17 21:06 编辑

看了sokoban版主的博客,又认真研究了一下Fibonacci数列的通项公式,根据递推公式
M(2n)=3M(2n-2)-M(2n-4)+2n+24
P(2n)=3P(2n-2)-P(2n-4)+11
且M(4)=48, M(6)=170; P(4)=15, P(6)=57, 可以推导出如下公式:
M2nP2n.png

这同时也验证了18#的结论。

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

Archiver|手机版|魔方吧·中文魔方俱乐部

GMT+8, 2024-3-29 05:25

Powered by Discuz! X2

© 2001-2011 Comsenz Inc.

回顶部