c语言程序设计竞赛辅导.ppt

《c语言程序设计竞赛辅导.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、8/12/20211c程序设计竞赛竞赛与考试的区别一、注重程序效率二、信息数字化1.数学模型提高程序效率2.算术技巧提高程序效率三、数据存储（机试的共同特点）1.状态信息数字化2.特征信息数字化文件操作3.优化数据结构提高程序效率1.数学知识提高程序效率【例1】杨辉三角形的应用求n次二项式各项的系数：已知二项式的展开式为：(a+b)n=Cn0an+Cn1an-1b+Cn2an-2b2+……+Cnnbn它们共有n+1个系数。若你编写程序用n!/(j!*(n-j)!))计算组合系数Cnj,会怎样?8/12/20214coeff(inta[],in

2、tn){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]);}返回8/12/20215【例2】最大公约数的应用数组中有n个数据，要将它们顺序循环向后移k位，即前面的元素向后

3、移k位，后面的元素则循环向前移k位，例：1、2、3、4、5循环移3位后为：3、4、5、1、2。考虑到n会很大，不允许用2*n以上个空间来完成此题。若题目没有关于存储空间的限制，可以方便地开辟两个一维数组，一个存储原始数据，另一个存储移动后的数据。分析1：8/12/20216程序1如下：main(){inta[100],b[100],i,n,k;scanf(“%d%d”,&n,&k);for(i=0;i

4、)printf(“%d”,b[i]);}8/12/20217分析2：1）一组循环移动的情况：通过计算我们可以确定某个元素移动后的具体位置。当n=5,k=3时，可计算出14,42,25,53,31的位置,一组移动正好将全部数据按要求进行了移动。这样只需一个辅助变量就可完成整个移动过程。2）多组循环移动的情况：但若把问题就这样按一组移动去解决，会怎样?8/12/20218数学模型：问题与最大公约数有关，即循环移动的组数等于N与K的最大公约数。这就是利用数学知识建模的过程。“感知”是否正确可以通过数学方法证明（就象哥德巴赫猜想），或通过程序进行大量

5、数据验证。1）编写函数，完成求n,k最大公约数m的功能2）进行m组循环移动。3）每组移动，和程序1一样，通过计算可以确定某个元素移动后的具体位置。在移动之前，用临时变量存储需要被覆盖的数据。实现要点：8/12/20219程序2如下：main(){inta[100],b,i,n,k,m;printf(“inputthenumberofdata”);scanf(“%d”,&n);printf(“inputthedistantofmoving”);scanf(“%d”,&k);for(i=0;i

6、ff(n,k);for(j=0;j

7、之间的整数x，将它分别除以3、5和7并得到三个余数。你把这三个余数告诉计算机，计算机能马上猜出你心中的这个数。游戏过程如下：pleasethinkofanumberbetween1and100yournumberdividedby3hasaremainderof?1yournumberdividedby5hasaremainderof?0yournumberdividedby7hasaremainderof?5letmethinkamoment…yournumberwas408/12/202112用程序模拟这个游戏过程的关键是：找出余数与求解

8、数之间的关系，也就是建立问题的数学模型。分析：数学模型：记a，b，c分别为所猜数据d除以3，5，7后的余数，则d=70*a+21*b+15*c。则建立数学模d=70