NOIP真题题库 - 第28页

第541题

（格雷码， 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");
}

第542题

（连续邮资问题）某国发行了 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();
}

第543题

书架上有 4 本不同的书 A、B、C、D。其中 A 和 B 是红皮的， C和 D 是黑皮的。把这 4 本书摆在书架上，满足所有黑皮的书都排在一起的摆法有 _____ 种。满足 A 必须比 C 靠左，所有红皮的书要摆放在一起，所有黑皮的书要摆放在一起，共有 ______ 种摆法。

第544题

有 6 个城市，任何两个城市之间都有一条道路连接， 6 个城市两两之间的距离如下表所示，则城市 1 到城市 6 的最短距离为 _____________ 。

第545题

#include<iostream>
using namespace std;
int main()
{
  int i, a, b, c, d, f[4];
  for(i = 0; i < 4; i++) cin >> f[i]; 
  a = f[0] + f[1] + f[2] + f[3];
  a = a / f[0];
  b = f[0] + f[2] + f[3];
  b = b / a;
  c = (b * f[1] + a) / f[2];
  d = f[(b / c ) % 4];
  if(f[(a + b + c + d) % 4] > f[2])
    cout << a + b<< endl;
  else
    cout << c + d << endl;
  return 0;
}

输入： 9 19 29 39

输出： _______________

第546题

#include<iostream>
using namespace std;
void foo(int a, int b, int c)
{
  if(a > b)
    foo(c, a, b);
  else
    cout<<a<<','<<b<<','<<c<<endl;
}
int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  foo(a, b, c);
  return 0;
}

输入: 3 1 2

输出: __________

第547题

#include <iostream>
using namespace std;
void func(int ary[], int n ) 
{
  int i=0, j, x;
  j=n-1;
  while(i<j)
  {
  while (i<j&&ary[i]>0) i++;
  while (i<j&&ary[j]<0) j--;
  if (i<j)
  {
    x=ary[i];
    ary[i++]=ary[j];
    ary[j--]=x;
  }
  }
}
int main()
{
  int a[20], i, m;
  m=10;
  for(i=0; i<m; i++) 
  {
     in>>a[i];
  }
  func(a, m);
  for (i=0; i<m; i++)
  cout<<a[i]<<" ";
  cout<< endl;
  return 0;
}

输入： 5 4 -6 -11 6 -59 22 -6 1 10

输出： ___________________________________

第548题

#include<iostream>
#include<cstring>
using namespace std;
#define MAX 100 
void solve(char first[], int spos_f, int epos_f, char mid[], int spos_m, int epos_m)
{
  int i, root_m;
  if(spos_f > epos_f)
  return;
  for(i = spos_m; i <= epos_m; i++)
  if(first[spos_f] == mid[i])
  {
     root_m = i;
     break;
  }
  solve(first, spos_f + 1, spos_f + (root_m - spos_m), mid, spos_m, root_m - 1);
  solve(first, spos_f + (root_m - spos_m) + 1, epos_f, mid, root_m + 1, epos_m);
  cout << first[spos_f];
}
int main()
{
  char first[MAX], mid[MAX];
  int len;
  cin >> len;
  cin >> first >> mid;
  solve(first, 0, len - 1, mid , 0, len - 1);
  cout << endl;
  return 0;
}

输入： 7 ABDCEGF BDAGECF

输出： ______________________________

第549题

（字符串替换）给定一个字符串 S（S 仅包含大小写字母），下面的程序将 S 中的每个字母用规定的字母替换，并输出 S 经过替换后的结果。程序的输入是两个字符串，第一个字符串是给定的字符串 S，第二个字符串 S’由 26 个字母组成，它是 a-z 的任一排列，大小写不定， S’规定了每个字母对应的替换字母： S’中的第一个字母是字母 A 和 a 的替换字母，即 S 中的 A 用该字母的大写替换， S 中的 a 用该字母的小写替换； S’中的第二个字母是字母 B 和 b 的替换字母，即 S 中的 B用该字母的大写替换， S 中的 b 用该字母的小写替换；…… 以此类推。

#include <iostream>
#include <string.h>
char change[26], str[5000];
using namespace std;
void CheckChangeRule()
{
  int i;
  for (i = 0;i < 26;i ++)
  {
    if ( ① )
    change[i] -= 'A' - 'a';
  }
}
void ChangeString()
{
  int i;
  for (i = 0;i <strlen(str);i ++)
  {
     if ( ② )
       str[i] = change[str[i] - 'A'] -'a' + 'A';
     else
       ③
  }
}
int main()
{
   int i;
   cin >> str ;
   cin >> change;
   CheckChangeRule();
    ④
   cout << str << endl;
   return 0;
}

第550题

( 找第 k 大的数 ) 给定一个长度为 1,000,000 的无序正整数序列 , 以及另一个数 n (1<=n<=1000000), 然后以类似快速排序的方法找到序列中第 n 大的数（关于第 n 大的数：例如序列 {1 ，2，3，4，5，6} 中第 3 大的数是 4）。

#include <iostream>
using namespace std;
int a[1000001],n,ans = -1;
void swap(int &a,int &b)
{
  int c;
  c = a; a = b; b = c;
}
int FindKth(int left, int right, int n)
{
  int tmp,value,i,j;
  if (left == right) return left;
  tmp = rand()% (right - left) + left;
  swap(a[tmp],a[left]);
  value = ①
  i = left;
  j = right;
  while (i < j)
  {
     while (i < j && ② ) j --;
     if (i < j) {a[i] = a[j]; i ++;} else break;
     while (i < j && ③ ) i ++;
     if (i < j) {a[j] = a[i]; j - -;} else break;
  }
  ④
  if (i < n) return FindKth( ⑤ );
  if (i > n) return ⑥
  return i; 
}

第551题

有 6 个城市，任何两个城市之间都有一条道路连接， 6 个城市两两之间的距离如下表所示，则城市 1 到城市 6 的最短距离为 _____________ 。

第552题

书架上有 21 本书，编号从 1 到 21 ，从其中选 4 本，其中每两本的编号都不相邻的选法一共有 ______ 种。

第553题

#include<stdio.h>
int main()
{
  int i, a, b, c, d, f[4];
  for(i = 0; i < 4; i++)
   scanf("%d", &f[i]);
  a = f[0] + f[1] + f[2] + f[3];
  a = a / f[0];
  b = f[0] + f[2] + f[3];
  b = b / a;
  c = (b * f[1] + a) / f[2];
  d = f[(b / c ) % 4];
  if(f[(a + b + c + d) % 4] > f[2])
    printf("%d\n", a + b);
  else
    printf("%d\n", c + d);
  return 0;
}

输入： 9 19 29 39

输出： _______________

第554题

#include<stdio.h>
void foo(int a, int b, int c)
{
  if(a > b) 
   foo(c, a, b);
  else
   printf("%d,%d,%d\n", a, b, c);
}
int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  foo(a, b, c);
  return 0;
}

输入： 2 1 3

输出 :__________

第555题

#include<stdio.h>
void f(int a, int b, int c)
{
  printf("%d%d%d/", a, b, c);
  if(a == 3 && b == 2 && c == 1)
return;
  if(b < c)
    f(a, c, b);
  else if(a < b)
  {
    if(a < c)
      f(c, a, b);
    else
      f(b, c, a);
  }
}
int main()
{
  int a, b, c;
  scanf("%d %d %d", &a, &b, &c);
  f(a, b, c);
  printf("\n");
  return 0; 
}

输入 : 1 3 2

输出： ________________________

第556题

#include <stdio.h>
#include <string.h>
int i,j,len;
char s[50];
int main()
{
  scanf("%s", s);
  len = strlen(s);
  for (i = 0;i < len; ++i)
  {
     if (s[i] >= 'A' && s[i] <= 'Z') s[i] -= 'A' - 'a';
  }
  for (i = 0;i < len; ++i)
  {
     if (s[i] < 'x') s[i] += 3; else s[i] += -23;
  }
  printf("%s/", s);
  for (j = 1;j < 4;j ++)
  {
     for (i = 0;i < len-j; i = i + j)
     {
        s[i] = s[i + j] ;
     }   
  }
  printf("%s\n", s);
  return 0;
}

输入： ABCDEFGuvwxyz

输出： __________________________

第557题

( 找第 k 大的数 ) 给定一个长度为 1,000,000 的无序正整数序列，以及另一个数 n(1<=n<=1000000) ，接下来以类似快速排序的方法找到序列中第 n 大的数（关于第 n 大的数：例如序列 {1 ，2， 3， 4，5，6} 中第 3 大的数是 4）。

#include <stdlib.h>
#include <stdio.h>
int a[1000001],n,ans = -1;
void swap(int *a,int *b)
{
  int c;
  c = *a; *a = *b; *b = c;
}
int FindKth(int left, int right, int n)
{
  int tmp,value,i,j;
  if (left == right) return left;
  tmp = rand()% (right - left) + left;
  swap( &a[tmp], &a[left] );
  value = ①
  i = left;
  j = right;
  while (i < j)
  {
    while (i < j && ② ) j --;
    if (i < j) {a[i] = a[j]; i ++;} else break;
    while (i < j && ③ ) i ++;
    if (i < j) {a[j] = a[i]; j - -;} else break;
  }
   ④
  if (i < n) return FindKth( ⑤ );
  if (i > n) return ⑥
  return i;
}
int main()
{
  int i; 
  int m = 1000000;
  for (i = 1;i <= m;i ++)
   scanf("%d", &a[i]);
  scanf("%d", &n);
  ans = FindKth(1,m,n);
  printf("%d\n", a[ans]);
  return 0;
}

第558题

（矩阵中的数字）有一个 n*n(1<=n<=5000) 的矩阵 a，对于 1<=i < n,1<=j<=n, a[i,j] < a[i + 1,j] a[j,i] < a[j,i+1] 。即矩阵中左右相邻的两个元素，右边的元素一定比左边的大。上下相邻的两个元素，下面的元素一定比上面的大。给定矩阵 a 中的一个数字 k，找出 k 所在的行列（注意：输入数据保证矩阵中的数各不相同）。

#include <stdio.h>
int n,k,answerx,answery;
int a[5001][5001];
void FindKPosition()
{
  int i = n,j = n;
  while (j > 0)
  {
    if (a[n][j] < k) break;
    j --;
  }
    ①
  while (a[i][j] != k)
  {
    while ( ② && i > 1) i --;
    while ( ③ && j <= n) j ++;
  }
    ④
    ⑤
}
int main() 
{
  int i,j;
  scanf( "%d", &n );
  for (i = 1;i <= n;i ++)
  for (j = 1;j <= n;j ++)
  scanf( "%d", &a[i][j]);
  scanf( "%d", &k );
  FindKPosition();
  printf("%d %d\n", answerx, answery);
  return 0;
}

第559题

小陈现有2个任务A，B要完成，每个任务分别有若干步骤如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何时候，小陈只能专心做某个任务的一个步骤。但是如果愿意，他可以在做完手中任务的当前步骤后，切换至另一个任务，从上次此任务第一个未做的步骤继续。每个任务的步骤顺序不能打乱，例如……a2->b2->a3->b3……是合法的，而……a2->b3->a3->b2……是不合法的。小陈从B任务的b1步骤开始做，当恰做完某个任务的某个步骤后，就停工回家吃饭了。当他回来时，只记得自己已经完成了整个任务A，其他的都忘了。试计算小陈饭前已做的可能的任务步骤序列共有______ 种。

第560题

有如下的一段程序：

1. a=1;

2. b=a;

3. d=-a;

4. e=a+d;

5. c=2*d;

6. f=b+e-d;

7. g=a*f+c;

现在要把这段程序分配到若干台（数量充足）用电缆连接的PC上做并行执行。每台PC执行其中的某几个语句，并可随时通过电缆与其他PC通讯，交换一些中间结果。假设每台PC 每单位时间可以执行一个语句，且通讯花费的时间不计。则这段程序最快可以在 _______单位时间内执行完毕。注意：任意中间结果只有在某台PC上已经得到，才可以被其他PC 引用。例如若语句4和6被分别分配到两台PC上执行，则因为语句6需要引用语句4的计算结果，语句6必须在语句4之后执行。

训练

NOIP真题

知识点标签