pascal搜索回溯Word文档格式.docx
- 文档编号:8158239
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:16
- 大小:25.79KB
pascal搜索回溯Word文档格式.docx
《pascal搜索回溯Word文档格式.docx》由会员分享,可在线阅读,更多相关《pascal搜索回溯Word文档格式.docx(16页珍藏版)》请在冰点文库上搜索。
Ok!
UsesTime:
'
times);
=1tondowrite(a[i],'
readln;
end.
[参考程序2]
usescrt;
constn=10000;
array[1..n]oflongint;
i,j,k,l,y:
clrscr;
fillchar(a,sizeof(a),0);
i:
j:
a[i]:
repeat
y:
=2*a[i]+1;
k:
=j;
whiley〈a[k]dobegin
a[k+1]:
=a[k];
=k-1;
ify>
a[k]thenbegin
=y;
=j+1;
end
elseforl:
=k+1tojdoa[l]:
=a[l+1];
j:
a[j]:
=3*a[i]+1;
inc(i);
untilk>
=n;
=1tondobegin
write(a[i],'
if(imod10=0)or(i=n)thenwriteln
[参考程序3]
n,i,one,another,long,s,x,y:
n='
one:
another:
whilelongythenbegins:
inc(another);
end
elsebegins:
=x;
inc(one);
end;
=s;
[参考程序4]
varn:
integer;
top,x:
functioninit(x:
longint):
boolean;
ifx=1theninit:
=true
elseif((x-1)mod2=0)and(init((x-1)div2))
or((x-1)mod3=0)and(init((x-1)div3))then
init:
elseinit:
=false;
inputn:
readln(n);
x:
=0;
top:
whiletop<
ndobegin
=x+1;
ifinit(x)then
=top+1;
write(x:
8);
outputend.'
readln
〖问题描述〗用高精度计算出S=1!
+2!
+3!
+...n!
(n<
=50)
其中"
!
"
表示阶乘,例如:
5!
=5*4*3*2*1
要求:
输入正整数N,输出计算结果S
四、搜索回溯法
搜索回溯法是程序设计中最常用的一种算法,其思想方法是按一定的顺序对每阶段试探所有可能性:
即从初始态出发向前搜索,如果成功则继续,否则回退一步,如此反复直至所有可能都试遍。
在搜索过程中,须作标志以记住已搜索过的步骤,设栈实现回溯。
算法框架
1、初始化
2、进行第一步搜索(试探)
3、判断搜索是否成功,若成功转5;
若不成功,则继续
4、进行该步下一种情况搜索,若该步所有可能都搜索完则转8;
否则转3
5、当前情况步数等作标志(进栈),并前进一步
6、判断是否搜索到终点,不是则转2;
否则继续。
7、打印结果,清除并转4
8、退后一步(回溯)
9、判断是否退回到初始态,不是则转4;
是则结果程序
一、素数环把从1到20这20个数摆成一个环,要求相邻的两个数的和是一个素数。
〖算法分析〗从1开始,每个空位有20(19)种可能,只要填进去的数合法:
与前面的数不相同;
与左边相邻的数的和是一个素数。
第20个数还要判断和第1个数的和是否素数。
1、数据初始化;
2、递归填数:
判断第J种可能是否合法;
A、如果合法:
填数;
判断是否到达目标(20个已填完):
是,打印结果;
不是,递归填下一个;
B、如果不合法:
选择下一种可能;
programtt;
array[1..20]ofinteger;
functionpd1(j,i:
integer):
pd1:
fork:
=1toi-1do
ifa[k]=jthenbeginpd1:
exit;
functionpd2(x:
pd2:
=2totrunc(sqrt(x))do
ifxmodk=0thenbeginpd2:
exit;
functionpd3(j,i:
ifi<
20thenpd3:
=pd2(j+a[i-1])
elsepd3:
=pd2(j+a[i-1])andpd2(j+1);
procedureprint;
=1to20dowrite(a[k]:
4);
writeln;
proceduretry(i:
integer);
varj:
forj:
=2to20do
begin
ifpd1(j,i)andpd3(j,i)thenbegin
ifi=20thenbeginprint;
halt;
elsetry(i+1);
=1to20doa[k]:
try
(2);
二、编写程序走左图所示的迷宫,要求从A走到B,并印出路径,在走迷宫的过程中,若遇到死胡同,退出时即给堵上。
〖算法分析〗:
将每一格对应每一步,每走一步计算相应的坐标值,每一步又按1、2、3、4四个方向进行试探,是否有路,若有路则前进,否则换方向继续试探;
若四个方向都不行,则回溯,并将此路堵上。
三、八皇后问题在一个8×
8的棋盘里放置8个皇后,要求每个皇后两两之间不相"
冲"
(在每一横列竖列斜列只有一个皇后)。
〖问题分析〗主要解决以下几个问题:
1、冲突。
包括行、列、两条对角线:
(1)列:
规定每一列放一个皇后,不会造成列上的冲突;
(2)行:
当第I行摆上皇后,则同一行上不能再放皇后,把I为下标的标记置为被占领状态;
(3)对角线:
对角线有两个方向。
在同一对角线上的所有点(设下标为(i,j)),要么(i+j)是常数,要么(i-j)是常数。
因此,当第I个皇后占领了第J列后,要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2、数据结构。
(1)解数组A。
A[I]表示第I个皇后放置的列;
范围:
1..8
(2)行冲突标记数组B。
B[I]=0表示第I行空闲;
B[I]=1表示第I行被占领;
(3)对角线冲突标记数组C、D。
C[I-J]=0表示第(I-J)条对角线空闲;
C[I-J]=1表示第(I-J)条对角线被占领;
-7..7
D[I+J]=0表示第(I+J)条对角线空闲;
D[I+J]=1表示第(I+J)条对角线被占领;
2..16
〖算法流程〗
1、数据初始化。
2、从n列开始摆放第n个皇后,先测试当前位置(n,m)是否等于0(未被占领):
如果是,摆放第n个皇后,并宣布占领(记得要横列竖列斜列一起来),接着进行递归;
如果不是,测试下一个位置(n,m+1),若当n<
=8,m=8时,已经无法摆放时,进行回溯。
3、当n>
8时,便一一打印出结果。
皇后N
4
5
6
7
8
9
10
方案数
2
40
92
352
724
programqueen;
{八皇后问题程序}
constn=8;
vara,b:
array[1..n]ofinteger;
{数组a存放解:
a[i]表示第i个皇后放在第a[i]列;
c:
array[1-n,n-1]ofinteger;
d:
array[2..n+n]ofinteger;
{b为行标志,c、d表示对角线标志}
{打印结果}
=1tondowrite(a[j]:
procedruetry(i:
{递归搜索解}
{每个皇后的可放置位置。
注意:
一定要在过程中定义;
否则当递归时会覆盖掉它的值,不能得到正确结果}
=1tondo
if(b[j]=0)and(c[i-j]=0)and
(d[i+j]=0)then{检查位置是否合法}
{置第i个皇后的位置是第j行}
b[j]:
c[i-j]:
d[i+j]:
{作已摆放标志}
nthentry(i+1)
elseprint;
{如果末达目标则继续,否则打印结果}
d[i+j]:
{回溯:
清摆放标志}
=1tondob[k]:
{初始化数据}
=1-nton-1doc[k]:
=2ton+ndod[k]:
try
(1);
四、〖题目描述〗输入两个数字(i,j),在第一个数字i中间添上若干个加号,使得这个代数式的值等于第二个数字j。
〖问题分析〗这道题采用的算法是剪枝搜索,逐一在第一个数字i各个数字之间添上加号,并计算出当前代数式的值,如果等于第二个数字j,则退出循环,打印结果“YES”;
如果不是,则继续循环;
当循环结束后,还未能得出第二个数j,则打印结果“NO”。
1、首先将以字符串输入的第一个数字i切成一个数字e段,放进一个数组a[e]里。
2、接着进行循环,逐一在第一个数字i各个数字之间添上加号,由于在各个数字之间添上加号后代数式的值只有两种情况:
大于第二个数字j或小于第二个数字j,所以循环的内容可以如下:
(1)以h,i分别作为当前处理的数字的首位在数组里的位置和在当前数字的第i位添加号。
(2)分别以x1,x2存放添加号后加号前的数值以及加号后的数值,x3将赋值为x1+x2,作为当前代数式的值。
当x3>
j时,则进行将h赋值为i,将要处理的数字赋值为加号后的数值,并将x3赋值为x3-x2,作为加号前的数值;
当x3<
j时,而且i<
=e时,则将i赋值为i+1,在当前处理的数字添加号的数位的后一位添上加号,并将x3赋值为x3-x2;
若i>
e时,则将h赋值为h-1,i赋值为h+1,在当前处理的数字添加号的数位的前一位添上加号,并将x3赋值为x3-x2-a[i]。
3、当h<
=0、h>
e、i<
=0、i>
e、x3<
>
j时,则退出循环并打印结果“no”;
当0<
h<
=e、0<
i<
=e、x3=j时,则退出循环并打印结果“yes”。
〖参考程序〗
programaa;
text;
string;
d,e,g,h,i,x1,x2,x3,xx:
f:
array[1..100]ofinteger;
procedurebb;
assign(a,'
tjh.dat'
reset(a);
readln(a,c,d);
close(a);
procedurecc;
fore:
=1tolength(c)do
f[e]:
=ord(c[e])-48;
x1:
x2:
x3:
xx:
h:
whilex3<
ddo
forg:
=htoidox1:
=x1*10+f[g];
=i+1toedox2:
=x2*10+f[g];
=x1+x2+x3;
ifx3=dthenexit;
if(h<
0)or(i<
0)thenbeginxx:
ifx3<
dthen
=i+1;
=x3-x1-x2;
ifi=5thenbeginh:
=h-1;
=h+1;
=x3-f[i-1];
ifx3>
=h;
=x3-x2;
proceduredd;
assign(b,'
tjh.out'
rewrite(b);
ifxx=1thenwriteln(b,'
yes'
)
elsewriteln(b,'
no'
close(b);
bb;
cc;
dd;
〖习题〗
2、骑士游历问题设有一个N*M的棋盘(2≤N≤50,2≤M≤50),如图所示。
在棋盘上任一点有一个中国象棋马,马走的规则:
(1)马走日字;
(2)马只能向右走;
问题:
当N,M输入之后,找出一条从左下角到右上角的路径。
如:
输入N=4,M=4。
输出(1,1)-(2,3)-(4,4),若不存在路径,则输出‘NO’。
3、任何大于1的自然数N都可以拆分成若干个小于N的自然数之和。
输入N,计算和输出N的不同拆分方案。
4、有一集合,集合中有N个元素,每个元素都是正整数,它们存放在一维数组中,每个数组元素存放一个数,对给定的整数TOTAL(设集合中的每个元素的值都小于TOTAL),求出所有满足下列条件的子集,子集中各元素之和等于TOTAL。
(如设:
TOTAL=10,N=7,元素8,4,1,2,5,3,6)
5、有一个由数字1,2,3……,9组成的数字串(长度不超过200),问如何将M(M<
=20)个加号("
+"
)插入到这个数字串中,使所形成的算术表达式的值最小.请编一程序解决这个问题.
注意:
加号不能加在数字串的最前面或最末尾,也不应有两个或两个以上的另号相邻.M保证小于数字串的长度.
例如:
数字串798446,若需要加入两个加号,则最佳方案为79+84+46,算术表达式的值为133
程序如下:
程序中T数组用来存放子集
TOTAL=10:
N=7
FORI=1TO7:
READA(I):
NEXT
DATA8,4,1,2,5,3,7
S=0:
I=0以上初始化
60:
I=I+1往前搜索指针I加1
J=J+1:
T(J)=I元素编号,送入T数组
S=S+A(I)
IFS<
TOTALTHEN120
IFS=TOTALTHEN200
110S=S-A(I):
J=J-1回退
120IFI<
NTHEN60
I=T(J)重新设置搜索指针
IFI=NANDJ=1THENEND
150GOTO110
200FORK=1TOJ:
PRINTA(T(K));
:
NEXTK:
PRINT:
GOTO110
【题目】4×
4棋盘上每行每列各摆2颗棋子,要求每一行,每一列上只能放置2个有多少种摆法程序
10DIMa(6),b(6)
20FORi=1TO6:
READa(i),b(i):
NEXTi
30DATA1,2,1,3,1,4,2,3,2,4,3,4
40i=0
50i=i+1:
t(i)=0
60t(i)=t(i)+1
70IFt(i)<
=6THEN110
80i=i-1
90IFi<
0THENPRINTm:
END
100GOTO200
110x=t(i):
y(a(x))=y(a(x))+1:
y(b(x))=y(b(x))+1
120IFy(a(x))>
2ORy(b(x))>
2THENGOTO200
130IFi<
4THEN50
135m=m+1
140FORj=1TO4:
PRINTTAB(a(t(j)));
"
*"
;
TAB(b(t(j)));
NEXTj
200x=t(i):
y(a(x))=y(a(x))-1:
y(b(x))=y(b(x))-1:
GOTO60
【题目】在4×
4的棋盘上放置8个棋,要求每一行,每一列上只能放置2个.
【参考程序1】
算法:
8个棋子,填8次.深度为8.注意判断是否能放棋子时,两个两个为一行.
array[1..8]of0..4;
line,bz:
array[1..4]of0..2;
{line数组:
每行已放多少个的计数器}
{bz数组:
每列已放多少个的计数器}
total:
procedureoutput;
{输出}
vari:
inc(total);
write(total,'
=1to8dowrite(a[i]);
functionok(dep,i:
ok:
ifdepmod2=0then{假如是某一行的第2个,其位置必定要在第1个之后}
if(i<
=a[dep-1])thenok:
if(bz[i]=2)or(line[depdiv2]=2)thenok:
{某行或某列已放满2个}
procedurefind(dep:
=1to4dobegin
ifok(dep,i)thenbegin
a[dep]:
=i;
{放在dep行i列}
inc(bz[i]);
{某一列记数器加1}
inc(line[depdiv2]);
{某一行记数器加1}
ifdep=8thenoutputelsefind(dep+1);
dec(bz[i]);
{回溯}
dec(line[depdiv2]);
fillchar(bz,sizeof(bz),0);
find
(1);
【参考程序2】
某一行的放法可能性是(1,2格),(1,3格),(1,4格)....共6种放法
const
fa:
array[1..6]ofarray[1..2]of1..4=((1,2),(1,3),(1,4),(2,3),(2,4),(3,4));
{六种可能放法的行坐标}
var
a:
bz:
{列放了多少个的记数器}
{判断现在的放法中,相应的两列是否已放够2个}
if(bz[fa[i,1]]=2)or(bz[fa[i,2]]=2)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- pascal 搜索 回溯