UC知道解释下 Pascal程序
来源：百度知道 编辑：UC知道 时间：2024/06/14 02:49:38
魔板（template）
问题描述：
1 2 3 4
5 6 7 8
在Rubik先生发明的魔方风靡世界以后，他又发明了它的魔板，初始状态如上图所示，他又定义了三种操作：
A操作：上下两行对调；
B操作：全部右移一格；
C操作：中间四格顺时针旋转一格。
现任意给出一个终止状态，通过A、B、C三种操作，将上表所示初始状态变成给出终止状态。
[算法分析]
该题目很明显是用搜索做，如果用深度优先搜索，则可能出现死循环，而且时间很长，所以只能用宽度优先搜索。但是如果没有一种好的方法来判断是否已经加入列表，时间可能会超时，所以想到了哈希表。按照初始状态标号，则共有8！=40320个情况。根据公式：
可以将每一种情况唯一对应到0~40319中的一个数。再用宽度优先搜索可以很轻松的实现这一算法。
[参考程序]
program template;
Const
Fact:array[0..7] of word=(1,1,2,6,24,120,720,5040);
rule:array[1..3,1..8] of byte=((5,6,7,8,1,2,3,4),(4,1,2,3,6,7,8,5),(1,7,2,4,5,3,6,8));
obj=40319;
type
Ttable=array[1..8] of byte;
Tlist=^Tnode;
Tnode=object
Now:word;
Next:tlist;
End;
Var
T,t1:ttable;
Head,tail:tlist;
I,j:byte;
State:array[0..40319] of byte;
Function change1:word;
Var
I,j,s:word;
K:ttab
问题描述：
1 2 3 4
5 6 7 8
在Rubik先生发明的魔方风靡世界以后，他又发明了它的魔板，初始状态如上图所示，他又定义了三种操作：
A操作：上下两行对调；
B操作：全部右移一格；
C操作：中间四格顺时针旋转一格。
现任意给出一个终止状态，通过A、B、C三种操作，将上表所示初始状态变成给出终止状态。
[算法分析]
该题目很明显是用搜索做，如果用深度优先搜索，则可能出现死循环，而且时间很长，所以只能用宽度优先搜索。但是如果没有一种好的方法来判断是否已经加入列表，时间可能会超时，所以想到了哈希表。按照初始状态标号，则共有8！=40320个情况。根据公式：
可以将每一种情况唯一对应到0~40319中的一个数。再用宽度优先搜索可以很轻松的实现这一算法。
[参考程序]
program template;
Const
Fact:array[0..7] of word=(1,1,2,6,24,120,720,5040);
rule:array[1..3,1..8] of byte=((5,6,7,8,1,2,3,4),(4,1,2,3,6,7,8,5),(1,7,2,4,5,3,6,8));
obj=40319;
type
Ttable=array[1..8] of byte;
Tlist=^Tnode;
Tnode=object
Now:word;
Next:tlist;
End;
Var
T,t1:ttable;
Head,tail:tlist;
I,j:byte;
State:array[0..40319] of byte;
Function change1:word;
Var
I,j,s:word;
K:ttab
首先说一句Hash表开的应该比总数小才叫Hash表，这个不是。
第二，你既然已经定义了一个40320的数组为什么还要链表呢？
我的建议是开一个40320大小的word数组，然后用黑白灰节点表示，每次扩展所有灰节点，应该是比较能解决办法的。
看完了，哪句不懂啊？