当前位置:首页 >> 学科竞赛 >>

骑士周游问题


回专题模式 回学习阶段模式 【题目名称、来源】 骑士周游问题(经典题目 knight.pas) 【问题描述】 骑士周游问题 如下图所示,国际象棋棋盘上的马一步可以跳向八个方向,问:如果给出一个 n*m 的 棋盘,马从左上角开始跳,是否能够不重复的跳遍所有的格子。 输入:棋盘大小 n m 输出:n*m 个数,分 n 行 m 列,便利棋盘格子的顺序


>
源程序: 【所属专题】 【适合学习阶段】 【解题思路】 问题分析: 该问题是经典搜索问题 解答树: 2,3

1,1 3,2

1,5

3,5

4,4

3,4 存储结构: const direct:array[1..8,1..2] of integer= ((-2,1),(-1,2),(2,1),(1,2),(2,-1),(1,-2),(-1,-2),(-2,-1)); {马可以跳向八个方向的相对位移,使用常量数组可以将规则统一} Var a:array[1..10,1..10] of integer;{使用数组作为棋盘的存储, 如果某一格子没有走过值为 0, 否则为步数} 【测试数据】

【源程序】 program qishi;{Qi shi zhou you wen ti} const direct:array[1..8,1..2] of integer= ((-2,1),(-1,2),(2,1),(1,2),(2,-1),(1,-2),(-1,-2),(-2,-1)); {马可以跳向八个方向的相对位移,使用常量数组可以将规则统一} var n,m,x,y:integer; i,j,count:integer; a:array[1..10,1..10] of integer; procedure tiao(step,x,y:integer);{递归过程实现回溯} var r,i,j,k,l:integer;{r 是规则号,i,j 是按照 r 规则跳后的新位置} begin for r:=1 to 8 do begin i:=x+direct[r,1];j:=y+direct[r,2];{求新位置} if (i>=1)and(i<=n)and(j<=m)and(j>=1) then {如果新位置合法} if a[i,j]=0 then begin a[i,j]:=step; if step=n*m then begin{如果到达终点则打印} for k:=1 to n do begin for l:=1 to m do write(a[k,l]:3); writeln; end; close(output); halt; end else tiao(step+1,i,j);{如果没有到终点,跳下一步} a[i,j]:=0;{回溯} end; end; end; begin assign(input,'qishi.in'); reset(input); readln(n,m); {init} assign(output,'qishi.out'); rewrite(output); for i:=1 to n do for j:=1 to m do a[i,j]:=0; {初始化数组} a[1,1]:=1; tiao(2,1,1); writeln('Impossible'); close(output); end.


相关文章:
旅行商问题
TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于国际象棋 棋盘中的 64 个方格,走访 64 个方格一次且仅一次,并且最终返回到起始点。 TSP 由...
TSP问题的概述
TSP 问题的由来 TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于国际 象棋棋盘中的 64 个方格,走访 64 个方格一次且仅一次,并且最终返回到...
2.旅行商TSP问题(1.1)
TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于 国际象棋棋盘中的 64 个方格, 走访 64 个方格一次且仅一次,并且最终返回到起 始点。 TSP...
旅行商问题
4、TSP 的历史很久,最早的描述是 1759 年欧拉研究的骑士周游问题,即对于国际象棋棋盘 中的 64 个方格,走访 64 个方格一次且仅一次,并且最终返回到起始点。TSP ...
高斯的确是神一般的存在
Gauss 可以在六步以内解决骑士周游问题。 Gauss 同时给 Bertrand Russell 和自己理发。 Gauss 想喝果汁时,直接对橙子使用夹挤定理。 Gauss 唱完 “Aleph-Null ...
运筹学学习心得体会
而此论文与范德 蒙德的一篇关于骑士周游问题的文章,则是继承了莱布尼茨提出的“位置分析” 的方法。 欧拉提出的关于凸多边形顶点数、棱数及面数之间的关系的欧拉...
旅行商问题(TSP)及其应用 安康学院毕业论文
20 - 前 言 旅行商问题(Traveling Salesman Problem,简称 TSP)是数学领域的著名问题之 一.TSP 的历史悠久,最早描述的是 1759 年欧拉研究的骑士周游问题.即对于...
基于蚁群算法的TSP问题求解策略研究
TSP 问题的历史悠久,最早的描述是 1759 年欧拉研究的骑士周游问题,即 对于国际象棋棋盘中的 64 个方格,如何做到每个方格都走访并只走访一次之后 回到起点位置。TSP...
数据结构课程设计贪心法求解TSP问题
TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中 的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。类似的问题有: 中国...
基于模拟退火算法的TSP问题优化
1.1 TSP 问题的介绍 1.1.1 TSP 问题的发展 TSP 的历史很悠久,在欧洲这个问题类似于骑士周游问题,一个骑士需要周游若 干个城市,但是不能重复经过同一个城市,...
更多相关标签:
骑士周游 | 骑士周游算法 | 八皇后问题 | 骑士周游问题 java | 骑士巡逻 | 骑士周游程序 | 骑士周游问题c | 骑士周游问题 欧拉 |