急需pascal宽搜、深搜程序
var
a:array[1..10] of integer;
b:array[1..10] of boolean;
c:array[1..20] of boolean;
d:array[-9..9] of boolean;
n:integer;
procedure print;
var i:integer;
begin
for i:=1 to n do write(a[i],' ');
writeln;
end;
procedure try(t:integer);
var j:integer;
begin
if t>n then
begin
print;
exit;
end;
for j:=1 to n do
if b[j] and c[t+j] and d[t-j] then
begin
a[t]:=j;
b[j]:=false;
c[t+j]:=false;
d[t-j]:=false;
try(t+1);
b[j]:=true;
c[t+j]:=true;
d[t-j]:=true;
end;
End;
begin
assign(input,'queen.in');
assign(output,'queen.out');
reset(input);
rewrite(output);
readln(n);
fillchar(b,sizeof(b),true);
fillchar(c,sizeof(c),true);
fillchar(d,sizeof(d),true);
try(1);
close(input);
close(output);
end.
这个程序是N皇后问题的程序,也包括8皇后
骑士问题
输入文件:knight.in
输出文件:knight.out
问题描述:
在一个标准8*8的图际象棋棋盘上,棋盘中有些格子可能是有障碍物的。已知骑士的初始位置和目标位置,你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。有障碍物的格子当然不可以到达。
标准的8*8的国际象棋棋盘中每一个格子可以用唯一的编号确定。行用1-8这8个数字依次表示,列用’a’—‘h’这8个字母依次表示。例如左下图的骑士所在位置(图中有n的格子)的编号为“d4”(注意’d’和’4’之间没有空格)。
我们知道国际象棋中的骑士可以按“L”路线移动(一个方向走2个格子,接着垂直方向走1个格子)。因此,如左上图中的骑士(位于d4),可以到达位置c2、b3、b5、c6、e6、f5、f3和e2(图中有’x’)标记的格子)。此外,骑士不能移出棋盘。
骑士可以按照移动规则自由地在棋盘上没有障碍物的格子中移动,右上图给出了一个骑士移动的例子。初始格子用’n’标记,目标格子用’N’标记,有障碍物的格子用’b’标记。一个可行的移动序列在图中用数字标记出来。(a1,b3,a5,c6,e5,g4,h2,f1)。总共需要7步才能完成。事实上,这也就是最小的步数了。
输入格式:
输入文件包括1个或多个测试数据。
每一个测试数据的第一行是一个整数b(-1<=b<=62),表示棋盘中有障碍物的格子数目,当b=-1时,输入文件结束。
第二行含b个不同的有障碍物的格子编号,用空格隔开。当b=0时,此行为空行。
第三行是骑士的初始格子和目标格子的编号,也是用空格隔开。初始格子和目标格子是不同的,且都没有障碍物。
输出格式:
对于每个数据,输出一行。格式:Board n: m moves
其中n表示数据的序号(从1开始)m表示骑士所用的最小的步数。
如果骑士无法到达目标格子,输出:Board n: not reachable
输入样例:
10
c1 d1 d5 c2 c3 c4 d2 d3 d4 c5
a1 f1
0
c1 b3
2
b3 c2
a1 b2
-1
输出样例:
Board 1:7 moves
Board 2:1 moves
Board 3:not reachable
宽搜(骑士问题)
const f:array[1..8,1..2]of integer=((-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1));
type zb=record
i:integer;
j:integer;
bu:integer;
end;
var b,i,j,k,answer:integer;
pan:array[-1..10,-1..10]of boolean;
start,finish:zb;
qi:array[1..100000]of zb;
can:boolean;
procedure zhuan(s:string;var i,j:integer);
begin
i:=ord(s[2])-ord('0');
j:=ord(s[1])-ord('a')+1;
end;
procedure init;
var s,sub:string;
i,j:integer;
begin
readln(s);
if s'' then
repeat
sub:=copy(s,1,2);
zhuan(sub,i,j);
pan[i,j]:=false;
delete(s,1,3);
until s='';
readln(s);
sub:=copy(s,1,2);
zhuan(sub,start.i,start.j);
sub:=copy(s,4,2);
zhuan(sub,finish.i,finish.j);
end;
function ok(i,j:integer):boolean;
begin
if (i>0) and (i0) and (j<9) and pan[i,j] then ok:=true else ok:=false;
end;
procedure work;
var p,q,i:integer;
qs,kz:zb;
pd:boolean;
begin
p:=0;
q:=1;
qi[1].i:=start.i;
qi[1].j:=start.j;
qi[1].bu:=0;
can:=true;
pd:=false;
repeat
inc(p);
qs:=qi[p];
for i:=1 to 8 do
begin
kz.i:=qs.i+f[i,1];
kz.j:=qs.j+f[i,2];
if ok(kz.i,kz.j) then
begin
pan[kz.i,kz.j]:=false;
inc(q);
qi[q].i:=kz.i;
qi[q].j:=kz.j;
qi[q].bu:=qi[p].bu+1;
if (kz.i=finish.i) and (kz.j=finish.j) then
begin
pd:=true;
answer:=qi[q].bu;
end;
end;
end;
until (p=q) or (pd);
if p=q then can:=false;
end;
procedure print;
begin
if can then writeln(answer,' moves') else writeln('not reachable');
end;
begin
assign(input,'knight.in'); reset(input);
assign(output,'knight.out'); rewrite(output);
k:=0;
repeat
readln(b);
inc(k);
if b-1 then
begin
write('Board ',k,': ');
for i:=1 to 8 do
for j:=1 to 8 do pan[i,j]:=true;
init;
work;
print;
end;
until b=-1;
close(input);
close(output);
end.
输入文件:knight.in
输出文件:knight.out
问题描述:
在一个标准8*8的图际象棋棋盘上,棋盘中有些格子可能是有障碍物的。已知骑士的初始位置和目标位置,你的任务是计算出骑士最少需要多少步可以从初始位置到达目标位置。有障碍物的格子当然不可以到达。
标准的8*8的国际象棋棋盘中每一个格子可以用唯一的编号确定。行用1-8这8个数字依次表示,列用’a’—‘h’这8个字母依次表示。例如左下图的骑士所在位置(图中有n的格子)的编号为“d4”(注意’d’和’4’之间没有空格)。
我们知道国际象棋中的骑士可以按“L”路线移动(一个方向走2个格子,接着垂直方向走1个格子)。因此,如左上图中的骑士(位于d4),可以到达位置c2、b3、b5、c6、e6、f5、f3和e2(图中有’x’)标记的格子)。此外,骑士不能移出棋盘。
骑士可以按照移动规则自由地在棋盘上没有障碍物的格子中移动,右上图给出了一个骑士移动的例子。初始格子用’n’标记,目标格子用’N’标记,有障碍物的格子用’b’标记。一个可行的移动序列在图中用数字标记出来。(a1,b3,a5,c6,e5,g4,h2,f1)。总共需要7步才能完成。事实上,这也就是最小的步数了。
输入格式:
输入文件包括1个或多个测试数据。
每一个测试数据的第一行是一个整数b(-1<=b<=62),表示棋盘中有障碍物的格子数目,当b=-1时,输入文件结束。
第二行含b个不同的有障碍物的格子编号,用空格隔开。当b=0时,此行为空行。
第三行是骑士的初始格子和目标格子的编号,也是用空格隔开。初始格子和目标格子是不同的,且都没有障碍物。
输出格式:
对于每个数据,输出一行。格式:Board n: m moves
其中n表示数据的序号(从1开始)m表示骑士所用的最小的步数。
如果骑士无法到达目标格子,输出:Board n: not reachable
输入样例:
10
c1 d1 d5 c2 c3 c4 d2 d3 d4 c5
a1 f1
0
c1 b3
2
b3 c2
a1 b2
-1
输出样例:
Board 1:7 moves
Board 2:1 moves
Board 3:not reachable
宽搜(骑士问题)
const f:array[1..8,1..2]of integer=((-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1));
type zb=record
i:integer;
j:integer;
bu:integer;
end;
var b,i,j,k,answer:integer;
pan:array[-1..10,-1..10]of boolean;
start,finish:zb;
qi:array[1..100000]of zb;
can:boolean;
procedure zhuan(s:string;var i,j:integer);
begin
i:=ord(s[2])-ord('0');
j:=ord(s[1])-ord('a')+1;
end;
procedure init;
var s,sub:string;
i,j:integer;
begin
readln(s);
if s<>'' then
repeat
sub:=copy(s,1,2);
zhuan(sub,i,j);
pan[i,j]:=false;
delete(s,1,3);
until s='';
readln(s);
sub:=copy(s,1,2);
zhuan(sub,start.i,start.j);
sub:=copy(s,4,2);
zhuan(sub,finish.i,finish.j);
end;
function ok(i,j:integer):boolean;
begin
if (i>0) and (i<9) and (j>0) and (j<9) and pan[i,j] then ok:=true else ok:=false;
end;
procedure work;
var p,q,i:integer;
qs,kz:zb;
pd:boolean;
begin
p:=0;
q:=1;
qi[1].i:=start.i;
qi[1].j:=start.j;
qi[1].bu:=0;
can:=true;
pd:=false;
repeat
inc(p);
qs:=qi[p];
for i:=1 to 8 do
begin
kz.i:=qs.i+f[i,1];
kz.j:=qs.j+f[i,2];
if ok(kz.i,kz.j) then
begin
pan[kz.i,kz.j]:=false;
inc(q);
qi[q].i:=kz.i;
qi[q].j:=kz.j;
qi[q].bu:=qi[p].bu+1;
if (kz.i=finish.i) and (kz.j=finish.j) then
begin
pd:=true;
answer:=qi[q].bu;
end;
end;
end;
until (p=q) or (pd);
if p=q then can:=false;
end;
procedure print;
begin
if can then writeln(answer,' moves') else writeln('not reachable');
end;
begin
assign(input,'knight.in'); reset(input);
assign(output,'knight.out'); rewrite(output);
k:=0;
repeat
readln(b);
inc(k);
if b<>-1 then
begin
write('Board ',k,': ');
for i:=1 to 8 do
for j:=1 to 8 do pan[i,j]:=true;
init;
work;
print;
end;
until b=-1;
close(input);
close(output);
end.
pascal中一个数组后加点,如q[f].x 是什么意思?
加点是记录类型访问域,力的例子说明数组q的元素是记录类型(record),而且有一个叫做x的域
NOIP 如果想得全国一等奖的话需要学习那些知识?
必备:【模拟】高精度加、减、乘 【图论】图的表示:邻接矩阵,邻接表,边表 传递闭包和floyd 最小生成树算法(至少会一种)单源最短路dijkstra(O(n2))或者bellman(spfa优化,O(km))拓扑排序 【树】 树的先序、中序、后序遍历 树中的最长路(两遍bfs或者dfs)并查集 【搜索】深搜、宽搜 ...
pascal细胞
const dx:array[1..4]of integer=(1,0,-1,0);dy:array[1..4]of integer=(0,1,0,-1);var n,m,x,y,i,j,s:integer; a:array[0..100,0..100]of char;procedure search(x,y:integer); {遍历一个细胞的所有点} var i:integer;begin a[x,y]:=' ';{标记已检测过} for...
高中信息学联赛经典题型(pascal)
第八届全国青少年信息学奥林匹克联赛(NOIP2002)初赛试题 (提高组 PASCAL语言 二小时完成)审定:全国青少年信息学奥林匹克竞赛科学委员会 主管:中国科协、教育部 主办:中国计算机学会 承办:江苏省科协青少年科技中心 ●●全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效●● 一. 选择一个正确...
西肯大克: 给你个裸搜程序var can:Array[1..20]of boolean; num:array[1..20]of integer; n:integer; function pan(s:integer):boolean; var i:integer; Begin for i:=2 to s div 2 do if s mod i=0 then exit(false); exit(true); End; procedure go(k:integer); Var i:integer; Begin if ...
果洛藏族自治州17870928798: 谁有素数环PASCAL程序 - ?
西肯大克: 这是一个搜索问题,层数为20,在深搜可以接受的范围之内 思路是,先确定第一个元素为1 然后依次往后推,每个元素都要满足和前一个的和为素数 关于这个你可以先做一个初始化 f[i,j] of boolean 表示i后面能不能接j(这个在下面那个程序里没...
果洛藏族自治州17870928798: 求一个PASCAL程序 - ?
西肯大克: 用筛选法求1~N之间的所有素数.分析:对于数组flag[1..n],先初始化假设全为true.首先flag[1]=false,接着从数组中找到第1个为true的数flag[2],那么在2以后的所有数中,将2的倍数的数赋值为false.接着再从数组中找到下一个为true的3,将3...
果洛藏族自治州17870928798: pascal 顺序查找和二分查找的程序 - ?
西肯大克: procedure sch(s:string); {顺序查找,s为要查找到的字符串} var i:integer; begin for i:=1 to n do {n为数组元素个数} if a[i]=s then write(i,' '); end; procedure scht(t:integer); {二分查找,前提是数组是有序数组} var i,j:integer; begin i:=n; j:=1; while (a[i]...
果洛藏族自治州17870928798: 急需一计算质数Pascal程序?
西肯大克: var n,m,g,r,h:longint; pd:boolean; p:text; begin assign(p,'c:\zhishu.txt'); readln(r); rewrite(p); write(p,'2 3 '); n:=1; repeat n:=n+2; m:=1; pd:=true; repeat m:=m+2; g:=n mod m; if g=0 then pd:=false; until (m=n div 2)or(pd=false); if pd=true then begin write...
果洛藏族自治州17870928798: 记忆化搜索程序pascal框架 - ?
西肯大克: 1. 记忆化深度优先搜索 const nonsense=-1; {这个值可以随意定义,表示一个状态的最优值未知} var …… {全局变量定义} function work(s:statetype):longint; var …… {局部变量定义} begin if opt[s]nonsense then begin work:=opt[s]; exit; end; {如...
果洛藏族自治州17870928798: 求一个Pascal的程序?
西肯大克: 楼主的题目要求是 让用户输入两个数字和一个符号(+ - *没有除号), 再输入结果 然后让电脑判断计算的是否正确, 理解无误吧, 楼主的题目就是这样写的 给出程序var a, b, res, ires: Double; c: Char; begin Write('Please input two numbers: '); ...
果洛藏族自治州17870928798: 求bfs Pascal 程序 - ?
西肯大克: 2.广度优先搜索基本算法: 1)从某个顶点出发开始访问,被访问的顶点作相应的标记,并输出访问顶点号; 2)从被访问的顶点出发,依次搜索与该顶点有边的关联的所有未被访问的邻接点,并作相应的标记. 3)再依次根据2)中所有被访问...
果洛藏族自治州17870928798: 求Pascal程序 - ?
西肯大克: 一共有四种方法 我全把它列出来了 好幸苦啊1.回溯法 program qplshuisu; var stack:array[0..20] of integer; s:set of 0..20; n,i,k,top:integer; begin {assign(input,'qpl.in'); assign(output,'qpl.out'); reset(input); rewrite(output);} readln(n); k:=0;top:=0; while ...
果洛藏族自治州17870928798: 宽搜 怎么弄pascal - ?
西肯大克: 用队列,读取头节点,处理后把与之相关的节点加入队列,直到队列的头节点赶上尾节点q[1,1]:=x1;q[1,2]:=y1;//最初的节点进队列 t:=1;//队首指针 tail:=1;//队尾指针 while t<=tail do begin找与之相关的节点if 符合要求 then begin处理头节点,加入与之相关的节点end;end;t:=t+1; end; (以上结构适合有一个用二维数组储存的'地图'的宽搜.如果是其他的话请补充一下)