信息学奥赛N题详解

第一题（30分）在一个超市的收银处有10位顾客在排队等着付款，他们的编 号依次为1, 2,，10o由于每个顾客所购的商品不同，因此付款时所需的 等待时间也就不一样。假设这10个每个人单独付款所需的时间依次为 74612820513216请编程找出这10个人排队的一种顺序，使得10个人的平均等待时间最少。 说明：平均等待时间是把每个人的等待时间相加最后再除以n得到。假设这n 个人是按照编号1至n的自然顺序排列的，则此时的平均等待时间为： 平均等待时间=输出格式要求：程序的输出共分两行，其中第一行是编程求到的一种排列顺序，即1到n的一 种排列；第二行是这种排列方案下的最少平均等待时间，要求输出的结果精确 到小数点后两位。第二题（30分）利用循环结构编程打印如下的图案。AABCABCDEABCDEFGABCDEFGHIABCDEFGABCDEABC A第三题（40分）用高精度计算S =1! +2! +3! + -+n!的准确值，其中n50。说明：上面求和公式当中的“！ ”表示阶乘，它表示连乘，例如：10! =10*9*8*7*6*5*4*3*2*1编程要求：从键盘上输入一个小于50的正整数n,要求能够输出结果S的准确 值。例如：输入：6输出：S=873第题对于任意输入的一个字符串，求出每一种字符的个数和它在原字符串中 所处的位置。例如：输入字符串Waabcdaweaccd,dcb则输出W1 1表示大写英文字母W,在原字符串中有一个，位置在1； 再如a423 7 10表示小写字母a,在原字符串中有4个，位置 分别在2, 3, 7, 10；编程要求：(1) 原字符串在一行内输入；(2) 输点每个字符E一行，第一个位置为该字符内容，第二个位置为该字 符在原字符串中的个数，以后的为其在原字符串中所处的位置。每个输出项之 间均用一个空格隔开。CLSINPUT a$DIM a(33 TO 126)1 = LEN(a$)FOR i = 1 TO 1x$ = MID$(a$, i, 1)a(ASC(x$) = a(ASC(x$) + 1NEXTiFOR i = 33 TO 126IF a(i) 0 THENPRINT CHR$(i); a(i);f = INSTR(a$, CHR$(i)PRINT f;DOf = INSTR(f + l,a$, CHR$(i)IFf = 0 THEN EXIT DOPRINT f;LOOPPRINTEND IFNEXTiEND第二题对于任意输入的不超过240位长的两个自然数求它们的差。例如：第一行输入被减数为5649第二行输入减数1200第三行输出显示差为4449编程要求：在屏幕的第一行输入被关数，第二行输入减数，第三行输出 这两个自然数的差。DOINPUT a$=; a$INPUT b$=; b$LOOP UNTIL LEN(a$) 0 AND LEN(a$) 0 ANDLEN(b$) v 240la = LEN(a$): lb = LEN(b$)PRINT a$PRINT b$IF lb la OR lb = la AND b$ a$ THENSWAP a$, b$: SWAP la, lb: c$ =END IFDIM a(la + lb), b(la + lb) n = laFOR i = 1 TO na(i) = 0: b(i) = 0NEXTiFOR i = 1 TO laa(i) = VAL(MID$(a$, la + 1 - i, 1)NEXTiFOR i = 1 TO lbb(i) = VAL(MID$(b$, lb + 1 - i, 1)NEXTiFOR i = 1 TO na(i) = a(i) - b(i)IF a(i) v 0 THEN a(i + 1) = a(i + 1) - 1: a(i) = a(i) + 10NEXTiDO WHILE a(n) = 0 AND n 1n = n - 1LOOPIF c$ = THEN PRINTFOR i = n TO 1 STEP-1PRINT USING a(i);NEXTiEND字符排列一、试题键盘输入一个仅由小写字母组成的字符串，输出以该串中任取M个字母的 所有排列及排 列总数。输入数据均不需判错。二、算法分析该题属于计数和枚举类型。若掌握组合数学的计数理论，该题的排列数是 不难求出的。设字符长度为n。若n个小写字母各不相同，即每个字母在字串中出现的 频率为1 ,则任 取m个字母的排列总数为 n!c (n, m)=(n-m)! m!在这种情况下，n不可能超过2 6 ,而试题并未明确规定字串长度。因此, 输入字母中可能出现重复字母，不同位置上的相同字母应看作“本质”不同的元素。那么 如何求在n个不同元素的集合中取m个元素的排列数呢？针对这种允许重复的排列问题，我 们设计一个对 应的母函数设字串中共有P种字母(1WPWN),第1种字母的频率为nl,第2种字母 的频率为n2,第P种字母的频率为np,显然nl+n2+np=n0考虑下面形式的幕级数(l+x+x2+xnl) (l+x+. . . +xn2) (. . .) (l+x+. . . xnp)它的展开式中，xm的系数即为任取M个字母的排列总数。但这只是问题的一半解。试题不仅要求得出排列数，而且还要枚举每个排 列方案。因此，我们不得不改弦易辙，采用回溯法来枚举每个满足条件的排列并累计排列数。 如果搜索流程和约束条件正确，不重复或疏漏方案，同样也能得出与计数理论相同的结论。设tot方案数；lev字符指针，指出当前排列中正在确定其值的元素序号；显然，搜索前tot和tov应初始化为零。另外还应在输入字串的同时统计 出每种字母的频率，即排列中每种字母允许出现的最大次数。在搜索中，若某字母进入排列，其频率应减1 ,表示该字母在以后位置上的出现次数应少一次。若某字母的频率为0,则说明 具有该字母形式的元素已经全部取出，不应该再进入排列了。Procedure search;beginif lev=M 若M个字母的排列产生then begintottot+1; 累计方案数输出第tot个排列；end thenelse beginlevlev+1: 取当前排列的下一个元素for c:- a to z do 顺序搜索第lev个元素的所有可能值if当前字母的频率0then begin该字母频率减1并进入当前排列的第lev个位置；递归调用secrch,取下一个元素；该字母频率加1,恢复递归前的值；end; thenlevlev-1: 回溯，重新取当前排列的前一个元素end;elseend;search由上述回溯法得出的tot,即为正确的排列总数。三、程序分析PROGRAM Pai_lie;USESCrt;VARNum : arraya. . z of integer;输入串中的各小写字母在排列中允许出现的次数Ans : string; 排列方案M, tot, lev : integer; 排列长度、方案总数、字符指针 PROCEDURE Init;vari : integer;str : string; 字串beginwritein(5 Input string : ); 输入字串 readln(str);write ( M=，) ; 输入排列长度readln(M);fillchar (Num, sizeof(Num), 0);for i :=1 to length (str) do 统计串中每个字母的频率 inc (Numstri);tot :=0; lev:=0; 排列数和字符指针初始化Ans:=copy (str, 1, M) ; 第1个排列方案初始化end; initPROCEDURE Search;varc : char;beginif lev=M 若产生M个字母的排列，则累计方案数并输出该方案 then begin inc(tot);writein(tot,) , Ans);end thenelse begininc (lev); 右移字符指针for c:=，a to z do 顺序枚举一个字母if Numc0若某字母还允许使用,则允许使用的次数减1,字母移入排列的第lev个位置then begindec (Numc);Anslev:=c;Search; 递归搜索排列的第lev+1个位置的字母inc (Numc) : 恢复该字母递归前的可使用次数end; thendec (lev); 回溯，即左移一位字符指针end; elseend; searchBEGINInit; 初始化Search; 计算并输出输入串中任取M个字母的所有排列writeln(5 tot=，, tot) : 输出排列总数END. main高精度实数减法一、试题编程实现两个高精度实数减法，两数分别由键盘输入，均不超过240位。输入数据均不需判错。二、算法分析因计算机只能表示有限位的实数，所以在计算机上的实数运算要注意值的 大小（范围）和值的精度。TRUBO. PASCAL中的REAL类型只能提供1 0 38的范围和1 1位 十进制数字的精度。即一个实数有1 1位有效数字，最大约1 0 38,非零绝对值最小数约1 0_39 o而试题要求有效数字的位数为2 4 0,对于这种数位要求，任何高级语言的实数类型 都望尘莫及，况且还要实现两个实数的高精度运算。由于计算机所能表示的实数的有限位数 与之相差甚远，因此，采用实数运算的计算误差是在所难免的。采用字符串类型STRING表示实数是一个比较合适的作法。如果一个字符 对应一位数字，则STRING的字符长度为2 5 6 ,自然满足试题2 4 0位有效数位的要求。而 且每个数符可以通过ORD函数转换为对应位上的整数进行运算。但是要利用字串进行高精度实 数运算，必须解决如下几个问题。为了帮助读者理解，我们围绕一个简单和示例展开讨论：cl=l. 23 cl对应的字串为Nl= 1. 23；c2=12. 024 c2 结应的字串为 N2二12. 024；求c3=cl-c2结应的字串N31、数位对齐由于实数运算和比较大小是逐位进行的，因此在运算前有必要先解决数位 对齐的问题。我们以小数点为界，从右向左计算N1和N2中整数部分的子串长度，由左而右计算N 1和N2中小数部分的子串长度。若两个整数部分子串的长度不等，则在较短的那个子串的左端添0,使之对齐；若两个小数部分子串的长度不等，则在较短的那个子 串的右端添0，使之对齐。对齐后的两个字串的长度相等。N1=01. 230；N2=12. 024；用作分界整数部分和小数部分的小数点是非数字符，不参与运算，因此在 运算前将之去 除，但需记下小数点的位置L,以便在求出两数之差后，还原该位置的小数点。Nl=01230； N2=120245；L=3；2、比较大小 根据减法的运算法则，两数相减的结果应为 r 0 cl=c2cl c2=-| cl-c2 clc21- -(c2-cl) clN2i,则求 N3； 若 Nlip2若N1和N2的小数位数不等,则在小数位数较短的串的尾部添零，使两串的小 数部分 对齐 then begin add:=pl:for i:=1 to pl-p2 do N2:=N2+O;end then else begin add:=p2; for i:=1 to p2-pl do N1:=N1+O; end; elseif length (Nl) N2i 若 N1N2,则计算和输出 N1-N21. 3. 1 then Subelse begin 若 N1WN2,则计算和输出-(N2-N1)N3:=N1; N1:=N2; N2:=N3;writeSub;end; else end; else end; main第三层最后求精1. 3. 1sub的过程说明PROCEDURE Sub;var i,j,k : integer;beginN4 0: =N1 0 ; 结果串的长度初始化for i :=len down to 1 do 按低位f高位的顺序逐位相减 if Nli=N2i 若被减数的i位3减数的i位,够减 then N4i :=chr (ord(5 05) +ord(N1 i)-ord(N2 i) else begin 否则向被减数的高位借位N4i :=chr (ord(5 05) +10+ord(N1 i)-ord(N2 i);j：=i-l；while N1j=，05 do beginNlj:= 95 ;dec(j);end; whileNlj:=chr(ord(Nl;end; elseN4:=copy(N4, 1, len-add)+5. +copy(N4, len-add+1, add);在结果串中移入小数点while N4length(N4)=, 05 do delete (N4, length(N4), 1);截去结果串尾部的无用零while (N4l=, 05) and (N42.)do delete (N4, 1, 1);截去结果串头部的无用零if N4length(N4)=,. 5 then delete (N4, length(N4), 1);若结果串为整数，则截去小数点writein (N4) : 输出 Nl-N2 的差end; sub实数数列一、试题一个实数数列共有N项，已知a i= ( a i-1- a i+1) / 2 + d, (liN) (N60)键盘输入N, d, a 1, a n, m,输出am。输入数据均不需判错。二、算法分析该题的数学味颇浓。解题前需耐下心来，对公式Ai=(Ai-l-Ai+l)/2+d (li N) (n0 do begin 逐一删去 S 个数符i:=l;while (i=Ni+l)1) and (Nl=,05) do delete(N, 1, 1);删去串头的无用零writein(N) : 输出剩下的数码END. main方阵集合一、试题一个NXN的方阵由数字0、1、2组成。定义由该方阵中若干元素组成的 集合P,满足： P中元素的值要么全部为1,要么全部为2； 假设P全由值为1的元素组成，若方阵中任一元素Y,其值也为1,并 且Y与P中的某一元素存在一条全由值为1的元素组成的四连通路径，则Y必定也属于P；同样，假设P全由值为2的元素组成，若方阵中任一元素Y,其值也为2, 并且Y与P中的某一元素存在一条全由值为2的元素组成的四连通路径，则Y必定也属于P； 对于任一元素X,若属于P,则其在原方阵中上下左右四个方向上的相 邻元素的值只能为1或2,或者超出方阵的边界，但不可能为0。编程输出原始方阵中这样的集合总数和每个集合所含元素的个数。原始方阵由文本文件输入，文件第一行是一个数字N,表示方阵的大小， 其下N行为该方阵，同一行中各数字以空格分隔。NN then begin y:=1; inc(x); end;if xN then exit:until (Takenx, y=0) and (Mapx, y0):设集合存在标志，(X,Y)被检验，集合元素个数为1right:=true: Takenx, y:=1; size:=l:repeat 重复，直至四连通路径无法延伸为止more:=false; 四连通路径延伸标志初始化搜索方阵中每个被检验位置for i:=1 to N do for j:=1 to N doif Takeni, j=l then begin 若(i, j)被检验，则inc(Takeni, j) : 累计(i, j)的检验次数for k:=l to 4 do begin按方向方向4的顺序搜索(i, j)的相邻格 ii:=i+wayk, 1: jj:=j+wayk, 2:求(i, j)在K方向上的相邻格(ii, jj)if Mapii, jj=O 若(ii, jj)=O,则集合不存在 then right:=falseelse if (Takenii, jj=0) and (Mapii, jj=Mapi, j) 否则，若(ii, jj)未检验且(i, j)与(ii, jj)的数字相同 then begin则置(ii, jj)检验标志，集合元素增1,置四连通路径延伸标志 Takenii, jj:=1: inc (size);more:=true;end; then end; for end; then until not more: if right then begin 若集合存在，则输出集合的元素个数 inc(tot);writeln(tot,5) 5, size):end;until true二false; end; main BEGIN Init; 输入方阵 Main; 计算和输出每个满足条件的集合所含元素的个数 writeln(5 tot = , tot) ; 输出集合总数 END. main132、求精1. 2init的过程说明输入被减数N1和减数N2。通过化整添零，使两串对齐。PROCEDURE Init;var i, p, pl, p2 : integer;PlN1中小数点的位置:P2N2中小数点的位置;i, p辅助变量 beginclrscr; 清屏writein(2 * * 5 Input first number :输入被减数串readln(Nl);writein(5 Input second number : ); 输入减数串