信息技术竞赛培训教程

1、信息技术竞赛培训教程 目录 第二部分 数据结构 （一）栈（二）队列（三）链表（四）迭代与递推（五）递归（六）搜索与回溯（七）树与二叉树（八）排序算法（九）查找算法（十）图论基础知识l l         广度优先搜索l l         广度优先搜索第二部分 算法和数据结构 （一）栈 说到学习和掌握数据结构，很容易让人想到的就是其最本的数据结构模式：栈、队这一讲，我们就来谈谈“栈”。“

2、栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么，“栈”为何物呢？栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取。堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。一个栈可以用定长为的数组来表示，用一个栈指针TOP指向栈顶。若TOP0，表示栈空，TOP=N时栈满。进栈时TOP加。退栈时TOP减。当TOP<0时为下溢。栈指针在运

3、算中永远指向栈顶。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;

4、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;对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可用来作为控制程序转移的判断标志，是十分有用的。对

5、于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。堆栈的数组模拟十进制数N和其它d进制数的转换是实现计算的基本问题，解决方法很多，下面给出一中算法原理：N=(N div d)×dN mod d （其中 div 为整除运算，mod为求余运算）。例如：(1348)10(2504)8运算过程如下：NN div 8N mod 8134816841682102125202NN div 8N mod 89413            1、 1、&

6、#160; 填空：(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; rep

7、eat 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的出站序列。  栈的用途极为广泛，在源程序编译中表达式的计算、过程的嵌套调用和递归调用等都要用到栈，下面以表达式计算为例子加以说明。源程序编译中，若要把一

8、个含有表达式的赋值语句翻译成正确求值的机器语言，首先应正确地解释表达式。例如，对赋值语句X:48×23; (式 11.1)其正确的计算结果应该是，但若在编译程序中简单地按自左向右扫描的原则进行计算，则为：X12×2324321这结果显然是错误的。因此，为了使编译程序能够正确地求值，必须事先规定求值的顺序和规则。通常采用运算符优先数法。一般表达式中会遇到操作数、运算符和语句结束符等，以算术运算符为例，对每种运算赋予一个优先数，如：运算符：×÷优先数：（语句结束符“；”的优先数为零）在运算过程中，优先数高的运算符应先进行运算（但遇到括号时，应另作处理）。按这

9、样的规定，对式（11.1）自左向右进行运算时，其计算顺序就被唯一地确定下来了。计算顺序确定后，在对表达式进行编译时，一般设立两个栈，一个称为运算符栈（OPS），另一个称为操作数栈（OVS），以便分别存放表达式中的运算符和操作数。编译程序自左向右扫描表达式直至语句结束，其处理原则是：凡遇到操作数，一律进入操作数栈；当遇到运算符时，则将运算符的优先数与运算符栈中的栈顶元素的优先数相比较；若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在操作数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入操作数栈，然后继续比较该运算符与栈顶元素的优先数。例如式（11.1）中，当扫描到“”和

10、“×”时都要将运算符入栈。接着扫描到“”号， 其优先数小于乘号所以乘号退栈，并执行×，将结果再存入操作数栈。再将“”号的优先数与运算符栈的栈顶元素“”号的优先数相比较，两者相等，所以再将加号退栈，进行，结果为，再入栈，接着，由于运算栈已空，所以减号入栈。当扫描到“”时，操作数入栈。当扫描到“；”时，其优先数最低， 所以减号退栈并执行，结果为并入栈。因已扫描到语句结束符，所以表达式的求值结束，结果为。例题模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。分析:建立两个栈，

11、一个是操作数栈（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

12、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 '+',

13、'-') 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

14、si = '(' do 左括号处理 begin push; inc(i); end; j := i; repeat 取数入操作数栈 inc(i); until (si < '0') or (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

15、; 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、读入一英文句子，单词之间用空格或逗号隔开，统计其中单词个数，并输出各个字母出现的频率。(句子末尾不一定用"."结束) 如果含有其他的字符，则只要求输出错误信息及错误类型。含有大

16、写字母 错误类型 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<=26)。这个N决定了转换关系。 例如当N=1，输入的句子为ABCXYZ时，则其转换码为ABCXYZ不变。当N=2时，其转换码为BCDYZA，其它的非字母字符不变。为使编码较于破译，将转换码的信息自左而右两两交换，若最后仅剩单个字符

17、则不换。然后，将一开始表示转换关系的N根据ascii表序号化成大写字母放在最前面。如：abcABCxyzXYZ-/,1. n=3cdeCDEzabZAB-/,1. 根据N的值转换dcCeEDazZbBA/-1,. 两两交换CdcCeEDazZbBA/-1,. 最后编码解码过程为编码的逆过程。 4、计算器的改良【第三届全国青少年信息学奥林匹克分区联赛复赛试题普及组题一】问题描述NCL是一家专门从事计算器改良与升级的实验室。最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交组了一个刚进入的新手ZL先生。为了很好的完成这个任务

18、，ZL先生首先研究了一些一元一次方程的实例：4+3X=86a-5+1=2-2-5+12Y=0 ZL先生被告知：在计算器上键入的一个一元一次方程中，只包含整数、小写字母入+、-、=这三个数学符号（当然，“-”既可当减号也可当负号）。方程中并没有括号，也没有除号，方程中的字母表示末知数。问题求解编写程序，解输入的一元一次方程，将解方程的结果（精确到小数点后三位）输出至屏幕。键入的一元一次方程均合法，且有唯一的实数解。样例输入：6a-5+1=2-2a输出：a=0.750 （二）队列 在（一）中，我们谈了"栈"的应用，下面我们谈谈队列，队列是限定在一端进行插入，

19、另一端进行删除和特殊线性表。正象排列买东西，排在前面的人买完东西后离开队伍（删除），而后来的人总是排在队伍未尾（插入）。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。由于总是先入队的元素先出队（先排队的人先买完东西），这种表也称为先进先表（FIFO）表。队列可以用数组Q1来存储，数组的上界即是队列所容许的最大容量。在队列的运算中需设两个指针：head：队头指针，指向实际队头元素的前一个位置tall：队尾指针，指向实际队尾元素所在的位置一般情况下，两个指针的初值设为，这时队列为空，没有

20、元素。图1 ( a)画出了一个由个元素构成的队列，数组定义Q110。Q(i) i=3,4,5,6,7,8头指针head2，尾指针tail8。队列中拥有的元素个数为:L=tail-head现要让排头的元素出队，则需将头指针加。即head=head+1这时头指针向上移动一个位置，指向Q(3)，表示Q(3)已出队。见图1 (b)。如果想让一个新元素入队，则需尾指针向上移动一个位置。即tail=tail+1这时Q(9)入队，见图1 (c)。当队尾已经处理在最上面时，即tail=10，见图1 (d)，如果还要执行入队操作，则要发生"上溢"，但实际上队列中还有三个空位置，所以这种溢出称

21、为"假溢出"。克服假溢出的方法有两种。一种是将队列中的所有元素均向低地址区移动，显然这种方法是很浪费时间的；另一种方法是将数组存储区看成是一个首尾相接的环形区域。当存放到n地址后，下一个地址就"翻转"为。在结构上采用这种技巧来存储的队列称为循环队列，见图2循环队的入队算法如下：1、tail=tail+1；2、若tail=n+1，则tail=1；3、若head=tail尾指针与头指针重合了，表示元素已装满队列， 则作上溢出错处理；4、否则，Q(tail)=X，结束（X为新入出元素）。队列和栈一样，有着非常广泛的应用。 考虑一个分时系统，如果一台计算机联有四

22、个终端，即允许四个用户同时使用这一台计算机。那么， 计算机系统必须设立一个队列， 用以管理各终端用户使用CPU的请求。当某个用户要求使用CPU时，相应的终端代号就入队（插入队尾），而队头的终端用户则是CPU当前服务的对象。我们考虑最简单的情况， 对于当前用户（队头），系统每次分配一个为时间片的时间间隔，在一个时间片内，如果当前用户的作业没有结束，则该终端用户的代号出队后重新入队，插入队尾，等待下一次CPU服务。如果某个用户的作业运行结束，则先退出，出队后不再入队， 整个运行过程就是各终端代号不断地入队、出队，CPU 轮流地为（）个终端用户服务。由于计算机的运行速度极快，所以，对于每个终端用户来

23、说，似乎计算机是单独在为其服务。 和线性表一样，栈和队可以采用链表存储结构，当要实现多个栈共享内存或多个队共享内存时，选择链式分配结构则更为合适。例1 求两个一元多项式的和。输入多项式方式为，多项式项数，每项系数和指数，按指数从大到小的顺序输入。分析多项式的算术运算是表处理的一个经典问题。建立两张表、分别存放两个多项式的内容，建立表指针ta、tb，指向表和表的元素，根据表、元素中的指数大小合并输出。、比较ta、tb指向元素的大小，若ta的指数大于tb的指数，输出ta元素，改变指针ta；2、若ta的指数小于tb的指数，输出tb元素，改变指针tb；3、若ta的指数等于tb的指数，ta、tb元素的系

24、数相加输出，同时改变指针ta和tb；4、若有一表取空，则输出另一表剩余的内容。源程序一：多项式相加的顺序表实现program ex11_5a;type node = record zhi, xi: integer; end; ar = array1.1000 of node;var a, b: ar; ta, tb, n: integer;begin write('One : '); readln(n); 输入第一个多项式的系数和指数 for ta := n downto 1 do readln(ata.xi, ata.zhi); ta := n; write('Two

25、 : '); readln(n); 输入第二个多项式的系数和指数 for tb := n downto 1 do readln(btb.xi, btb.zhi); tb := n; write('Result is '); while (ta > 0) and (tb > 0) do 当两个表均不空时 begin 比较两表指针指向的项指数,输出指数小的项系数和指数, 同时改变该表指针 if ata.zhi > btb.zhi then begin if ata.xi < 0 then write(#8' '#8); write(a

26、ta.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 the

27、n write(#8' '#8); write(btb.xi + ata.xi, 'x', btb.zhi, '+'); end; dec(ta); dec(tb); end;end;while ta > 0 do 若有一表空,则输出另一表的剩余项 begin if ata.xi < 0 then write(#8' '#8); write(ata.xi, 'x', ata.zhi, '+'); dec(ta); end;while tb > 0 do begin if btb.x

28、i < 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);

29、 建立多项式系数、指数链表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('Resul

30、t 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, &

31、#39;+'); 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.x

32、i, 'x', a.zhi, '+'); a := a.nxt; end;while b <> nil do begin if b.xi < 0 then write(#8' '#8); write(b.xi, 'x', b.zhi, '+'); b := b.nxt; end;writeln(#8' '#8);readln;end.3.队列的应用：例：设有一个表，记为L=(a1,a2,a3,.,an)，其中L表名a1,a2,a3,.,an表中元素。当ai为数值时表示元素，当ai为

33、大写字母时，表示另一个表，但不能循环定义。例如，下列的定义是合法的（约定L是第一个表的表名）：L=(3.4,3,4,K,8,0,8)K=(15,5,8,P,9,4)P=(4,7,8,9)程序要求：当全部表给出后，示出所有元素的最大元素。思路：(1)可以建立两种队列，一种队列是存放数值的数值队列Q1，并有Q1A到Q1Z共26条数值队列，另一种队列Q2存放字母，表示将要向该字母所对应的数值队列输入数值的事件队列。(2)根据题目要求，事件队列Q2中应先放入字母L，表示首先输入L数值队列的数据。(3)从事件队列Q2中取出一个字母，并招待该字母对应的数值队列的数值输入，如果输入的数据中包含字母，则把字母

34、放入事件队列中，并记录输入的数值中的最大值。(4)重复(3)步骤，直到事件队列中为空。  （三）链表 在（二）中，我们介绍了"队"及"队"的应用，在这一讲中，我们将再通过两道例题，进一步的了解的学习"队"的灵活使用。例、设有个人依次围成一圈，从第个人开始报数，数到第个人出列，然后从出列的下一个人开始报数，数到第个人又出列，如此反复到所有的人全部出列为止。设个人的编号分别为1，2，n，打印出出列的顺序。分析：本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高

35、。人围成一圈，把一人看成一个结点，人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个指针指向下一个结点，最后一个结点指针指向第一个结点。这就是单循环链的数据结构。当人出列时，将结点的前继结点指针指向结点的后继结点指针，即把结点驱出循环链。1、 1、 建立循环链表。当用数组实现本题链式结构时，数组ai作为"指针"变量来使用，ai存放下一个结点的位置。设立指针j指向当前结点，则移动结点过程为j:=aj，当数到m时，m结点出链，则aj:=aaj。 当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到m时，m出链，将m结点

36、的前继结点指针指向其后继结点；2、设立指针，指向当前结点，设立计数器，计数数到多少人；3、沿链移动指针，每移动一个结点，计数器值加，当计数器值为时，则结点出链。计数器值置为；4、重复、直到n个结点均出链为止。源程序一：用数组实现链式结构program ex11-6a;const n=14;m=4;设有10个人,报到4的人出列var a:array1.n of integer;i,j,k,p:integer;beginfor i:=1 to n-1 do ai:=i+1;建立链表an:=1;j:=n;k:=1;p:=0;第n人指向第1人,并置初始repeatj:=aj;k:=k+1;报数,计数器

37、加1if k=m then 数到m,m人出队,计数器置1beginwrite(aj:4);p:=p+1;aj:=aaj;k:=1;enduntil p=n;直到n个人均出队为止end.源程序二：单链环实现program ex11-6b;type pointer=node;node=recordval:integer;link:pointerend;var ptr,ptb:pointer;i,j,n,m:integer;beginreadln(n,m);new(ptb);ptb.val:=1;ptr:=ptb;申请第1个结点for i:=2 to n do beginnew(ptr.link);

38、ptr:=ptr.link; 申请第2到n结点ptr.val:=i;end;ptr.link:=ptb;j:=0;第n结点指针指向第1个结点repeati:=1;repeat 报数,报到m人出列ptr:=ptb;ptb:=ptb.link;i:=i+1;until i=m;write(ptb.val:2);ptb:=ptb.link;ptr.link:=ptb;j:=j+1;将m结点驱出链表until j=n-1;直到n个人均出队为止writeln(ptb.val:4)end.例3、 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定

39、矩形阵列的细胞个数。如:阵列 0234500067103456050020456006710000000089有4个细胞。算法步骤：1 从文件中读入m*n矩阵阵列，将其转换为boolean矩阵存入bz数组中；2 沿bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞；3 将细胞的位置入队h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；4 将h队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置bz数组置为FLASE；5 重复4，直至h队空为止，则此时找出了一个细胞；6 重复2，直至矩阵找不到细胞；7 输出找到的细胞数。program xi

40、bao;const dx:array1.4 of -1.1=(-1,0,1,0);dy:array1.4 of -1.1=(0,1,0,-1);var int:text;name,s:string;pic:array1.50,1.79 of byte;bz:array1.50,1.79 of boolean;m,n,i,j,num:integer;h:array1.4000,1.2 of byte;procedure doing(p,q:integer);var i,t,w,x,y:integer;begininc(num);bzp,q:=false;t:=1;w:=1;h1,1:=p;h1,

41、2:=q;遇到的第一个细胞入队repeatfor i:=1 to 4 do沿细胞的上下左右四个方向搜索细胞beginx:=ht,1+dxi;y:=ht,2+dyi;if (x>0) and (x<=m) and (y>0) and (y<=n) and bzx,ythen begin inc(w);hw,1:=x;hw,2:=y;bzx,y:=false;end;为细胞的入队end;inc(t);队头指针加1until t>w;直至队空为止end;beginfillchar(bz,sizeof(bz),true);num:=0;write('input f

42、ile:');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 cel

43、ls=',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，

44、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 的算术

45、平方根的近似值就可以转化为求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.41421

46、35516E+00开始时，迭代函数的根的近似值设定在0,0.5之间， 由于区间宽度大于给定误差许可值，于是再进行迭代运算，产生下一个区间0.4,0.5； 其宽度仍然大于误差许可值，再产生下一个区间；如此反复，直到区间的宽度小于误差给定值时，则表明在该区间中，任意选择一个数都可以满足根的近似值要求了。为方便起见，取下该区间的边界置作为近似值。这就是迭代算法的一般原则的体现了。二、.递推对于一个的序列来说，如果已知它的通项公式（即表达位置与位置上的数据的关系的公式），那么，要求出数列中某项之值是十分容易的。但是，在许多情况下，要得到数列的通项公式是很困难的，甚至无法得到。然而，一个有规律的数列的相

47、邻位置上的数项之间通常存在着一定的关系，我们可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，如此反复，直到找到所需的那一项为止，这样的方法称为递推算法。递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。例2 著名的菲波纳葜(Fibonacci)数列，其第一项为0，第二项为1， 从第三项开始，其每一项都是前两项的和。编程求出该数列第N项数据。分析：按菲波纳葜数列的原则，数列为：0 1 1 2 3 5 8 13 21 34 55无疑地，寻找其项

48、数位置与项值的关系（即通项公式）是非常困难的。而根椐该数列的形成规则，其有一个的公式即"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,

49、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

50、； 测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入：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;begin

51、read(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. （五）递归 在（四）中，我们了解了迭代与递推。与迭代、递推相对应的算法为递归，本趣谈数据结构，我们就来谈一谈递归算法。递归算法作为计算机程序设计中的一种重要的算法，是较难理解的算法之一。简单地说，递归就是编写这样的

52、一个特殊的过程，该过程体中有一个语句用于调用过程自身（称为递归调用）。递归过程由于实现了自我的嵌套执行，使这种过程的执行变得复杂起来，其执行的流程可以用图1所示。 图1递归过程的执行流程从图1可以看出，递归过程的执行总是一个过程体未执行完， 就带着本次执行的结果又进入另一轮过程体的执行，如此反复，不断深入，直到某次过程的执行遇到终止递归调用的条件成立时，则不再深入，而执行本次的过程体余下的部分，然后又返回到上一次调用的过程体中，执行其余下的部分，如此反复，直到回到起始位置上，才最终结束整个递归过程的执行，得到相应的执行结果。递归过程的程序设计的核心就是参照这种执行流程，设计出一种适合"

53、;逐步深入，而后又逐步返回"的递归调用模型，以解决实际问题。利用递归调用程序设计技术可以解决很复杂但规律性很强的问题，并且可以使程序变得十分简短。例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(

54、n-1);t:=t*n;end;end;beginwrite('N=');readln(n);find(n);writeln('N!=',t:1:0);end.在过程find中，当N>1时，又调用过程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-