c语言复赛题.doc

信息学奥赛复赛练习题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的内容为：10样例输出：moni.out的内容为：12489main() int i,n,s,x; int a1000; scanf(%d,&n); for(i=1;in;i+) ai=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=0) printf(%d ,i);s=s+1; if(s=0) printf(0);3【问题描述-明明的随机数】明明想在学校中请一些同学一起做问卷调查，为了实验的客观性，他先用计算机生成了N 个1 到1000 之间的随机整数，（N100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。【输入文件】输入文件random.in 有2 行，第1 行为1 个正整数，表示所生成的随机数的个数：N 第二行有N 个用空格隔开的正整数，为所产生的随机数。【输出文件】输出文件random.out 也是2 行，第1 行为1 个正整数M，表示不相同的随机数的个数。第2 行为M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。【输入样例】10 20 40 32 67 40 20 89 300 400 15 【输出样例】815 20 32 40 67 89 300 400 /*本题主要是考察对排序算法的掌握，只不过外加了一个去重的操作。本题的算法有很多，我们在考试时，时间紧，题目难度大。如果我们能用最简单的思维方式解决问题的话，就不一定把很多的时间放在代码执行效率的优化问题上。有时候牺牲一点空间（内存）和时间对于获取更多的考试时间是非常有必要的。本题最简单的思想方法，就是根据题目要求，先对给定的一组数据进行排序，排序的方法可以使用最简单的冒泡算法来完成。由于本题的输出结果要求我们必须先统计出不重复数据的个数，所以当数据排序之后，我们可以先对所有的数据遍历一次，这一次遍历的目的就是让我们统计出不重复数据的个数，并将其输出。最后，我们还需进行一次遍历，这次遍历用于打印出排序之后不重复的所有数据结果.*/#include int 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 filen); return 0; fscanf(fp1,%d,&N); /输入随机数的个数 for(i=0;iN;i+) fscanf(fp1,%d,&numi); /将已知的随机数存放到初始数组中 for(i=0;i for(j=i+1;jnumj) a=numi; numi=numj; numj=a; fp2=fopen(random.out,w); /打开写文件的指针 for(i=0;i if(i0&numi=numi-1) /思考一下这个去重的操作中为什么有i0这个条件 continue; M+; fprintf(fp2,%dn,M); /在结果文件中打印出不重复数据的个数 并键入一个回车符 for(i=0;i if(i0&numi=numi-1) /思考一下这个去重的操作中为什么有i0这个条件 continue; fprintf(fp2,%d ,numi); fclose(fp1); fclose(fp2); return 0; 4【问题描述-开心的金明】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数15 表示，第5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为vj，重要度为wj，共选中了k 件物品，编号依次为，j1,j2,jk ，则所求的总和为：vj1*wj1+vj2*wj2+vjk*wjk （其中*为乘号） 请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件happy.in 的第1 行，为两个正整数，用一个空格隔开： N m （其中N（30000）表示总钱数，m(25)为希望购买物品的个数。） 从第2 行到第m+1 行，第j 行给出了编号为j-1的物品的基本数据，每行有2 个非负整数v p （其中v 表示该物品的价格（v10000），p 表示该物品的重要度（1-5） 【输出文件】输出文件happy.out 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）【输入样例】1000 5 800 2 400 5 300 5 400 3 200 2 【输出样例】3900 背包问题的解决办法有很多，但是都不太容易理解，本算法采用穷举法结合二进制数据的排列来穷举所有价值组合主要思想：根据物品的个数先计算出所有物品排列组合的排列数，每件物品取为1，不取为0假设用n个物品，从n个物品中任意取出若干个的最大组合次数为：2n-1种，因此只要穷举出2n-1种组合情况，计算出其中的最大价值组合，就是本题的算法本题的关键是计算出对应的二进制数据列，每一种组合对应一个二进制数列，然后根据二进制数组的0，1值来形成物品不同的组合，从而计算出当前二进制组合下的价值和，通过2n-1比较后就能计算出最大价值#include int main() int N,m; /其中N（30000）表示总钱数，m(25)为希望购买物品的个数 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）组合总数 2n-1 n=m; /恢复n的值以便下面计算所用 for(i=1;i=0) /第二个while 循环用于将二进制序列的高位置0 bin=0; n-; /*以上这段代码段完成将num转换成n位二进制数组的过程*/ n=m; /恢复n的值以便下面计算所用 /第2步：计算出当前取舍组合（0，1）中的价值和，并于最大价值和进行比较，找到新的最大的价值和 for(j=0;jN) /首先考察计算出来的总价格是否超过了允许的总价格 TotalWeight=0; /计算下一趟组合之前清0 ValueSum=0; /计算下一趟组合之前清0 continue; /当计算出本次组合的总价格超出既定总价格时，continue到下一趟组合（即跳转到外层for循环 ) if(ValueSumMaxValueSum) /在上一步保证总价格没有超过既定价格的条件下，判断本次组合的价值和是否超过最大的价值和 MaxValueSum=ValueSum; TotalWeight=0; /计算下一趟组合之前清0 ValueSum=0; /计算下一趟组合之前清0 fp2=fopen(bag.out,w); fprintf(fp2,%d,MaxValueSum); /输出最大的价值和的结果 fclose(fp1); fclose(fp2); return 0;5【问题描述-猴子选大王】：M只猴子要选大王，选举办法如下：所有猴子按1-M编号围坐一圈，从1号开始按顺序1，2，K报数，凡报到K的猴子退出到圈外，如此循环报数，直到圈内只剩下一只猴子时，这只猴子就是大王。M和K由输入文件提供，要求在输出文件中打印出最后剩下的猴子的编号。数据规模（M=1000,K=10）【输入文件】 输入文件monkey.in 的第1 行，为两个正整数，用一个空格隔开:M K【输出文件】输出文件monkey.out 只有一个正整数,输出最后一个猴子的编号【输入样例】7 3【输出样例】4这个问题记得给大家上机练习中做过，即对报数问题的求解。在我做完这个题目的时候，我其实并不知道这就是顶顶有名的约瑟夫问题。之后有个学生（陈亮宇）告诉我才知道这是一个据说是由古罗马著名史学家Josephus提出的问题演变而来的。称之为约瑟夫问题。很多资料上对这一问题解释得过于繁杂，实现起来不好理解。在这里介绍一下本人的一些想法以供大家参考。 这个题目其实就是一种编程的经验问题。我们可以假设猴子就位的状态用1表示，把猴子离开的状态用0表示。那么我们就可以用一个aM的数组来存放M个猴子是否就位的状态。我们可以一边报数一边遍历该数组，每遇到第K个1时，就把当前位置的1变为0，表示当前位置的猴子已经出局了。一直循环遍历到我们的状态数组只有一个1的时候，这个存放1的数组下标再加上1（因为数组下标是由0开始的，所以要加1）即为选出的大王的编号。想法很简单，现在关键的问题是如何解决当报数到第M个猴子的时候如何使得下一个报数重新回到第1个猴子处，也就是如何使用一维数组来解决环型问题的求解技巧。大家想一下当我们的猴子围成圈坐的时候，问题其实由简单的一维数组变成了首尾相接的环型数组，也就是我们数据结构中的环型队列。假设p为当前数组某一元素的下标，对于一维数组来说，我们只要p+就可以移动到下一个元素的位置上。那么当p=M时，如果我们直接使用p+的话，p的值就超出了aM数组的最大长度，我们想要的是p+之后等于0。那么如何实现呢？解决环型数组循环遍历元素的方法：对于环型数组移动下标时，我们如果每次在p+之后再加上p=p%M的话就能解决先前遇到的越界的问题。下标变量p也就可以周而复始的在aM中顺时针地循环移动了.请认真查阅以下程序源代码分析，关键掌握环型数组的遍历！程序参考:#include int main() int n; int n1=0; /表示报数记数器 int p=0; /指向当前数组元素的下标 int NumOfKing; /大王的编号 int M,K; /M为已知猴子总数,K为报数的量级 int a1000; FILE *fp1,*fp2;fp1=fopen(monkey.in,r); fscanf(fp1,%d%d,&M,&K); /从文件中读取已知数据 n=M; /M为圈的长度，即初始猴子数 for(int i=0;i1) /n当前圈内还剩下的猴子数,控制循环在圈内只剩下一只猴子时结束循环 while(n1 if(ap=1 ) /如果当前位置有猴子 n1+; /报数记数器加1 if(n1=K) ap=0; /将第K次报数的猴子置0，表示退出圈子 p+; /移动到下一个位置 p=p%M; /这一步是为了解决循环数组成环遍历的目的 n1=0; /当报完K个数后将报数记数变量清0，以备下次重新报数 n-; /当报完一轮后总猴子数减1 for(int i=0;i if(ai=1) NumOfKing=i+1; break; fp2=fopen(monkey.out,w); fprintf(fp2,%d,NumOfKing); fclose(fp1); fclose(fp2); return 0;6【问题描述:合并果子】 在一个果园里,多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆.多多决定把所有的果子合成一堆. 每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和.可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了.多多在合并果子时总共消耗的体力等于每次合并所消耗体力之和. 因为还要花大力气把这些果子般回家,所以多多在合并果子时要尽可能地节省体力.假定每个果子重量都是1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值.例如:有3种果子,数目依次为1,2,9.可以先将1,2堆合并,新堆数目为3,耗费体力为3.接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12.所以多多总共耗费体力为3+12=15.可以证明15为最小的体力耗费值.【输入文件】输入文件fruit.in包括两行,第一行是一个整数n(1n30000),表示果子的种类数.第二行包含n个整数,用空格分隔,第i个整数ai(1ai20000)是第i种果子的数目.【输出文件】输出文件fruit.out包括一行,这一行只包含一个整数,也就是最小的体力耗费值.【输入样例】32 1 9【输出样例】15【解题思路】为了使最终的体力耗费值最小,我们应该每一次都选择最小的两堆果子合并,使每次合并耗费的体力值最小.我们可以按照以下算法过程来解决问题:1. 读入每堆果子的数目ai(ai为第i堆果子的数目).2. 将果子数目按递增顺序进行排序.3. 合并数目最少的两堆果子,并增加体力耗费值到total变量4. 在果子序列中清除合并的两堆果子数目,增加合并后的果子数目.5. 重复步骤2-4,直到所有果子合并为一堆.6. 输出total问题的关键在于第4步,如何在数组中清除合并的两堆果子,并增加合并后的果子数到数组中,然后再完成剩余果子的重排序. 解决这个问题的方法有很多,可以在同一数组中解决,也可以利用另外一个空数组来重新存放每次合并之后的堆.建议大家考虑在同一数组中如何解决这样的问题.【基本算法练习部分】1. 在实际应用中我们经常遇到这样的问题,在处理一些高精度的计算时,由于数据类型字长的限制,使得对一些海量数据不能直接用某种数据类型来定义,比如:1234567890987654321,已经超出了我们基本数据类型的范围,那么我们如何处理这些高精度的海量数据呢?在处理这样的数据时,我们一般的方法是首先定义一个字符数组来存放将这些高精度的字符数据,然后将其每一位字符数据转化为对应的整型,并重新保存在一个整形数组中.当所有的字符数组转存到整型数组后,我们就可以对其进行运算了.试写一个程序,将字符串”1234567890987654321”,转换成对应的整数并输出.提示:字符数字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=aj) j-; if(ij) at=aj;t=j; while(i=ai) i+; if(ij) at=ai;t=i; while(i!=j); at=k; if(x if(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+aj) head+;j+; else j+=2; printf(%dn,ans); system(pause); return 0; /n;i+)/j)/j)/j)&(k=aj)/n;i+)/n;j+)/m;i+)/N;j+)/N;i+)/L，而是i/n;i+)/n;i+)