信息技术竞赛培训教程(编辑修改稿)

信息技术竞赛培训教程(编辑修改稿)内容摘要：

有的人全部出列为止。 设ｎ个人的编号分别为 1， 2，„， n，打印出出列的顺序。 分析：本题我们可以用数组建立标志位等方法求解，但如果用上数据结构中循环链的思想，则更贴切题意，解题效率更高。 ｎ人围成一圈，把一人看成一个结点，ｎ人之间的关系采用链接方式，即每一结点有一个前继结点和一个后继结点，每一个结点有一个 指针指向下一个结点，最后一个结点指针指向第一个结点。 这就是单循环链的数据结构。 当ｍ人出列时，将ｍ结点的前继结点指针指向ｍ结点的后继结点指针，即把ｍ结点驱出循环链。 建立循环链表。 当用数组实现本题链式结构时，数组 a[i]作为 指针 变量来使用， a[i]存放下一个结点的位置。 设立指针 j 指向当前结点，则移动结点过程为 j:=a[j]，当数到 m时， m结点出链，则 a[j]:=a[a[j]]。 当直接用链来实现时，则比较直观，每个结点有两个域：一个数值域，一个指针域，当数到 m 时， m 出链，将 m 结点的前继结点指针指向 其后继结点； 设立指针，指向当前结点，设立计数器，计数数到多少人； 沿链移动指针，每移动一个结点，计数器值加１，当计数器值为ｍ时，则ｍ结点出链。 计数器值置为１； 重复３、直到 n 个结点均出链为止。 源程序一： 用数组实现链式结构 program ex116a。 const n=14。 m=4。 {设有 10 个人 ,报到 4 的人出列 } var a:array[1..n] of integer。 i,j,k,p:integer。 begin for i:=1 to n1 do a[i]:=i+1。 {建立链表 } a[n]:=1。 j:=n。 k:=1。 p:=0。 {第 n 人指向第 1 人 ,并置初始 } repeat j:=a[j]。 k:=k+1。 {报数 ,计数器加 1} if k=m then {数到 m,m人出队 ,计数器置 1} begin write(a[j]:4)。 p:=p+1。 a[j]:=a[a[j]]。 k:=1。 end until p=n。 {直到 n 个人均出队为止 } end. 源程序二： 单链环实现 program ex116b。 type pointer=^node。 node=record val:integer。 link:pointer end。 var ptr,ptb:pointer。 i,j,n,m:integer。 begin readln(n,m)。 new(ptb)。 ptb^.val:=1。 ptr:=ptb。 {申请第 1 个结点 } for i:=2 to n do begin new(ptr^.link)。 ptr:=ptr^.link。 {申请第 2 到 n 结点 } ptr^.val:=i。 end。 ptr^.link:=ptb。 j:=0。 {第 n 结点指针指向第 1 个结点 } repeat i:=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=n1。 {直到 n 个人均出队为止 } writeln(ptb^.val:4) end. 例 一矩形阵列由数字 0 到 9组成 ,数字 1 到 9代表细胞 ,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞 ,求给定矩形阵列的细胞个数。 如 :阵列 0234500067 1034560500 2045600671 0000000089 有 4 个细胞。 算法步骤： 1． 从文件中读入 m*n 矩阵阵列，将其转换为 boolean 矩阵存入 bz数组中； 2． 沿 bz数组矩阵从上到下，从左到右，找到遇到的第一个细胞； 3． 将细胞的位置入队 h，并沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置 bz数组置为 FLASE； 4． 将 h 队的队头出队，沿其上、下、左、右四个方向上的细胞位置入队，入队后的位置 bz数组置为 FLASE； 5． 重复 4，直至 h 队空为止，则此时找出了一个细胞； 6． 重复 2，直至矩阵找不到细胞； 7． 输出找到的细胞数。 program xibao。 const dx:array[1..4] of 1..1=(1,0,1,0)。 dy:array[1..4] of 1..1=(0,1,0,1)。 var int:text。 name,s:string。 pic:array[1..50,1..79] of byte。 bz:array[1..50,1..79] of boolean。 m,n,i,j,num:integer。 h:array[1..4000,1..2] of byte。 procedure doing(p,q:integer)。 var i,t,w,x,y:integer。 begin inc(num)。 bz[p,q]:=false。 t:=1。 w:=1。 h[1,1]:=p。 h[1,2]:=q。 {遇到的第一个细胞入队 } repeat for i:=1 to 4 do{沿细胞的上下左右四个方向搜索细胞 } begin x:=h[t,1]+dx[i]。 y:=h[t,2]+dy[i]。 if (x0) and (x=m) and (y0) and (y=n) and bz[x,y] then begin inc(w)。 h[w,1]:=x。 h[w,2]:=y。 bz[x,y]:=false。 end。 {为细胞的入队 } end。 inc(t)。 {队头指针加 1} until tw。 {直至队空为止 } end。 begin fillchar(bz,sizeof(bz),true)。 num:=0。 write(39。 input file:39。 )。 readln(name)。 assign(int,name)。 reset(int)。 readln(int,m,n)。 for i:=1 to m do begin readln(int,s)。 for j:=1 to n do begin pic[i,j]:=ord(s[j])ord(39。 039。 )。 if pic[i,j]=0 then bz[i,j]:=false。 end。 end。 close(int)。 for i:=1 to m do for j:=1 to n do if bz[i,j] then doing(i,j)。 {在矩阵中寻找细胞 } writeln(39。 NUMBER of cells=39。 ,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，„„，Ｘ n2，Ｘ n1，Ｘ n｝ 当Ｘ n－Ｘ n1 小于一个特定值（误差许可值）时，Ｘ≈Ｘ n1≈Ｘ n，这时可认定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，误差值设定为 ， 则程序可写成： program ex11_7。 const a=。 var x0,x1,X:real。 begin x0:=0。 x1:=1/(x0+2)。 while abs(x1x0)a do begin x0:=x1。 x1:=1/(x0+2)。 end。 x:=x1+1。 {将 X1 的值转为 2 的算术平方根 } writeln(39。 sqrt(2)=39。 ,x)。 end. 程序的输出结果如下： SQRT(2)=+00 开始时，迭代函数的根的近似值设定在 [0,]之间， 由于区间宽度大于给定误差许可值，于是再进行迭代运算，产生下一个区间 [,]； 其宽度仍然大于误差许可值，再产生下一个区间；„„；如此反复，直到区间的宽度小于误差给定值时，则表明在该区间中，任意选择一个数都可以满足根的近似值要求了。 为方便起见，取下该区间的边界置作为近似值。 这就是迭代算法的一般原则的体现了。 二、 .递推 对于一个的序列来说，如果 已知它的通项公式（即表达位置与位置上的数据的关系的公式），那么，要求出数列中某项之值是十分容易的。 但是，在许多情况下，要得到数列的通项公式是很困难的，甚至无法得到。 然而，一个有规律的数列的相邻位置上的数项之间通常存在着一定的关系，我们可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，„„，如此反复，直到找到所需的那一项为止，这样的方法称为递推算法。 递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。 递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。 一般说来，可以将递推算法看成是一种特殊的迭代算法。 例 2 著名的菲波纳葜 (Fibonacci)数列，其第一项为 0，第二项为 1， 从第三项开始，其每一项都是前两项的和。 编程求出该数列第 N 项数据。 分析：按菲波纳葜数列的原则，数列为： 0 1 1 2 3 5 8 13 21 34 55…… 无疑地，寻找其项数位置与项值的关系（即通项公式）是非常困难的。 而根椐该数列的形成规则，其有一个的公式即 Ｕ n＝Ｕ n1＋Ｕ n2 表明了相邻的数据项之间的明显关系。 因此，可以其作为递推公式，以已知项 0 与 1为起点，逐项产生第 3 项、第 4 项、„„，直到取得需要的第 N 项为止。 在其递推算法的语言实现上，可取 J、 K、 P 三个变量，分别表示前二项、前一项与当前项， J、 K分别取初值 0 与 1。 第一次通过递推公式 P=J+K得到第三项，并进行移位，即 J 取 K 值、 K 取 P 值， 为下次递推作准备；„„；如此反复，经过 N2 次的递推， P 就是第 N 项的值（第 1次产生的是 3 项的值）。 源程序如下 : program ex11_8。 var n,i,j,k,p:longint。 begin write(39。 N=39。 )。 readln(n)。 i:=2。 j:=0。 k:=1。 repeat inc(i)。 p:=j+k。 j:=k。 k:=p。 until i=n。 writeln(39。 F(39。 ,n,39。 )=39。 ,p)。 end. 菲波纳葜数列的递推明确地体现了递推算法程序设计的一般原则，即递推公式取得。 例 3 数字三角形。 如下所示为一个数字三角形。 请编一个程序计算从顶到底的某处的一条 路径，使该路径所经过的数字总和最大。 只要求输出总和。 一步可沿左斜线向下或右斜线向下走； 角形行数小于等于 100； 三角形中的数字为 0， 1， „， 99； 测试数据通过键盘逐行输入，如上例数据应以如下所示格式输入： 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 分析：此题解法有多种，从递推的思想出发，可以设想，当从顶层沿某条路径走到第 I 层向第 I+1 层前进时，我们的选择一定是沿其下两条可行路径中最大数字的方向前进，为此，我们可以采用倒推的手法，设 a[i， j]存放从 i， j 出发到达。