编号 (i)
pyz(i).xzb
pyz(i).yzb
方向
0
2
1
右上
1
2
-1
右下
2
1
2
右上
3
1
-2
右下
从当前位置搜索它的相邻位置的时候，为了便于程序的实现，我们可以按照移动编号的固定顺序来进行，比如，首先尝试第0种移动方法，其次尝试第1种移动方法，再次尝试第2种移动方法，最后尝试第3种移动方法。
任务一参考程序如下：
cls
type dian
xzb as integer
yzb as integer
end type
dim pyz(3) as dian, lj(50) as dian
dim herep as dian, nextp as dian
dim m as integer, n as integer
rem初始化偏移值
pyz(0).xzb = 2: pyz(0).yzb = 1
pyz(1).xzb = 2: pyz(1).yzb = -1
pyz(2).xzb = 1: pyz(2).yzb = 2
pyz(3).xzb = 1: pyz(3).yzb = -2
rem初始化当前位置
herep.xzb = 1: herep.yzb = 1
input "please input m and n:", m, n
rem在m×n的棋盘上寻找从左下角到右上角的一条路径
def fnfind (m, n)
rem初始化变量opti（用来标识是哪种移动方法）和栈顶元素指针k
opti = 0: k = 0
rem是否可以向下一位置移动
do while not (herep.xzb = m and herep.yzb = n)
do while opti <= 3
r = herep.xzb + pyz(opti).xzb
c = herep.yzb + pyz(opti).yzb
if r <= m and c <= n and c >= 1 then exit do
opti = opti + 1
loop
rem若可以向下一位置移动，就移动到下一位置
if opti <= 3 then
k = k + 1: lj(k).xzb = herep.xzb
lj(k).yzb = herep.yzb
herep.xzb = r: herep.yzb = c
opti = 0
rem若不能再向下移动，就回溯
else
rem若栈空，则返回0，并结束寻找
if k = 0 then
fnfind = 0
exit def
end if
rem栈顶元素出栈，并存入nextp
nextp.xzb = lj(k).xzb
nextp.yzb = lj(k).yzb
k = k – 1
rem确定下一种移动方法
if herep.xzb - nextp.xzb = 2 then
if herep.yzb > nextp.yzb then
opti = 1
else opti = 2
end if
elseif herep.yzb > nextp.yzb then
opti = 3
end if
rem产生新的当前位置herep
herep.xzb = nextp.xzb
herep.yzb = nextp.yzb
end if
loop
fnfind = 1
end def
zd = fnfind(m, n)
if zd = 1 then
for i = 1 to k
print "("; lj(i).xzb; ","; lj(i).yzb; ")->";
next i
print "("; m; ","; n; ")"
else print "No"
end if
end
对于任务二，要找出从起点到终点的所有路径的数目。我们可以设置一个统计变量ljs。在搜索解空间的过程中，每当搜索到一条从起点到终点的路径，就让统计变量ljs的值增1。这样，当对解空间的搜索过程结束之后，统计变量ljs的值就是问题的答案。
算法程序如下：
1．初始化统计变量
2．寻找从起点到终点的所有路径
3．输出答案（统计变量ljs的值）
其中第2步需要求精。
回溯是实现递归过程的一种有效方法，利用递归过程的层层调用及层层返回，每次返回，都返回到调用语句的下一条语句继续执行的特点，从当前位置通往终点的所有路径的寻找过程，我们使用递归回溯很容易得以实现。
任务二参考程序如下：
declare sub try (x as integer, y as integer)
cls
type dian
xzb as integer
yzb as integer
end type
dim shared pyz(3) as dian
dim shared qidian as dian, zhongdian as dian
dim shared ljs as integer, m as integer, n as integer
input "please input m and n:", m, n
input "starting point:", qidian.xzb, qidian.yzb
input "end point:", zhongdian.xzb, zhongdian.yzb
rem初始化偏移值
pyz(0).xzb = 2: pyz(0).yzb = 1
pyz(1).xzb = 2: pyz(1).yzb = -1
pyz(2).xzb = 1: pyz(2).yzb = 2
pyz(3).xzb = 1: pyz(3).yzb = -2
rem初始化变量ljs（用来统计路径的数目）
ljs = 0
rem寻找从起点到终点的所有路径
call try(qidian.xzb, qidian.yzb)
print ljs
end
rem寻找从当前位置(x,y)通往终点的所有路径
sub try (x as integer, y as integer)
for i = 0 TO 3
rem保存当前位置
x0 = x: y0 = y
rem移动到相邻位置
x = x + pyz(i).xzb: y = y + pyz(i).yzb
rem若已经走到终点（即找到一条路径），就让路径数加1
if x = zhongdian.xzb and y = zhongdian.yzb then
ljs = ljs + 1
else
rem若可以继续向下移动，则递归调用过程try
if x <= zhongdian.xzb and y <= n and y >= 1 then
call try(x, y)
end if
end if
rem释放当前位置
x = x0: y = y0
next i
end sub
注：此文刊于《中学生电脑》杂志2003年第2期
|