NOIP第十三届全国青少年信息学奥林匹克联赛初赛试题[2007提高组]

第21题

给定 n 个有标号的球，标号依次为 1，2，…，n。将这 n 个球放入 r 个相同的盒子里，不允许 有空盒，其不同放置方法的总数记为 S(n,r) 。例如， S(4,2)=7 ，这 7 种不同的放置方法依次为 {(1),(234)},{(2),(134)},{(3),(124)},{(4),(123)},{(12),(34)},{(13),(24)}, {(14),(23)} 。当 n=7,r=4 时， S(7,4)=_____________

第22题

N 个人在操场里围成一圈，将这 N 个人按顺时针方向从 1 到N 编号，然后，从第一个人起，每 隔一个人让下一个人离开操场，显然，第一轮过后，具有偶数编号的人都离开了操场。依次做下去，直 到 操 场 只 剩 下 一 个 人 ， 记 这 个 人 的 编 号 为J(N) ， 例 如 ，J(5)=3 ，J(10)=5 ， 等 等 。 则 J(400)=______________ 。 

（提示：对 N=2 m+r 进行分析，其中 0≤r<2 m ）。

第23题

#include<stdio.h>
int main()
{
	int i,p[5],q[5],x,y=20;
	for(i=0;i<=4;i++)
	scanf("%d",&p[i]);
	q[0]=(p[0]+p[1])+(p[2]+p[3]+p[4])/7;
	q[1]=p[0]+p[1]/((p[2]+p[3])/p[4]);
	q[2]=p[0]*p[1]/p[2];
	q[3]=q[0]*q[1];
	q[4]=q[1]+q[2]+q[3];
	x=(q[0]+q[4]+2)-p[(q[3]+3)%4];
	if(x>10)
		y+=(q[1]*100-q[3])/(p[p[4]%3]*5);
	else
		y+=20+(q[2]*100-q[3])/(p[p[4]%3]*5);
	printf("%d,%d\n",x,y);
	return 0; 
}
/* 注：本例中，给定的输入数据可以避免分母为 0 或数组元素下标越界。 */

输入： 66553 

输出： _______________

第24题

#include<stdio.h>
void fun(int*a,int*b)
{
	int*k;
	k=a;a=b;b=k;
}
int main()
{
	int a=3,b=6,*x=&a,*y=&b;
	fun(x,y);
	printf("No.1:%d,%d",a,b);
	fun(&a,&b);
	printf("No.2:%d,%d\n",a,b);
}

输出 :___________________

第25题

#include"math.h"
#include"stdio.h"
int main()
{
	int a1[51]={0};
	int i,j,t,t2,n=50;
	for(i=2;i<=sqrt(n);i++)
	if(a1[i]==0)
	{
		t2=n/i;
		for(j=2;j<=t2;j++)a1[i*j]=1;
	}
	t=0;
	for(i=2;i<=n;i++)
	if(a1[i]==0)
	{
		printf("%4d",i);t++;
		if(t%10==0)printf("\n");
	}
	printf("\n");
}

输出： _____________________

第26题

#include"stdio.h"
char ch[]={'q','A','S','O','R','T','E','X','A','M','P','L','E'};
int n=12;
void shift(intk,intn)
{
	char v;
	int j;
	v=ch[k];j=k+k;
	while(j<=n)
	{
		if((j<n)&&(ch[j]<ch[j+1])) j++;
		if(v<ch[j])
		{
			ch[j/2]=ch[j];j*=2;
		}
		else
		return;
		ch[j/2]=v;
	}
}
void hpsrt(void)
{
	int k;
	char tmp;
	for(k=n/2;k>0;k--)shift(k,n);/* 建堆 */
	printf("No.1:");
	for(k=1;k<=n;k++)putchar(ch[k]);
	putchar('\n');
	for(k=n;k>0;k--)
	{
	tmp=ch[1];ch[1]=ch[k];ch[k]=tmp;
	shift(1,k-1);
	}
}
int main()
{
	int k;
	hpsrt();
	printf("No.2:"); 
	for(k=1;k<=n;k++)putchar(ch[k]);
	putchar('\n');
}

输出： ___________

第27题

（格雷码， GrayCode ） 格雷码是对十进制数的一种二进制编码。编码顺序与相应的十进制数的大小不一致。其特点是：对于 两个相邻的十进制数，对应的两个格雷码只有一个二进制位不同。另外，最大数与最小数之间也仅有一个 二进制位不同，以 4 位二进制数为例，编码如下：

如果把每个二进制的位看作一个开关，则将一个数变为相邻的另一个数，只须改动一个开关。因此， 格雷码广泛用于信号处理、数 - 模转换等领域。 

下面程序的任务是：由键盘输入二进制数的位数 n(n<16) ，再输入一个十进制数 m(0 ≤m<2n) ，然 后输出对应于 m 的格雷码（共 n 位，用数组 gr[] 存放）。 

为了将程序补充完整，你必须认真分析上表的规律，特别是对格雷码固定的某一位，从哪个十进制数 起，由 0 变为 1，或由 1 变为 0。

#include<stdio.h>
int main()
{
	int bound=1,m,n,i,j,b,p,gr[15];
	printf("inputn,m\n");
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)bound= ①;
	if(m<0||m>=bound)
	{
		printf("Dataerror!\n");
		② ;
	}
	b=1;
	for(i=1;i<=n;i++)
	{
		p=0;b=b*2;
		for( ③;j<=m;j++)
		if( ④ )
		p=1-p;
		gr[i]=p;
	}
	for(i=n; ⑤ )
	printf("%1d",gr[i]);/* 在"%1d" 中出现的是数字 1，不是字母 l*/
	printf("\n");
}

第28题

（连续邮资问题）某国发行了 n 种不同面值的邮票，并规定每封信最多允许贴 m 张邮票，在这 些约束下，为了能贴出 {1 ， 2，3, …，maxvalue} 连续整数集合的所有邮资，并使 maxvalue 的值最 大，应该如何设计各邮票的面值？例如，当 n=5 、m=4 时，面值设计为 {1 ， 3，11 ，15 ，32} ，可使 maxvalue 达到最大值 70 （或者说，用这些面值的 1 至4 张邮票可以表示不超过 70 的所有邮资，但无 法表示邮资 71 。而用其他面值的 1 至4 张邮票如果可以表示不超过 k 的所有邮资，必有 k ≤70 ）。

 下面是用递归回溯求解连续邮资问题的程序。数组 x[1:n] 表示 n 种不同的邮票面值，并约定各元 素按下标是严格递增的。数组 bestx[1:n] 存放使 maxvalue 达到最大值的邮票面值（最优解）， 数组 y[maxl] 用于记录当前已选定的邮票面值 x[1:i] 能贴出的各种邮资所需的最少邮票张数。请将程 序补充完整。

#include<stdio.h>
#defineNN20
#definemaxint30000
#definemaxl500/* 邮资的最大值 */
int n,m,bestx[NN],x[NN],y[maxl],maxvalue=0;
void result()
{ 
	输出结果：最大值： maxvalue 及 最优解： bestx[1:n] （略）
}
void backtrace(inti,intr)
{
	int j,k,z[maxl];
	for(j=0;j<= ① ;j++)
	if(y[j]<m)
	for(k=1;k<=m-y[j];k++)
	if(y[j]+k<=y[ ② ])
	y[ ③ ]=y[j]+k;
	while(y[r]<maxint)r++;
	if(i>n)
	{
		if(r-1>maxvalue)
		{
			maxvalue= ④ ; 
			for(j=1;j<=n;j++)
			bestx[j]=x[j];
		}
		return;
	}
	for(k=0;k<maxl;k++)
	z[k]=y[k];
	for(j= ⑤ ;j<=r;j++)
	{
		x[i]=j;
		⑥ ;
		for(k=0;k<maxl;k++)
		y[k]=z[k];
	}
}
void main()
{
	int j;
	printf("inputn,m:\n");
	scanf( "%d%d",&n,&m);
	for(j=1;j<maxl;j++)
	y[j]=maxint;
	y[0]=0;x[0]=0;x[1]=1;
	backtrace(2,1);
	result();
}