2023年c语言复赛题

信息学奥赛复赛练习题

1.模拟开关(题目名称：moni.bas)(12分)

［题目描述］:有N盏电灯排成一行，依次编号为1,2,3,…,N。现各有一个开关，开始灯都亮着的。现在尚有N个人，第一人走过来

依次把1和1的倍数电灯的开关都拉一下。第三个人走过来依次把3和3的倍数的开关都拉一下，第五个人走过来依次把5和5的倍数的

开关都拉一下(按奇数的规律)，…问最后都有哪些灯是关着的？

［输入文献］文献名：moni.in

文献中只有一行，包含1个整数N(其中5<N<30)

［输出文献］文献名：moni.out

文献中共有若干行，每一行一个数据，分别为那些关着的灯泡的编号。

规定：每一行的输出数据都从第一列开始。

［样例输入］:moni.in的内容为:

10

［样例输出］：moni.out的内容为：

1

2

4

8

9

main()

{

inti,n,s,x;

inta［1000］;

scanf("%cT,&n);

for(i=1;i<n;i++)

a［i］=1；

x=1；

while(x<=n)

s=0;

while(s<=n)

{s=s+x;

a[s]=1-a[s];

)

x=x+2;

)

s=0;

for(i=1;i<n;i++)

if(a[i]==O)

{printf("%d",i);s=s+1;

}

if(s==O)printf("O");

)

3.【问题描述-明明的随机数】

明明想在学校中请一些同学一起做问卷调查，为了实验的客观性，他先用计算机生成了

N个1JIJ1000之间的随机整数，(NR00),对于其中反复的数字，只保存一个，把其余相

同的数去掉，不同的数相应着不同的学生的学号。然后再把这些数从小到大排序，按照排好

的顺序去找同学做调查。请你协助明明完毕“去重”与“排序”的工作。

【输入文献】

输入文献random.in有2行，第1行为1个正整数，表达所生成的随机数的个数：N

第二行有N个用空格隔开的正整数，为所产生的随机数。

【输出文献】

输出文献random.out也是2行，第1行为1个正整数M,表达不相同的随机数的个数。

第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

【输入样例】

10

2040326740208930040015

【输出样例】

8

152032406789300400

〃本题重要是考察对排序算法的掌握，只但是外加了一个去重的操作。本题的算法有很多，我们在考试时，时间紧，题目难度大。假

如我们能用最简朴的思维方式解决问题的话，就不一定把很多的时间放在代码执行效率的优化问题上。有时候牺牲一点空间(内存)和时

间对于获取更多的考试时间是非常有必要的。本题最简朴的思想方法，就是根据题目规定，先对给定的一组数据进行排序，排序的方法可

以使用最简朴的冒泡算法来完毕。由于本题的输出结果规定我们必须先记录出不反复数据的个数，所以当数据排序之后，我们可以先对所

有的数据遍历一次，这一次遍历的目的就是让我们记录出不反复数据的个数，并将其输出。最后，我们还需进行一次遍历，这次遍历用于

打印出排序之后不反复的所有数据结果.

7

include

intmain()

(

FILE*fp1,*fp2;

intN,M=0;

inti,j;

inta;

intnum[100];〃根据题口所给的数据规模定义数组的大小

if((fp1=fopen(,'random.in,,,,,r,,))==NULL)

(

printf("cannotopenfile\nM);

return0;

)

fscanf(fp1,”％d”,&N);//输入随机数的个数

for(i=0;i<N;i++)

fscanf(fp1,”％d”,&num[i]);〃将己知的随机数存放到初始数组中

for(i=0;i

for(j=i+1;j<N;j++)

if(num[i]>num[j])

a=num[i];

num[i]=num[j];

num[j]=a;

)

)

fp2=fopen("random.out","w");〃打开写文献的指针

for(i=0;i

(

if(i>0&&num[i]==num/1])〃思考一下这个去重的操作中为什么有i>0这个条件

continue;

M++;

)

fprintf(fp2J%d\rT,M);〃在结果文献中打印出不反复数据的个数并键入一个回车符

for(i=0;i

(

计(i>0&&num[i]==num/1])〃思考一下这个去重的操作中为什么有i>0这个条件

continue;

fprintf(fp2；'%d",num[i]);

)

fclose(fpl);

fclose(fp2);

return0;

4.【问题描述-开心的金明】

金明今天很开心，家里购置的新房就要领钥匙了，新房里有•间他自己专用的很宽敞的房间。更让他快乐的是，妈妈昨天对他说：“你

的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行，今天一早金明就开始做预算，但是他想买的东西太多了，肯

定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表达，第5等最重要。他还从因特网上查

到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品，编号依次为，

j1,j2.......jk,则所求的总和为:v[j1]*w[j1]+vD2]*w[j2]+……+v[jk]*w[jk]（其中*为乘号）

请你帮助金明设计一个满足规定的购物单。

【输入文献】

输入文献happy.in的第1行，为两个正整数，用一个空格隔开：

Nm（其中N（＜30000）表达总钱数，m（＜25）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为卜1的物品的基本数据，每行有2个非负整数

vp（其中v表达该物品的价格（v＜10000）,p表达该物品的重要度（1-5））

【输出文献】

输出文献happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（＜）

【输入样例】

10005

8002

4005

3005

4003

2002

【输出样例】

3900

背包问题的解决办法有很多，但是都不太容易理解，本算法采用穷举法结合二进制数据的排列来穷举所有价值组合

重要思想：

根据物品的个数先计算出所有物品排列组合的排列数，每件物品取为1,不取为0

假设用n个物品，从n个物品中任意取出若干个的最大组合次数为：2叮-1种，因此只要穷举出2"n-1种组合情况，计算出其中的最

大价值组合，就是本题的算法

本题的关键是计算出相应的二进制数据列，每一种组合相应一个二进制数列，然后根据二进制数组的0,1值来形成物品不同的组合,

从而计算出当前二进制组合下的价值和，通过2、-1比较后就能计算出最大价值

#include

intmain()

{

intN,m;//其中N(<30000)表达总钱数，m(<25)为希望购买物品的个数

intbi[24];//用于每次取物组合的0,1序列

intwi[24];〃用于存放每件物品的价格

intvi[24];//用于存放每件物品的重要度

inti,j,n,num;

intMaxValueSum=0,ValueSum=0,TotalWeight=0;

longk=1;

FILE*fp1,*fp2;

fscanf(fp1,"%d%d",&N,&m);//读取数据：其中N(<30000)表达总钱数，m(<25)为希望购买物品的个数

for(i=0;i<m;i++)

(

fscanf(fp1,"%d%d”,&wi[i],&vi[i]);〃读取数据：将各个物品的价格和重要度分别存放到相应的数组当中

)

n=m;〃将物品的总个数存放到一个中间变量中以方便计算

/*一方面计算出n种物品取舍组合的总数*/

while(n>0)

(

k=2*k;

n-;

)

k=k-1;〃求得k的值，即为n种物品取舍的(0,1)组合总数25-1

n=m;〃恢复n的值以便下面计算所用

for(i=1；iv=k;i++)//该循环的功能是循环遍历k种组合，比较并计算出”价值和“最大的组合

(

〃第1步，必须求出每次取舍组合的二进制序列

num=i;

/*****以下这段代码段完毕将num转换成n位二进制数组的过程*****/

while(num!=O)〃其中第一个while循环完毕了有效数值的转换

(

y=num%2;

num=num/2;

bi[n-1]=y;

n-；

)

while(n>=0)〃第二个while循环用于将二进制序列的高位置0

(

bi[n]=O;

n-；

)

/*****以上这段代码段完毕将num转换成n位二进制数组的过程*****/n=m;〃恢复n的值以便下面计算所用

〃第2步：计算出当前取舍组合(0,1)中的价值和，并于最大价值和进行比较，找到新的最大的价值和

for(j=0;j<n;j++)

(

讦(bi[j]==0)〃当bi[j]==0,表达当前物品并没有取操作，因此直接跳转考察下一个物品的取舍状态

continue;

TotalWeight+=wi[j];

ValueSum+=wi[j]*vi[j];

)〃循环结束后，可求得本次组合的总价格Totalweight和总价值和ValueSum

if(TotalWeight>N)〃一方面考察计算出来的总价格是否超过了允许的总价格

(

TotalWeight=0;//计算下一趟组合之前清0

ValueSum=O;〃计算下一趟组合之前清0

continue;〃当计算出本次组合的总价格超过既定总价格时，continue到下一趟组合(即跳转到外层for循环)

)

if(ValueSum>MaxValueSum)〃在上一步保证总价格没有超过既定价格的条件下，判断本次组合的价值和是否超过最大的价值和

MaxValueSum=ValueSum;

TotalWeight=0;〃计算下一趟组合之前清0

ValueSum=O;〃计算下一趟组合之前清0

)

fp2=fopen("bag.out","w");

fprintf(fp2,"％d",MaxValueSum);〃输出最大的价值和的结果

fclose(fpl);

fclose(fp2);

return0;

)

5.【问题描述-猴子选大王】：M只猴子要选大王，选举办法如下：所有猴子按1-M编号围坐一圈，从1号开始按顺序1,2,,,K

报数，凡报到K的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。M和K由输入文献提供，规定在

输出文献中打印出最后剩下的猴子的编号。数据规模(Mv=1000,Kv=10)

【输入文献】

输入文献monkey.in的第1行，为两个正整数，用一个空格隔开：

MK

【输出文献】

输出文献monkey.out只有一个正整数，输出最后一个猴子的编号

【输入样例】

73

【输出样例】

4

这个问题记得给大家上机练习中做过，即对报数问题的求解。在我做完这个题口的时候，我其实并不知道这就是顶顶有名的约瑟夫问

题。之后有个学生(陈亮宇)告诉我才知道这是一个据说是由古罗马著名史学家Josephus提出的问题演变而来的。称之为约瑟夫问题。

很多资料上对这一问题解释得过于繁杂，实现起来不好理解。在这里介绍一下本人的一些想法以供大家参考。

这个题目其实就是一种编程的经验问题。我们可以假设猴子就位的状态用1表达，把猴子离开的状态用0表达。那么我们就可以用

一个a[M]的数组来存放M个猴子是否就位的状态。我们可以一边报数一边遍历该数组，每碰到第K个1时，就把当前位置的1变为0,

表达当前位置的猴子已经出局了。一直循环遍历到我们的状态数组只有•个1的时候，这个存放1的数组下标再加上1(由于数组下标是

由。开始的，所以要加1)即为选出的大王的编号。想法很简朴，现在关键的问题是如何解决当报数到第M个猴子的时候如何使得下一个

报数重新回到第1个猴子处，也就是如何使用一维数组来解决环型问题的求解技巧。大家想一下当我们的猴子围成圈坐的时候，问题其实

由简朴的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列•假设p为当前数组某一元素的下标，对于一维数组来

说，我们只要p++就可以移动到下一个元素的位置上。那么当p=M时，假如我们直接使用p++的话，p的值就超过了数组的最大长

度，我们想要的是P++之后等于0。那么如何实现呢？解决环型数组循环遍历元素的方法：对于环型数组移动下标时，我们假如每次在p++

之后再加上p=p%M的话就能解决先前碰到的越界的问题。下标变量p也就可以周而复始的在a[M]中顺时针地循环移动了.请认真查阅以

下程序源代码分析，关键掌握环型数组的遍历！

程序参考：

#include

intmain()

(

intn;

intn1=0;〃表达报数记数器

intp=0;〃指向当前数组元素的下标

intNumOfKing;//大王的编号

intM,K;//M为已知猴子总数,K为报数的量级

inta[1000];

FILE*fp1,*fp2;

fp1=fopen("monkey.in","r");

fscanf(fp1,"%d%d”,&M,&K);//从文献中读取已知数据

n=M;〃M为圈的长度，即初始猴子数

for(inti=O;i<n;i++)

a[i]=1;〃初试话状态数组，所有猴子都是就位的

while(n>1)〃n当前圈内还剩下的猴子数，控制循环在圈内只剩下一只猴子时结束循环

(

while(n1

(

if(a[p]==1)//假如当前位置有猴子

(

n1++;〃报数记数器加1

if(n1==K)

a[p]=O;〃将第K次报数的猴子置0,表达退出圈子

)

P++；//移动到下一个位置

p=p%M;〃这一步是为了解决循环数组成环遍历的目的

}

n1=0;〃当报完K个数后将报数记数变量清0,以备下次重新报数

n--;〃当报完一轮后总猴子数减1

)

for(inti=0;i

(

if(a[il==1)

(

NumOfKing=i+1;

break;

)

)

fp2=fopen("monkey.out","w");

fpnntf(fp2,H%d",NumOfKing);

fclose(fpl);

fclose(fp2);

return0;

6.1问题描述:合并果子】

在一个果园里，多多已经将所有的果子打了下来，并且按果子的不同种类提成了不同的堆.多多决定把所有的果子合成一堆.

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和.可以看出，所有的果子通过n-1次合并之后,就只剩

下一堆了.多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和.

由于还要花大力气把这些果子般回家，所以多多在合并果子时要尽也许地节省体力.假定每个果子重量都是1,并且己知果子的种类数

和每种果子的数目,你的任务是设计出合并的顺序方案，使多多花费的体力最少，并输出这个最小的体力花费值.

例如:有3种果子，数目依次为1,2,9.可以先将1,2堆合并，新堆数目为3,花费体力为3.接着，将新堆与原先的第三堆合并，又得到新的堆，

数口为12,花费体力为12.所以多多总共花费体力为3+12=15.可以证明15为最小的体力花费值.

【输入文献】

输入文献fruit.in涉及两行，第一行是一个整数n(1Vnv30000),表达果子的种类数.第二行包含n个整数，用空格分隔，第i个整数

ai(Eais20230)是第i种果子的数目.

【输出文献】

输出文献fruit.out涉及一行，这一行只包含一个整数,也就是最小的体力花费值.

【输入样例】

3

219

【输出样例】

15

【解题思绪】

为了使最终的体力花费值最小，我们应当每一次都选择最小的两堆果子合并，使每次合并花费的体力值最小.我们可以按照以下算法过程

来解决问题：

1.读入每堆果子的数目a[i](a[i]为第i堆果子的数目).

2.将果子数目按递增顺序进行排序.

3.合并数目最少的两堆果子,并增长体力花费值到total变量

4.在果子序列中清除合并的两堆果子数目,增长合并后的果子数目.

5.反复环节2-4,直到所有果子合并为一堆.

6.输出total

问题的关键在于第4步,如何在数组中清除合并的两堆果子，并增长合并后的果子数到数组中，然后再完毕剩余果子的重排序.解决这个

问题的方法有很多，可以在同一数组中解决，也可以运用此外一个空数组来重新存放每次合并之后的堆.建议大家考虑在同一数组中如何解决

这样的问题.

【基本算法练习部分】

1.在实际应用中我们经常碰到这样的问题,在解决•些高精度的计算时，由于数据类型字长的限制，使得对一些海量数据不能直接用某

种数据类型来定义，比如7654321,已经超过了我们基本数据类型的范围，那么我们如何解决这些高精度的海量数据呢?在解决这样的数据时,

我们一般的方法是一方面定义一个字符数组来存放将这些高精度的字符数据，然后将其每一位字符数据转化为相应的整型，并重新保存在一

个整形数组中.当所有的字符数组转存到整型数组后，我们就可以对其进行运算了.

试写一个程序，将字符串”7654321”,转换成相应的整数并输出.

提醒:字符数字'0'-'9'相应的ASCII分别为48-57