搜索
5/20/20201c程序设计竞赛竞赛与考试的区别一、注重程序效率二、信息数字化1.数学模型提高程序效率2.算术技巧提高程序效率三、数据存储（机试的共同特点）1.状态信息数字化2.特征信息数字化文件操作3.优化数据结构提高程序效率1.数学知识提高程序效率【例1】杨辉三角形的应用求n次二项式各项的系数：已知二项式的展开式为：(a+b)n=Cn0an+Cn1an-1b+Cn2an-2b2+……+Cnnbn它们共有n+1个系数。若你编写程序用n!/(j!*(n-j)!))计算组合系数Cnj,会怎样?5/20/20204coeff(inta[],intn){if(n==1){a[1]=1;a[2]=1;}else{coeff(a,n-1)a[n+1]=1for(i=n;i=2;i--)a[i]=a[i]+a[i-1];a[1]=1;}}程序如下：main(){inta[100],i,n;scanf(“%d”,&n);for(i=1;i=n;i++)scanf(“%d”,&a[i]);coeff(a,n);for(i=1;i=n;i++)printf(“%d”,a[i]);}返回5/20/20205【例2】最大公约数的应用数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后移k位，后面的元素则循环向前移k位，例：1、2、3、4、5循环移3位后为：3、4、5、1、2。考虑到n会很大，不允许用2*n以上个空间来完成此题。若题目没有关于存储空间的限制，可以方便地开辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。分析1：5/20/20206程序1如下：main(){inta[100],b[100],i,n,k;scanf(“%d%d”,&n,&k);for(i=0;in;i++)scanf(“%d”,&a[i]);for(i=0;in;i++)b[(k+i)%n]=a[i];for(i=0;in;i++)printf(“%d”,b[i]);}5/20/20207分析2：1）一组循环移动的情况：通过计算我们可以确定某个元素移动后的具体位置。当n=5,k=3时，可计算出14,42,25,53,31的位置,一组移动正好将全部数据按要求进行了移动。这样只需一个辅助变量就可完成整个移动过程。2）多组循环移动的情况：但若把问题就这样按一组移动去解决，会怎样?5/20/20208数学模型：问题与最大公约数有关，即循环移动的组数等于N与K的最大公约数。这就是利用数学知识建模的过程。“感知”是否正确可以通过数学方法证明（就象哥德巴赫猜想），或通过程序进行大量数据验证。1）编写函数，完成求n,k最大公约数m的功能2）进行m组循环移动。3）每组移动，和程序1一样，通过计算可以确定某个元素移动后的具体位置。在移动之前，用临时变量存储需要被覆盖的数据。实现要点：5/20/20209程序2如下：main(){inta[100],b,i,n,k,m;printf(“inputthenumberofdata”);scanf(“%d”,&n);printf(“inputthedistantofmoving”);scanf(“%d”,&k);for(i=0;in;i++)scanf(“%d”,&a[i]);m=ff(n,k);for(j=0;jm;j++)for(i=j;in;i=i+k){b=a[(j+k)%n];a[(j+k)%n]=a[j];a[j]=b;}for(i=0;in;i++)printf(“%d”,a[i]);}返回5/20/202010ff(inta，intb){t=1for(i=2；i=a&&i=b；i++)while(a%i==0&&b%i==0){t=t*i;a=a/i;b=b/i;}return(t);}5/20/202011【例3】最小公倍数的应用编写程序完成下面给“余”猜数的游戏：你心里先想好一个1~100之间的整数x，将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机，计算机能马上猜出你心中的这个数。游戏过程如下：pleasethinkofanumberbetween1and100yournumberdividedby3hasaremainderof?1yournumberdividedby5hasaremainderof?0yournumberdividedby7hasaremainderof?5letmethinkamoment…yournumberwas405/20/202012用程序模拟这个游戏过程的关键是：找出余数与求解数之间的关系，也就是建立问题的数学模型。分析：数学模型：记a，b，c分别为所猜数据d除以3，5，7后的余数，则d=70*a+21*b+15*c。则建立数学模d=70*a+21*b+15*c的过程如下:5/20/202013a、b、c的系数必须满足：1）b、c的系数能被3整除，且a的系数被3整除余1；这样d除以3的余数与a相同。2）a、c的系数能被5整除，且b的系数被5整除余1；这样d除以5的余数与b相同。3)a、b的系数能被7整除，且c的系数被7整除余1；这样d除以7的余数与c相同。d=70*a+21*b+15*c5/20/202014由上可见：c的系数是3和5的最公倍数且被7整除余1，正好是15；a的系数是7和5的最公倍数且被3整除余1，最小是70；b的系数是7和3的最公倍数且被5整除余1，正好是21。实现要点：用以上数学模型求解的数d，可能比100大，这时只要减去3，5，7的最小公倍数就是问题的解了。游戏程序如下：5/20/202015main(){inta,b,c,d;printf(“pleasethinkofanumberbetween1and100.”);printf(“yournumberdivdedby3hasaremainkerof”);scanf(“%d”,&a);printf(“yournumberdivdedby5hasaremainkerof”);scanf(“%d”,&b);printf(“yournumberdivdedby7hasaremainkerof”);scanf(“%d”,&c);printf(“letmethinkamoment…”);for(i=1,i1500;i++)d=70*a+21*b+15*c;while(d105)d=d-105;printf(“yournumberwas%d”,d);}返回5/20/2020162.算术运算的妙用1）减化或避免条件判断【例1】一次考试，共考了五门课。统计五十个学生中至少有三门课成绩高于90分的人数。实现要点：1）对每个同学，先计算其成绩高于90分的课程数目，若超过3，则累加满足条件的人数中。2）用二重循环实现以上过程，外层循环模拟50个同学，内层循环模拟五门课程。5/20/202017main(){inta[5],i,j,s,num=0;for(i=1;i=50;i++){s=0;for(j=0;j=4;j++){scanf(“%d”,&a[j]);if(a[i]=90)s=s+1;}if(s=3)num=num+1;}printf(“Thenumberof=90is“%d”,num);}程序如下:对于计算其成绩高于90分的课程数目,应如何编写?5/20/202018【例2】开灯问题：有从1到n依次编号的n个同学和n盏灯。1号同学将所有的灯都关掉；2号同学将编号为2的倍数的灯都打开；3号同学则将编号为3的倍数的灯作相反处理（该号灯如打开的，则关掉；如关闭的，则打开）；以后的同学都将自己编号的倍数的灯，作相反处理。问经n个同学操作后，哪些灯是打开的？5/20/2020191）定义有n个元素的a数组，它的每个下标变量a[i]视为一灯，i表示其编号。a[i]=1表示灯处于打开状态，a[i]=0表示灯处于关闭状态。2）当a[i]为1时，a[i]被重新赋为0；当a[i]为0时，a[i]被重新赋为1。但通过以下算术运算：a[i]=1-a[i]就很好地模拟“开关”灯的操作。我们把这种形式的赋值语句形象地称为“乒乓开关”。分析：5/20/202020main(){intn,a[1000],i,k;printf(“inputanumber”);scanf(“%d”,&n);for(i=1;i=n;i++)a[i]=0;for(i=2;i=n;i++){k=1while(i*k=n){a[i*k]=1-a[i*k];k=k+1;}}for(i=1;i=n;i++)printf(“%d”,a[i]);}程序如下:程序中第二个for循环i枚举的不是灯的编号，而是编号为i的同学，其内层循环中，就将包含i因素的灯的编号为“i*k”的灯，改变其状态。程序中还用计算省去了用if语句判断编号能被哪些数整除的过程。5/20/202021【例3】右图中所示的圆圈中，我们把相隔一个数据的两个数（如1和10，3和5，3和6）称作是“一对数”，试编写程序求出乘积最大的一对数和乘积最小的一对数。输出格式如下：max：?*?=?min：?*?=?其中？表示：找到的满足条件的数和乘积。117168101216519931581265/20/2020221)数据有前后“位置”关系，必须用数组来存储。数组定义为a[num]，则有a[0]——a[num-1]共num个元素。2)用i代表下标，题目就是顺序将a（i-1）与a（i+1）相乘，求出乘积的最大值和最小值即可。3)关键是i=num-1时，保证i+1的“值”是0；当i=0时，保证i-1的“值”是num-1，把数组当成圆圈操作通过求余运算很容易实现：当i=num-1时，(i+1)%num等于0；当i=0时(num+i1)%num等于num-1。实现要点：5/20/2020234)通过求余运算，便“避免了”判别数组起点与终点的操作。用变量Max记录当前最大的乘积，m、n为对应的两个乘数；变量min记录当前最小的乘积，s、t为对应的两个乘数。5/20/202024程序如下：main(){intmax=1,min=32767,a[100],num,i,k,m,n,s,t;printf(“inputanumber”);scanf(“%d”,&num);for(i=0;inum;i++)scanf(“%d”,&a[i]);for(i=0;inum;i++){p=(num+i-1)%num;q=(i+1)%num;k=a[p]*a[q];if(kmax){max=k;m=a[p];n=a[q];}if(kmin){min=k;s=a[p];t=a[q];}}printf(”max=%d*%d=%d”,m,n,max);printf(”min=%d*%d=%d”,s,t,min);}返回5/20/2020252）构造下标【例】请编写程序统计100人的身高分布，分布等级：180以上、175—180、170—175、165—170、160—165、155-160、155以下。分析：此类问题表面看不太适合用switch语句来完成。因为即使身高是整数若不借助数学运算至少也有20多种情况，需要20多个case子句。但若注意到每个等级基本是5分一段，通过除法运算将成绩（变量sg）除以5后，分支最多也就只有6个了。5/20/202026main(){intsg,k,s[7],t;printf(“Input%dheight:”,100);for(k=1;k=100;k++){scanf(“%d”,&sg);if(sg0||sg300){printf(“Inputerror!，Inputagain”);k--;continue;}t=sg/5-30;if(t0){s[0]=s[0]+1;t=0;}elseif(t=6){s[6]=s[6]+1;t=6;}elses[t]=s[t]+1;}程序如下：通过计算t=sg/5-30使七类统计区间与数组下标对应，提高了程