电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

高中信息技术 全国青少年奥林匹克联赛教案 搜索法二VIP免费

高中信息技术 全国青少年奥林匹克联赛教案 搜索法二_第1页
1/6
高中信息技术 全国青少年奥林匹克联赛教案 搜索法二_第2页
2/6
高中信息技术 全国青少年奥林匹克联赛教案 搜索法二_第3页
3/6
算法在信息学奥赛中的应用(搜索法二)在深度优先搜索算法中,深度越大的结点越先得到扩展,若把它改为深度越小的结点越先得到扩展,就是广度优先搜索法。广度优先搜索基本算法:programbfs;初始化;建立队列data;设队列首指针closed:=0;队列尾指针open:=1;repeatclosed增1,取出closed所指结点进行扩展;fori:=1tordobeginif子结点符合条件thenbeginopen增1,并把新结点存入数据库队尾;if新结点与原有结点有重复then删于该结点(open减1)elseif新结点即目标then输出并退出;end{if};end{for};untilclosed>=open;{队列为空}使用广度优先搜索时,离根结点最近的结点先扩展,所以广度优先搜索法比较适合求步数最少的解,由于深度优先使用了标志法,使得存储空间大大减少,而广度优先要保留所有搜索过的节点,随着搜索程度的加深,所需的存储空间成指数增加。因此在必要时我们采用双向搜索来减少搜索空间和存储空间,如下面的例子。广度优先算法应用例字串变换(NOIP2002tg)[问题描述]:已知有两个字串A$,B$及一组字串变换的规则(至多6个规则):A1$->B1$A2$->B2$规则的含义为:在A$中的子串A1$可以变换为B1$、A2$可以变换为B2$…。例如:A$='abcd'B$='xyz'变换规则为:‘abc’->‘xu’‘ud’->‘y’‘y’->‘yz’则此时,A$可以经过一系列的变换变为B$,其变换的过程为:‘abcd’->‘xud’->‘xy’->‘xyz’共进行了三次变换,使得A$变换为B$。[输入]:键盘输人文件名。文件格式如下:A$B$A1$B1$\A2$B2$|->变换规则....../所有字符串长度的上限为20。[输出]:输出至屏幕。格式如下:若在10步(包含10步)以内能将A$变换为B$,则输出最少的变换步数;否则输出"NOANSWER!"[输入输出样例]b.in:abcdxyzabcxuudyyyz屏幕显示:3算法分析:此题是求变换的最少步数,很显然可以使用广度优先搜索法,如果直接从初状态搜到目标状态,最坏情况下存储的结点数超过6的10次方幂,搜索空间过大,因此我们考虑使双向搜索,同时从初始状态和目标状态向中间状态搜索,当相遇时搜索结束。采用双向搜索,存储的结点数还有可能超限,我们在前向搜索队列中存储5步内变换的结点,在后向搜索队列中,由于第5步产生的结点只是用来与前向队列中的结点比较,所以可以不存储在队列中,后向搜索队列只需存储4步内的结点,这样就解决了存储空间问题。为了使用方便,在程序设计中用一个数组a[1..max]存储两个队列,前向搜索队列为a[1..mid],后向搜索队列为a[mid..max],用st存储搜索方向,st=0表示前向搜索,st=1表示后向搜索,用op[st]和cl[st]分别表示队列尾指针和首指针,用be表示队列起始位置,循环产生每一个结点,若在10内无解退出循环,若在10内找到解则输出解并退出程序。源程序:constmid=12000;max=16000;typenode=records:string;x:byte;end;vari,mark:integer;a:array[1..max]of^node;x:array[0..6,0..1]ofstring[20];d,fil:string;op,cl:array[0..1]ofinteger;procedureInit;{读取数据,初始化}varf:text;t:string;beginreadln(fil);assign(f,fil);reset(f);i:=0;whilenoteof(f)dobeginreadln(f,t);x[i,0]:=copy(t,1,pos('',t)-1);x[i,1]:=copy(t,pos('',t)+1,length(t));inc(i);end;{while}mark:=i-1;close(f);end;{判断是否到达目标状态}procedurebool(be,st:integer);beginfori:=mid-be+1tocl[1-st]doifa[cl[st]]^.s=a[i]^.sthenbeginwriteln(a[cl[st]]^.x+a[i]^.x);halt;end;{if}end;{判断节点是否与前面的结点重复}procedurecheck(be,st:integer);beginfori:=be+1tocl[st]-1doifa[i]^.s=a[cl[st]]^.sthenbegindec(cl[st]);exit;end;bool(be,st);end;{扩展产生新节点}procedureexpand(be,st:integer);vari,j,k,lx,ld:integer;begininc(op[st]);d:=a[op[st]]^.s;k:=a[op[st]]^.x;ld:=length(d);fori:=1tomarkdobeginlx:=length(x[i,st]);forj:=1tolddobeginif(copy(d,j,lx)=x[i,st])thenbeginif(st<>1)or(k<>4)thenbegininc(cl[st]);new(a[cl[st]]);end;{if}a[cl[st]]^.s:=copy(d,1,j-1)+x[i,1-st]+copy(d,j+lx,ld);a[cl[st]]^.x:=k+1;check(be,st);{检查是否重复}end;{if}end;{for}end;{for}end;pro...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

高中信息技术 全国青少年奥林匹克联赛教案 搜索法二

您可能关注的文档

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部