信息学竞赛搜索专题.ppt

搜索 给出初始节点，要求寻找到符合约束条件的目标节点 给出初始节点和目标节点，要求找到从初始节点到目标节点的一条路径。 最优解？较优解？全部解？ 搜索算法 枚举 广度优先搜索 深度优先搜索、回溯 A* 深度优先 系统栈实例 Function jc(n:integer):integer; begin if n=1 then jc:=1 else jc:=n*jc(n-1); end; Begin write(jc(4)); End. 系统栈 在调用过程或函数之前，系统需完成三件事： ⑴将所有的实在参数、返回地址等信息传递给被调用过程保存； ⑵为被调用过程的局部变量分配存储区； ⑶将控制转移到被调过程的入口。 从被调用过程返回调用过程之前，系统也应完成三件工作： ⑴保存被调过程的计算结果； ⑵释放被调过程的数据区； ⑶依照被调过程保存的返回地址将控制转移到调用过程。当有多个过程构成嵌套调用时，按照“后调用先返回”的原则 系统栈——例 汉诺塔（tower of Hanoi）问题。 Procedure move(n:integer; A,B,C:char); if n=1 then A→C else 　move(n-1，A，C，B) 　　　　　 A→C 　　　　　 move(n-1，B，A，C) 请写出系统栈的变化过程 move(3,’A’,’B’,’C’) 栈的特点 线性 读写操作都在栈顶 先进后出 栈的定义 静态—数组 Type arr=array[1..n ] of integer; stack=record vec:arr; top:integer; end; Var s:stack; 栈的基本操作 应用举例 入栈顺序为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}，现进行{进、进、进、初、进、出、进}，问：出栈序列，栈顶指针，栈顶元素 应用举例 元素e1,e2,e3,e4,e5,e6依次通过栈s，若出栈顺序为2,4,3,6,5,1，则栈s的容量至少为？ 车厢重组：{1,2,3,4,5}进站，第一个到达出口的是3号车厢，问：可能的排列总数？ 栈的简单应用——表达式 中缀表示法 运算优先级问题、括号的出现改变运算顺序 后缀表示法（逆波兰式）---一次扫描 后缀表示法 3/5+6 3 5 / 6 + 6-9*(4+3)+5 6 9 4 3 + * - 5 + 转换方法 2*(x+y)/(1-x) (25+x)*(a*(a+b)+b) 后缀表示法——栈的使用 6-9*(4+3)+5 优先级 6-9*(4+3)+5# 中缀—栈—求解 栈的应用——八皇后（递归） Procedure try(I); 选择第I个皇后的位置； if 安全 then (1) 放置第I个皇后； (2) if I=8 then 输出 else try(I+1); 尝试下一个位置； Procedure try(I); For j:=1 to 8 do if b[j] and c[I+j] and d[I-j] then a[i[]:=j; b[j]:=f; c[I+j]:=f; d[I-j]:=f; if I8 then try(I+1) else print; b[j]:=t; c[I+j]:=t; d[I-j]:=t; 栈：I、 j 系统维护 b 、c、 d 手动维护 递归调用返回即回溯 八皇后——非递归 Top:=1; j:=0; While top0 do j:=j+1; if j8 then top:=top-1; j:=a[top]; b[j] c[top+j] d[top-j]:=t; else if (top=8) and b[j] and c[top+j] and d[top-j] then a[t