解法步数随关卡大小成指数增长的关卡

jinyou

三个房间结合的新题目，和对应答案能上传吗

我喜欢一个箱子。
想当初《老封推箱子》是我找到的，第一个能只搬一下，就自动完成任务的程序。同期洋程序只支持2500步，不能用。
jy2_one_space424.rar (754 Bytes, 下载次数: 63)

2009-6-10 22:58:21 上传

下载次数: 63

jinyou

《老封推箱子》v1.0 2002年吧

jinyou

这类步数随关卡大小成指数增长的关卡，其实每一步都不能变换了（故意浪费不算），
用计算机暴力计算比较容易。
经验证，这是最优解。

jinyou

18#
老封的早期版本我没有了。但是我觉得没有必要收集那些有许多BUG的东西。他1.85是修改已知BUG的。后来他突然大改界面，就很快升到4.0。中间几个版本都是修改界面BUG的。

14#
我画的一个箱子绝对不是线性增长，用地图大小和路程做坐标画出的绝不会是直线。当然没有达到指数级。

jinyou

这样的符合指数要求吗

#############################
#  #  #  #  #  #  #  #  #   #
#.   $#.   $#.   $#.  $ #.$ #
# $#. # $#. # $#. # $#+ # $ #
#. # $#. # $#. # $#. #  #.$##
# $#. # $#. # $#. # $#*$#  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #.$#
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #. #
# $#. # $#. # $#. # $#* #  #
#. # $#. # $#. # $#. #  #* #
# $#.   $#.   $#.    #. $  #
#  #  #  #  #  #  #  #  #  #
############################

lddddddddddddddrDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruurDluuurDluuurDluuurDluuurDluuurDluuurDluuurDrrddrUldddrUldddrUldddrUldddrUldddrUldddrUldddrUrruuuuuuuuuuuurUldddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUluuuuuuuuuuuuuurrddLruulldDDDrUdlDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddlllluurDluuurDDluuuurDDluuuurDDluuuurDDluuuurDDluuuurDDluuuurDDlddddddddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDluuUUrDDlddddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDluuUUrDDlddddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDluuUUrDDlddddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDluUUrDDlddRRRdrUUUlDuuuuuuuuuuuuuuurrddLruulldDDDrUldDDrUUlddDDrUUlddDDrUUlddDDrUUlddDDrUUddddLLLdlUUUrDldRuuuulDruuulDruuulDruuulDruuulDruuulDruuulDlllddrUldddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUlddddrUUluuuuuuuuuuuuuuRRRurDDDlU…… ……30259

jinyou

对不起粗心了.
题目是我贴的答案演示到省略号时的图案.

jinyou

又找到一题
level 0
#####
# + ##
##$.$ #
#  *  #
#  *  #
##  ###
####  
level 1
#####
# + #
#$.$#
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  
level 2
#####
# + #
#$.$#
# * #
# * #
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  
level 7
#####
# + #
#$.$#
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * #
# * ##
## *  #
#  *  #
#  *  #
##  ###
####  

每一级增加两个箱子，只能是偶数个，奇数个无解

level0="rDrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

level1="rDDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

level2="rDDDLUdrDDLUdrrddlLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuuuullDDRUldDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuuuurrDDLUdrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLLUlldRdrUrruulDuuuullDDRUldDDRUdddlUluRurrrddLLUdrruulDlddlUluRuuurrDDLUdrrddLLUlldRdrUrruulDuullDDRUdddlUluRurrrddLUruL"

box=2X+4=箱子个数
X|box | Total Pushes |   Total Moves |
0|  4 |           15 |            48 |
1|  6 |           57 |           170 |
2|  8 |          167 |           494 |
3| 10 |          455 |         1,346 |
4| 12 |        1,209 |         3,580 |
5| 14 |        3,183 |         9,432 |
6| 16 |        8,351 |        24,756 |
7| 18 |       21,881 |        64,878 |
8| 20 |       57,303 |       169,922 |
9| 22 |      150,039 |       444,934 |
10| 24 |      392,825 |     1,164,928 |
11| 26 |    1,028,447 |     3,049,900 |
12| 28 |    2,692,527 |     7,984,824 |
13| 30 |    7,049,145 |    20,904,626 |
14| 32 |   18,454,919 |    54,729,110 |
15| 34 |   48,315,623 |   143,282,762 |
16| 36 |  126,491,961 |   375,119,236 |
17| 38 |  331,160,271 |   982,075,008 |
18| 40 |  866,988,863 | 2,571,105,852 |
19| 42 |2,269,806,329 | 6,731,242,614 |

这个比较象九连环
以下用FOXPRO写了一个解法计算程序(仅对此题)，从用到两重循环可知，一定是指数级的。

************
set talk off
clear

maxn=9
DIME sa[10],sb[10],sc[10],sz[10]
*Sc[0]=""
*Sa[0]=""
Sa[1]="DDLUdr"
*Sb0="LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
Sc[1]="LUdrruulDlddlUluRuuurrDDLUdrrddL"
Sb[1]="LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"+ "LUlldRdrUrruulDuu" + "uu" +"ll" +"DDRUld" +"DDRUdddlUluRurrrddL"+ Sc[1]+ "LUlldRdrUrruulDuu"+"ll"+"DDRUdddlUluRurrrddL"
Sz[1]="rD"+Sa[1]+ "rddl" +Sb[1] + "UruL"

for n=2 to maxn

  Sa[n]=fm("DDLUdr",n)
  Sc[n]="LUdrruulDlddlUluRu" + fm("uu",n) +"rr"+ Sa[n] + "rddL"
  Sb[n]=Sb[n-1] +"LUlldRdrUrruulDuu" + fm("uu",n) +"ll" +fm("DDRUld",n) +"DDRUdddlUluRurrrddL"

  *Sb[n]=Sb[n] +Sc[1] +Sb[0]
  Sb[n]=Sb[n] +Sc[1] +"LUlldRdrUrruulDuullDDRUdddlUluRurrrddL"
  FOR j=2 to n
    Sb[n]=Sb[n] +Sc[j] +Sb[j-1]
  next
  Sz[n]="rD"+Sa[n]+ "rddl" +Sb[n] + "UruL"

  _cliptext=Sz[n]
  ?"level","box","move and push"
  ?      n,n*2+4, len(Sz[n])
  wait
next

return

func fm(fs,fm)
fss=""
if fm>=1 then
        for fi=1 to fm
                fss=fss+fs
        next
endif
return fss
***********

[ 本帖最后由 jinyou 于 2009-6-15 16:26 编辑 ]

jinyou

我的程序只算了十几个箱子．１００个箱子答案长度比魔方的可能状态数还多，我这种字符串累加方法，怎么能用，要是只计算长度那是很快的．极限(L[n+1]/L[n])=2.618=(((根号5)+1)/2) * (((根号5)+1)/2) （n 对应的箱子数=2*n+4） 就是每加两个箱子将增加 黄金比例平方倍 。

jinyou

37楼朋友说的对，是这个数。50355四舍五入就是10万。