NOIP 提高组 初赛 四、阅读程序写结果 习题集（二）NOIP2000-NOIP2001
NOIP 提高组 初赛 四、阅读程序写结果 习题集（二）NOIP2000-NOIP2001
1.第六届(NOIP2000)
问题（原文是pascal,按题意，本人改写成C，C++版本）：
1.
//NOIP2000 3.1#include <stdio.h>
#include <math.h>
const int n=7,m=6;
float disp(int x1,int y1,int x2,int y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
int i,j,x0,y0,x1,y1,x2,y2;
float d;
int p;
int g[n+1][m+1];
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
g[i][j]=0;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
g[x1][y1]=1;
g[x2][y2]=1;
p=1;
while(p){
p=0;
d=disp(x1,y1,x2,y2);
x0=x1;
y0=y1;
for(i=4;i<=n;i++)
for(j=0;j<=m;j++)
if(d>disp(i,j,x2,y2)&&g[i][j]==0){
d=disp(i,j,x2,y2);
x0=i;
y0=j;
}
if(x0!=x1||y0!=y1){
x1=x0;
y1=y0;
p=1;
g[x1][y1]=1;
}
d=disp(x1,y1,x2,y2);
x0=x2;
y0=y2;
for(i=0;i<=3;i++)
for(j=0;j<=m;j++)
if(d<disp(x1,y1,i,j)&&g[i][j]==0){
d=disp(x1,y1,i,j);
x0=i;
y0=j;
}
if(x0!=x2||y0!=y2){
x2=x0;
y2=y0;
p=1;
g[x2][y2]=1;
}
}
printf("%d %d %d %d\n",x1,y1,x2,y2);
return 0;
}
//输入7 6 0 0
2.
//NOIP2000 3.2
#include <stdio.h>
int main(){
int i,j,L,n,k,s,t;
int b[11];
scanf("%d%d",&L,&n);
s=L;
k=1;
t=L;
if(n>L){
while(s<n){
k++;
t*=L;
s+=t;
}
s-=t;
n=n-s-1;
for(i=1;i<=10;i++)
b[i]=0;
j=11;
while(n>0){
j--;
b[j]=n%L;
n/=L;
}
for(i=10-k+1;i<=10;i++)
printf("%c",'A'+b[i]);
}else
printf("%c\n",'A'+n-1);
return 0;
}
//输入：4 167
问题解答：
1.
阅读跟踪程序，可以发现：
for(i=4;i<=n;i++)
for(j=0;j<=m;j++)
if(d>disp(i,j,x2,y2)&&g[i][j]==0){
d=disp(i,j,x2,y2);
x0=i;
y0=j;
}
是找最小的长度。
for(i=0;i<=3;i++)
for(j=0;j<=m;j++)
if(d<disp(x1,y1,i,j)&&g[i][j]==0){
d=disp(x1,y1,i,j);
x0=i;
y0=j;
}
是找最大的长度。
思考过程如图所示：
(x1,y1)0,(x2,y2)0表示初始值。
(x1,y1)1,(x2,y2)1表示第一次循环后的值。
(x1,y1)2,(x2,y2)2表示第二次循环后的值。
依次类推，一共会进行8次循环，第6次找到(x2,y2)6值，第7次找到(x1,y1)7值。第8次p=0。
答案：4 3 0 2
1难，涉及矩阵，空间的变换，开始需要顺着程序跟踪，弄明白意思后，可以画二维图进行思考。
2016-12-13
2.执行过程如下：
答案：BBAC
1难2简单
2.第七届(NOIP2001)
问题（原文是pascal,按题意，本人改写成C，C++版本）：
1.
//NOIP2001 3.1
#include <stdio.h>
int ack(int m,int n){
if(m==0)
return n+1;
else if(n==0)
return ack(m-1,1);
else
return ack(m-1,ack(m,n-1));
}
int main(){
printf("%d\n",ack(3,4));
}
2.
//2001.3.2
#include <stdio.h>
int main(){
int p,q,s,t;
scanf("%d",&p);
for(q=p+1;q<=2*p;q++){
t=0;
s=(p*q)%(q-p);
if(s==0){
t=p+q+(p*q)/(q-p);
printf("%4d",t);
}
}
}
//输入：12
//输出：
3.
//2001.3.3
#include <stdio.h>
int main(){
int i,j,h,m,n,k;
int b[11];
scanf("%d",&n);
for(i=1;i<=10;i++){
m=n;
j=11;
while(m>0){
j--;
b[j]=m%10;
m/=10;
}
for(h=j;h<=10;h++)
n+=b[h];
}
printf("%d\n",n);
return 0;
}
//输入：1234
//输出：
4.
//2001.3.4
#include <stdio.h>
int main(){
int x,y1,y2,y3;
scanf("%d",&x);
y1=0;
y2=1;
y3=1;
while(y2<=x){
y1++;
y3+=2;
y2+=y3;
}
printf("%d\n",y1);
return 0;
}
//输入：23420
//输出：
问题解答：
1.
思考过程如下：
ack(0,0)=1
ack(0,1)=2
ack(0,2)=4
ack(0,3)=4
ack(0,4)=5
ack(1,0)=ack(0,1)=2
ack(1,1)=ack(0,ack(1,0))=ack(0,2)=3
ack(1,2)=ack(0,ack(1,1))=ack(0,3)=4
ack(1,3)=ack(0,ack(1,2))=ack(0,4)=5
ack(1,4)=ack(0,ack(1,3))=ack(0,5)=6
ack(2,0)=ack(1,1)=3
ack(2,1)=ack(1,ack(2,0))=ack(1,3)=5
ack(2,2)=ack(1,ack(2,1))=ack(1,5)=7
ack(2,3)=ack(1,ack(2,2))=ack(1,7)=9
ack(2,4)=ack(1,ack(2,3))=ack(1,9)=11
ack(3,0)=ack(2,1)=5
ack(3,1)=ack(2,ack(3,0))=ack(2,5)=13
ack(3,2)=ack(2,ack(3,1))=ack(2,13)=29
ack(3,3)=ack(2,ack(3,2))=ack(2,29)=61
ack(3,4)=ack(2,ack(3,3))=ack(2,61)=125
上述过程，略去一些小细节，但读者可以依照上述推导将该问题解决。
自下而上，对付递归的好办法。
2.思考过程如图所示：
答案：181 110 87 76 66 62 61 60
3.
根据该图找规律：
根据该图做计算：
答案：1348
4.
y1=1
y3=3
y2=4
y1=2
y3=5
y2=9
y1=3
y3=7
y2=16
y1=4
y3=9
y2=25
发现y2变化规律与第五届(NOIP1999)第二大题很象。
为了照顾之前学习的数学体系，令y1=n，y2=y(n)
y(1)=4
y(2)=y(1)+5=y(1)+2*2+1
y(3)=y(2)+7=y(2)+2*3+1
y(4)=y(3)+9=y(2)+2*4+1
……
y(n)=y(n-1)+2*n+1 :1
有了通式后，开始推导y(n):
y(n)=y(n-2)+2*(n-1)+1+2*n+1 :2
y(n)=y(n-3)+2*(n-2)+1+2*n+1 :3
y(n)=y(n-4)+2*(n-3)+1+2*n+1 :4
……
y(n)=y(1)+2*(1+1)+1+……+2*n+1 :
2*(1+1)+1+……+2*n+1个数为x
n-x=1
x=n-1
等差数列
2*(1+1)+1+……+2*n+1=(2*(1+1)+1+2*n+1)*(n-1)/2
2*(1+1)+1+……+2*n+1=(n+3)(n-1)
y(n)=4+(n+3)(n-1)
输入数据：
y(n)=23420
n^2+2*n-23419=0
n=(-2+sqrt(4+4*23419))/2;(负值已被舍去)
n=-1+2*sqrt(5855);
手工计算：
75^2=5625
76^2=5776
77^2=5929
76.5^2=5852.25
假定：
sqrt(5855)=76.55
n=76.55*2-1
n=152.1
取大于152.1的整数
n=153
即y1=153
答案：153
1难2中等3中等4难
2016-12-9 20:55