当前位置:首页 >> 学科竞赛 >>

基础题


基础题 串运算

基础题
有些基础题虽然直接给出了计算公式 或算法十分明显(例如统计数和), 但是,如果变量的数据类型选错了, 或者不会文件操作,同样会做错题, 导致意外的失误。因此作题必须强调 两基: 基础知识 基本基能

基础题主要考核
1.课内的基础知识 2.分析和解决简单问题的能力 3.编程的基本能力

/>
【问题描述】津津上初中了。妈妈认为津津应该更加用功学习, 所以津津除了上学之外,还要参加妈妈为她报名的各科复习班。 另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如 果一天上课超过八个小时就会不高兴,而且上得越久就会越不 高兴。假设津津不会因为其它事不高兴,并且她的不高兴不会 持续到第二天。请你帮忙检查一下津津下周的日程安排,看看 下周她会不会不高兴;如果会的话,哪天最不高兴。 【输入文件】输入文件unhappy.in包括七行数据,分别表示周一到 周日的日程安排。每行包括两个小于10的非负整数,用空格隔 开,分别表示津津在学校上课的时间和妈妈安排她上课的时间。 【输出文件】输出文件unhappy.out包括一行,这一行只包含一个数 字。如果不会不高兴则输出0,如果会则输出最不高兴的是周几 (用1, 2, 3, 4, 5, 6, 7分别表示周一,周二,周三,周四,周五, 周六,周日)。如果有两天或两天以上不高兴的程度相当,则 输出时间最靠前的一天。 【数据说明】所有数据时限均为1秒。

不高兴的津津

设津津在校上课的时间序列为a,妈妈安排上课的 时间序列为b,津津的学习时间序列为c,其中星 期i津津在校上课的时间为a[i],妈妈安排上课的 时间为b[i],两者之和即为津津在星期i的学习时 间c[i]=a[i]+b[i]。 显然,若每天的学习时间不超过8小时,则津津 整个一星期都高兴;若出现c[i]>8,则说明星期i 是津津不高兴的一天;在津津不高兴的所有日子 里,学习时间为max= 的一天,是津津 最不高兴的。

算法分析

for i:=1 to 7 do{读入津津每天在校上课的时间和妈妈安 排上课的时间,并计算该天学习时间} begin readln(a[i],b[i]);c[i]:=a[i]+b[i];end;{for} max:=0; maxi:=0;{计算上课时间最多的日期maxi 和该天 的学习时间max } for i:=1 to 7 do if c[i]>max then begin max:=c[i];maxi:=i;end;{then} if max<=8{若每天上课的最多时间不超过8小时,则津 津不会不高兴;否则上课最多的那天是津津最不高兴 的日子} then writeln('0') else writeln(maxi);

津津的储蓄计划
【问题描述】津津的零花钱一直都是自己管理。每个月的月初妈妈给津津300元钱,津津 会预算这个月的花销,并且总能做到实际花销和预算的相同。 为了让津津学习如何储蓄,妈妈提出,津津可以随时把整百的钱存在她那里,到了 年末她会加上20%还给津津。因此津津制定了一个储蓄计划:每个月的月初,在得到 妈妈给的零花钱后,如果她预计到这个月的月末手中还会有多于100元或恰好100元, 她就会把整百的钱存在妈妈那里,剩余的钱留在自己手中。 例如11月初津津手中还有83元,妈妈给了津津300元。津津预计11月的花销是180元, 那么她就会在妈妈那里存200元,自己留下183元。到了11月月末,津津手中会剩下3元 钱。 津津发现这个储蓄计划的主要风险是,存在妈妈那里的钱在年末之前不能取出。有 可能在某个月的月初,津津手中的钱加上这个月妈妈给的钱,不够这个月的原定预算。 如果出现这种情况,津津将不得不在这个月省吃俭用,压缩预算。 现在请你根据2004年1月到12月每个月津津的预算,判断会不会出现这种情况。如果 不会,计算到2004年年末,妈妈将津津平常存的钱加上20%还给津津之后,津津手中会 有多少钱。 【输入文件】输入文件save.in包括12行数据,每行包含一个小于350的非负整数,分别表示 1月到12月津津的预算。 【输出文件】输出文件save.out包括一行,这一行只包含一个整数。如果储蓄计划实施过程 中出现某个月钱不够用的情况,输出-X,X表示出现这种情况的第一个月;否则输出 到2004年年末津津手中会有多少钱。

算法分析

这道题属于一道基础题,出题的目的,主要是为了考核 同学能不能应用程序设计语言的基本知识(一维数组, 复合、循环、选择三种控制结构)和数学推理的一般方 法,编程解决简单问题。设 var i,total,p:integer; {total为当前剩余的钱;p为百元为单位的 储蓄数; a:array[1..12] of integer;{每个月的预算,其中a[i]为第i个月 的预算} 由于每个月的月初妈妈给津津300元钱,因此津津第i个月 剩余的钱total=total+(300-a[i])。若total<0,则说明第i 个月的钱不够用;否则应该储蓄(total div) 100 个100元, 这样到了月底,津津剩余的钱实际为total=total mod 100。 按照上述方法递推至12月后,储蓄在妈妈那儿有p个100 元,津津剩余的钱为total。由于年末妈妈会加上20%还 给津津,因此津津手中的钱实际为p*120+total。

for i:=1 to 12 do readln(a[i]);{读入每个月的预算} for i:=1 to 12 do begin inc(total,300-a[i]);{计算第i个月剩余的钱} if total<0 {若第i个月的钱不够用,则输出预算失败信息 并退出} then begin write('-',i);halt;end;{then} if total>100{若剩余的钱够储蓄,则以百元为单位累计 储蓄数,并计算剩余的钱} then begin inc(p,total div 100);total:=total mod 100; end; {then} end;{for} writeln(p*120+total);{输出年末手中的钱}

TV-station
? 在一维空间轴上,存在N个整点X1~XN,每个点上 有一定数量的居民。要求在该轴上建立一个TVstation,使得所有人到达TV-station的距离和 尽可能小。数据量:0 < N < 15000,0 < X < 50000 ? 输入: ? n ? X1~XN ? 输出 ? TV-station的x坐标

计算中位数
? 易证TV-station一定设在城市中,并且一定 在最中间一个人的所在城市。 ? 这题的城市坐标为整数且上限才50000,可 以用计数排序(hash sort),枚举1~50000, 即可找到人数的中点。 ? 设a[j]为坐标值为j的坐标个数;tot为坐标 总数。目标是找出第(tot+1)div 2个坐标。 ?

read(n); fillchar(a,sizeof(a),0); tot:=0; for i:=1 to n do begin read(j,k);{输入第i个坐标的值j和坐标数k} inc(a[j],k); inc(tot,k) {累计坐标数} end; temp:=(tot+1) div 2;{计算中位数} s:=0; for i:=0 to 50000 do{由左而右枚举坐标} begin inc(s,a[i]);{累计坐标数} if s>=temp{若为中位数,则输出坐标} then begin writeln(i,'.00000'); halt end end;

在基础题中需注意的问题
? 语言规范和编程技术:例如
1. 数据类型与问题规模对应; 2. 文件操作; 3. 甄别和处理不同类型的数据。 4. 区别read和readln、write和writeln

等; ? 如果问题规模较大,则需要优化算法

级数求和
已知:Sn=1+1/2+1/3+….+1/n。显然当n.非常大的时 候,Sn可大于任何一个整数K。现给出一个整数K (1≤K≤15),要求计算出一个最小的n,使得Sn>K。 输入 键盘输入 k
输出 屏幕输出

n

输入输出样例 输入:1 输出:2

算法分析
该题考核选手的并不是编程能力,而是选择变量类型的能力。 由于该数列是递减的,而k的上限为15,因此项数很大,即便 是 longint 也容纳不下。但未必非高精度运算不可。只要启动 浮点数运算({$n+}),将项数设为extended类型,便可以得 出正确解。 {$n+} {启动浮点数运算} var s,b,k:extended;{数列的和、项数、最接近sn(大于sn)的整数值} extended外的其它类型,则会失分! begin s←0; b←0; {数列的和、项数初始化} readln(k); {读最接近sn(大于sn)的整数值k} while s<=k do{若目前数列的和小于k,则项数b+1,计算sb} begin b←b+1;s←s+1/b; end;{while} 输出项数round(b); end.{main}

关键是b的类型。如果设为string, 则增加了编程难度;如果设为除

乒乓球
【问题背景】国际乒联现在主席沙拉拉自从上任以来就立志于推 行一系列改革,以推动乒乓球运动在全球的普及。其中11分制 改革引起了很大的争议,有一部分球员因为无法适应新规则只 能选择退役。华华就是其中一位,他退役之后走上了乒乓球研 究工作,意图弄明白11分制和21分制对选手的不同影响。在开 展他的研究之前,他首先需要对他多年比赛的统计数据进行一 些分析,所以需要你的帮忙。 【问题描述】华华通过以下方式进行分析,首先将比赛每个球的 胜负列成一张表,然后分别计算在11分制和21分制下,双方的 比赛结果(截至记录末尾)。 比如现在有这么一份记录,(其中W表示华华获得一分,L表示华 华对手获得一分):

WWWWWWWWWWWWWWWWWWWWWWLW 在11分制下,此时比赛的结果是华华第一局11比0获胜,第二局 11比0获胜,正在进行第三局,当前比分1比1。而在21分制下, 此时比赛结果是华华第一局21比0获胜,正在进行第二局,比分 2比1。如果一局比赛刚开始,则此时比分为0比0。 你的程序就是要对于一系列比赛信息的输入(WL形式),输出 正确的结果。 【输入格式】每个输入文件包含若干行字符串(每行至多20个 字母),字符串有大写的 W、L和E组成。其中E表示比赛信息结 束,程序应该忽略E之后的所有内容。 【输出格式】输出由两部分组成,每部分有若干行,每一行对 应一局比赛的比分(按比赛信息输入顺序)。其中第一部分是 11分制下的结果,第二部分是21分制下的结果,两部分之间由 一个空行分隔。

算法分析
首先,对当前输入行计算11分制下每一局比赛的比分。设 a为当前局华华的得分,每输入一个‘W’,a+1;b为当前局对 方的得分,每输入一个‘L’,b+1。若输入‘E’或者华华的得 分 a 或 者 对 方 得 分 b 达 到 11 分 且 双 方 的 分 数 差 值 大 于 1 (((a≥11) or(b≥11))and (abs(a-b)>1)),则输出当前局 的比分 a : b 。请注意,如果输入的字符为‘ E’ ,则标志比赛 结束,11分制计算完毕;否则,继续读下一个字符,计算新 一局的比分。然后,对当前输入行计算21分制下每一局比赛 的比分。计算方法基本如上。有所不同的是,若华华得分a或 者对方得分 b 达到 21 分且双方的分数差值大于 1 ( ((a≥21) or(b≥21))and (abs(a-b)>1) ),则输出当前局的比分 a : b 。 按照上述方法对每一输入行计算 11 分制和21 分制的比赛结 果,直至文件读完(eof(input))为止。

assign(input,inp); reset(input);{输入文件读准备} assign(output,out);rewrite(output);{输出文件写准备} a:=0;b:=0;{ 当前局双方的比分初始化} while not eof (input) do{若文件未读完,则循环} begin while not eoln(input) do{若当前行处理完,则11分制的比赛结束} begin read(ch);{读一个字符} case ch of{根据字符的种类分情形处理} 'E': begin{若比赛结束,则输出双方比分} writeln(a,':',b); break;{退出11分制的计算过程} end;{ 'E'} 'W',’L’: begin{华华或对方得一分} if ch=’W’then inc(a) else inc(b); if ((a>=11)or(b>=11)) and (abs(a-b)>1) then{若有一方得 分达到11分且双方的分数差值大于1,则输出双方比分} begin writeln(a,':',b);

a:=0;b:=0;{新一局的比分初始化} end;{then} end; {'W',’L’} end;{case} end;{while} readln; end; {while} a:=0; b:=0; {新一局的比分初始化} writeln;

reset(input);{重新读输入行}
while not eof(input) do{若文件未读完且比赛未结束,则循环} begin while not eoln(input) do{若当前行处理完,则21分制的比赛结束} begin read(ch);{读一个字符}

case ch of{根据字符的种类分情形处理} ‘E’:begin{若比赛结束,则输出双方比分,退出21分制的计算过程} writeln(a,':',b); break; end;{ 'E'} 'W',’L’: begin{华华或对方得一分} if ch=’W’then inc(a) else inc(b); if ((a>=21)or(b>=21)) and (abs(a-b)>1) { 若有一方得分达 到21分且双方的分数差值大于1,则输出双方比分} then begin writeln(a,':',b); a:=0;b:=0;{新一局的比分初始化} end;{then} end;{ 'W',’L’} end;{case} end;{while} readln; end;{while} close(input); close(output);{关闭输入文件和输出文件}

关键是文件操作。如果在计算21分 制的得分前,不会通过reset(input) 将读头移到文件首,则会出错!

谁拿了最多奖学金
【问题描述】某校的惯例是在每学期的期末考试之后发放奖学金。发 放的奖学金共有五种,获取的条件各自不同: 1)院士奖学金,每人8000元,期末平均成绩高于80分(>80),并且在 本学期内发表1篇或1篇以上论文的学生均可获得; 2)五四奖学金,每人4000元,期末平均成绩高于85分(>85),并且班 级评议成绩高于80分(>80)的学生均可获得; 3)成绩优秀奖,每人2000元,期末平均成绩高于90分(>90)的学生均 可获得; 4)西部奖学金,每人1000元,期末平均成绩高于85分(>85)的西部省 份学生均可获得; 5)班级贡献奖,每人850元,班级评议成绩高于80分(>80)的学生干 部均可获得; 只要符合条件就可以得奖,每项奖学金的获奖人数没有限制,每 名学生也可以同时获得多项奖学金。例如姚林的期末平均成绩是87 分,班级评议成绩82分,同时他还是一位学生干部,那么他可以同 时获得五四奖学金和班级贡献奖,奖金总数是4850元。 现在给出若干学生的相关数据,请计算哪些同学获得的奖金总 数最高(假设总有同学能满足获得奖学金的条件)。

【输入文件】输入文件scholar.in的第一行是一个整数N (1≤N≤100),表示学生的总数。接下来的N行每行是一位 学生的数据,从左向右依次是姓名,期末平均成绩,班级评 议成绩,是否是学生干部,是否是西部省份学生,以及发表 的论文数。姓名是由大小写英文字母组成的长度不超过20的 字符串(不含空格);期末平均成绩和班级评议成绩都是0到 100之间的整数(包括0和100);是否是学生干部和是否是西 部省份学生分别用一个字符表示,Y表示是,N表示不是;发 表的论文数是0到10的整数(包括0和10)。每两个相邻数据 项之间用一个空格分隔。 【输出文件】输出文件scholar.out包括三行,第一行是获得最 多奖金的学生的姓名,第二行是这名学生获得的奖金总数。 如果有两位或两位以上的学生获得的奖金最多,输出他们之 中在输入文件中出现最早的学生的姓名。第三行是这N个学生 获得的奖学金的总数。

算法分析
难度分析:本题的算法是直叙式模拟,属于一 道简单的数理统计题,毋需建立与问题对应 的数学模型。唯一的难点就是输入数据的处 理,因为每行的数据既包括字串,又包括数 值,需要选手清晰地甄别和处理不同类型的 数据。

方法1、一次读入后分离
读入一个字符串S。利用pos(‘ ‘,s)命令找 出空格位置。再利用Copy函数进行截取, 并通过Val函数将其中的数串转换为数值。 对本题来说,这种稍显复杂的方法可以避 免,但对NOIP来说,此方法应该掌握。因 为在某种情况下,可能非这样做不可。

? 用一个纪录型数组、或者多个不同类型的数组记录 所有学生的信息。计算出获得最多奖金的学生并不 一定要先记录下所有学生的信息,而是通过依次统 计每个学生奖金的办法亦可以达到这个目的。 ? 在依次读一个学生的诸方面信息时,同一数据类型 的信息用一条read语句读入,每个学生的最后一条 信息用readln语句读入。 ? 我们在读完一行数据后就可统计其奖金数了,并调 整目前获奖金最多的学生信息。注意,记录奖金总 数的变量必须采用Longint类型(为什么)。

var name,nn:array [1..30] of char;{获得最多奖金的学生姓名为name;当前 学生姓名为nn} n,i,j,tot,max,x,m1,m2,u:longint; b1,b2,ch:char; begin assign(input,'scholar.in'); reset(input); readln(n);{ 读学生数} tot:=0;max:=0;fillchar(name,sizeof(name),' '); for i:=1 to n do{读入每位学生的数据} begin fillchar(nn,sizeof(nn),' ');j:=0;{读第i位学生的姓名nn} repeat read(ch); if ch=' ' then break; inc(j);nn[j]:=ch until false; read(m1,m2);{ 读第i位学生的期末平均成绩和班级评议成绩、是否是学生 干部和是否是西部省份学生的信息} repeat read(b1) until (b1='Y') or (b1='N'); repeat read(b2) until (b2='Y') or (b2='N');

readln(u);{读发表的论文数} x:=0;{累计第i位学生的奖金} if (m1>80) and (u>=1) then x:=x+8000; if (m1>85) and (m2>80) then x:=x+4000; if (m1>90) then x:=x+2000; if (m1>85) and (b2='Y') then x:=x+1000; if (m1>80) and (b1='Y') then x:=x+850; tot:=tot+x;{ 累计前i位学生的奖金总数} if x>max{若第i位学生的奖金最多,则调整max并记下其名字} then begin max:=x;name:=nn end{ then } end;{ for } close(input);{关闭输入文件} assign(output,'scholar.out'); rewrite(output);{输出文件写准备} i:=1;{输出获得最多奖金的学生姓名和奖金数} while name[i]<>' ' do begin write(name[i]);inc(i) end;{ while } writeln; writeln(max); writeln(tot);{输出N个学生获得的奖学金总数} close(output){关闭输出文件} end.

校门外的树
? 【问题描述】某校大门外长度为L的马路上有一排树,每两棵相 邻的树之间的间隔都是1米。我们可以把马路看成一个数轴,马 路的一端在数轴0的位臵,另一端在L的位臵;数轴上的每个整 数点,即0,1,2,……,L,都种有一棵树。 ? 由于马路上有一些区域要用来建地铁。这些区域用它们在数轴 上的起始点和终止点表示。已知任一区域的起始点和终止点的 坐标都是整数,区域之间可能有重合的部分。现在要把这些区 域中的树(包括区域端点处的两棵树)移走。你的任务是计算 将这些树都移走后,马路上还有多少棵树。 ? 【输入文件】输入文件tree.in的第一行有两个整数L(1 ≤ L ≤ 10000)和 M(1 ≤ M ≤ 100),L代表马路的长度,M代 表区域的数目,L和M之间用一个空格隔开。接下来的M行每行包 含两个不同的整数,用一个空格隔开,表示一个区域的起始点 和终止点的坐标。 ? 【输出文件】输出文件tree.out包括一行,这一行只包含一个 整数,表示马路上剩余的树的数目。

第1种方法:模拟统计
在一个布尔类型数组的支持下直接模拟,数组的下标表示坐标,坐标从0开始。值为 true表示该位置有树,false表示该位置没树。每次读入一段区间,就将这个区间内所 有下标的布尔值设为false。显然,最后布尔数组中值为true的下标个数即为马路上剩 余树木的总数。 program ex; var a:array[0..10000] of boolean; l,m,x,y,i,j,ans:longint; begin assign(input,'tree.in');assign(output,'tree.out'); reset(input);rewrite(output); readln(l,m); {读马路的长度和区域数} fillchar(a,sizeof(a),true); for i:=1 to m do begin readln(x,y);{读第i个区域的起始点和终止点的坐标} for j:=x to y do a[j]:=false{该区域的树被移走} end;{for} ans:=0; {计算马路上剩余的树数} for i:=0 to l do if a[i] then inc(ans); writeln(ans);{输出结果} close(input);close(output){关闭输入文件和输出文件} end. 上述算法的时间复杂度为O(L*M)。

第2种方法:线段分割
? 逐一将地铁区域置入区间表。每读入一个地铁区域,则与区 间表中的每一条线段比较,去掉线段中被重合的部分,因为 该区间内的树将被移走。例如,[a,b]为区间表中的一条线 段,[c,d]为地铁区域,阴影部分为调整后的线段。

? 最后,统计区间表中所有线段所含的坐标数total(total即 为被移走的树的总数),

const maxn=2000; type linetype=record{线段的类型} a,b:longint{起始点和终止点的坐标} end; var line:array[1..maxn]of linetype;{线段序列} a,b,i,tot,total,n,j,l:longint; function cross(a,b,c,d:longint):boolean;{若线段(a,b)与线段(c,d)相交,则返回true; 否则返回false} begin if (a>d)or(c>b) then cross:=false else cross:=true end;{ cross } procedure add(a,b:longint);{将线段(a,b)加入线段序列line } Begin tot:=tot+1; line[tot].a:=a;line[tot].b:=b;end;{ add } procedure dlt(num:integer);{去除线段序列line中的第num条线段} begin line[num]:=line[tot];tot:=tot-1;end;{ dlt } procedure cut(num:integer;cc,dd:longint);{若线段序列line中的第num条线段覆盖线段 (cc,dd),则线段序列不变;否则线段序列line中的第num条线段被分割后的子线段取代} begin if line[num].a<cc then add(line[num].a,cc-1);{线段(line[num].a,cc-1)进入线段序列 line} if line[num].b>dd then add(dd+1,line[num].b);{ 线段(dd+1,line[num].b)进入线段序 列line } dlt(num){删除线段序列line中的第num条线段} end;{ cut }

第3种方法:快速排序
? 首先,将所有的地铁区域按起始点坐标递增的顺序排 列,建立数组a,其中[a[i,1],a[i,2]]为序列中第i个 地铁区域。设一个尾指针en,初始时,en为地铁区域1 的终止点坐标a[1,2]。然后依次处理每一个地铁区域, 累计被移走的树木数total:

每处理一个地铁区域i后,en调整为a[i,2]。依次类 推,直至处理完地铁区域m后,便计算出被移走的树 木总数total。显然,L+1- total即为问题的解。时 间复杂度为O(MlogM)。

program ex; const maxn=2000; type atype=array[1..2]of longint; var a:array[1..maxn]of atype; i,j,n:integer; en,total,l:longint; procedure change(num1,num2:integer); var temp:atype; begin temp:=a[num1];a[num1]:=a[num2];a[num2]:=temp end; procedure qsort(s,e:integer);{线段a[s]…a[e]按照起始位臵的顺序进行排列} var i,j:integer; aa:atype; begin if s>=e then exit; aa:=a[s+random(e-s)];{随机选出一条线段aa} i:=s-1;j:=e+1;{左右指针初始化} while true do{寻找中间指针j,使得左区间a[s,1]…a[j,1]都小于等于aa[1],右区间 a[j+1,1] …a[e] 都大于aa[1]} begin repeat i:=i+1 until a[i,1]>=aa[1];{ 由左而右搜索第一个a[i,1]≥aa[1]的元素a[i]} repeat j:=j-1 until a[j,1]<=aa[1];{由右而左搜索第一个a[j,1]≤aa[1]的元素a[j]} if i<j then change(i,j){a[i]与a[j]交换} else break end;{ while } qsort(s,j);{对左区间快速排序} qsort(j+1,e){对右区间快速排序} end;{ qsort }

begin assign(input,'tree.in');reset(input); {输入文件读准备,输出文件写 准备} assign(output,'tree.out'); rewrite(output); randomize;{随机数发生器初始化} readln(l,n); {读马路的长度和区域数} for i:=1 to n do readln(a[i,1],a[i,2]);{读n个区域的起始点和终止点 的坐标} qsort(1,n);{ {线段a[1]…a[n]按照起始位臵的顺序进行排列}} en:=a[1,2];{当前移树区间的尾指针初始化} total:=a[1,2]-a[1,1]+1;{ 线段a[1]中的树被移走} for i:=2 to n do if a[i,1]<en{若a[i,1]<en<a[i,2],则区间[en+1…a[i,2]]内的树被移走} then begin if a[i,2]>en then begin total:=total+a[i,2]-en;en:=a[i,2] end end{ then } else begin total:=total+a[i,2]-a[i,1]+1;en:=a[i,2] end;{若 a[i,1]≥en,则线段a[i]内的树被移走} writeln(l+1-total);{ 输出马路上剩余的树数} close(input);close(output);{ 关闭输入文件和输出文件} end.

? 【问题描述】 ? 乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规 律。一天,他突然对数的正整数次幂产生了兴趣。 ? 众所周知,2的正整数次幂最后一位数总是不断的在重复2,4, 8,6,2,4,8,6……我们说2的正整数次幂最后一位的循环 长度是4(实际上4的倍数都可以说是循环长度,但我们只考虑 最小的循环长度)。类似的,其余的数字的正整数次幂最后一 位数也有类似的循环现象:
循环
2
3 4 5

循环

循环长度
4
4 2 1

2、4、8、6
3、9、7、1 4 、6 5

6
7 8 9

6
7、9、3、1 8、4、2、6 9 、1

1
4 4 2

这时乐乐的问题就出来了:是不是只有最后一位才有这样的循 环呢?对于一个整数n的正整数次幂来说,它的后k位是否会 发生循环?如果循环的话,循环长度是多少呢? 注意: 1. 如果n的某个正整数次幂的位数不足k,那么不足的高位看 做是0。 2. 如果循环长度是L,那么说明对于任意的正整数a,n的a次 幂和a + L次幂的最后k位都相同。 【输入文件】输入文件circle.in只有一行,包含两个整数n (1≤n<10100)和k(1≤k≤100),n和k之间用一个空格隔开, 表示要求n的正整数次幂的最后k位的循环长度。 【输出文件】输出文件circle.out包括一行,这一行只包含一 个整数,表示循环长度。如果循环不存在,输出-1。

问题的规模要求采用高精度计算
? 本题要求计算n(1≤n<10100)的正整数次幂 的最后k(1≤k≤100)位的循环长度,因此 必须采用k位高精度运算。不仅每次乘幂运 算需要通过高精度乘法保留后k位,而且由 于最小循环长度是任何整数类型无法容纳的, 因此其计算过程也需要用到k位高精度加法。

必须采用倍增思想提高时效
? 如果采用简单的连乘运算,是根本不可能满足时效 要求的,只能采用倍增思想逐位递推:先保证第1位 循环,求出最小的循环长度l1;接下来计算第2位循 环的最小循环长度:连乘 n l ,直至出现2位循环为 止。此时得出2位的最小循环长度l2;然后连乘 n l , 直至出现3位循环为止,由此得出第3位循环的最小 循环长度;……,依次类推,直至递推出第k位的最 小的循环长度lk。在计算第i(1≤i≤k)位循环时, 如果连乘了10次后没有结果,则输出无解信息。因 为第i位所有可能出现的数字都已经出现,因此不可 能递推出长于i位的循环节了。
1
2

数据结构
type ptype=array[1..200]of longint; ttype=array[1..200]of integer; var p,tempp,stp,pp:ptype;{参与运算的两个操作数为p 和tempp } tempt,t:ttype;{ 循环长度为tempt;连乘一次增加 的次幂数为t } k,tott,tottemp:longint;{tempt的长度为tottemp; t的长度为tott}

输入信息,建立整数数组
readln(st); {读输入串} st1:=copy(st,1,pos(' ',st)-1); delete(st,1,pos(' ',st));val(st,k,ok);{从输入串中截出底数st1和正 整数次幂的最后位数,将其转换为整数k} if length(st1)<k{若底数st1的长度不足k,则将其全 部转换为整数数组p;否则将其低k位转换为整数数组p} then for i:=1 to length(st1) do p[length(st1)-i+1]:=ord(st1[i])-ord('0') else for i:=1 to k do p[i]:=ord(st1[length(st1)-i+1])-ord('0'); end;

计算循环长度
stp:=p; tempp:=p; tempt[1]:=0;tottemp:=1;{循环长度初始化}; while true do{先保证第1位循环,求出最小循环长度tempt[1]} begin inc(tempt[1]);pp:=p; {pp=ptempt[1]} mul(p,tempp);{k位运算:p←p*tempp} if check(stp,p,1) then break{若p 的第1位出现循环,则退出while } end;{ while } t:=tempt;tott:=tottemp;{暂存tempt 及其长度} for kk:=2 to k do{依次递推第2位…第k位循环的最小循环长度} begin p:=stp; tempp:=pp;{暂存kk-1位运算的乘幂} fillchar(pp,sizeof(pp),0); pp[1]:=1;{pp←1} fillchar(tempt,sizeof(tempt),0); tottemp:=0;{ 最小循环长度tempt初 始化为0} tot:=0;{ 相乘次数初始化}

while true do begin

plus(tempt,t,tottemp,tott); {tempt←tempt+t}
mul(p,tempp);mul(pp,tempp);{p←p*tempp,pp←pp*tempp,即 pp=p/stp} if check(stp,p,kk) then break; {若p的第kk位出现循环,则 退出while} tot:=tot+1;{累计相乘次数} if tot>10 then 输出-1{若连续乘了10次仍然没有出现循环, 则输出无解信息。因为第kk位所有能出现过的数字都已经出现 过了,仍没有我们想要的n的第kk位,就表示不可能循环了} end;{ while } tempp:=pp; {当前位乘幂pp暂存tempp} t:=tempt;tott:=tottemp{循环长度tempt暂存t} end;{ for } for i:=tott downto 1 do write(tempt[i]);{输出循环长度} writeln; end;

检查p和tempp的后kk位是否相同
function check(p,tempp:ptype;kk:longint):boolean;{若整 数数组p 和tempp的后kk位相同,则返回true;否则返回 false} var i:longint; begin check:=false; for i:=1 to kk do if p[i]<>tempp[i]then exit; check:=true end;{ check }

计算t←t+ tempt
procedure plus(var t:ttype;tempt:ttype;var tott:longint;tottemp:longint);{t的长度为tott,tempt的长度为tottemp} var i,tt:integer; begin if tott>tottemp{计算运算的位数} then tt:=tott else tt:=tottemp; for i:=1 to tt do t[i]:=t[i]+tempt[i];{逐位相加} for i:=1 to tt do{每位规整为十进制数} begin t[i+1]:=t[i+1]+t[i] div 10;t[i]:=t[i] mod 10 end;{ for } while t[tt+1]>0 do{最高位的进位处理} begin t[tt+1]:=t[tt+1]+t[tt] div 10; t[tt]:=t[tt] mod 10; inc(tt) end; tott:=tt{返回和的位数} end;{ plus }

计算p←p*tempp,
procedure mul(var p:ptype;tempp:ptype);{p的初始长度和tempp 的长度为k} var i,j:longint; temp:ptype; begin temp:=p; fillchar(p,sizeof(p),0);{积初始化} for i:=1 to k do{逐位相乘} for j:=1 to k do p[i+j-1]:=p[i+j-1]+temp[i]*tempp[j]; for i:=1 to k do{p的第k位…第1位规整为十进制数} begin p[i+1]:=p[i+1]+p[i] div 10;p[i]:=p[i] mod 10 end;{ for } for i:=k+1to2*k-1 do p[i]:=0{p的第k+1位…第2*k-1位清零} end;

等价表达式
【问题描述】明明进了中学之后,学到了代数表达式。有一天,他碰到一个很麻 烦的选择题。这个题目的题干中首先给出了一个代数表达式,然后列出了若 干选项,每个选项也是一个代数表达式,题目的要求是判断选项中哪些代数 表达式是和题干中的表达式等价的。 这个题目手算很麻烦,因为明明对计算机编程很感兴趣,所以他想是不 是可以用计算机来解决这个问题。假设你是明明,能完成这个任务吗? 这个选择题中的每个表达式都满足下面的性质: 1. 表达式只可能包含一个变量‘a’。 2. 表达式中出现的数都是正整数,而且都小于10000。 3. 表达式中可以包括四种运算‘+’(加),‘-’(减),‘*’(乘),‘^’ (乘幂),以及小括号‘(’,‘)’。小括号的优先级最高,其次是‘^’,然后 是‘*’,最后是‘+’和‘-’。‘+’和‘-’的优先级是相同的。相同优先级的运 算从左到右进行。(注意:运算符‘+’,‘-’,‘*’,‘^’以及小括号‘(’, ‘)’都是英文字符) 4. 幂指数只可能是1到10之间的正整数(包括1和10)。 5. 表达式内部,头部或者尾部都可能有一些多余的空格。 下面是一些合理的表达式的例子: ((a^1) ^ 2)^3,a*a+a-a,((a+a)),9999+(a-a)*a,1 + (a -1)^3, 1^10^9……

【输入文件】输入文件equal.in的第一行给出的是题干 中的表达式。第二行是一个整数n(2 ≤ n ≤ 26), 表示选项的个数。后面n行,每行包括一个选项中的表 达式。这n个选项的标号分别是A,B,C,D…… 输入中的表达式的长度都不超过50个字符,而 且保证选项中总有表达式和题干中的表达式是等价的。 【输出文件】输出文件equal.out包括一行,这一行包 括一系列选项的标号,表示哪些选项是和题干中的表 达式等价的。选项的标号按照字母顺序排列,而且之 间没有空格。

问题的核心是如何判断表达式等价
? 判断表达式等价的方法一般有两种: ? 表达式化简后判断 ? 表达式代值后判断

判断等价的方法1:展开多项式后 判断
将所有的表达式全部转化为最简形式,然后再 计算。其一般过程:先将阶乘化乘,再展开。 计算同时合并同类项,并用数组记录每一个表 达式的最简形式。然后比较每一个表达式的数 组与题干表达式的数组是否相同。若相同,则 说明该表达式与题干表达式是等价的。 优点:准确和严密 缺点:实现相当麻烦,时间效率不高,尤其是在 乘幂多、幂次大的情况下。

判断等价的方法2:代值后判断
将数值代入并计算。 误判的可能:假如碰巧代入的值使两个多项式值相等 避免的方法:多次代入不同数值、代入较大数值等等……。虽然 这个算法并不一定正确,但多次随机代值后的出错概率已经可以 忽略不计了,而且实现又比较简单。取值的有效方法: 取随机函数生成的数列。这种方法比较有效,无规律。 取伪随机数列。这是一种比较便于人工控制的手段。 取实数。优点:由于系数和次幂和常数皆为整数,因此小数部分 便成为判断的优越条件。缺点:由于计算中出现了次方运算,所 以可能溢出。避免整数溢出的方法:在求值过程中采用取模运算, 并且多取几个模。 我们采取多代整数、多取模的方法判断表达式等价。于是,如何 计算表达式的值成了问题的关键

? ? ?

?

表达式求值的方法1:栈操作
建立两个栈,一个是存储操作数的数栈,一个是存储 运算符的符号栈。每一个符号定义一个优先级,优先级 高的运算符先算。为了方便起见,我们定义特殊符号# 的级别最低(赋-1),先将它臵符号栈的栈底。然后 依次读入每个字符,如果是数字,则入数栈。如果是 运算符,则与符号栈的栈顶元素比较优先级。如果相 等,则出栈,读下一字符;如果栈外大,则入栈;如 果栈内大,则符号栈的栈顶元素出栈,与数栈最顶2元 素运算,结果入数栈。这个符号继续处理(再与栈顶 比较)。直到读到最后符号‘#’使栈底‘#’出栈时,数 栈顶即为表达式结果。

表达式求值的方法2:并查集操作
? 每次在尚未运算的运算符找出一个优先级最 高的符号,进行相应的运算,直至仅剩一个 数字时返回。这种方法符合自然思维和运算 规则,实现简单明了,不易出错。

1、数据结构
? 我们由左而右扫描表达式串st的每一个字符, 存储每一个运算的信息。其中第i个运算的运 算符存储在c[i],优先级存储在d[i] ? (d[i]=
) *3 ?1 ? (括号嵌套重数 ? ) *3 ? 2 ?(括号嵌套重数 ?(括号嵌套重数 ) *3 ? 3 ? ‘? ‘ ’ ?’ ‘* ’ ),操作 ‘?’

? 数存储在r[i](若第i个运算的操作数为变量 a,则r[i]=-1)

我们将目前所有参与过运算的操作数放在集合 里,其中第p个操作数参与运算后的结果记入第 f[p]个操作数,即所有具有同一个f值的操作数 组成一个集合,它们运算后的结果记入第f[p]个 操作数。 如果c[i]为当前的运算符,则从f[i]和f[i+1] 出发,顺着f指针即可找到参与运算的两个操作 数。

const xn=3;{代入的a的总数} mn=2;{模的总数} var cm,rc,nn,n,i,j:longint;{选项数为nn;运算数为n} st:string;{表达式串} c:array [1..30] of char;{c[i]为第i个运算的运算符} d:array [1..30] of longint;{ d[i]为第i个运算的优先级} r,u:array [1..30] of int64;{ r[i]为第i个运算的操作数。若r[i]=-1, 则第i个运算的操作数为变量a} a:array [1..xn,1..mn] of int64;{将第i个变量值和第j个模代入题干后的 值为a[i,j]} x:array [1..xn] of longint;{a的第i个代入值为x[i];模的第i个代入值 为y[i]} y:array [1..mn] of longint; yes:boolean;{当前选项与题干等价的标志} mv:int64;{当前选项的值}

2、记录当前选项的每一个运算
procedure ff; var top,i,j,v:longint;{i为读字符串的指针;top为括号嵌套 重数,v为操作数} begin top:=0;n:=1;i:=0;{括号嵌套重数、运算顺序数和字串指针初 始化} fillchar(r,sizeof(r),0);{操作数序列初始化} while i<length(st) do begin inc(i);{字串指针右移} case st[i] of{分析第i个字符的类型} '(':inc(top);{若为左括号,括号嵌套重数+1} ')':dec(top); {若为右括号,括号嵌套重数-1}

'0'..'9':begin{若为数串,则计算对应的数字,记入r[n]。字串指针指向数串 后的第一个字符} j:=i;v:=0; while(j<=length(st))and((st[j]>='0')and(st[j]<='9')or(st[j]=' '))do begin if st[j]<>' ' then v:=v*10+ord(st[j])-48;inc(j) end;{ while } r[n]:=v;i:=j-1 end;{ '0'..'9'} 'a': r[n]:=-1; ' ':continue; ? else begin
c[n]:=st[i];{记下运算符} case st[i] of{记下优先级} '+','-':d[n]:=top*3+1; '*':d[n]:=top*3+2; '^':d[n]:=top*3+3 end;{ case }

inc(n){运算顺序+1} end{ else } end;{case} end;{while} end; {ff}

3、求值过程
? 设b为运算完成的标志序列,其中b[i]=true,标志已完成c[i] 运算符指定的运算。 ? 在含有n个运算的表达式中,含有n-1个运算符。参与当前运算 的两个操作数为r[p]和r[q]。我们采用类似并查集的方法计算 表达式值,即初始时,N个操作数各组成n个集合。当计算 r[p]←r[p] op r[q]后,集合q并入集合p (f[q]←p),表明 第p个操作数和第q个操作数已经完成了运算,计算结果记入第p 个操作数。 ? 首先将n个变量操作数进行代值,并对n个操作数进行取摸运算。 然后在未参与运算的运算符中寻找运算级最高的运算符 {d [i ] b[i ] ? false}。然后从max和max+1位臵开 c[max],d[max]= max 1?i ? n 始沿着f指针寻找两个待运算的操作数u[p]和u[q](f[p]=p, f[q]=q),完成由c[max]指定的运算,结果记入u[p],集合q并 入集合p。b[max]←true。依次类推,直至完成n-1个运算为止。

例如变量a=1、模为10时,计算表达式a+(1+2)^3的值: -1 1 2 3 r序列 找出运算符优先级最高的d[2](对应括 1 2 3 4 f序列 号内的‘+’)和两个操作数r[2]、 + + ^ c序列 1 4 3 d序列 r[3] ,r[2]←(r[2]+r[3])mod 10=3
b序列 r序列 f序列 c序列 d序列 b序列 false -1 1 + 1 false false 3 2 + 4 true false 2 2 ^ 3 false False false 3 4

再在未参与运算的运算符中找出优先级 最高的运算符‘^’(d[3]=3),r[2] ←(r[2]^r[4])mod 10=7

r序列 f序列 c序列 d序列 b序列 r序列 f序列 c序列 d序列

1 1 + 1 false 1 1 + 1

7 2 + 4 true 7 1 + 4

2 2 ^ 3 true 2 2 ^ 3

3 2

这时仅剩c[1]=‘+’未参与运算了, r[1] ←(r[1]+r[2])mod 10=8

3 2

b序列

true

true

true

function cal(x,m:longint):int64;{计算当a=x时,字符串st所代表的表达式结 果模m的余数} var f:array [1..30] of longint;{单链表形式的并查集,f[i]=i表明第i个操作数 为待运算的操作数} b:array [1..30] of boolean;{ 运算完成的标志序列} vv:int64;{乘幂的结果} i,j,max,p,q:longint;{当前参与运算的两个操作数为u[p]、u[q]} begin u:=r;{记下操作数序列} for i:=1 to n do if u[i]=-1 then u[i]:=x;{变量代值} for i:=1 to n do u[i]:=((u[i] mod m)+m) mod m; {若u[i]是负数,则 u[i] mod m也是负数,为避免这种情况,采用两次取模} for i:=1 to n do f[i]:=i;{ 并查集初始化} fillchar(b,sizeof(b),false);{ 初始时,所有运算未完成} for i:=1 to n-1 do begin max:=1;while b[max] do inc(max);{由左而右寻找第一个没有完成的运 算序号max } for j:=max+1 to n-1 do{在max位臵后寻找一个优先级最高的未完成运算} if (d[j]>d[max]) and not b[j] then max:=j; b[max]:=true;{完成该运算}

p:=max;while f[p]<>p do p:=f[p];{ 用类似并查集的方法寻找参与运 算的两个操作数u[p]和u[q]} q:=max+1;while f[q]<>q do q:=f[q]; f[q]:=p;{合并} case c[max] of{根据max位臵的运算符进行运算} '+':u[p]:=(((u[p]+u[q]) mod m)+m) mod m; '-':u[p]:=(((u[p]-u[q]) mod m)+m) mod m; '*':u[p]:=(((u[p]*u[q]) mod m)+m) mod m; '^':begin vv:=1; for j:=1 to u[q] do vv:=((vv*u[p] mod m)+m) mod m; u[p]:=vv end{'^'} end;{ case } end;{ for } cal:=u[1]{返回代值后的结果} end;{ cal }

主程序
? 首先我们将每一个变量值和每一个模代入 题干,将所有的结果记入数组a。然后依次读 入每一个选项,计算每一个选项代入变量值 和模后的所有可能值。若某个选项所有代值 后的结果均与a中的对应数据相同,则输出这 个选项的标号。

x[1]:=37;x[2]:=101;x[3]:=19541;{选定变量a的3个值} y[1]:=19991;y[2]:=19997;{选定两个模} readln(st);{读题干中的表达式} ff; {记录题干的每一个运算} for i:=1 to xn do{代入每一个变量值和每一个模,计 算a} for j:=1 to mn do a[i,j]:=cal(x[i],y[j]); readln(nn);{读选项的个数}

for rc:=1 to nn do{依次读入每一个选项} begin readln(st);{读第i个选项} ff; {记录第i个选项的每一个运算} yes:=true; for i:=1 to xn do{计算第i个选项代入变量值和模后的所有可 能值} for j:=1 to mn do begin mv:=cal(x[i],y[j]); {计算该选项代入第i个变量值、第j个 模后的结果mv} if mv<>a[i,j]then yes:=false;{若与题干代值后的结果不 同,则标志失败} end; if yes then write(chr(rc+64)){ 若题干代值后的结果均与第i 个选项所有代值后的结果相同,则输出第i个选项的标号} end;{ for } writeln;


相关文章:
集合基础习题(有答案)
集合基础习题(有答案)_数学_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 集合基础习题(有答案)_数学_高中教育_教育专区。xxxXXXXX 学校 XXXX 年学...
集合基础练习题
集合基础练习题_数学_高中教育_教育专区。高一数学第一章 集合基础练习题知识框架 1.某些指定的对象集在一起就成为一个集合。集合元素具有 性。 2.常用符号及其...
集合基础习题
集合基础习题_哲学_高等教育_教育专区。集合基础题 1. 已知集合 A ? x x (...集合基础题 1. 已知集合 A ? x x ( x ? 1) ? 0 ,那么下列结论正确的...
中考数学基础题练习
(用含 n 的代数式表示) 基础题练习五 班级 1. (﹣2)0 等于 A. 1 B.2 姓名 C. 0 D.﹣2( ) 学号 ) 得分 12.25 2.下列图案中,属于轴对称图形的...
基础试题库
B、维护国家文化利益 C、维护国家主权和领土完整 D、维护国家政治利益 二、多项选择题(正确答案不止一项,多选、漏选均不得分) 1.爱国主义的基本要求是(ABCD )...
软件基础题库(全)
软件基础题库(全)_财会/金融考试_资格考试/认证_教育专区。第一章 软件工程 1、填空 1)软件包含___以及开发、使用和维护程序需要的所有文档。 (程序) 2) ...
初中数学基础题
初中数学基础题_初三数学_数学_初中教育_教育专区。初中数学基础知识测试题学校 姓名 得分 一、填空题(本题共 30 小题,每小题 2 分,满分 60 分) 1、 和 ...
《HTML基础试题》
《HTML基础试题》_电脑基础知识_IT/计算机_专业资料。《HTML基础试题》里面包含常用到的一些HTML试题考点及经典用法。《HTML 基础试题》一、单项选择题: 1、下面哪...
数列基础练习题(简单)
数列基础练习题(简单)_高一数学_数学_高中教育_教育专区。等差数列 一、填空题 1. 等差数列 8,5,2,…的第 20 项为___. 2. 在等差数列中已知 a1=12,...
电路基础试题库
电路基础试题库_理学_高等教育_教育专区。第1章 试题库一、填空题(建议较易填空每空 0.5 分,较难填空每空 1 分) 填空题 1、电流所经过的路径叫做 分组成...
更多相关标签:
基础 | 语文基础题 | 数学基础题 | 手绘基础练习 | 小学语文基础题 | 公共基础知识题库 | java基础试题及答案 | 公共基础知识1000题 |