2024年c语言复赛题

信息学奥赛复赛练习题

1.模拟开关（题目名称moni.bas）（12分）［题目描述］有N盏电灯排成一行，依次编号为1,2,3,...,N现各有一个开关，开始灯都亮着的目前尚有N个人，第一人走过来依次把1和1的倍数O电灯的开关都拉一下第三个人走过来依次把3和3的倍数的开关都拉一下，第五个人走过来依次把5和5的倍数的开关都拉一下（按奇数的规律），…问最后都有哪些灯是关着的？［输入文献］文献名moni.in文献中只有一行，包括1个整数N（其中5N30）［输出文献］文献名:moni.out文献中共有若干行，每一行一个数据，分别为那些关着的灯泡的编号要求每一行的输出数据都从第一列开始［样例输入］:moni.in的内容为10［样例输出］:moni.out的内容为12489（）main（int i,n,s,x;［］int a1000;％scanf“d”,n;continue;〃当计算出本次组合的总价格超出既定总价格时，continue到下一趟组合即跳转到外层for循环计ValueSumMaxValueSum〃在上一步确保总价格没有超出既定价格的条件下，判断本次组合的价值和是否超出最大的价值和MaxValueSum=ValueSum;TotalWeight=0;〃计算下一趟组合之前清0ValueSum=O;//计算下一趟组合之前清0fp2=fopenbag.out,,,,w;fprintffp2J%d”,MaxVMueSum;〃输出最大的价值和的成果fclosefpl;fclosefp2;return0;

5.【问题描述•猴子选大王】M只猴子要选大王，选举措施如下所有猴子按1-M编号围坐一圈，从1号开始按次序1,2,,,I报数，凡报到K的猴子退出到圈外，如此循环报数，直到圈内只剩余一只猴子时，这只猴子就是大王M和K由输入文献提供，要求在输出文献中打印出最后剩余的猴子的编号数据规模Mv=1000,Kv=10【输入文献】输入文献monkey.in的第1行，为两个正整数，用一个空格隔开M K【输出文献】输出文献monkey.out只有一个正整数，输出最后一个猴子的编号【输入样例】【输出样例】4这个问题记得给大家上机练习中做过，即对报数问题的求解在我做完这个题目标时候，我其实并不懂得这就是顶顶有名的约瑟夫问题之后有个学生（陈亮宇）告诉我才懂得这是一个据说是由古罗马知名史学家Josephus提出的问题演变而来的称之为约瑟夫问题诸多资料上对这一问题解释得过于繁杂，实现起来不好了解在这里简介一下本人的某些想法以供大家参考这个题目其实就是一个编程的经验问题我们能够假设猴子就位的状态用1表示，把猴子离开的状态用0表示那么我们就能够用一个a[M]的数组来存储M个猴子是否就位的状态我们能够一边报数一边遍历该数组，每遇到第K个1时，就把目前位置的1变为0,表示目前位置的猴子已经出局了一直循环遍历到我们的状态数组只有一个1的时候，这个存储1的数组下标再加上1（因为数组下标是由开始的，因此要加1）即为选出的大王的编号想法很简单，目前核心的问题是怎样处理当报数到第M个猴子的时候怎样使得下一个报数重新回到第1个猴子处，也就是怎样使用一维数组来处理环型问题的求解技巧大家想一下当我们的猴子围成圈坐的时候，问题其实由简单的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列假设p为目前数组某一元素的下标，对于一维数组来说，我们只要p++就能够移动到下一个元素的位置上那么当p=M时，假如我们直接使用p++的话，p的值就超出了a[M]数组的最大长度，我们想要的是p++之后等于0那么怎样实现呢？处理环型数组循环遍历元素的措施对于环型数组移动下标时，我们假如每次在p++之后再加上p=p%M的话就能处理先前遇到的越界的问题下标变量p也就能够周而复始的在a[M]中顺时针地循环移动了.请仔细查阅如下程序源代码分析，核心掌握环型数组的遍历！程序参考#include（）（int mainintn;int p=0;〃指向目前数组元素的下标int NumOfKing;//大王的编号int M,K;//M为已知猴子总数,K为报数的量级int a

[1000];FILE*fp1,*fp2;fp1=fopen,monkey.in,,,r;fscanffp1J%d%d”,M,K;〃从文献中读取已知数据n=M;//M为圈的长度，即初始猴子数forint i=0;in;i++初试话状态数组，所有猴子都是就位的whilen1//n R前圈内还剩余的猴子数，控制循环在圈内只剩余一只猴子时结束循环{whilen1ifa[p]==1〃假如目前位置有猴子n1++;〃报数记数器加1ifn1==Ka[p]=0;〃将第K次报数的猴子置0,表示退出圈子P++；〃移动到下一个位置p=p%M;//这一步是为了处理循环数组成环遍历的目标n1=0;〃当报完K个数后将报数记数变量清0,以备下次重新报数n-;〃当报完一轮后总猴子数减1forint i=0;iifa[i]==1NumOfKing=i+1;break;fp2=fopenmonkey.out,w,;fprintffp2；,%d,,,NumOfKing;fclosefpl;fclosefp2;return0;

6.【问题描述:合并果子】在一个果园里，多多已经将所有的果子打了下来，并且按果子的不一样种类提成了不一样的堆,多多决定把所有的果子合成一堆.每一次合并，多多能够把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和.能够看出，所有的果子通过n-1次合并之后,就只剩余一堆了,多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和.因为还要花大力气把这些果子般回家，因此多多在合并果子时要尽也许地节约体力,假定每个果子重量都是1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案，使多多花费的体力最少，并输出这个最小的体力花费值.例如:有3种果子，数目依次为

129.能够先将•1,2堆合并，新堆数目为3,花费体力为

3.接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12,花费体力为

12.因此多多总共花费体力为3+12=

15.能够证明15为最小的体力花费值.【输入文献】输入文献fru比in包括两行，第一行是一个整数n（14展30000）,表示果子的种类数.第二行包括n个整数，用空格分隔，第i个整数ai（1与区0）是第i种果子的数目.【输出文献】输出文献frWt.out包括一行，这一行只包括一个整数,也就是最小的体力花费值.【输入样例】3219【输出样例】15【解题思绪】为了使最后的体力花费值最小，我们应当每一次都选择最小的两堆果子合并，使每次合并花费的体力值最小.我们能够按照如下算法过程来处理问题

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

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

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

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

0.

5.重复步骤2・4,直到所有果子合并为一堆.6,输出total问题的核心在于第4步,怎样在数组中清除合并的两堆果子，并增加合并后的果子数到数组中，然后再完成剩余果子的重排序.处理这个问题的措施有诸多，能够在同一数组中处理，也能够利用另外一个空数组来重新存储每次合并之后的堆.提议大家考虑在同一数组中怎样处理这么的问题.【基本算法练习部分】

1.在实际应用中我们常常遇到这么的问题,在处理某些高精度的计算时，因为数据类型字长的限制，使得对某些海量数据不能直接用某种数据类型来定义，例如7654321,已经超出了我们基本数据类型的范围，那么我们怎样处理这些高精度的海量数据呢？在处理这么的数据时,我们一般的措施是首先定义一个字符数组来存储将这些高精度的字符数据，然后将其每一位字符数据转化为对应的整型，并重新保存在一个整形数组中.当所有的字符数组转存到整型数组后，我们就能够对其进行运算了.试写一个程序，将字符串”7654321”,转换成对应的整数并输出.提示:字符数字对应的ASCII分别为48-57例如字符数字6,转换成整型数字6的措施如下Int k=6-48;〃k的值即为6#define lim6555int a

[1000],b

[1000];void sortintx,int yint i,j,k,t;i=x;j=y;k=a[i];t=x;doifivj{a[t]=aO];t=j;}whileijk=a[i]；i++ifivj{a[t]=a[i];t=i;}whilei!=j;a[t]=k;ifxifi+1int mminint i,int j,int k{int min;min=i;ifj ifkreturn min;int main{inti,j,k,m,n,head,tail,ans;％scanf”cT,n;fori=1;i=n;i++；scanf%d,a[i]fori=1;i=n;i++b[i]=lim;a[n+1]=lim;a[n+2]=lim;sort1,n;j=1;head=k;fori=1;ivn;i++k=mminb[head]4-b[head+1],b[head]+a[j],a[j]+a[j+1];tail++;a[tail]=k;ans+=b[tail];ifk==b[head]+b[head+1]head+=2;else ifk=b[head]+b[head]+a[j]{head++;j++;}else j+=2;printfH%d\n,ans;systemnpauseM;/j/jkx/j/jk=a[j]v/n;i++；v/n j++/m;i++v/N;j++/N;i++/L,而是iv=Lv/n;i++/n;i++fori=1;in;i++；a[i]=1；x=1whilex=ns=0;whiles=n{s=s+x;a[s]=1-a[s];x=x+2;s=0;fori=1;in;i++ifa[i]==O{printfH%d n,i;s=s+1;ifs==O printf,O;

3.1问题描述■明明的随机数】明明想在学校中请某些同学一起做问卷调查，为了试验的客观性，他先用计算机生成了N个1到1000之间的随机整数，N100,对于其中重复的数字，只保存一个，把其他相同的数去掉，不一样的数对应着不一样的学生的学号然后再把这些数从小到大排序，按照排好的次序去找同学做调查请你协助明明完成“去重”与“排序”的工作【输入文献】输入文献random.in有2行，第1行为1个正整数，表示所生成的随机数的个数N第二行有N个用空格隔开的正整数，为所产生的随机数【输出文献】输出文献random.out也是2行，第1行为1个正整数M,表示不相同的随机数的个数第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数【输入样例】102040326740208930040015【输出样例】8152032406789300400/*本题重要是考查对排序算法的掌握，只不过外加了一个去重的操作本题的算法有诸多，我们在考试时，时间紧，题目难度大假如我们能用最简单的思维方式处理问题的话，就不一定把诸多的时间放在代码执行效率的优化问题上有时候牺牲一点空间（内存）和时间对于获取更多的考试时间是非常有必要的本题最简单的思想措施，就是依照题目要求，先对给定的一组数据进行排序，排序的措施能够使用最简单的冒泡算法来完成因为本题的输出成果要求我们必须先统计出不重复数据的个数，因此当数据排序之后，我们能够先对所有的数据遍历一次，这一次遍历的目标就是让我们统计出不重复数据的个数，并将其输出最后，我们还需进行一次遍历，这次遍历用于打印出排序之后不重复的所有数据成果.*/includeint mainintN,M=O;int ij;int a;int num

[100];//依照题目所给的数据规模定义数组的大小iffp1=fopennrandom.in,,,r==NULLprintf“cannot openfile\nH;return0;fscanffp1J%d”,N;//输入随机数的个数fori=0;iN;i++fscanffp1J%d”,num[i];〃将已知的随机数存储到初始数组中fori=0;iforj=i+1;jN;j++ifnum[i]num[j]a=num[i];num[i]=num[j];num[j]=a;fp2=fopen”random.outJw;//打开写文献的指针fori=0;iifi0num[i]==num[i-1]〃思考一下这个去重的操作中为何有i0这个条件continue;M++;fprintffp2J%d\n“,M;//在成果文献中打印出不重复数据的个数并键入一个回车符fori=0;i{ifi0num[i]==num[i-1]〃思考一下这个去重的操作中为何有i0这个条件continue;fprintffp2；,%d H,num[i];fclosefpl;fclosefp2;

4.【问题描述•开心的金明】金明今日很开心，家里购置的新居就要领钥匙了，新居里有一间他自己专用的很宽阔的房间更让他高兴的是，妈妈昨天对他说“你的房间需要购置哪些物品，怎么布置，你说了算，只要不超出N元钱就行，今日一早金明就开始做预算，不过他想买的东西太多了，肯定会超出妈妈限定的N元于是，他把每件物品要求了一个重要度，分为5等用整数1〜5表示，第5等最重要他还从因特网上查到了每件物品的价格（都是整数元）他希望在不超出N元（能够等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大设第j件物品的价格为v[j],重要度为w[j],共选中了k件物品，编号依次为，j1J2,……jk,则所求的总和为v[j1]*w[j1]+v[j2]*w[j2]+……+vOk]*wOk]（其中*为乘号）请你协助金明设计一个满足要求的购物单【输入文献】输入文献happy.in的第1行，为两个正整数，用一个空格隔开Nm（其中N（＜30000）表示总钱数，m（v25）为希望购置物品的个数）从第2行到第m+1行，第j行给出了编号为卜1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格（VW10000）,p表示该物品的重要度（1・5））【输出文献】输出文献happy.out只有一个正整数，为不超出总钱数的物品的价格与重要度乘积的总和的最大值（＜）【输入样例】1000580024005300540032002【输出样例】3900背包问题的处理措施有诸多，不过都不太轻易了解，本算法采取穷举法结合二进制数据的排列来穷举所有价值组合重要思想依照物品的个数先计算出所有物品排列组合的排列数，每件物品取为1,不取为0假设用n个物品，从n个物品中任意取出若干个的最大组合次数为2”・1种，因此只要穷举出2”・1种组合情况，计算出其中的最大价值组合，就是本题的算法本题的核心是计算出对应的二进制数据列，每一个组合对应一个二进制数列，然后依照二进制数组的0,1值来形成物品不一样的组合，从而计算出目前二进制组合下的价值和，通过2”・1比较后就能计算出最大价值#includeint mainintN,m;//其中N30000表示总钱数，mv25为希望购置物品的个数int bi

[24];〃用于每次取物组合的0,1序列int wi

[24];〃用于存储每件物品的价格int vi

[24];〃用于存储每件物品的重要度inti,j,n,num;int MaxValueSum=0,ValueSum=0,TotalWeight=0;long k=1;FILE*fp1,*fp2;fscanffp1J%d%d”,N,m;〃读取数据其中N30000表示总钱数，mv25为希望购置物品的个数fori=0;im;i++fscanffp1J%d%d”,wi[i],vi[i];〃读取数据将各个物品的价格和重要度分别存储到对应的数组当中n=m;〃将物品的总个数存储到一个中间变量中以以便计算/*首先计算出n种物品取舍组合的总数*/whilen0k=2*k;；n-卜=1-1;〃求得女的值，即为n种物品取舍的0,1组合总数2An-1n=m;〃恢复n的值以便下面计算所用fori=1;i=k;i//该循环的功效是循环遍历k种组合，比较并计算出”价值和“最大的组合++{〃第1步，必须求出每次取舍组合的二进制序列num=i;/••*••如下这段代码段完成将m转换成n位二进制数组的过程****/whilenum!=0〃其中第一个while循环完成了有效数值的转换num=num/2;bi[n-1]=y;；n-whilen=0〃第二个while循环用于将二进制序列的高位置0bi[n]=O;；n--/•••••以上这段代码段完成将mm转换成n位二进制数组的过程*****/n=m;〃恢复n的值以便下面计算所用〃第2步计算出目前取舍组合0,1中的价值和，并于最大价值和进行比较，找到新的最大的价值和forj=0;jn;j++讦咖==0//当bi[j]==0,表示目前物品并没有取操作，因此直接跳转考查下一个物品的取舍状态continue;TotalWeight+=wi[j];ValueSum+=wi[j]*vi[j];}〃循环结束后，可求得本次组合的总价格Totalweight和总价值和ValueSum巩TotalWeightN〃首先考查计算出来的总价格是否超出了允许的总价格TotalWeight=0;〃计算下一趟组合之前清0ValueSum=0;//计算下一趟组合之前清0。