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

第21题

（子集划分）将 n 个数{1，2，…，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=6,r=3 时，S(6,3)= _____________。 

（提示：先固定一个数，对于其余的 5 个数考虑 S(5,3)与 S(5,2)，再分这两种情况对原固定的数 进行分析）。

第22题

（最短路线）某城市 的街道是一个很规整的矩形网格（见下图），有 7 条南北向的纵街，5 条东 西向的横街。现要从西南角的 A 走到东北角的 B，最短的走法共有多少种？_________________.

第23题

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

输入：6 6 5 5 3 输出：_______________

第24题

#include <iostream.h>
void fun(int *a,int *b)
{
 int *k;
 k=a; a=b; b=k;
}
void main( )
{
 int a=3, b=6, *x=&a, *y=&b;
 fun(x,y);
 cout<<a<<","<<b<<endl;
}

输出:____________________

第25题

#include <iostream.h>
#include <iomanip.h>
#include "math.h"
void 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)
	{
		cout<<setw(4)<<i; t++;
		if(t%10==0) cout<<endl;
	}
	cout<<endl;
}

输出： _______________________________

第26题

#include <iostream.h>
#include "ctype.h"
void expand(char s1[],char s2[])
{ 
	int i,j,a,b,c;
	j=0;
	for(i=0;(c=s1[i])!='\0';i++)
	if(c=='-')
	{ 
		a=s1[i-1]; b=s1[i+1];
		if ( isalpha(a)&&isalpha(b) || isdigit(a)&&isdigit(b) )
		//函数 isalpha(a)用于判断字符 a 是否为字母，isdigit(b) 用于判断字符 b 是否为数字，如果是，返回 1，否则返回 0
        { 
        j--;
        do 
		s2[j++]=a++;
		while(tolower(a)<tolower(s1[i+1]));
		} 
		else s2[j++]=c;
	}
	else s2[j++]=c;
	s2[j]='\0';
}
void main()
{ 
	char s1[100],s2[300];
	cin>>s1;
	expand(s1,s2);
	cout<<s2<<endl;
}

输入：wer2345d-h454-82qqq 输出：____________________________________

第27题

（求字符串的逆序）下面的程序的功能是输入若干行字符串，每输入一行，就按逆序输出该行，最后键入-1 终止程序。

请将程序补充完整。

#include <iostream.h>
#include <string.h>
int maxline=200,kz;
int reverse(char s[])
{
	int i,j,t;
 	for(i=0,j=strlen(s)-1; i<j; ① ， ② )
 	{
 		t=s[i]; s[i]=s[j]; s[j]=t;
	}
 	return 0;
}
void main()
{
 	char line[100];
 	cout<<"continue? -1 for end."<<endl;
 	cin>>kz;
 	while( ③ )
 	{
  	cin>>line;
 	④ ;
 	cout<<line<<endl;
 	cout<<"continue? -1 for end."<<endl;
 	cin>>kz;
 	} 
}

第28题

（棋盘覆盖问题）在一个 k k 2 × 2 个方格组成的棋盘中恰有一个方格与其他方格不同（图中标记为 -1 的方格），称之为特殊方格。现用 L 型（占 3 个小格）纸片覆盖棋盘上除特殊方格的所有部分，各纸 片不得重叠，于是，用到的纸片数恰好是(4 −1)/ 3 k 。在下表给出的一个覆盖方案中，k=2，相同的 3 个数字构成一个纸片。 

下面给出的程序是用分治法设计的，将棋盘一分为四，依次处理左上角、右上角、左下角、右下角， 递归进行。请将程序补充完整。

#include <iostream.h>
#include <iomanip.h>
int board[65][65],tile; // tile 为纸片编号
void chessboard(int tr,int tc,int dr,int dc,int size)
// dr,dc 依次为特殊方格的行、列号
{
	int t,s;
 	if (size==1)
	 ⑤ ;
	t=tile++;
	s=size/2;
	if( ⑥ )
		chessboard(tr,tc,dr,dc,s);
	else
	{
		board[tr+s-1][tc+s-1]=t;
		⑦ ;
	}
	if(dr<tr+s && dc>=tc+s)
		chessboard(tr,tc+s,dr,dc,s);
	else
	{
		board[tr+s-1][tc+s]=t;
		⑧ ;
	}
	if(dr>=tr+s && dc<tc+s)
		chessboard(tr+s,tc,dr,dc,s);
	else 
	{	
		board[tr+s][tc+s-1]=t;
		⑨ ;
	}
	if(dr>=tr+s && dc>=tc+s)
		chessboard(tr+s,tc+s,dr,dc,s);
	else
	{
		board[tr+s][tc+s]=t;
		⑩ ;
	}
}
void prt1(int b[][65],int n)
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		cout<<setw(3)<<b[i][j];
		cout<<endl;;
	}
}
void main()
{
	int size,dr,dc;
	cout<<"input size(4/8/16/64):"<<endl;
	cin>>size;
	cout<<"input the position of special block(x,y):"<<endl;
	cin>>dr>>dc;
	board[dr][dc]=-1;
	tile++;
	chessboard(1,1,dr,dc,size);
	prt1(board,size);
}