当前位置:首页 >> 学科竞赛 >> 栈、队列与广搜(赵宗昌2012)

栈、队列与广搜(赵宗昌2012)


栈和队列
东营胜利一中 李云军

基本概念
数据结构 + 算法=程序
数据结构是计算机存储、组织数据的方式。数据结构 是指相互之间存在一种或多种特定关系的数据元素的 集合。通常情况下,精心选择的数据结构可以带来更 高的运行或者存储效率。

基本概念
? 根据数据元素间关系的不同特性,通常有下列四

类基本的结构: ? ⑴集合结构。该结构的数据元素间的关系是 “属于同一个集合”。 ? ⑵线性结构。该结构的数据元素之间存在着 一对一的关系。 ? ⑶树型结构。该结构的数据元素之间存在着 一对多的关系。 ? ⑷图形结构。该结构的数据元素之间存在着 多对多的关系,也称网状结构。

基本概念
? 线性表是最简单、最基本、也是最常用的一种线 性结构。 线性表是具有相同数据类型的n(n>=0) 个数据元素的有限序列,通常记为: ? (a1,a2,… ai-1,ai,ai+1,…an) ? 其中n为表长, n=0 时称为空表。 它有两种 存储方法:顺序存储和链式存储,它的主要基本 操作是插入、删除和检索等。 ? 除了首尾结点,所有的结点都有前驱和后继; ? 首结点只有后继没有前驱,尾结点只有前驱没有 后继; ? 线性表的任何位置都可以进行插入删除等操作。

一、栈的概念和特性
? 现在我们对线性表的操作做一点限制, 规定所有的插入或删除操作只能在线性表的一 端进行,这样的线性表称为栈(stack)。 ? 栈是一种特殊的线性表,对它的插入和 删除都限制在表的同一端进行。

a1 a2 a3 a4

一、栈的概念和特性
? 把可以操作的一端 称为栈顶,不允许操作 的一端称为栈底。在栈 顶插入一个元素,称为 进栈,在栈顶删除一个 元素称为出栈。 ? 栈中元素的进出是 栈顶 按后进先出的原则进行, 这是栈结构的重要特征。 栈底 ? (LIFO:Last In First Out) ? 用一个变量记录栈 顶的位置,通常称这个 变量为栈指针。 a5 进栈 出栈
a4 a3 a2 a1

练习1
?元素R1、R2、R3、R4、R5入栈的顺序为 R1、R2、R3、R4、R5。如果第一个出栈 的是R3,那么第五个出栈的不可能是 ( )。
A.R1 B.R2 C.R4 D.R5

答案:B

练习2
? 设栈S的初始状态为空,现有5个元素组成 的序列{1,2,3,4,5},对该序列在S 栈上依次进 行如下操作(从序列中的1开始,出栈后不再进 栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,问: ?出栈的元素序列是:_________, ?栈顶指针的值为______, ?栈顶元素为:______________。
解答: 出栈序列为{3,4}, 栈顶指针值为3, 栈顶元素为5。
1 3 4 2 5 4 3

练习3
? 设栈S初始状态为空,元素e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6依次通过栈S, 若出栈后的输出顺序为e 2 ,e 4 ,e 3 , e 6 ,e 5 ,e 1 ,则栈S的容量至少应 该为( )。 ? A)2 B)3 C)4 D)5
e1 e2 5 3 e6 e4

e2 e4 e3 e6 e5 e1

练习4
? 若已知一个栈的入栈顺序是1,2, 3,……,n,其输出序列为P1,P2, P3,……,Pn,若P1是n,则Pi是( )。
B)n-1 C)n-i+1 D)不确定

?A)i

【分析】 1, 2, 3,……, n P1,P2,P3,……,Pn 已知 p1=n,说明所有的元素进栈以后,才开始出栈。 所以p2=n-1,pi=n-i+1。

二、栈的存储结构
?顺序栈 ? type arraytype= array[1.. n] of datatype; ? var stack:arraytype; ? top:integer; ?使用一维数组stack作为栈的存储结构 ?n是栈的容量,即栈中最多可存放的元素 ?top是栈指针,top=0,表示栈空,top=n, n 表示栈满;top>n或者top<0,则栈溢出
a1 a2 a3 a4

top=4

三、栈的基本操作
?⑴在使用栈之前,首先需要将栈初始化; ?⑵往栈顶加入一个新元素,称进栈(压栈); ?⑶删除栈顶元素,称出栈(退栈、弹出); ?⑷查看当前的栈顶元素,称读栈; ?⑸在使用栈的过程中,还要不断测试栈是否 为空或已满,称为测试栈。

三、栈的基本操作
? (1)栈的初始化操作(栈置空) ? top:=0 ? (2)判断栈空函数 ? function sempty(stack:arraytype):boolean; ? begin ? sempty:=(top=0); ? end; ? (3)判断栈满函数 ? function sfull(stack:arraytype):boolean; ? begin ? sfull:=(top=n); ? end;

三、栈的基本操作
?(4)进栈的操作过程(压栈push) ?procedure push(var tack:arraytype;x:integer); ? begin ? if sfull(stack) ? then writeln(‘Stack full!’) ? else begin ? top:=top+1; stack[top]:= x ? end ? end;

三、栈的基本操作
?(4)读栈函数 ? function reads(stack:arraytype):integer;
? begin ? if sempty(stack) ? then writeln(‘Stack empty!’) ? else reads:=stack[top]; ? end; ? (6)出栈操作过程(pop) ? procedure pop(var stack:arraytype;var x:integer); ? begin ? if sempty(stack) ? then begin writeln(‘Stack empty!’); end ? else begin x:=stack[top]; top:=top-1 end ? end;

例1自然数有序拆分
?【问题描述】 ? 任何一个大于1的自然数总可以拆分成若 干个自然数之和。例如n=4, ?4=1+1+1+1 解的特点: ?4=1+1+2 1.最多有n项; ?4=1+3 2.Si+1>=Si ?4=2+2

例1自然数有序拆分
? 【问题分析】 ? 设有序拆分出的数s1,s2,…,sk,满足关 系s1≤s2≤…≤sk。 ? 定义数组s为一个栈,用来存放拆分的元素。 ? 变量sum对拆分的元素求和,若sum<n则求 下一个拆分的元素;若sum =n,输出一个 解;若sum>n,则栈顶元素置0,退栈,即 3 2 0 3 2 1 1 回溯。 1 1 0 2
top top top

top

top

?var ? top,j,n,m:integer; ? s:array[0..100] of integer;
?procedure print; ? var i:integer; ? begin ? write(n,’=‘,s[1]); ? for i:=2 to top do write(‘+’,s[i]); ? writeln; ? end;

function sum(top:integer):integer; var i,t:integer; begin t:=0; for i:=1 to top do t:=t+s[i]; sum:=t; end; function cr(top:integer):boolean; {判断si>si+1} var i:integer; begin cr:=true; for i:=1 to top-1 do if s[i]>s[i+1] then exit(false); end;

{主程序} begin fillchar(s,sizeof(s),0); readln(n); top:=1; repeat inc(s[top]);m:=sum(top); if m<=n then if (m=n) and cr(top) then print else inc(top) else begin s[top]:=0;dec(top);end; until top=0; end.

例2表达式计算
? 计算表达式3×5+(6-8/4)×7的值。
3×5=15 8/4=2 6-2=4 4×7=28 15+28=43

4

/

7 2 8
28 6 5 4

× (

15 43 3

+ ×

例2表达式计算
? 【问题分析】 ? 为了便于用程序计算将中缀表达式转换成 后缀表达式: ? 3×5+(6-8/4)×7 {中缀表达式} ? 3 5×6 8 4 / -7×+ {后缀表达式} ? 要解决两个问题 ? 如何将中缀表达式转换成后缀表达式 ? 如何计算后缀表达式的值

例2表达式计算

? 中缀表达式转换后缀表达 式 ? 从左向右扫描表达式 ? 运算数送到输出队列 ? 运算符进栈 ? 如果运算优先级大于栈 顶元素直接进栈 ? 如果运算优先级小于或 等于栈顶元素,则先弹 出栈顶元素,再进栈 ? 左括号直接进栈 ? 右括号则依次弹出栈中的 元素,直到遇到第一个左 括号为止。

运算符
# -1

优先级



0(直接入栈)

+ * )

/

1 2 单独处理

25+6*32-(21+5)/7

输出队列 6 9 4 3 + * 5 + #

6-9*(4+3)+5#
6 9 4 3 +*-5 +
运算符 优先级 -1 0(直接入栈) / 1 2 单独处理

+ ( * + #

1 0 2 1 1 -1

# ( + * )

请你试一试
?将下列中缀表达式转换成后缀表达式: 16-9*(4+3)
16□9□4□3□+*-

2*(x+y)/(1-x)
2□x□y□+*1□x□-/

(25+8)*(4*(4+7)+7)
25□8□+4□4□7□+*7□+*

例2表达式计算——中缀转后缀
?【数据结构】 ? type ? stack=array[1..100] of char; ? var ? top,i,j,h:integer; ? ch,w:char; ? a,s :stack;
? a:输出队列 ? j:输出队列指针 s:栈 top:栈指针

例2表达式计算——中缀转后缀
? Function t(p1:char):integer; ? begin ? case p1 of 函数t定义运算符的优先级 ? '#': t:=-1; 运算符 优先级 ? '(': t:=0; ? '+': t:=1; -1 # 0 ( ? '-': t:=1; ? '*': t:=2; + 1 ? '/': t:=2; * / 2 ? ')': t:=3; 3 ) ? end; ? end;

procedure push(var s:stack; ch:char); {进栈} begin inc(top); s[top]:=ch; end; procedure pop(var s:stack); {出栈} begin dec(top); end; function readtop(s:stack):char; {读栈} begin readtop:=s[top]; end;

begin push(s,'#'); j:=0; read(ch); while ch<> '#' do {从左到右逐字读入表达式} begin if ch in ['0'..'9'] then begin while ch in ['0'..'9'] do begin {读入数字直 inc(j); 接进入输出 a[j]:=ch; 队列} read(ch); end; inc(j); a[j]:=' '; {数字后面加一个空格} end

else begin case ch of '+','-','*','/':begin w:=readtop(s); while t(ch)<=t(w) do begin inc(j);a[j]:=w; pop(s); w:=readtop(s); end; push(s,ch); end;

'(': push(s,ch); ')':begin while s[top]<>'('do begin inc(j); a[j]:=s[top]; pop(s); end; {丢弃左括号} pop(s); end; end; read(ch); end; end;

w:= readtop(s); {表达式扫描结束,栈中 while w<>'#' do 剩余的元素全部弹出} begin inc(j);a[j]:=w; pop(s);w:=readtop(s); end; inc(j); a[j]:='#';pop(s); h:=0; repeat inc(h); write(a[h]); until a[h]='#'; writeln(a[h]);

end.

例2表达式计算——后缀表达式计算
输出队列 6 9

6 9 4 3 +*-5 +#
4 3 + * 5 + #

-52 -57 6 4+3=7 9*7=63

9 63 5

4 7

3
6-63=-57 -57+5=-52

例2表达式计算——后缀表达式计算
?【数据结构】

? const n=20; ? type ? arr=array [1..n] of char; ? arr1=array [1..n] of real; ? var ? a:arr; {存储后缀表达式} ? s:arr1; {栈} ? i,j,k,top:integer; ? t,x:real; ? ch:char;

procedure readdata(var a:arr); var i,k:integer; {读入后缀表达式} begin assign(input,'count.in');reset(input); read(ch);i:=0; while ch<>‘#' do begin i:=i+1;a[i]:=ch; read(ch); end; i:=i+1; a[i]:=‘#';close(input); end;

function comp(a:arr; var s:arr1):real; var i,k:integer; begin i:=1; top:=0; ch:=a[i]; while ch<>‘#' do begin {将数字字符串转换为实数} case ch of '0'..'9':begin x:=0; while (ch<>' ') do begin x:=x*10+ord(ch)-ord('0'); i:=i+1; ch:=a[i]; end; top:=top+1; end;

'+':begin x:=s[top-1]+s[top];dec(top); end; '-':begin x:=s[top-1]-s[top]; dec(top); end; '*':begin x:=s[top-1]*s[top]; dec(top); end; '/':begin if s[top]<>0 then begin x:=s[top-1]/s[top];dec(top); end else begin writeln(‘error’); close(output); halt; end; end; end ; {case} s[top]:=x;i:=i+1;ch:=a[i]; end ;{while} comp:=s[top]; end;{function}

主程序
begin assign(output,'count.out'); rewrite(output); for i:=1 to n do s[i]:=0; readdata(a); t:=comp(a,s); writeln('t=',t:0:2); close(output); end.

1.队列的基础知识
?到医院看病排队挂号排队 ?在学校食堂就餐排队买饭 ?到银行办理存款或取款业务排队
?共同的特征
?严格遵守先来后到原则 ?不存在插队现象

出队 A2 A1

A 3 A4 A5 A 6 A7 A8

进队 A9 A10

队列

1.1 队列的概念
?队列是限定在表的一端进行插入,在表的另 一端进行删除的线性表。
?队尾(rear):可以插入的一端 ?队首(front):可以删除的一端

?“先进先出”(FIFO—first in first out)

线性表。 出队 A1 A2A3 A4 …… Ai F(队首) R(队尾) 进队

1.2 队列的基本术语
?队首指针f:指向队首元素前一个位置
?初始状态:f=0

?队尾指针r:指向队尾元素
?初始状态:r=0

?出队:从队列头部删除一个元素 ?进队:将一个元素插入队列尾部
1 2
a

3
b

4
c

5


d e

i

i+1
f

F

R

1.3 队列的存储结构—顺序存储
Const m=队列元素的上限; Type queue=array[1..m] of elemtype; {队列的类型定义} Var q:queue; {队列} f, r: integer ; {队尾指针和队首指针}

2.队列的基本操作运算
?(1)初始化队列 Qini (Q) ?(2)判断队列是否为空 qempty(Q) ?(3)判断队列是否为满qfull(Q) ?(4)入队 QADD(Q,X) ?(5)出队 QDel(Q,X)

2.1初始化操作过程
?设定队列为空

procedure Qini (var Q:queue); begin f:=0; r:=0; end;

f=r=0

2.2 判断队列是否为空的函数
?若队列Q为空,则返回值true,否则返回值 false。

function qempty(Q:queue):Boolean;

begin
qempty:=(r=f)

end;

2.3 判断队列是否为满的函数
?若队列满,则返回值true,否则返回值false。

function qfull(Q:queue):Boolean; begin Qfull:=(r=m);

end;

2.4元素进队过程
?若队列Q不满时,把元素X插入到队列Q的队 尾,否则返回信息“Overflow”。
procedure QADD(var q:queue;x:elemtype); begin if qfull(Q) {上溢} then writeln (‘overflow’) else begin r:=r+1; q[r]:=x;{将元素插入队尾} end; end;

2.5 元素出队过程
?若队列Q不空,则把队头元素删除并返回值 给X,否则输出信息“Underflow”。 procedure Qdel(var q:queue;var x:elemtype); begin if qempty(Q) {下溢} then writeln(‘Underflow’) else begin f:=f+1; x:=q[f];{从队首删除一个元素} end; end;

例题3 周末舞会
假设在周末舞会上,男士们和女士 们进入舞厅时,各自排成一队。跳舞开 始时,依次从男队和女队的队头上各出 一人配成舞伴。规定每个舞曲能有一对 跳舞者。若两队初始人数不相同,则较 长的那一队中未配对者等待下一轮舞曲。 现要求写一个程序,模拟上述舞伴配对 问题。

例题 周3末舞会
输入3个整数m,n,k,分别表示男 士人数、女士人数、几轮舞曲。 例如:2 4 6

输出各轮舞曲的配对方案。
例如:
11 22 13 24 11 22

例题3 周末舞会
? 设计两个队列分别存放男士和女士。每对 跳舞的人一旦跳完后就回到队尾等待下次被 选。 ?m=3 n=2 k=6
A 1 2 3 1 2 3 1

B

1

2

1

2

1

2

例题3 周末舞会
?数据结构
?a、b分别为两个队列 ?f1,r1,f2,r2分别为两个队列的首尾指针

const max=1000; var a,b:array[1..max] of integer; m,n,k,i,f1,r1,f2,r2:integer;

例题3 周末舞会
?初始化
?读入数据 ?建立两个初始队列

readln(m,n,k); for i:=1 to m do a[i]:=i; for i:=1 to n do b[i]:=i; f1:=0;r1:=m; f2:=0;r2:=n;

例题3 周末舞会
?模拟舞会 配对

for i:=1 to k do begin f1:=f1+1; f2:=f2+1; writeln(a[f1]:3,' ',b[f1]:3); r1:=r1+1;a[r1]:=a[f1];

r2:=r2+1;b[r2]:=b[f2];
end;

2.6队列的“假溢出”现象
? 当尾指针指向数组的最后一个元素时,即 r=m,下一个元素就不能进队了。但是数组 的前部因元素出队空出很多位置闲置无用, 这种现象称为“假溢出”。 ?将m+1的元素放入1,指针绕数组移动。

r:=r+1 if r>m then r:=r mod m

r:=(r mod m)+1

2.7 循环队列

?初始化:f=r=m ?队空:f=r ?队满:f=(r mod m)+1 ?进队:r=r mod m+1 ?出队:f=f mod m+1

m 1 2

3 r

f

深度、广度优先搜索
?在搜索过程中,我们把每个状态看作是结 点,把状态之间的联系看做是边,这样我 们就可以得到一棵树,我们把这棵树称为 “搜索树”。

深度、广度优先搜索
?初始状态对应根结点,目标状态对应目标 结点。问题的一个解就是一条从根结点到 目标结点的路径。 ?对“搜索树”的搜索算法类似于树的遍历 ,通常有两种不同的实现方法:
?广度优先搜索(BFS) ?深度优先搜索(DFS)

广度优先搜索
?BFS每次都先将搜索树某一层的所有节点全 部访问完毕后再访问下一层,因此也被称 作“按层搜索”。

广度优先搜索
?一般来说,BFS使用队列来实现。 ?BFS一般用来求最优解。 ?在存储数据时,除了需要存储当前状态外 ,还需要存储当前状态的父状态以及由父 状态转换过来所执行的操作。

Data

OP

Pre

? 广度优先搜索算法: ? 初始化;建立数据库data(既存储接点的队列,一般用一个数组来实现 ,每一个节点一般包含接点数据,深度值,父节点指针等信息); ? 初始状态存入数据库;设队列首指针closed:=0;队列尾指针open:=1; ? repeat ? 取下一个closed所指节点; ? for r:=1 to rmax do {r为产生式规则编号(产生新接点的规则)} ? begin ? if 子节点符合条件 then ? begin ? open:=open+1; ? 把新接点存入数据库队尾; ? if 新接点与原接点重复 then ? 删去该接点(open:=open-1) ? else if 新接点是目标 then 输出并退出; ? end(if) ? end(for) ? until closed>=open{队列空};

例4 最少中转路线(work1)
? 最少中转路线(work1) ? 下图表示的是从城市A到城市H的交通图。从图中 可以看出,从从一个城市到另一个城市要经过若 干个城市。 ? 现要找出一条经过城市最少的一条路线。

? Program road ? Type ? Node=record ? St:integer; ? Deep:integer; ? Pre:integer; ? End; ? Var g[1..8][1..8]:array of integer=(…….); ? Data:array[1..20]of node; ? Function check(k:integer):Boolean ; ? Begin end;

? 广度优先搜索算法: ? 初始化;建立数据库 data(既存储接点的队 列,一般用一个数组 来实现,每一个节点 一般包含接点数据, 深度值,父节点指针 等信息); ? ? ? ? ?

? Begin ? Closed:=0; open:=1; ? Data[1].st:=1;data[1].deep:=0;data[1].pr e:=0; ? Reapeat ? Closed:=closed+1; ? For r:=1 to 8 do ? ? Begin ? If(g[r][data[closed].st]=1)and check( r)then ? Begin ? Open:=open+1; ? Data[open].st:=r; ? Data[open].deep:=data[closed].deep+1; ? Data[open].pre:=closed; ? If data[open].st=8 then 输出 break; ? Endif; ? Endfor; ? Until closed>=open;

? 初始状态存入数据库;设队列首指针 closed:=0;队列尾指针open:=1; ? ? repeat ? 取下一个closed所指节点; ? for r:=1 to rmax do {r为产生式规则 编号(产生新接点的规则)} ? begin ? if 子节点符合条件且新接点与原接点 重复 then ? begin ? open:=open+1; ? 把新接点存入数据库队尾; ? ? if 新接点是目标 then 输出并退出; ? end(if) ? end(for) ? until closed>=open{队列空};

例题5 迷宫问题
? 编一个程序,找出一条通过迷宫的路径。 这里有兰色方块的区域表示走不通,将一只 老鼠从入口处经过迷宫到出口处的最短的一 条通路打印出来。 入口

出口

例题5 迷宫问题
? 【问题分析】
? (1)用二维数组表示迷宫,1代表不能走入 的区域,0表示可以走通。

0 1 0 0 1 0

1 0 1 1 0 1

1 1 0 1 0 1

1 0 0 1 1 0

0 1 1 0 1 0

1 0 1 0 0 1

1 1 1 1 0 1

1 0 1 1 0 0

例题5 迷宫问题
?(2)老鼠在迷宫中怎样探索路径?有几个方 向可以探索呢?
(a)有三个方向可以试 探。 (b)有五个方向可以试 探。 (c)有八个方向可以试 探。 a b c

例题5 迷宫问题
1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1

1
1 1 1 1 1

1
0 0 1 0 1

0
1 1 0 1 1

1
0 1 0 1 1

0
0 1 1 0 1

1
1 0 1 0 1

0
1 0 0 1 1

1
1 1 0 1 1

0
1 1 0 0 1

1
1 1 1 1 1

0 1 0 0 1 0

1 0 1 1 0 1

1 1 0 1 0 1

1 0 0 1 1 0

0 1 1 0 1 0

1 0 1 0 0 1

1 1 1 1 0 1

1 0 1 1 0 0

Dx 0 1 1 1 0

Dy 1 1 0 -1 -1 -1 0 1

(x-1,y) (x-1,y+1) (x-1,y-1) (x,y-1) (x,y) (x,y+1) (x+1,y-1) (x+1,y)(x+1,y+1)

-1 -1 -1

例题4.5 迷宫问题
?(3)用一个队列记 录探索的路径。 ?x:当前位置的所在 行 ?y:当前位置的所在 列 ?pre:前一个位置的 记录在队列中的序 号

? 队列操作的一般过程 ? (1)初始化: ? 指针赋初值,f:=0;r:=1; ? 第一个结点进队,q[1.1]:=1;q[2.1]:=1;q[3,1]:=0; ? (2)出队操作,f:=f+1; x:=q[1,f];y:=q[2,f]; ? (3)依次探索八个方向,如果能走通,则进队, ? r:=r+1; q[1.r]:=x;q[2.r]:=y;q[3,r]:=f; ? (4)重复(2)(3)步,直到目标状态出现,输出结果, 结束。 ? (5)如果目标状态一直不出现,则队空循环结束, 无解。

例题5 迷宫问题
? 【数据结构】 ? const dx=array[1..8] of integer=(0,1,1,1,0,-1,-1,1); ? dy=array[1..8] of integer=(1,1,0,-1,-1,1,0,1); ? max=10; ? type sqtype=array[1..3,1..max*max] of integer; ? var mg:array[0..max+1;0..max+1] of integer; ? sq:sqtype; ? f,r,i,j,n,m:integer;

Procedure mglj(var sq:sqtype); Begin f:=0;r:=1;sq[1,1]:=1;sq[2,1]:=1;sq[3,1]:=0; While f<r do Begin f:=f+1; x:=sq[1,f];y:=sq[2,f]; for v:=1 to 8 do begin i:=x+dx[v]; j:=y+dy[v]; if mg[i,j]=0 then begin inc(r);sq[1,r]:=i;sq[2,r]:=j;sq[3,r]:=f; mg[i,j]:=-1; end; if (i=m) and (j=n) then print; end; {for} End; Writeln(‘迷宫无路径’); End;

Procedure print(var sq:sqtype;r:integer); Begin i:=r; repeat writeln(‘(‘,sq[1,i],’,’,sq[2,i],’)’); i:=sq[3,i] until i=0; halt; End;

(6,8) (5,7) (4,6) (4,5) (3,4) (3,3) (2,2) (1,1)

例题6 分油问题
?【问题描述】 ? 在10升的容器中装有 10升油,另有两个7升和3 升的空容器,现要求用这 三个容器倒油,使得最后 在10升和7升的容器中各 有5升油。
C10 10 3 3 6 6 9 9 2 2 5 C7 0 7 4 4 1 1 0 7 5 5 C3 0 0 3 0 3 0 1 1 3 0

例题6 分油问题
?【问题分析】 ? 三个容器可以看作三个变量 C10,C7, C3,每次倒油的可能性只有如下六种情况: ? ① C10 向 C7 倒油 ② C10 向 C3 倒油 ? ③ C7 向 C10 倒油 ④ C7 向 C3 倒油 ? ⑤ C3 向 C10 倒油 ⑥ C3 向 C7 倒油

(1)(c10>0) and (c7<7) c10?c7 c10+c7>7? c10:=c10+c7-7;c7:=7; c10+c7<=7? c7:=c10+c7;c10:=0; c10+c3>3? c10:=c10+c3-3;c3:=3; c10+c3<=3? c3:=c10+c3;c10:=0;

(2)(c10>0) and (c3<3)
c10?c3

(3)c7>0 c7?c10: c10:=c10+c7;c7:=0; (4)(c7>0) and (c3<3)

c7?c3

c7+c3>3? c7:=c7+c3-3;c3:=3; c7+c3<=3? c3:=c7+c3;c7:=0;

例题4.6 分油问题

?【数据结构】 ?Var q:array [1..4,1..100] of integer; ? f,r,p:integer; ? c10,c7,c3:integer;

begin f:=0;r:=1; q[1,1]:=10;q[2,1]:=0;q[3,1]:=0; q[4,1]:=0; While f<r do Begin inc(f); c10:=q[1,f];c7:=q[2,f]; c3:=q[3,f]; for p:=1 to 6 do {主程序} begin case p of {for case可去掉} 1:f1(c10,c7,c3); 2:f2(c10,c7,c3); 3:f3(c10,c7,c3); 4:f4(c10,c7,c3); 5:f5(c10,c7,c3); if f=r then 6:f6(c10,c7,c3); End; writeln(‘no answer’); end; end.

procedure f1(w10,w7,w3:integer); begin if (w10>0) and (w7<7) then if w10+w7>7 then begin w10:=w10+w7-7;w7:=7;end else begin w7:=w10+w7;w10:=0;end; if flag(w10,w7,w3) then begin inc(r); q[1,r]:=w10;q[2,r]:=w7; q[3,r]:=w3;q[4,r]:=f; end; if (w10=5) and (w7=5) then print; end;

function flag(w10,w7,w3):boolean; var i:integer; begin flag:=true; for i:=1 to r do if (q[1,i]=w10) and (q[2.i]=w7) and (q[3.i]=w3) then flag:=false; end;

广度优先搜索的局限
?对于BFS而言,当求解步骤较长时,由于需 要存储全部的扩展结点,很容易造成空间 不够的情况。 ?对于这种情况,往往会通过剪枝减去不可 能的状态,节约空间;或者在容许的情况 下使用循环队列;或者采用别的方法来解 决问题。

上机练习1最少中转路线(work1)
? 最少中转路线(work1) ? 下图表示的是从城市A到城市H的交通图。从图中 可以看出,从从一个城市到另一个城市要经过若 干个城市。 ? 现要找出一条经过城市最少的一条路线。

上机练习1最少中转路线(work1)
? 输入(work1.in): ? 输入包含1行:两个字母,中间用空格隔开,分别 表示出发点和目标点 ? 输出:(work1.out): ? 输出只有一个非负整数,为出发点到目标点最少 经过的城市数(不包含出发点含目标点)。 ? 输入输出样例 ? 输入 ?AH ? 输出 ?2

上机练习2 括弧匹配检验work2
? 假设表达式中允许包含两种括号:圆括号和方括 号,其嵌套的顺序随意,如([ ]())或[([ ] [ ])]等为正确的匹配,[(])或([ ]( ) 或 (()))均为错误的匹配。 ? 现在的问题是,要求检验一个给定表达式中的括 弧是否正确匹配? ? 输入一个只包含圆括号和方括号的字符串,判断 字符串中的括号是否匹配,匹配就输出 “OK” ,不匹 配就输出“Wrong”。 ? 输入一个字符串: ? [([][])] ? 输出: ? OK

上机练习2 括弧匹配检验work2
? 【输入】 ? 输入仅一行字符(字符个数小于255) ? 【输出】 ? 匹配就输出 “OK” ,不匹配就输出“Wrong”。 ? 【样例】 ? 输入(work2.in) ? [(]) ? 输出(work2.out) ? Wrong

上机练习3青铜莲花池(bronlily)
? Farmer John 建造了一个美丽的池塘,用于让他的 牛们审美和锻炼。这个长方形的池子被分割成了 M 行和 N 列( 1 ≤ M ≤ 30 ; 1 ≤ N ≤ 30 ) 正方形格子的 。某些格子上有惊人的坚固的莲花,还有一些岩石 ,其余的只是美丽,纯净,湛蓝的水。 ? 贝茜正在练习芭蕾舞,她从一个莲花跳跃到另一个 莲花,当前位于一个莲花。她希望在莲花上一个一 个的跳,目标是另一个给定莲花。她能跳既不入水 ,也不到一个岩石上。 ? 令门外汉惊讶的是,贝茜的每次的跳跃像国际象棋 中的骑士一样:横向移动M1(1 ≤M1 ≤ 30 ),纵向移 动然后量M2 (1 ≤M2 ≤ 30 ;M1 ≠ M2 ) ,或纵向移动 然后量M1,横向移动M2。贝茜有时可能会有多达8

上机练习3青铜莲花池(bronlily)
?输入(bronlily.in): ?第 1 行: 四个用空格隔开的整数: M, N, M1, M2 ?第 2..M + 1 行: 第 i + 1 行 有 N 个整数,表 示该位置的状态: 0 为水; 1 为莲花; 2 为岩 石; 3 为贝茜开始的位置; 4 为贝茜要去的目 标位置。 ?输出( bronlily.out): ?第 1 行: 一个整数,从起始点到要去的位置 ,贝茜最小的跳跃次数。

上机练习3青铜莲花池(bronlily)
? 样例输入 ?4512 ?10101 ?30204 ?01200 ?00010 ? 样例输出 ?2 ? 输入解释 :贝茜从第2行第1个位置开始,她的目标在 第2行最右边。 ? 输出解释 :贝茜聪明地跳跃到了第1行第3个位置,然 后就到了目的地。

上机练习4 家庭问题work4
? 有n个人,编号为1,2,……n,另外还知道存在K 个关系。一个关系的表达为二元组(α,β)形式, 表示α,β为同一家庭的成员。 ? 问题:当n,k和k个关系给出之后,求出其中共有多 少个家庭、最大的家庭中有多少人? ? 例如: ? n=6,k=3,三个关系为(1,2),(1,3),(4,5) ? 此时,6个人组成三个家庭,即:{1,2,3}为一个 家庭,{4,5}为一个家庭,{6}单独为一个家庭, 其中第一个家庭的人数为最多。

上机练习4 家庭问题work4
【输入】(work4.in) 文件的第一行为n,k 二个整数(1≤n≤100) (用空格分隔) 接下来的k行,每行 二个整数(用空格分隔) 表示关系 【输出】(work4.out) 二个整数(分别表示 家庭个数和最大家庭人数) ? 【样例输入】 ? 输入文件(family.in) ?6 3 ?1 2 ?1 3 ?4 5 ? 输出文件 (family.out) ?3 3

上机练习4 家庭问题work4
?家庭关系

1 1 1

1

1 1

谢谢大家!


更多相关文档:

第3章-栈和队列_参考答案

第3 章 栈和队列一、选择题 1~5 BBDAA 6~10 CACAC 11~19 BBAB 11~15 ABBAA 二、填空题 1.顶指针 5.队尾 对头 三、综合题 1.Sina 2.6 ...

第三章 栈与队列 习题及答案

第三章 栈与队列 习题及答案_理学_高等教育_教育专区。自考数据结构 栈与队列 习题及答案第三章 栈与队列 习题及答案 一、基础知识题 3.1 设将整数 1,2,3,...

第3章 栈和队列答案

中华IT 学习网 www.100itxx.com 官方总站:圣才学习网 www.100xuexi.com 栈和队列答案 第三章 栈和队列答案一、选择题 1.B 9.D 21.D 33.1B 1.√ 13...

数据结构练习题 第三章 栈、队列和数组 习题及答案

数据结构练习题 第三章 队列和数组 习题及答案_工学_高等教育_教育专区。数据结构 第三章:队列和数组习题和答案 答案在最后 ...

第三章 栈和队列答案

搜 试试 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 理学...√ 2.3B 12.C 24.C 33.4C 5.× 栈和队列 2.5.C 14.C 26.A 34.C...

栈与队列-例子

实验三 栈和队列 3.1 实验目的:(1) 熟悉的特点(先进后出)及的基本操作,如入、出等,掌握的基本操作 在的顺序存储结构和链式存储结构上的实现; ...

栈与队列 实验报告

栈与队列 实验报告_电脑基础知识_IT/计算机_专业资料。栈与队列一,问题的提出在这次的实验当中,我选的题目是用队列的知识解决停车场问题。停车场问 题的具体描述...

实验四 栈与队列

实验四 栈与队列 姓名 王艳青 实验题目 学号 520713130135 日期栈与队列 2009.12.9 实验内容 1.采用链式存储实现的初始化、入、出操作。 2.采用顺序存储...

3 栈和队列答案

3 栈和队列答案_计算机软件及应用_IT/计算机_专业资料。你你岁的第3 章 栈和队列一、基础知识题 3.1 设将整数 1,2,3,4 依次进栈,但只要出栈时栈非空,则...

第3章 栈和队列

搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...第3章 栈和队列_工学_高等教育_教育专区。第3章...文档贡献者 zbmyth 贡献于2012-03-24 专题推荐 ...
更多相关标签:
赵宗昌 | 栈和队列 | 队列和栈的区别 | 两个栈实现一个队列 | 栈和队列的共同点是 | 栈和队列的共同特点是 | 栈 队列 | 栈和队列实验报告 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com