《2023年c语言复赛题.pdf》由会员分享，可在线阅读，更多相关《2023年c语言复赛题.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息学奥赛复赛练习题1.模拟开关(题目名称：moni.bas)(12分)题目描述:有N盏电灯排成一行，依次编号为1,2,3,N。现各有一个开关，开始灯都亮着的。现在尚有N个人，第一人走过来依次把1和1的倍数电灯的开关都拉一下。第三个人走过来依次把3和3的倍数的开关都拉一下，第五个人走过来依次把5和5的倍数的开关都拉一下(按奇数的规律)，问最后都有哪些灯是关着的？输入文献文献名：moni.in文献中只有一行，包含1个整数N(其中5N30)输出文献文献名：moni.out文献中共有若干行，每一行一个数据，分别为那些关着的灯泡的编号。规定：每一行的输出数据都从第一列开始。样例输入:moni.in的内
2、容为:10 样例输出：moni.out的内容为：12489main()int i,n,s,x;int a 1000;scanf(%cT,&n);for(i=1;in;i+)a i=1；x=1；while(x=n)s=0;while(s=n)s=s+x;as=1-as;)x=x+2;)s=0;for(i=1;in;i+)if(ai=O)printf(%d,i);s=s+1;if(s=O)printf(O);)3.【问题描述-明明的随机数】明明想在学校中请一些同学一起做问卷调查，为了实验的客观性，他先用计算机生成了N个1 JIJ 1000之间的随机整数，(N R 0 0),对于其中反复的数字，只保
3、存一个，把其余相同的数去掉，不同的数相应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完毕“去重”与“排序”的工作。【输入文献】输入文献random.in有2行，第1行为1个正整数，表达所生成的随机数的个数：N第二行有N个用空格隔开的正整数，为所产生的随机数。【输出文献】输出文献random.out也是2行，第1行为1个正整数M,表达不相同的随机数的个数。第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例】1020 40 32 67 40 20 89 300 400 15【输出样例】815 20 32 40 67 89 30
4、0 400本题重要是考察对排序算法的掌握，只但是外加了一个去重的操作。本题的算法有很多，我们在考试时，时间紧，题目难度大。假如我们能用最简朴的思维方式解决问题的话，就不一定把很多的时间放在代码执行效率的优化问题上。有时候牺牲一点空间(内存)和时间对于获取更多的考试时间是非常有必要的。本题最简朴的思想方法，就是根据题目规定，先对给定的一组数据进行排序，排序的方法可以使用最简朴的冒泡算法来完毕。由于本题的输出结果规定我们必须先记录出不反复数据的个数，所以当数据排序之后，我们可以先对所有的数据遍历一次，这一次遍历的目的就是让我们记录出不反复数据的个数，并将其输出。最后，我们还需进行一次遍历，这次遍历
5、用于打印出排序之后不反复的所有数据结果.7includeint main()(FILE*fp1,*fp2;int N,M=0;int i,j;int a;int num100;根据题口所给的数据规模定义数组的大小if(fp1=fopen(,random.in,r,)=NULL)(printf(cannot open filenM);return 0;)fscanf(fp1,”d”,&N);/输入随机数的个数for(i=0;iN;i+)fscanf(fp1,”d”,&numi);将己知的随机数存放到初始数组中for(i=0;ifor(j=i+1;jnumj)a=numi;numi=numj;nu
6、mj=a;)fp2=fopen(random.out,w);打开写文献的指针for(i=0;i(if(i0&numi=num/1)思考一下这个去重的操作中为什么有i0这个条件continue;M+;)fprintf(fp2J%drT,M);在结果文献中打印出不反复数据的个数 并键入一个回车符for(i=0;i(计(i0&numi=num/1)思考一下这个去重的操作中为什么有i0这个条件continue;fprintf(fp2；%d,numi);)fclose(fpl);fclose(fp2);return 0;4.【问题描述-开心的金明】金明今天很开心，家里购置的新房就要领钥匙了，新房里有间他
7、自己专用的很宽敞的房间。更让他快乐的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行，今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数15表达，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为v j,重要度为w j,共选中了 k 件物品，编号依次为，j1,j2.jk,则所求的总和为:vj1*wj1+vD2*wj2+vjk*w jk（其中*为
8、乘号）请你帮助金明设计一个满足规定的购物单。【输入文献】输入文献happy.in的第1 行，为两个正整数，用一个空格隔开：Nm（其中N（30000）表达总钱数，m（25）为希望购买物品的个数。）从第2 行到第m+1行，第 j 行给出了编号为卜1 的物品的基本数据，每行有2 个非负整数vp（其中v 表达该物品的价格（v10000）,p 表达该物品的重要度（1-5）【输出文献】输出文献happy.out只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（）【输入样例】1000 5800 2400 5300 5400 3200 2【输出样例】3900背包问题的解决办法有很多，但是都
9、不太容易理解，本算法采用穷举法结合二进制数据的排列来穷举所有价值组合重要思想：根据物品的个数先计算出所有物品排列组合的排列数，每件物品取为1,不取为0假设用n 个物品，从 n 个物品中任意取出若干个的最大组合次数为：2叮-1 种，因此只要穷举出2n-1种组合情况，计算出其中的最大价值组合，就是本题的算法本题的关键是计算出相应的二进制数据列，每一种组合相应一个二进制数列，然后根据二进制数组的0,1 值来形成物品不同的组合,从而计算出当前二进制组合下的价值和，通过2、-1 比较后就能计算出最大价值#includeint main()intN,m;/其中N(30000)表达总钱数，m(25)为希望购
10、买物品的个数int bi24;/用于每次取物组合的0,1 序列int wi24;用于存放每件物品的价格int vi24;/用于存放每件物品的重要度int i,j,n,num;int MaxValueSum=0,ValueSum=0,TotalWeight=0;long k=1;FILE*fp1,*fp2;fscanf(fp1,%d%d,&N,&m);/读取数据：其中N(30000)表达总钱数，m(25)为希望购买物品的个数for(i=0;i0)(k=2*k;n-;)k=k-1;求得k 的值，即为n 种物品取舍的(0,1)组合总数25-1n=m;恢复n 的值以便下面计算所用for(i=1；iv=
11、k;i+)/该循环的功能是循环遍历k 种组合，比较并计算出”价值和“最大的组合(第1 步，必须求出每次取舍组合的二进制序列num=i;/*以下这段代码段完毕将num转换成n 位二进制数组的过程*/while(num!=O)其中第一个while循环完毕了有效数值的转换(y=num%2;num=num/2;bin-1=y;n-；)while(n=0)第二个w hile循环用于将二进制序列的高位置0(bin=O;n-；)/*以上这段代码段完毕将num转换成n 位二进制数组的过程*/n=m;恢复n 的值以便下面计算所用第2 步：计算出当前取舍组合(0,1)中的价值和，并于最大价值和进行比较，找到新的最
12、大的价值和for(j=0;jN)一方面考察计算出来的总价格是否超过了允许的总价格(TotalWeight=0;/计算下一趟组合之前清0ValueSum=O;计算下一趟组合之前清0continue;当计算出本次组合的总价格超过既定总价格时，continue到下一趟组合(即跳转到外层for循 环)if(ValueSumMaxValueSum)在上一步保证总价格没有超过既定价格的条件下，判断本次组合的价值和是否超过最大的价值和MaxValueSum=ValueSum;TotalWeight=0;计算下一趟组合之前清0ValueSum=O;计算下一趟组合之前清0)fp2=fopen(bag.out,w
13、);fprintf(fp2,d,MaxValueSum);输出最大的价值和的结果fclose(fpl);fclose(fp2);return 0;)5.【问题描述-猴子选大王】：M 只猴子要选大王，选举办法如下：所有猴子按1-M编号围坐一圈，从 1 号开始按顺序1,2,K报数，凡报到K 的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。M 和 K 由输入文献提供，规定在输出文献中打印出最后剩下的猴子的编号。数据规模(Mv=1000,Kv=10)【输入文献】输入文献monkey.in的第1 行，为两个正整数，用一个空格隔开：M K【输出文献】输出文献monkey.out
14、只有一个正整数，输出最后一个猴子的编号【输入样例】73【输出样例】4这个问题记得给大家上机练习中做过，即对报数问题的求解。在我做完这个题口的时候，我其实并不知道这就是顶顶有名的约瑟夫问题。之后有个学生(陈亮宇)告诉我才知道这是一个据说是由古罗马著名史学家Josephus提出的问题演变而来的。称之为约瑟夫问题。很多资料上对这一问题解释得过于繁杂，实现起来不好理解。在这里介绍一下本人的一些想法以供大家参考。这个题目其实就是一种编程的经验问题。我们可以假设猴子就位的状态用1表达，把猴子离开的状态用0表达。那么我们就可以用一个aM的数组来存放M个猴子是否就位的状态。我们可以一边报数一边遍历该数组，每碰
15、到第K个1时，就把当前位置的1变为0,表达当前位置的猴子已经出局了。一直循环遍历到我们的状态数组只有个1的时候，这个存放1的数组下标再加上1 (由于数组下标是由。开始的，所以要加1)即为选出的大王的编号。想法很简朴，现在关键的问题是如何解决当报数到第M个猴子的时候如何使得下一个报数重新回到第1个猴子处，也就是如何使用一维数组来解决环型问题的求解技巧。大家想一下当我们的猴子围成圈坐的时候，问题其实由简朴的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列 假设p为当前数组某一元素的下标，对于一维数组来说，我们只要p+就可以移动到下一个元素的位置上。那么当p=M时，假如我们直接使用p
16、+的话，p的值就超过了 数组的最大长度，我们想要的是P+之后等于0。那么如何实现呢？解决环型数组循环遍历元素的方法：对于环型数组移动下标时，我们假如每次在p+之后再加上p=p%M的话就能解决先前碰到的越界的问题。下标变量p也就可以周而复始的在aM中顺时针地循环移动了.请认真查阅以下程序源代码分析，关键掌握环型数组的遍历！程序参考：#includeint main()(int n;intn1=0;表达报数记数器int p=0;指向当前数组元素的下标int NumOfKing;/大王的编号int M,K;/M为已知猴子总数,K为报数的量级int a1000;FILE*fp1,*fp2;fp1=fo
17、pen(monkey.in,r);fscanf(fp1,%d%d”,&M,&K);/从文献中读取已知数据n=M;M为圈的长度，即初始猴子数for(int i=O;i1)n当前圈内还剩下的猴子数，控制循环在圈内只剩下一只猴子时结束循环(while(n1(if(ap=1)/假如当前位置有猴子(n1+;报数记数器加1if(n1=K)ap=O;将第K次报数的猴子置0,表达退出圈子)P+；/移动到下一个位置p=p%M;这一步是为了解决循环数组成环遍历的目的n1=0;当报完K个数后将报数记数变量清0,以备下次重新报数n-;当报完一轮后总猴子数减1)for(int i=0;i(if(ail=1)(NumOf
18、King=i+1;break;)fp2=fopen(monkey.out,w);fpnntf(fp2,H%d,NumOfKing);fclose(fpl);fclose(fp2);return 0;6.1问题描述:合并果子】在一个果园里，多多已经将所有的果子打了下来，并且按果子的不同种类提成了不同的堆.多多决定把所有的果子合成一堆.每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和.可以看出，所有的果子通过n-1次合并之后,就只剩下一堆了.多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和.由于还要花大力气把这些果子般回家，所以多多在合并果子时要尽也许地节省体力.
19、假定每个果子重量都是1,并且己知果子的种类数和每种果子的数目,你的任务是设计出合并的顺序方案，使多多花费的体力最少，并输出这个最小的体力花费值.例如:有3 种果子，数目依次为1,2,9.可以先将1,2堆合并，新堆数目为3,花费体力为3.接着，将新堆与原先的第三堆合并，又得到新的堆，数口为12,花费体力为12.所以多多总共花费体力为3+12=15.可以证明15为最小的体力花费值.【输入文献】输入文献fruit.in涉及两行，第一行是一个整数n(1Vnv30000),表达果子的种类数.第二行包含n 个整数，用空格分隔，第 i 个整数ai(Eais20230)是第i 种果子的数目.【输出文献】输出文
20、献fruit.out涉及一行，这一行只包含一个整数,也就是最小的体力花费值.【输入样例】32 1 9【输出样例】15【解题思绪】为了使最终的体力花费值最小，我们应当每一次都选择最小的两堆果子合并，使每次合并花费的体力值最小.我们可以按照以下算法过程来解决问题：1.读入每堆果子的数目ai(ai为第i 堆果子的数目).2.将果子数目按递增顺序进行排序.3.合并数目最少的两堆果子,并增长体力花费值到total变量4.在果子序列中清除合并的两堆果子数目,增长合并后的果子数目.5.反复环节2-4,直到所有果子合并为一堆.6.输出 total问题的关键在于第4 步,如何在数组中清除合并的两堆果子，并增长合
21、并后的果子数到数组中，然后再完毕剩余果子的重排序.解决这个问题的方法有很多，可以在同一数组中解决，也可以运用此外一个空数组来重新存放每次合并之后的堆.建议大家考虑在同一数组中如何解决这样的问题.【基本算法练习部分】1.在实际应用中我们经常碰到这样的问题,在解决些高精度的计算时，由于数据类型字长的限制，使得对一些海量数据不能直接用某种数据类型来定义，比如7654321,已经超过了我们基本数据类型的范围，那么我们如何解决这些高精度的海量数据呢?在解决这样的数据时,我们一般的方法是一方面定义一个字符数组来存放将这些高精度的字符数据，然后将其每一位字符数据转化为相应的整型，并重新保存在一个整形数组中.
22、当所有的字符数组转存到整型数组后，我们就可以对其进行运算了.试写一个程序，将字符串”7654321”,转换成相应的整数并输出.提醒:字符数字0-9相应的ASCII分别为48-57例如：字符数字6,转换成整型数字6 的方法如下：Int k=6-48;/k 的值即为 6#define lim 6555int a1000,b1000;void sort(int x,int y)(int i,j,k,t；i=x;j=y;k=ai;t=x;do(while(ij)&(k=aO)j-；if3)at=aj;t=j;while(i=ai)i+；if(ij)at=ai;t=i;)while(i!=j);at=k
23、;if(xif(i+1)int mmin(int i,int j,int k)int min;min=i;if(j if(k return min;)int main()int i,j,k,m,n,head,tail,ans;scanf(%d,&n);for(i=1;i=n;i+)scanf(%d,&ai);for(i=1;i=n;i+)bi=lim;an+1 =lim;an+2=lim;sort(1,n);j=1;head=k;for(i=1;in;i+)(k=mmin(bhead+bhead+1,bhead+aj,aj+aj+1);tail+;atail=k;ans+=btail;if(k=bhead+bhead+1)head+=2;else if(k=bhead+bhead+aO)head+;j+;else j+=2;)printf(%dn,ans);system(pause);return 0;/n;i+)/j)/j)&(kx/j)/j)&(k=aj)/n;i+)/n;j+)/m;i+)/N;j+)v/N;i+)/L,而是 i=Lx/n;i+)/n;i+)