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

《信息技术竞赛培训教程.docx》由会员分享，可在线阅读，更多相关《信息技术竞赛培训教程.docx（12页珍藏版）》请在三一文库上搜索。

1、信息技术竞赛培训教程信息技术竞赛培训教程目录 第二部分数据结构（一）栈 （二）队列 （三）链表 （四）迭代与递推（五）递归（六）搜索与回溯（七）树与二叉树（八）排序算法（九）查找算法 （十）图论基础知识 l l广度优先搜索l l广度优先搜索 第二部分算法和数据结构 （一）栈说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式栈、队这一讲，我们 就来谈谈栈”。栈”的应用很广泛，大家在 PASCAL程序设计中，常遇 的一种错误就是 栈"超界，那么，栈”为何物呢 栈是只能在 莫一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往 堆。取走时，只能从上面一

2、件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和 插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH）,删除则称为退栈（POP）。栈也称为后进先生表（LIFO表）。一个栈可以用定长为N的数组S来表示，用一个栈指 针TOP指向栈顶。若TOP=0,表示栈空，TOPN时栈满。进栈时TOP加1 o退栈时TOP减1 o当 TOP then exit; if si in * , / and symbolp in * , / then exit; can false; end; begin write String ; readlns; s s ; i

3、1; p 0; while i 9 ; t copys, j, i - j; valt, numberp, code; repeat if si then 右括号处理 begin while symbolp do pop; decp; numberp numberp 1; end else begin 根据 标志函数值作运算符入栈或由栈运算处理 while can do pop;push; end; inci; until i lengths or si - 1; end; write Result ,number0; readln; end. 练习题 1、读入一英文句子，单 词之间用空格或逗

4、号隔开，统计其中单词个数，并输由各个 字母由现的频率。句子末尾不一定用”.结束 如果含有其他的字符，则只要求输由错误信息及错误类型。含有大写字母错误类型error 1数字(0-9)错误类型 error 2其他非法字符 错误类型error 3如输入It is 12输 出 error 1 2 3 输入 i am ,a student 输由 4 2、 2、 编码解 码从键盘输入一个英文句子，设计一个编码、解码程序。string编码过程先键入一个正整数 N1 0 and tb 0 do 当 两个表均不空时 begin 比较两表指针指向的项指数，输由指 数小的项系数和指数，同时改变该表指针 if ata

5、.zhibtb.zhi then begin if ata.xi 0 then begin if btb.xi ata.xi 0 do 若有一表空，则输由另一表的剩余项 begin if ata.xi 0 dobegin if btb.xi nil and b nil do begin if a.zhi b.zhi then begin if a.xi 0 then begin if b.xi a.xi nil do begin if a.xi nil do begin if b.xi 0 and x0 and yw; 直至队空为止 end; begin fillcharbz,sizeofbz

6、,true;num0; write input file ;readlnname; assignint,name;resetint;readlnint,m,n;for i1 to m dobegin readlnint,s;for j1 to n dobeginpici,jordsj-ord 0 ;if pici,j0then bzi,jfalse;end; end; closeint; for i1 to m do for j1 to n do if bzi,j then doingi,j; 在矩阵中寻找细胞 writeln NUMBER of cells ,num;readln; end.

7、（四）迭代与递推本次我们想与大家共同探讨一下迭代与递推。在计算机数值程序设计中，迭代与递推是两个重要的基础算法。一、迭代许多的实际问题都能转化为解方程Fx0的实数解的问题。求根可以直接从方程由发，逐步缩小根的存在区间，把 根的近似值逐步精确到要以满足具体实际问题的需要为止， 该算法称为迭代。迭代的一般原则可以用一个数学模型来描述，现要求由方程Fx0的解先设FxGx-x ,则方程Fx0可化为xGx ,这就 产生了一个迭代算法的数学模型Xn1G （X n）从奥一个数X0出发,按此迭代模型，求由一个序列 X0, X1, X2, X3, Xn-2, X n-1 , Xn 当X n Xn-1小于一个特定

8、值（误差许可值）时，XXn-IXn,这时可认定xGx o也就是说，求生的X n已经可以作为原方程 fx0根的近似 值了。设误差许可值为 A,则迭代算法的 NS图如图1。图1迭代算法NS框图 迭代算 法的关键在于确定迭代函数Gx o确定Gx时需保证产生的迭代序列X n 是否能使两个相邻的数之间的差距越来越小（即两数的差值越靠近误差 值，我们称这样的序列为收敛序列），因为只有这样才能使根的存在范围越来越小，从而为根的取得创造条件。例1求2的算术平方根（不使用内部函数）。分析使用迭代算法来解决这个问题，使用迭代法可 以先设XSQRT2-1 ,则求2的算术平方根的近似值就可以转 化为求XX21的正根。

9、列由等价方程 X1/X2 ,以1/X2为迭代函数，以 0为初 始近似值X 0,误差值设定为0.0000001,则程序可写成 program ex11_7; const a0.0000001; var x0,x1,Xreal; beginx00;x11/x02; while absx1-x0a do begin x0x1;x11/x02; end; xx11; 将 X1的值转为 2的算术平方根 writeln sqrt2 ,x; end. 程序的输生结果如下 SQRT21.4142135516E00开始时，迭代函数的根的近似值设定在0,0.5之间，由于区间宽度大于给定误差许可值，于 是再进行迭代

10、运算，产生下一个区间040.5;其宽度仍然大于误差许可值，再产生下一个区间；如此反复，直到区间的宽度小于误差给定值时，则表明在该区间中，任意选择 一个数都可以满足根的近似值要求了。为方便起见，取下该区间的边界置作为近似值。这就是迭代算法的一般原则的体现了。二、.递推 对于一个的序列来说， 如果已知它的通项公 式（即表达位置与位置上的数据的关系的公式），那么，要求生数列中奥项之值是十分容易的。但是，在许多情况下，要得到数列的通项公式是很困难 的，甚至无法得到。然而，一个有规律的数列的相邻位置上的数项之间通常 存在着一定的关系，我们可以借助已知的项，利用特定的关 系逐项推算由它的后继项的值，如此反

11、复，直到找到所需 的那一项为止，这样的方法称为递推算法。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。例2著名的菲波纳契Fibonacci数列，其第一项为0,第 二项为1,从第三项开始，其每一项都是前两项的和。编程求由该数列第 N项数据。分析按菲波纳契数列的原则，数列为0 1 12 3 58 13 21 34 55无疑地，寻找其项数位置与项值的关系（即通项公式）是非常困难的。而根楣该数列的形成规则，其有一个的公式即bn = Un-1 + U n-2

12、袭明了相邻的数据项之间的明显关系。因此，可以其作为递推公式，以已知项 0与1为起点， 逐项产生第3项、第4项、，直到取得需要的第 N项为止。在其递推算法的语言实现上，可取J、K、P三个变量，分别表示前二项、前一项与当前项，J、K分别取初值0与1。第一次通过递推公式 PJK得到第三项，并进行移位，即J 取K值、K取P值，为下次递推作准备；如此反复，经过 N-2次的递推，P就是第N项的值（第1次产生的是3项的 值）。源程序如下 program ex11_8; var n,i,j,k,plongint; begin write N ;readlnn; i2;j0;k1; repeat inci;pj

13、k;jk;kp; until in;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层向第I1层前进时，我们的

14、选择一定是 沿其下两条可行路径中最大数字的方向前进，为此，我们可 以采用倒推的手法，设 ai, j存放从i, j由发到达n层的最 大值，则 ai, jmaxai , jai1 , j, ai, jai1 , j1 , a1, 1即为所求的数字总和的最大值。源 程序如 下 program ex11_9; var n,j,iinteger; aarray1.100,1.,100 of integer; begin readn; for i1 to n do for j1 to i do readai,j; for in-1 downto 1 do for j1 to i do begin if a

15、i1,jai1,j1 then ai,j ai,jai1,j else ai,jai,jai1,j1; end; writelna1,1; end.（五） 递归 在（四）中，我们了解了迭代与递推。与迭代、递推相对应的算法为递归，本趣谈数据结构， 我们就来谈一谈递归算法。递归算法作为计算机程序设计中的一种重要的算法，是 较难理解的算法之一。简单地说，递归就是编写这样的一个特殊的过程，该过 程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执 行变得复杂起来，其执行的流程可以用图1所示。图1递归过程的执行流程 从图1可以看由，递归过 程的执行总是一个过

16、程体未执行完，就带着本次执行的结果又进入另一轮过程体的执行，如此反复，不断深入，直 到莫次过程的执行遇到终止递归调用的条件成立时，则不再 深入，而执行本次的过程体余下的部分，然后又返回到上一 次调用的过程体中，执行其余下的部分，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相 应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设 计由一种适合 逐步深入，而后又逐步返回 的递归调用模型， 以解决实际问题。利用递归调用程序设计技术可以解决很复杂但规律性 很强的问题，并且可以使程序变得十分简短。例1利用递归调用手段编程计算No分析根楣数学知识，11,正整数N的阶乘为 N*

17、N-1*N-2*2*1 , 该阶乘序列可转换为求 N*N-1 ,而N-1 以可转换为 N-1*N-2 一 直至转换为 2*1 ,而11。源程序如下 program ex11_10; var nbyte; textended; procedure findnbyte; begin if n1 then t1 else begin findn-1;tt*n; end; end; begin write N ;readlnn; findn; writeln N ,t10; end. 在过程find中，当N1时，又调用过程 find,参数为N-1 -这种操作一直持续到N1为止。例如当N5时，find5

18、的值变为5*find4 , 求find 4又 变为4*find3 一当N 1时递归停止，逐步返回到第一次调用 的初始处，返回结果 5*4*3*2*1 ,即5。例2利用递归调用技术求菲波纳契数列的第N项。分析我们已经知道菲波纳契数列的各数列的产生可用 下列公式表示U 1 = 0 U 2= 1 U n = U n-1 +U n-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。

19、if源程序 program ex11_11; var nbyte; aarray1.100 of longint; function fnbytelongint; var ilongint; begin an-10 then ian-1 else ifn-1; if an-20 then iian-2 else iifn-2; ani;fi; end; begin write N ;readlnn; fillchara,sizeofa,0; a11;a21; writeln F ,n, ,fn; end. 本 程序采用了函数递归，函数 F的执行比较复杂。函数F由于存在着两次的递归调用，使递归调

20、用广生执行流程的 上叉树 行式，大家可参照图2来理解这个执行过 程。为方便起见，设定N5,图中的数码表示递归执行的顺序。图2F函数的 上叉树 执行流程 递归调用技术的运用， 是在牺牲计算机内存空间和程序执行速度的基础上得到的。因为在递归调用的执行过程中，系统必须花费时间与空 间以栈的方式记下每次调用的返回位置地址及每一次过程 执行的中间结果，以便当递归调用终止条件成立时，能沿着逐步深入的路线逐步返回；取得这些数据，最终准确地 回到初始调用处。比如，同是解决菲波纳契数列问题的程序，使用递推就 比使用递归算法设计的程序执行速度快了许多。当一个问题蕴含着递归关系且结构比较复杂时，采用 一般的算法，不

21、仅给程序的设计带来许多困难，而且也会给 设计生的程序带来篇幅大、可读性差的缺点，这时采用递归 调用技术来设计程序则会带来相反的效果。例3相传在古印度的布拉玛婆罗门圣庙的僧侣在进行一种被称为汉诺塔的游戏，具装置是一块铜板，上面有三根杆（编号A、B、C）, A杆上自下而上、由大到小按顺序串 上64个金盘（如图3）。游戏的目标是把【演示程序 DEM00_02,rar 1 A杆上的金盘全部移到C杆上，并仍原有顺序叠好。条件是每次只能移动一个盘，并且在每次移动都不允许 大盘移到小盘之上。现要求利用递归调用技术给由 N个盘从A杆移到C杆的 移动过程。图3 N阶汉诺塔分析这个移动过程很复杂与烦琐，但规律性却

22、很强。使用递归调用技术来解决这个移动过程，先得找到一个 递归调用模型。想要得到汉诺塔问题的简单解法，着眼点应该是移动A杆最底部的大盘，而不是其顶部的小盘。不考虑64个盘而考虑N个盘的一般情况。要想将A杆上的N个盘移至C杆，我们可以这样设想1.以C盘为临时杆，从 A杆将1至N-1号盘移至B杆。2 .将A杆中剩下的第N号盘移至C杆。3 .以A杆为临时杆，从B杆将1至N-1号盘移至C杆。我们看到，步骤 2只需移动一次就可以完成；步骤 1 与3的操作则完全相同，唯一区别仅在于各杆的作用有所不同这样，原问题被转换为与原问题相同性质的、规模小一 些的新问题（图4）。即 HANOIN,A,B,C 可转化为

23、HANOIN-1,A,C,B 与HANOIN-1,B,A,B 其中HANOI中的参数分别表示需移动 的盘数、起始盘、临时盘与终止盘， 这种转换直至转入的 盘数为0为止，因为这时已无盘可移了。 这就是需要我的递归调用模型。图4 N-1阶汉诺塔 源程序如下 programex11_12; var a,b,cchar; nbyte; procedure hanoinbyte;a,b,cchar; begin if n0 then begin hanoin-1,a,c,b; writeln Move ,a, to ,c; hanoin-1,b,a,c; end; end; begin a A ;b B ;c C ; write N