推箱子C语言课程设计

《推箱子C语言课程设计》由会员分享，可在线阅读，更多相关《推箱子C语言课程设计（5页珍藏版）》请在金锄头文库上搜索。

1、C语言课程设计报告C Program Experiment Designing 一、 C语言课程设计目的及要求目的：根据课堂讲授内容，学生做相应的自主练习，消化课堂所讲解的内容；通过调试典型例题或习题积累调试C程序的经验；通过完成辅导教材中的编程题，逐渐培养学生的编程能力、用计算机解决实际问题的能力。要求：1 熟悉Turbo C 的编程环境、主要菜单功能。2 通过上机验证运算符、表达式、运算规则、函数使用。3 熟练使用C语言的典型语句编写简单程序。4 调试典型例题或习题。5 提高上机编程能力二、 实验类型设计类型三、 实验学时40学时四、 实验设备微型计算机、WINDOWS98以上版本的操作系

2、统、Turbo C2.0 软件一套五、 C语言课程参考教材：1. C语言程序设计 清华大学出版社 马靖善主编2 谭浩强.C语言程序设计（第三版）.北京：高等教育出版社，2002 题目：推箱子1基本功能介绍：本程序为游戏推箱子，该程序的基本功能有：推箱子游戏的求解难度比其他游戏高很多。有一些游戏有固定的解法，比如魔方。Windows经典小游戏扫雷可以总结出通用推理规则(请参见作者的“自动扫雷”中的说明)。一些游戏的搜索空间很小，可以用电脑蛮力求解，比如华容道，每一步只有两三种可能性。有一些游戏虽然搜索空间比较大，但是可以给电脑制定启发式搜索规则，让电脑比较“智能”地进行搜索，比如空当接龙，作者的

3、空当接龙工具就是让电脑向着理顺牌的次序的方向前进。 推箱子游戏的搜索空间极大，又没有合适的一般方法。人可以总结出一些模糊的规则，但是这些规则非常难以用程序语言描述。推箱子问题已经被证明是一种“NP-难的问题”，“NP-难的问题”是计算机领域中至今没有找到有效算法的一类著名难题。 目前，根本不存在对所有推箱子问题都能有效求解的方法。网上现有的程序一般只能有效地解决1010大小之内的题目。我的程序也不例外。软件的特色 我的工具的特色是先进的死锁检测算法。死锁就是一旦把箱子推动到某些位置，一些箱子就再也无法推动或者无法推到目的点，比如四个箱子成22摆放。推箱子高手对何种情况引起死锁非常敏感，这样他们

4、预先就知道决不能让某些局面形成，这也是高手高于常人的原因之一。我的工具能够检测出绝大部分这样的死锁，并且，由于对死锁的特征进行了高度提炼，能够检测出很多人也无法很快看穿的死锁。这样，工具的效率得到很大的提高。对于1010大小以内的题目，一般都能很快解出。每一行代表仓库的一行，不能有空行。 空格或=表示地板。每行最后连续的地板可以省略。 #表示墙。 表示人。 $表示箱子。 .表示目的点。 *表示在目的点上的箱子。 +或%表示在目的点上的人。 “编辑”菜单下的“目标人位置”是本工具的特色之一。在求解一些大型题目时，虽然不能直接使用本工具，但是可以把题目分解成若干个子目标，有些目标可以用工具求解。这

5、时，仅仅把箱子推到位是不够的，往往要指定最终状态时人所在的位置。比如要让人通过一个充满箱子的通道，然后把箱子回复原状。这时这个命令就可以起作用，它指定最终状态时人必须在的位置。 工具界面使用不同颜色表示墙、箱子和人。在显示解答时，以推动一次箱子为一步，期间的人的移动不计。此时所有人所能到的格子用绿色填满。 在“试玩模式下”，移动人直接点击目标点即可，推动箱子的方法是鼠标右键点击箱子的目标点并且按住不放，然后点击左键。 Stage目录下提供一些推箱子的题目。其中有些是文本格式的。其中WVsoko目录下的题目由20603(仓库大师游戏的作者)提供。SoftStar目录下的关卡由网友金优转换。他的其

6、他一些收藏整理或创作的关卡放在JinYou目录下。在此向两位网友表示感谢。=关于目标宏 所谓“目标宏”是模拟这样一种解题思路：很多关卡明显可以分成若干区域，有些区域集中了目标点，另一些区域则集中了很多箱子。对于这样的关卡，人的思路显然是个个击破，对于目标点集中的区域考虑如何按次序摆满所有的目标点；箱子集中的区域考虑如何“突围而出”，然后再把两者集中起来。 推箱子工具可以模拟一种特殊情况下的目标宏，其条件是： 1. 存在一个“断点”。所谓断点是，假如去掉仓库区域里的所有箱子，然后在“断点”放一个箱子，则这个箱子把整个仓库区域分成严格互不连通的两个部分。 2. 初始状态时“断点”上不能有箱子，也不

7、能是目标点。(如果有箱子或目标点的话，一般可以很容易手工改造成没有箱子或目标点的等价的状态。) 3. 所有的箱子在“断点”的一边，所有的目标点在另一边。 4. “断点”的上下格都是墙或者左右格都是墙。 如果能够找到这样的断点，则程序自动把题目切分成两部分求解，效率有极大提高。 巧妙利用工具的目标宏功能可以提供不少有用技巧。比如可以人工把通道弄窄以造成“断点”，从而解出以前不能解出的关卡。又如，很多大型关卡的局部是“突围”问题或者是“目标点到位问题”，这时可以自己构造一个带“断点”的关卡，断点一边是非常容易求解的，另一边则是拷贝过来的难题局部，这样就可以利用工具求解这个局部了。给箱子编号。 找出

8、那些能推的箱子的编号和面 让后逐个推每推一次就记录当时的位置信息。退完再找一遍箱子的编号和面再推。推到不能退了或出现以前重复位置信息，停。换其他推法。一次类推试找到能解的步骤记录。2测试及运行效果 该程序复制到WIN-TC以后我试着在TROUB-2.0里应用了一下，首先进入程序会有提示是否进入程序，单击Y进入程序，我试着点击N，没有进入，说明其第一个选择语句正常的运行了，然后进入了程序的主要菜单，这是个挺老的游戏“推箱子”，我在vc+6.0下写的，在windowsXP下通过测试。 游戏规则很简单，只要把黄色的箱子全部推到圆圈的地方就可以了。用这种方法表示上面的题目，可以得到上图右侧的二维数组，

9、行数和列数均为9。你可以看到左图并不是整整齐齐的二维图，它的最外围有一些缺口，我们在右图中全部用W来表示。这是显而易见的，它们没有什么作用，只是为了把图形填充为整齐的二维数组。如果你想用S来表示也无所谓，不会影响我们的程序执行，不过我想W更合适。以上是一个推箱子问题状态的文本表示法，或者说是输入输出的方法，便于我们查看问题的状态。但是对于计算机程序处理来说，它并不是理想的表示方法，计算机更善于处理二进制的数字。所以我们还应该用二进制的方式来表示问题的状态，以便于程序的处理。同样的，我们还是使用二维数组来表示，不过这次数组的元素不是char字符，而是二进制的unsigned char。经过简单的

10、分析可以知道，一个格子可以用4个bit来表示所有状态： FlagWall = 0x01, / 是否障碍物 FlagBox = 0x02, / 是否有箱子 FlagDest = 0x04, / 是否目的地 FlagSoko = 0x08 / 是否有人在输入和输出问题状态时，需要进行这两种表示法之间的转换。即在输入时，把文本表示法转换为二进制表示法；在输出时，则把二进制表示法转换为文本表示法。我们不仅要知道箱子最终能否被推到目的地，更重要的是，我们要知道箱子如何被一步一步地推到目的地。因此，我们需要在问题状态中记录从初始问题状态到解答状态所经过的每一步，这正是成员变量steps_的作用。我们用一个

11、嵌套类SokoStep来表示一步移动，用vector来表示所经过的N步移动。由于我们不知道从初始问题状态到解答状态需要经过多少步移动，这时vector容器就可以帮助我们很方便地保存每一步的数据。由于我们所有四个成员变量都具有普通的值语义，所以编译器自动生成的拷贝构造函数、赋值操作符和析构函数都完全可用，我们可以省下不少功夫。不过后面还有很多事情要做，推箱子游戏可要比数独问题、N皇后问题难弄多了。我们还是从容易的方面入手，先来搞定输入、输出操作符。正如前面所说的，输入输出的过程其实就是两种表示法的转换，先来看看输入操作符。由于二维数组的行数和列数也需要输入，所以我把它们放在最前面，接着是指定行数

12、和列数的char阵列，阵列中的每个char必须是七个字符(“WBSDIKO”)中的一个，否则我们抛出一个异常来结束程序。每读入一个char，我们就根据该char（文本表示法）来设置map_数组的对应元素（二进制表示法）。现在我们回到stateEq()成员函数，它的作用是把SOKO（推箱子的人）在不推动箱子的前提下可以走到的位置（即他的自由活动范围）全部标记上FlagSoko。这样，我们在判断一个箱子能否移动时就可以简单一些了，只要这个箱子的某一侧为空格(Space)，而另一侧为FlagSoko，那么这个箱子就可以向空的一侧移动。我个人认为该范例的可用性很广，稍微修改便可应用于很多程序中，我认为做程序，人性化是很重要的一个环节，这个程序就很好的体现了这一点，其运行的效果也很好，但是仍然有需要改进的部分，在今后的学习生活中我应该继续努力，把程序做的更完善更人性化，以上就是我这次C语言程序设计的全部。