考试网 >> IT认证 >> 等级 >> 二级考试 >> C程序设计例解(07)

发布时间：2006-06-28 00:05     点击：

07. 有2*n个盒子排成一行，其中有两个相邻的空盒，有n-1个盒子有符号'A'，有n-1个盒子有符号'B'。例如，n=5，并有初始配置如下：

A

B

B

A

.

.

A

B

A

B

试编制程序，将输入的盒子排列状态按以下交换规则将全部‘A’放到全部‘B’的左边，不管相邻两空盒的位置。交换规则是任意两个非空相邻盒子的内容可移入两个空盒中，但移动时不得变更两符号的前后次序。编写程序输入初始配置后，找出达到目标要求的最少交换次数的方案。

解：

    从一种盒子排列出发，将其中两个非空相邻盒子中的内容移入空盒的每一种移动，会使盒子产生新的排列状态，采用试探法穷举所有可能的移动找问题的解。首先将盒子初始排列存入移动步聚表，然后是试探和回溯循环。循环工作内容有：检查当前排列，若当前排列是要求的最终状态，则将达到该状态的移动步聚保存，并回溯去找更少移动步数的解。在试探超 过限定的深度或当前状态的所有可能移动都已试探穷尽情况下回溯；否则对当前状态取其当前移动方法产生新的后继状态存入移动步聚表，并继续向前试探。为能从某种排列出发，通过移动产生更接近目标要求的排列，对移动方法的选取作如下规定：

    。掠过无意义的来回移动；

    。不把两个相邻的同为符号‘A’的盒子向后移；

    。不把两个相邻的同为符号‘B’的盒子向前移；

    。不把两个盒子移入到这样的位置，移入后其首尾没有一个与相邻的盒子相同。

试探回溯找解算法如下：

算法---试探回溯找解

{

    输入初始排列；

    初始状态存入移动步聚表；

    设置其它初值；

    d=0;        /*当前试探深，或当前状态位置*/

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。