信息技术竞赛培训教程.doc

广州搬家公司WWW.DAZHONGBANJIA888.COM 魔声耳机WWW.JINMAOWANG.COM 西藏旅游WWW.52XZLY.COM 淘宝网客服电话 WWW.AYXZ.COM/SORT/INDEX.HTM 金鲨银鲨WWW.YOYOQIPAI.COM 零点中文WWW.LGAA.NET 外链由卓越SEO团队发送WWW.268SEO.COM DBFQ信息技术竞赛培训教程目录第二部分 数据结构（一）栈（二）队列（三）链表（四）迭代与递推（五）递归（六）搜索与回溯（七）树与二叉树（八）排序算法（九）查找算法（十）图论基础知识l l 广度优先搜索l l 广度优先搜索第二部分 算法和数据结构（一）栈说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式：栈、队这一讲，我们就来谈谈“栈”。“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么，“栈”为何物呢？栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。一个栈可以用定长为的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP0时为下溢。栈指针在运算中永远指向栈顶。1、进栈（PUSH）算法若TOP时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作）；置TOP=TOP+1（栈指针加，指向进栈地址）；S(TOP)=X，结束（X为新进栈的元素）；2、退栈（POP）算法若TOP0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作)；X=S(SOP)，（退栈后的元素赋给X）；TOP=TOP-1，结束（栈指针减，指向栈顶）。进栈、出栈的Pascal实现过程程序：CONST n=100;TYPEstack=ARRAY1.n OF integer;PROCEDURE PUSH(VAR s:stack;VAR top,x:integer);入栈BEGINIF top=n THEN writeln(overflow) ELSE BEGINtop:=top+1;stop:=x;END;END;PROCEDURE POP(VAR s:stack;VAR y,top:integer);出栈BEGINIF top=0 THEN writeln(underflow) ELSE BEGIN y:=stop;top:=top-1; ENDEND;对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。堆栈的数组模拟十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一中算法原理：N=(N div d)dN mod d （其中 div 为整除运算，mod为求余运算）。例如：(1348)10(2504)8运算过程如下：NN div 8N mod 8134816841682102125202NN div 8N mod 894131、 1、 填空：(9413)10=( )8=( )16=( )22、下面的程序实现这个转换过程，请补充完整。数制转化程序【xoi00_07.pas】program xoi00_07;const size=100;var a:array1.size of integer; n,d,i,j:integer;begin writeln; write(Please enter a number(N) base 10:); readln(n); write(please enter a number(d):); readln(d); i:=1; repeat ai:=n mod d; n:=n div d; inc(i); until n=0; for j:=i-1 downto 1 do write(aj:5);end.出站进站2、火车站列车调度示意图如下，假设调度站两侧的轨道为单向行驶轨道。1、 1、 如果进站的车厢序列为123，则可能的出战车厢序列是什么？2、 2、 如果进展进站的车厢序列为123456，问能否得到135426和435612的出站序列。栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。源程序编译中，若要把一个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X:4823; (式 11.1)其正确的计算结果应该是，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X122324321这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先数法。一般表达式中会遇到操作数、运算符和语句结束符等，以算术运算符为例，对每种运算赋予一个优先数，如：运算符：优先数：（语句结束符“；”的优先数为零）在运算过程中，优先数高的运算符应先进行运算（但遇到括号时，应另作处理）。按这样的规定，对式（11.1）自左向右进行运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进行编译时，一般设立两个栈，一个称为运算符栈（OPS），另一个称为操作数栈（OVS），以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句结束，其处理原则是：凡遇到操作数，一律进入操作数栈；当遇到运算符时，则将运算符的优先数与运算符栈中的栈顶元素的优先数相比较；若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入操作数栈，然后继续比较该运算符与栈顶元素的优先数。例如式（11.1）中，当扫描到“”和“”时都要将运算符入栈。接着扫描到“”号， 其优先数小于乘号所以乘号退栈，并执行，将结果再存入操作数栈。再将“”号的优先数与运算符栈的栈顶元素“”号的优先数相比较，两者相等，所以再将加号退栈，进行，结果为，再入栈，接着，由于运算栈已空，所以减号入栈。当扫描到“”时，操作数入栈。当扫描到“；”时，其优先数最低， 所以减号退栈并执行，结果为并入栈。因已扫描到语句结束符，所以表达式的求值结束，结果为。例题模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含、运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。分析:建立两个栈，一个是操作数栈（number），一个是运算符栈（symbol），根据运算符的优先级对两个栈进行相应的操作。源程序program ex11_4;const max = 100;var number: array0.max of integer; symbol: array1.max of char; s, t: string; i, p, j, code: integer;procedure push; 算符入栈运算begin inc(p); symbolp := si;end;procedure pop; 运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算begin dec(p); case symbolp + 1 of +: inc(numberp, numberp + 1); -: dec(numberp, numberp + 1); *: numberp := numberp * numberp + 1; /: numberp := numberp div numberp + 1; end;end;function can: boolean; 判断运算符的优先级别,建立标志函数begin can := true; if (si in +, -) and (symbolp () then exit; if (si in *, /) and (symbolp in *, /) then exit; can := false;end;begin write(String : ); readln(s); s := ( + s + ); i := 1; p := 0; while i = length(s) do begin while si = ( do 左括号处理 begin push; inc(i); end; j := i; repeat 取数入操作数栈 inc(i); until (si 9); t := copy(s, j, i - j); val(t, numberp, code); repeat if si = ) then 右括号处理 begin while symbolp ( do pop; dec(p); numberp := numberp + 1; end else begin 根据标志函数值作运算符入栈或出栈运算处理 while can do pop; push; end; inc(i); until (i length(s) or (si - 1 ); end; write(Result=, number0); readln;end.练习题：1、读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用.结束) 如果含有其他的字符，则只要求输出错误信息及错误类型。含有大写字母 错误类型 error 1数字（0-9） 错误类型 error 2其他非法字符 错误类型 error 3如 输入： It is 12!输出： error 1 2 3输入： i am ,a student输出： 42、 2、 编码解码：从键盘输入一个英文句子，设计一个编码、解码程序。(string)编码过程：先键入一个正整数N(1=N 0) and (tb 0) do 当两个表均不空时 begin 比较两表指针指向的项指数,输出指数小的项系数和指数, 同时改变该表指针 if ata.zhi btb.zhi then begin if ata.xi 0 then write(#8 #8); write(ata.xi, x, ata.zhi, +); dec(ta); end else if ata.zhi begin if btb.xi 0 then write(#8 #8); write(btb.xi, x, btb.zhi, +); dec(tb); endelse begin 若两表指针指向的项指数相等,则两系数相加输出, 两表指针同时改变 if btb.xi + ata.xi 0 then begin if btb.xi + ata.xi 0 do 若有一表空,则输出另一表的剩余项 begin if ata.xi 0 do begin if btb.xi 0 then write(#8 #8); write(btb.xi, x, btb.zhi, +); dec(tb); end;writeln(#8 #8);readln;end.源程序二：多项式相加的链表实现program ex11_5b;type link = node; node = record zhi, xi: integer; nxt: link; end;var a, b: link; n: integer;procedure createfifo(var c: link); 建立多项式系数、指数链表var p: link; i: integer;begin new(p); readln(p.xi, p.zhi); c := p; for i := 1 to n - 1 do begin new(p.nxt); p := p.nxt; readln(p.xi, p.zhi); end; p.nxt := nil;end;begin write(One : ); readln(n); createfifo(a); write(Two : ); readln(n); createfifo(b); write(Result is ); while (a nil) and (b nil) do begin if a.zhi b.zhi then begin if a.xi 0 then write(#8 #8); write(a.xi, x, a.zhi, +); a := a.nxt; end else if a.zhi begin if b.xi 0 then write(#8 #8); write(b.xi, x, b.zhi, +); b := b.nxt; endelse begin if b.xi + a.xi 0 then begin if b.xi + a.xi 0 then write(#8 #8); write(b.xi + a.xi, x, b.zhi, +); end; b := b.nxt; a := a.nxt; end;end;while a nil do begin if a.xi 0 then write(#8 #8); write(a.xi, x, a.zhi, +); a := a.nxt; end;while b nil do begin if b.xi 0) and (x0) and (yw;直至队空为止end;beginfillchar(bz,sizeof(bz),true);num:=0;write(input file:);readln(name);assign(int,name);reset(int);readln(int,m,n);for i:=1 to m dobegin readln(int,s);for j:=1 to n dobegin pici,j:=ord(sj)-ord(0);if pici,j=0 then bzi,j:=false;end;end;close(int);for i:=1 to m dofor j:=1 to n do if bzi,j then doing(i,j);在矩阵中寻找细胞writeln(NUMBER of cells=,num);readln;end.（四）迭代与递推本次我们想与大家共同探讨一下迭代与递推。在计算机数值程序设计中，迭代与递推是两个重要的基础算法。一、迭代许多的实际问题都能转化为解方程F(x)=0的实数解的问题。求根可以直接从方程出发，逐步缩小根的存在区间，把根的近似值逐步精确到要以满足具体实际问题的需要为止，该算法称为迭代。迭代的一般原则可以用一个数学模型来描述，现要求出方程F(x)=0的解：先设F(x)=G(x)-x，则方程F(x)=0可化为x=G(x)， 这就产生了一个迭代算法的数学模型：n+1=（n）从某一个数0出发，按此迭代模型，求出一个序列：0，1，2，3，n-2，n-1，n当nn-1小于一个特定值（误差许可值）时，n-1n，这时可认定x=G(x)。也就是说，求出的n已经可以作为原方程f(x)=0根的近似值了。 设误差许可值为A，则迭代算法的NS图如图1。 图1 迭代算法NS框图迭代算法的关键在于确定迭代函数G(x)。确定G(x)时需保证产生的迭代序列n 是否能使两个相邻的数之间的差距越来越小（即两数的差值越靠近误差值，我们称这样的序列为收敛序列），因为只有这样才能使根的存在范围越来越小，从而为根的取得创造条件。例1 求2的算术平方根（不使用内部函数）。分析:使用迭代算法来解决这个问题，使用迭代法可以先设X=SQRT(2)-1，则求2 的算术平方根的近似值就可以转化为求X(X+2)=1的正根。列出等价方程X=1/(X+2)， 以1/(X+2)为迭代函数，以0为初始近似值0，误差值设定为0.0000001， 则程序可写成：program ex11_7;const a=0.0000001;var x0,x1,X:real;beginx0:=0;x1:=1/(x0+2);while abs(x1-x0)a dobeginx0:=x1;x1:=1/(x0+2);end;x:=x1+1; 将X1的值转为2的算术平方根writeln(sqrt(2)=,x);end.程序的输出结果如下：SQRT(2)=1.4142135516E+00开始时，迭代函数的根的近似值设定在0,0.5之间， 由于区间宽度大于给定误差许可值，于是再进行迭代运算，产生下一个区间0.4,0.5； 其宽度仍然大于误差许可值，再产生下一个区间；如此反复，直到区间的宽度小于误差给定值时，则表明在该区间中，任意选择一个数都可以满足根的近似值要求了。为方便起见，取下该区间的边界置作为近似值。这就是迭代算法的一般原则的体现了。二、.递推对于一个的序列来说，如果已知它的通项公式（即表达位置与位置上的数据的关系的公式），那么，要求出数列中某项之值是十分容易的。但是，在许多情况下，要得到数列的通项公式是很困难的，甚至无法得到。然而，一个有规律的数列的相邻位置上的数项之间通常存在着一定的关系，我们可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，如此反复，直到找到所需的那一项为止，这样的方法称为递推算法。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。例2 著名的菲波纳葜(Fibonacci)数列，其第一项为0，第二项为1， 从第三项开始，其每一项都是前两项的和。编程求出该数列第N项数据。分析：按菲波纳葜数列的原则，数列为：0 1 1 2 3 5 8 13 21 34 55无疑地，寻找其项数位置与项值的关系（即通项公式）是非常困难的。而根椐该数列的形成规则，其有一个的公式即nn-1n-2 表明了相邻的数据项之间的明显关系。因此，可以其作为递推公式，以已知项0与1为起点，逐项产生第3项、第4项、，直到取得需要的第N项为止。 在其递推算法的语言实现上，可取J、K、P三个变量，分别表示前二项、前一项与当前项，J、K分别取初值0与1。第一次通过递推公式P=J+K得到第三项，并进行移位，即J取K值、K取P值， 为下次递推作准备；如此反复，经过N-2次的递推，P就是第N项的值（第1次产生的是3项的值）。源程序如下:program ex11_8;varn,i,j,k,p:longint;beginwrite(N=);readln(n);i:=2;j:=0;k:=1;repeatinc(i);p:=j+k;j:=k;k:=p;until i=n;writeln(F(,n,)=,p);end.菲波纳葜数列的递推明确地体现了递推算法程序设计的一般原则，即递推公式取得。例3 数字三角形。如下所示为一个数字三角形。请编一个程序计算从顶到底的某处的一条路径，使该路径所经过的数字总和最大。只要求输出总和。1、 一步可沿左斜线向下或右斜线向下走； 2、 角形行数小于等于100； 3、 三角形中的数字为0，1，99； 测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：573 88 1 02 7 4 44 5 2 6 5分析：此题解法有多种，从递推的思想出发，可以设想，当从顶层沿某条路径走到第I层向第I+1层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设ai，j存放从i，j 出发到达n层的最大值，则ai，j=maxai，j+ai+1，j，ai，j+ai+1，j+1，a1，1 即为所求的数字总和的最大值。源程序如下：program ex11_9;var n,j,i:integer;a:array1.100,1.100 of integer;beginread(n);for i:=1 to n dofor j:=1 to i doread(ai,j);for i:=n-1 downto 1 dofor j:=1 to i dobeginif ai+1,j=ai+1,j+1 then ai,j:= ai,j+ai+1,jelse ai,j:=ai,j+ai+1,j+1;end;writeln(a1,1);end. （五）递归在（四）中，我们了解了迭代与递推。与迭代、递推相对应的算法为递归，本趣谈数据结构，我们就来谈一谈递归算法。递归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。简单地说，递归就是编写这样的一个特殊的过程，该过程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程可以用图1所示。 图1递归过程的执行流程从图1可以看出，递归过程的执行总是一个过程体未执行完， 就带着本次执行的结果又进入另一轮过程体的执行，如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合逐步深入，而后又逐步返回的递归调用模型，以解决实际问题。利用递归调用程序设计技术可以解决很复杂但规律性很强的问题，并且可以使程序变得十分简短。例1 利用递归调用手段编程计算N!。分析：根椐数学知识，1!=1，正整数N的阶乘为：N*(N-1)*(N-2)*2*1， 该阶乘序列可转换为求N*(N-1)!，而(N-1)!以可转换为(N-1)*(N-2)!，直至转换为2*1!，而1!=1。源程序如下:program ex11_10;varn:byte;t:extended;procedure find(n:byte);beginif n=1 then t:=1elsebeginfind(n-1);t:=t*n;end;end;beginwrite(N=);readln(n);find(n);writeln(N!=,t:1:0);end.在过程find中，当N1时，又调用过程find，参数为N-1，这种操作一直持续到N=1为止。例如当N=5时，find(5)的值变为5*find(4)， 求 find( 4)又变为4*find(3)，当N= 1时递归停止，逐步返回到第一次调用的初始处，返回结果5*4*3*2*1，即5!。例2 利用递归调用技术求菲波纳葜数列的第N项。分析：我们已经知道菲波纳葜数列的各数列的产生可用下列公式表示： 12 nn-1n-2 （当n2时）因此当N大于2时，求第N项值可转化为求第N-1项值与第N-2项值的和； 而求第N-1项又可转化为求N-2项值与N-3项的和，相应地，求N-2项值可转化为求N-3 项值和N-4项值的和；如此反复，直至转化为求第1项或第2项值，而第 1项与第2项为已知值1和2。源程序:program ex11_11;varn:byte; a:array1.100 of longint;function f(n:byte):longint;var i:longint;beginif an-10 then i:=an-1else i:=f(n-1);if an-20 then i:=i+an-2else i:=i+f(n-2);an:=i;f:=i;end;beginwrite(N=);readln(n);fillchar(a,sizeof(a),0);a1:=1;a2:=1;writeln(F(,n,)=,f(n);end.本程序采用了函数递归，函数