null搜索算法搜索算法深度优先深度优先栈——Why State?
搜索——深度优先搜索
递归(系统栈)
回溯(人工栈的维护)
什么是栈?系统栈实例系统栈实例Function jc(n:integer):integer;
begin
if n=1 then jc:=1
else jc:=n*jc(n-1);
end;
Begin
write(jc(4));
End.432系统栈系统栈在调用过程或函数之前,系统需完成三件事:
⑴将所有的实在参数、返回地址等信息传递给被调用过程保存;
⑵为被调用过程的局部变量分配存储区;
⑶将控制转移到被调过程的入口。
从被调用过程返回调用过程之前,系统也应完成三件工作:
⑴保存被调过程的计算结果;
⑵释放被调过程的数据区;
⑶依照被调过程保存的返回地址将控制转移到调用过程。当有多个过程构成嵌套调用时,按照“后调用先返回”的原则系统栈——例系统栈——例汉诺塔(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;Var stack:arr;
top:integer;
动态—链表
Type link=^node;
node=record
info:integer;
next:link;
end;
Var stack:link;
top:link;栈的基本操作栈的基本操作Top:=0top:=nil;Top=0top=nil;A[top]Top^.infoTop:=top+1; a[top]:=…;?Top:=top-1; ?应用举例应用举例入栈顺序为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#6-9*(4+3)+5## -16 - 19* 2( 04+ 13+*-+ 15++ 16943+*-5+中缀—栈—求解中缀—栈—求解6-9*(4+3)+5763-57+ 15-52栈的应用——八皇后(递归)栈的应用——八皇后(递归)Procedure try(I);
选择第I个皇后的位置;
if 安全 then
(1) 放置第I个皇后;
(2) if I=8 then 输出
else try(I+1);
尝试下一个位置;Procedure try(I);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 I<8 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 top>0 do
j:=j+1;
if j>8 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[top]:=j;b[j] c[top+j] d[top-j]:=f;
top:=top+1; j:=0;
if top>8 then print;全排列——递归全排列——递归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 I< 8 then try(I+1) else print;
b[j]:=t; c[I+j]:=t; d[I-j]:=t;
mm全排列——非递归全排列——非递归Top:=1; j:=0;
While top>0 do
j:=j+1;
if j> 8 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[top]:=j;b[j] c[top+j] d[top-j]:=f;
top:=top+1; j:=0;
if top> 8 then print;mm深度优先搜索深度优先搜索方式
递归 回溯
基本框架训练训练素数环:将1~20这20个数摆成一个环,
相邻的两个数的和是一个素数
走迷宫回溯——穷举回溯——穷举背包问题——简单枚举
有5个背包(不可拆分),背包的价值(w)、体积(t)各不相等,在容量(tj)范围内,如何选取,使价值最大?For a[1]:=0 to 1 do
for a[2]:=0 to 1 do
…
for a[5]:=0 to 1 do
P;St:=∑a[I]*t[I];
Sw:=∑a[I]*w[I]
If st<=tj and sw>max then 记录状态;有n个背包,问题如何解决?分析问题——找出实质分析问题——找出实质A: 逢1进位实质实质初值:0 0 0 0 ……0
找到需要进位的下标
如何查找?
N1
结束标记?程序框架——逢1进位程序框架——逢1进位For I:=0 to n do a[I]:=0;
While a[0]=0 do
j:=n;
while a[j]=1 do j:=j-1;
a[j]:=a[j]+1;
for I:=j+1 to n do a[I]:=0;
计算P;
打印;逢1进位逢1进位N个砝码(1,3,9,……,3n-1)可以放在重物一侧,也可以放在砝码一侧,给出一个重量,问:如何称?While a[0]=0 do
j:=n;
while a[j]=1 do j:=j-1;
a[j]:=a[j]+1;
for I:=j+1 to n do a[I]:= 0 ;
计算;-1相等进位相等进位有n种背包,每种背包有若干个(bi),……While a[0]=0 do
j:=n;
while a[j]= 1 do j:=j-1;
a[j]:=a[j]+1;
for I:=j+1 to n do a[I]:= 0 ;
计算;B[j]相等进位——组合问题相等进位——组合问题从1~m中任意取出n个,
打印所有取法
保证不重复选择 —— 升序第n 位进位标志:m
第n-1位进位标志:m-1
…
第 j 位进位标志?深度优先搜索深入应用深度优先搜索深入应用跳马周游棋盘问题跳马周游棋盘问题分析分析一棵八叉树
八个方向:目前位置(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)
用二维数组表示棋盘,未走过的地方设置为0
b[i1,j1] = 0 当棋格 ( i1, j 1) 未被占据
i 当棋格 ( i1, j1) 在第 i 次移动中被占据
范围:未走过的和不越出棋盘边界的那些位置
为了防止马跳出棋盘,将棋盘扩大二圈,这些位置的表示设置为-1
深度优先搜索的优化方法深度优先搜索的优化方法缩小搜索范围——避免无效搜索
改变搜索次序——在几个可能到达的位置中根据优劣条件选择一个最优点来跳马
剪枝迷宫问题 编一个程序,找出一条通过迷宫的路径。这里显示为1的单元表示走不通,将一只老鼠从入口处经过迷宫到出口处的通路一一打印出来。
入口→
→ 出口
迷宫问题基本题基本题1~6迷宫问题找出一个从入口到出口的最短路径(八个方向)迷宫问题null总行数:0——m+1, 总列数: 0——n+1
1方案1在深搜过程中,记录搜索步数并与最小值进行比较,记录当前最佳方案,最后打印输出
能否改进?
方案2方案2从步数的角度考虑问题,分别列举出一步能到达的结点、两步能到达的结点、……、发现的终点肯定是最优方案
如何记录方案?
记录每个结点的来由
基本8个方向表示可以用数组说明:如何记录探索的踪迹?
——队列基本迷宫问题如何防止重复探索:将迷宫中的0替换为-1
队列中入队、出队情况如下表:迷宫问题程序程序……迷宫(用不同的颜色表示步数)迷宫(用不同的颜色表示步数)结论结论与深搜区别之一:搜索的方向不影响搜索规模
主要影响因素是什么?
迷宫变形:起点在迷宫中心、几乎没有障碍迷宫变形迷宫变形结论结论在宽搜过程中,队列以几何数量级扩展,扩展层数越大,对存储的威胁越大
如何对存储进行压缩?——双向搜索
应用现要找出一条从A到B经过城市最少的一条路线。广度优先遍历: A 应用宽搜基本框架宽搜基本框架F,r,队列初始化;
While f<=r do
取队首;
nullsq[1].x:=1 ;sq[1].y:=1 ;sq[1].pre:=0 ;
front :=1; rear :=1 ; mg[1,1]:=-1 ;
while front<=rear do
x:=sq[front].x ; y:= sq[front].y ;
for v:=1 to 8 do
I:=x+z[v].x ; j:= y+z[v].y ;
if mg[I,j] =0 then
rear :=rear+1 ; sq[rear].pre:=front ;
sq[rear].x:=I ; sq[rear].y:=j ;
mg[I,j]:= -1 ;
if ( i=m ) and (j=n) then print;
front := front+1 ; 例 数值计算例 数值计算设有数字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次运算 )。 分析算法模式(1)数据的结构:参加运算的数据、参加运算的符号——可以用常量数组
data[1]—2,data[2]—3……,参与运算数据、符号顺序
(2)每步参加运算的数据及运算符号——
x, y , t:被加数、加数,结果(x ),t :从哪一步计算到此。
分析算法模式例 产生数给出一个整数n(n<1030)和k个变换规则(k<=15)。
规则:
1个数字可以变换成另一个数字
规则的右部不能为零。
例如:n=234,有规则(k=2):
2 → 5
3 → 6例 产生数例 倒油 [例题4] 有10升油在10升的容器中,另有两个7升和3升的空容器,现要求用这三个容器倒油,使得最后在10升和7升的容器中各有5升油。
[题解] 三个容器可以看作三个变量 C10,C7,C3,每次倒油的可能性只有如下六种情况:
① C10 向 C7 倒油 ② C10 向 C3 倒油
③ C7 向 C10 倒油 ④ C7 向 C3 倒油
⑤ C3 向 C10 倒油 ⑥ C3 向 C7 倒油
例 倒油细胞问题细胞问题一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。
如:阵列
0 2 3 4 5 0 0 0 6 7
1 0 3 4 5 6 0 5 0 0
2 0 4 5 6 0 0 6 7 1
0 0 0 0 0 0 0 0 8 9
有4个细胞。翻币问题翻币问题有N个硬币(N≥6)正面朝上排成一排,每次将5个硬币翻过来放在原位置,直到最后全部硬币翻成反面朝上为止。编程让计算机找出步数最少的方法并把翻币过程及次数打印出来。(用O表示正面,用*表示反面)。翻币问题翻币问题分析:
每次翻R个正面,可行性判断
正面个数>=R and 反面个数>=5-R
num>=R and (10-num)>=5-R
num>=R and num-R<=5
0<=num-R<=5
R=0~5双向搜索双向搜索问题求解模式:状态A-状态B且AB同质
正向队列Q1(队列首为起始状态A)
反向队列Q2(队列首为目标状态B)nullwhile (f1<=r1) and (f2<=r2) do
data1=q1[f1]
for i=1 to 方案总数
计算得新状态temp1
if 为新状态 (在q1内比对判重)
入队q1
if 与q2有相同状态(在q2内比对判重) then
终止搜索,得到解决方案
data2=q2[f2]
for i=1 to 方案总数
计算得新状态temp2
if 为新状态(在q2内比对判重)
入队q2
if 与q1有相同状态(在q1内比对判重 ) then
终止搜索,得到解决方案
f1++; f2++ 易错点易错点在队列中只需记录正面个数
翻了i个正面,(5-i)个反面的硬币后正向硬币的个数
打印方向:从前往后:递归
从后望前:非递归/递归
交界处重复打印
翻币次数如何计算最少拐弯问题最少拐弯问题作业作业骑士问题
过河问题
登山问题