信息学竞赛搜索专题汇总

JSOI搜索算法NJOI搜索•给出初始节点，要求寻找到符合约束条件的目标节点•给出初始节点和目标节点，要求找到从初始节点到目标节点的一条路径。•最优解？较优解？全部解？NJOI搜索算法•枚举•广度优先搜索•深度优先搜索、回溯•A*NJOI深度优先•栈——WhyState?•搜索——深度优先搜索•递归（系统栈）•回溯（人工栈的维护）•什么是栈？NJOIFunctionjc(n:integer):integer;beginifn=1thenjc:=1elsejc:=n*jc(n-1);end;Beginwrite(jc(4));End.432系统栈实例NJOI在调用过程或函数之前，系统需完成三件事：⑴将所有的实在参数、返回地址等信息传递给被调用过程保存；⑵为被调用过程的局部变量分配存储区；⑶将控制转移到被调过程的入口。从被调用过程返回调用过程之前，系统也应完成三件工作：⑴保存被调过程的计算结果；⑵释放被调过程的数据区；⑶依照被调过程保存的返回地址将控制转移到调用过程。当有多个过程构成嵌套调用时，按照“后调用先返回”的原则系统栈NJOI汉诺塔（towerofHanoi）问题。Proceduremove(n:integer;A,B,C:char);ifn=1thenA→Celsemove(n-1，A，C，B)A→Cmove(n-1，B，A，C)请写出系统栈的变化过程move(3,’A’,’B’,’C’)系统栈——例NJOI•线性•读写操作都在栈顶•先进后出栈的特点NJOI•静态—数组Typearr=array[1..n]ofinteger;stack=recordvec:arr;top:integer;end;Vars:stack;Varstack:arr;top:integer;动态—链表Typelink=^node;node=recordinfo:integer;next:link;end;Varstack:link;top:link;栈的定义NJOI操作静态数组(A,top)动态链表(H,top)建立栈测试栈是否为空读栈顶元素进栈(push)出栈(pop)Top:=0top:=nil;Top=0top=nil;A[top]Top^.infoTop:=top+1;a[top]:=…;？Top:=top-1;？头插法栈的基本操作NJOI•入栈顺序为1,2,3,…,n，出栈序列为p1,p2,p3,……,pn，已知p1=n，则pi=?•入栈顺序为1,2,3,…,n，出栈序列为p1,p2,p3,……,pn，已知pn=1，则pi=?•栈s初始为空，有元素{1,2,3,4,5}，现进行{进、进、进、初、进、出、进}，问：出栈序列，栈顶指针，栈顶元素应用举例NJOI•元素e1,e2,e3,e4,e5,e6依次通过栈s，若出栈顺序为2,4,3,6,5,1，则栈s的容量至少为？•车厢重组：{1,2,3,4,5}进站，第一个到达出口的是3号车厢，问：可能的排列总数？应用举例NJOI•中缀表示法•运算优先级问题、括号的出现改变运算顺序•后缀表示法（逆波兰式）---一次扫描栈的简单应用——表达式NJOI•3/5+6•35/6+•6-9*(4+3)+5•6943+*-5+•转换方法•2*(x+y)/(1-x)•(25+x)*(a*(a+b)+b)后缀表示法NJOI•6-9*(4+3)+5•优先级运算符优先级#-1（0（入栈时不作优先级比较）+-1*/2）单独处理入栈标准：优先级大于栈顶元素优先级后缀表示法——栈的使用NJOI#-16-19*2(04+13+*-+15++16943+*-5+6-9*(4+3)+5#NJOI6-9*(4+3)+53496+1(0*2-1#-1763-57+15-52中缀—栈—求解NJOIProceduretry(I);选择第I个皇后的位置；if安全then(1)放置第I个皇后；(2)ifI=8then输出elsetry(I+1);尝试下一个位置；栈的应用——八皇后（递归）13455248724648246462758245724885824762425253873837636382537335773625825523828352326374837463472486388247373663724NJOIForj:=1to8doifb[j]andc[I+j]andd[I-j]thena[i[]:=j;b[j]:=f;c[I+j]:=f;d[I-j]:=f;ifI8thentry(I+1)elseprint;b[j]:=t;c[I+j]:=t;d[I-j]:=t;栈：I、j系统维护b、c、d手动维护递归调用返回即回溯Proceduretry(I);NJOITop:=1;j:=0;Whiletop0doj:=j+1;ifj8thentop:=top-1;j:=a[top];b[j]c[top+j]d[top-j]:=t;elseif(top=8)andb[j]andc[top+j]andd[top-j]thena[top]:=j;b[j]c[top+j]d[top-j]:=f;top:=top+1;j:=0;iftop8thenprint;八皇后——非递归NJOIForj:=1to8doifb[j]andc[I+j]andd[I-j]thena[i[]:=j;b[j]:=f;c[I+j]:=f;d[I-j]:=f;ifI8thentry(I+1)elseprint;b[j]:=t;c[I+j]:=t;d[I-j]:=t;mm全排列——递归NJOITop:=1;j:=0;Whiletop0doj:=j+1;ifj8thentop:=top-1;j:=a[top];b[j]c[top+j]d[top-j]:=t;elseif(top=8)andb[j]andc[top+j]andd[top-j]thena[top]:=j;b[j]c[top+j]d[top-j]:=f;top:=top+1;j:=0;iftop8thenprint;mm全排列——非递归NJOI•方式•递归回溯•基本框架深度优先搜索NJOI•素数环：将1~20这20个数摆成一个环，要求相邻的两个数的和是一个素数•走迷宫训练NJOI方向：上下左右NJOI方向：右下左上研究背景NJOI•背包问题——简单枚举有5个背包（不可拆分），背包的价值(w)、体积(t)各不相等，在容量(tj)范围内，如何选取，使价值最大？Fora[1]:=0to1dofora[2]:=0to1do…fora[5]:=0to1doP;St:=∑a[I]*t[I];Sw:=∑a[I]*w[I]Ifst=tjandswmaxthen记录状态；有n个背包，问题如何解决？回溯——穷举NJOIA:1234500000000010001000011……11111逢1进位分析问题——找出实质NJOI•初值：0000……0•找到需要进位的下标•如何查找？•N1•结束标记？实质NJOIForI:=0tondoa[I]:=0;Whilea[0]=0doj:=n;whilea[j]=1doj:=j-1;a[j]:=a[j]+1;forI:=j+1tondoa[I]:=0;计算P;打印；程序框架——逢1进位NJOI•N个砝码（1，3，9，……，3n-1）可以放在重物一侧，也可以放在砝码一侧，给出一个重量，问：如何称？Whilea[0]=0doj:=n;whilea[j]=1doj:=j-1;a[j]:=a[j]+1;forI:=j+1tondoa[I]:=0;计算;-1逢1进位NJOI•有n种背包，每种背包有若干个(bi)，……Whilea[0]=0doj:=n;whilea[j]=1doj:=j-1;a[j]:=a[j]+1;forI:=j+1tondoa[I]:=0;计算;B[j]相等进位NJOI•从1~m中任意取出n个，打印所有取法123124125134135145234235245345保证不重复选择——升序第n位进位标志：m第n-1位进位标志：m-1…第j位进位标志?相等进位——组合问题JSOI深度优先搜索深入应用NJOI跳马周游棋盘问题NJOI•一棵八叉树八个方向：目前位置(i,j)，下一个位置：可能为：(i+1,j+2),(i-1,j+2),(i-2,j+1),(i-2,j-1),(i-1,j-2),(i+1,j-2),(i+2,j-1),(i+2,j+1)•用二维数组表示棋盘，未走过的地方设置为0b[i1,j1]＝0当棋格(i1,j1)未被占据i当棋格(i1,j1)在第i次移动中被占据•范围：未走过的和不越出棋盘边界的那些位置•为了防止马跳出棋盘，将棋盘扩大二圈，这些位置的表示设置为-1分析NJOI•缩小搜索范围——避免无效搜索•改变搜索次序——在几个可能到达的位置中根据优劣条件选择一个最优点来跳马•剪枝深度优先搜索的优化方法NJOI编一个程序，找出一条通过迷宫的路径。这里显示为1的单元表示走不通，将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。010000001000010001100000111001100000000000010入口→→出口迷宫问题NJOI基本题•1~6NJOI12345678910100010012000010101310100011140011000005000010010找出一个从入口到出口的最短路径（八个方向）迷宫问题总行数：0——m+1,总列数：0——n+111111111111101000100111000010101111010001111100110000011000010010111111111111NJOI•在深搜过程中，记录搜索步数并与最小值进行比较，记录当前最佳方案，最后打印输出•能否改进？方案1NJOI•从步数的角度考虑问题，分别列举出一步能到达的结点、两步能到达的结点、……、发现的终点肯定是最优方案•如何记录方案？•记录每个结点的来由方案28个方向表示可以用数组说明：10121131041-150-16-1-17-108-11如何记录探索的踪迹？——队列序号123456X123332…Y123144…pre012233…基本NJOI如何防止重复探索：将迷宫中的0替换为-1队列中入队、出队情况如下表：迷宫问题NJOI程序•……12345678910100010012000010101310100011140011000005000010010迷宫（用不同的颜色表示步数）NJOI•与深搜区别之一：搜索的方向不影响搜索规模•主要影响因素是什么？•迷宫变形：起点在迷宫中心、几乎没有障碍结论*迷宫变形NJOI•在宽搜过程中，队列以几何数量级扩展，扩展层数越大，对存储的威胁越大•如何对存储进行压缩？——双向搜索结论NJOI现要找出一条从A到B经过城市最少的一条路线。广度优先遍历:A应用NJOIF,r,队列初始化；Whilef=rdo取队首；宽搜基本框架NJOIsq[1].x:=1;sq[1].y:=1;sq[1].pre:=0;front:=1;rear:=1;mg[1,1]:=-1;whilefront=reardox:=sq[front].x;y:=sq[front].y;forv:=1to8doI:=x+z[v].x;j:=y+z[v].y;ifmg[I,j]=0thenrear:=rear+1;sq[rear].pre:=front;sq[rear].x:=I;sq[rear].y:=j;mg[I,j]:=-1;if(i=m)and(j=n)thenprint;front:=front+1;NJOI•设有数字2，3，5，7，13，运算符号：+,—,*,且运算无优先级之分，如2+3*5=25，3*5+2=17，编写一个程序，给出任意一个整数n，要求用以上的数和运算符，以最少的运算次数产生出n。例如：n=7,7=7,（0次运算）n=93，93=13*7+2（2次运算）。例数值计算NJOI（1）数据的结构：参加运算的