pascal历届noip复赛试题(1)-分析

《pascal历届noip复赛试题(1)-分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、二中信息学奥赛培训讲义——中级班第12讲-历届NOIP复赛试题(1)模拟试题中文名英文名题型分值时限Cantorcanor传统题1001s回文数huiwen传统题1001s装箱问题pack传统题1001s单词接龙dcjl传统题1001s1.Cantor表（cantor.pas/c/cpp）【问题描述】现代数学的著名证明之一是GeorgCantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：我们以Z字形给上表的每一项编号。第一项是1/1，然后是1/2，2/1，3/1，2/2，…【输入】整数N（1≤N≤10000000）【输出】表中的第N项【样例输入】7

2、【样例输出】-9-二中信息学奥赛培训讲义——中级班1/4【分析】基础题，模拟。首先确定所在斜行，然后针对奇数行和偶数行进行计算。【参考代码】varn,x:longint;beginassign(input,'cantor.in');reset(input);assign(output,'cantor.out');rewrite(output);readln(n);x:=0;repeat//确定所在的斜行inc(x);n:=n-x;untiln<=0;ifxmod2=0thenwrite((x+n),'/',(1-n))//确定如何输出elsewriteln((1-n

3、),'/',(x+n));close(input);close(output);end.2.回文数（huiwen.pas/c/cpp）【问题描述】若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。又如：对于10进制数87：STEP1：87+78=165STEP2：165+561=726STEP3：726+627=1353STEP4：1353+3531=4884在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。写一个程序，给定一

4、个N（2<=N<=10，N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”【输入】-9-二中信息学奥赛培训讲义——中级班两行，第一行N（2<=N<=10，N=16），表示进制；第二行M。【输出】一行，STEP=最少的步数【样例输入】87【样例输出】STEP=4【分析】高精度计算，可以分以下几步进行考虑：　　①由于输入的数据可能是二至十六进制的数，可以将每位数转换为十进制数后，按位存放在a[i]数组中。②利用高精度计算的方法，按位计算两个数的和。③判断这个数是否是回文数，如果不是，再看是否

5、超过30步，超过则结束程序，否则再转至第②步执行。【参考代码】programhuiwen;vara:array[1..10000]ofinteger;l,step,i,n:longint;m:string;procedurework;//求两个数的和varb:array[1..10000]ofinteger;i:longint;beginfillchar(b,sizeof(b),0);fori:=1toldob[i]:=a[i]+a[l+1-i];fori:=1toldoifb[i]>=nthenbegindec(b[i],n);inc(b[i+1]);end;if

6、b[l+1]>0theninc(l);fori:=1toldoa[i]:=b[i];end;functionjudge:boolean;//判断是否是回文数-9-二中信息学奥赛培训讲义——中级班vari:longint;beginfori:=1to(ldiv2)doifa[i]<>a[l+1-i]thenbeginjudge:=false;exit;end;judge:=true;end;beginassign(input,'huiwen.in');assign(output,'huiwen.out');reset(input);rewrite(output);re

7、adln(n);readln(m);l:=length(m);i:=1;step:=0;//记录转换的步数whilei<=ldo//将进制数转换为十进制数beginiford(m[i])=30)orjudge;ifstep>=30thenwriteln('Impossible!')elsewr