• 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

Pascal经典算法详解 – 骑士游历问题

大数据 水墨上仙 2237次浏览

设有一个m×n的棋盘(2≤m≤50,2≤n≤50),在棋盘上任一点有一个中国象棋“马”,马走的规则为:马走日字;马只能向右走。当m,n给出后,同时给出马起始的位置和终点的位置,试找出从起点到终点所有路径的数目。

输入:&nbsp&nbsp&nbsp&nbspm,n,x1,y1,x2,y2&nbsp(分别表示m,n、起点坐标和终点坐标)输出:&nbsp&nbsp&nbsp&nbsp路径数目(若不存在,则输出0)【分析】&nbsp&nbsp&nbsp本题可以使用深度搜索发求解,但是效率很低,当路径很多时,不可能在短时间内出解。可以采用动态规划的设计思想。&nbsp&nbsp&nbsp&nbsp从(x1,y1)位置出发,按照由左到右的顺序定义阶段的方向。位于(x2,y2)的左方且可达(x2,y2)的跳马位置集合都是(x2,y2)的子问题,起点至(x2,y2)的路径数实际上等于起点至这些位置集的路径数之和。可以按照阶段的顺序依次计算每一个阶段每个点的路径数目。&nbsp&nbsp&nbsp&nbsp阶段i:中国象棋马当前的列位置(x1≤i≤x2)&nbsp&nbsp&nbsp&nbsp状态j:中国象棋马在i列的行位置(1≤i≤m)&nbsp&nbsp&nbsp&nbsp状态转移方程map[i,j]:起点(x1,y1)至(i,j)的路径数目&nbsp&nbsp&nbsp&nbsp具体算法如下:

fillchar(map,sizeof(map),0);
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]);

详细代码:

program qishiyouli;
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.


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明Pascal经典算法详解 – 骑士游历问题
喜欢 (0)
加载中……