楼上的程序太麻烦,效率低【骑士游历问题】 设有一个m×n的棋盘(2≤m≤50,2≤n≤50),在棋盘上任一点有一个中国象棋“马”,马走的规则为:马走日字;马只能向右走。当m,n给出后,同时给出马起始的位置和终点的位置,试找出从起点到终点所有路径的数目。输入: m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)输出: 路径数目(若不存在,则输出0)【分析】 本题可以使用深度搜索发求解,但是效率很低,当路径很多时,不可能在短时间内出解。可以采用动态规划的设计思想。(专为楼下设计) 从(x1,y1)位置出发,按照由左到右的顺序定义阶段的方向。位于(x2,y2)的左方且可达(x2,y2)的跳马位置集合都是(x2,y2)的子问题,起点至(x2,y2)的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。 阶段i:中国象棋马当前的列位置(x1≤i≤x2) 状态j:中国象棋马在i列的行位置(1≤i≤m) 状态转移方程map[i,j]:起点(x1,y1)至(i,j)的路径数目附标程:const maxm=50; maxn=50;var m,n,x1,y1,x2,y2:integer; i,j,k,x,y:integer; map:array[-2..maxm+2,-2..maxn+2] of extended;beginfillchar(map,sizeof(map),0);readln(m,n,x1,y1,x2,y2);map[x1,y1]:=1;for i:=x1+1 to x2 do for j:=1 to m do map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];writeln(map[x2,y2]:0:0);end. 搜索比较慢,有代码如下:program p7_1;const dx:array[1..8] of integer=(1,-1,-2,-2,-1,1,2,2); dy:array[1..8] of integer=(2,2,-1,-1,-2,-2,-1,1);var board:array[-1..7,-1..7] of integer; t,i,j,a,b:integer;procedure search(t,x,y:integer);var p,m,n:integer;begin if t=26 then begin for m:=1 to 5 do begin for n:=1 to 5 do write(board[m,n]:3); writeln; end; t:=-1; halt end; if board[x,y]=0 then begin board[x,y]:=t;inc(t); for p:=1 to 8 do search(t,x+dx[p],y+dy[p]); board[x,y]:=0; end;end;begin t:=1; for i:=-1 to 7 do for j:=-1 to 7 do board[i,j]:=-1; for a:=1 to 5 do for b:=1 to 5 do board[a,b]:=0; search(t,1,1); if t-1 then write('Wrong!');end.
创新互联建站基于成都重庆香港及美国等地区分布式IDC机房数据中心构建的电信大带宽,联通大带宽,移动大带宽,多线BGP大带宽租用,是为众多客户提供专业遂宁托管服务器报价,主机托管价格性价比高,为金融证券行业服务器托管,ai人工智能服务器托管提供bgp线路100M独享,G口带宽及机柜租用的专业成都idc公司。
没做过,看过。“骑士总是移向具有最少出口且没有到达过的方格之一”是说,它可移动的位置有N个,在这N个中,寻找下一次可移动的位置最少的那个,做为骑士要去的点的位置。这是一种贪婪法,有的位置有解但你却求不出来。
楼上的程序太麻烦,效率低
【骑士游历问题】
设有一个m×n的棋盘(2≤m≤50,2≤n≤50),在棋盘上任一点有一个中国象棋“马”,马走的规则为:马走日字;马只能向右走。当m,n给出后,同时给出马起始的位置和终点的位置,试找出从起点到终点所有路径的数目。
输入:
m,n,x1,y1,x2,y2 (分别表示m,n、起点坐标和终点坐标)
输出:
路径数目(若不存在,则输出0)
【分析】
本题可以使用深度搜索发求解,但是效率很低,当路径很多时,不可能在短时间内出解。可以采用动态规划的设计思想。(专为楼下设计)
从(x1,y1)位置出发,按照由左到右的顺序定义阶段的方向。位于(x2,y2)的左方且可达(x2,y2)的跳马位置集合都是(x2,y2)的子问题,起点至(x2,y2)的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。
阶段i:中国象棋马当前的列位置(x1≤i≤x2)
状态j:中国象棋马在i列的行位置(1≤i≤m)
状态转移方程map[i,j]:起点(x1,y1)至(i,j)的路径数目
附标程:
const
maxm=50;
maxn=50;
var
m,n,x1,y1,x2,y2:integer;
i,j,k,x,y:integer;
map:array[-2..maxm+2,-2..maxn+2] of extended;
begin
fillchar(map,sizeof(map),0);
readln(m,n,x1,y1,x2,y2);
map[x1,y1]:=1;
for i:=x1+1 to x2 do
for j:=1 to m do
map[i,j]:=map[i-1,j-2]+map[i-1,j+2]+map[i-2,j-1]+map[i-2,j+1];
writeln(map[x2,y2]:0:0);
end.
搜索比较慢,有代码如下:
program p7_1;
const dx:array[1..8] of integer=(1,-1,-2,-2,-1,1,2,2);
dy:array[1..8] of integer=(2,2,-1,-1,-2,-2,-1,1);
var board:array[-1..7,-1..7] of integer;
t,i,j,a,b:integer;
procedure search(t,x,y:integer);
var p,m,n:integer;
begin
if t=26 then begin
for m:=1 to 5 do begin
for n:=1 to 5 do write(board[m,n]:3);
writeln;
end;
t:=-1;
halt
end;
if board[x,y]=0 then begin
board[x,y]:=t;inc(t);
for p:=1 to 8 do search(t,x+dx[p],y+dy[p]);
board[x,y]:=0;
end;
end;
begin
t:=1;
for i:=-1 to 7 do
for j:=-1 to 7 do board[i,j]:=-1;
for a:=1 to 5 do
for b:=1 to 5 do board[a,b]:=0;
search(t,1,1);
if t-1 then write('Wrong!');
end.