You have no items in your shopping cart.
Popular tags
Blog archive
滑铁卢计算机竞赛(CCC)数据分析报告
Wednesday, October 9, 2019
这是初级组的得分排名总表：
高级组的得分排名总表：
其实计算机最早是为了解决数学问题的数值计算而研制的，最早的编程语言如FORTRAN也是为了解决一些数学问题。
计算机和数学相互影响。计算机的运算模型离不开数学思想，数学的发展强有力地推动着计算机技术向前发展;同时计算机的高速运算能力也大大地推动了数学的发展。
编程实际上是求解某个问题的过程，这个过程实质上是设计算法到实现算法的过程，没有良好的数学思维很难写出高质量的算法和程序。
一维数组和二维数组是数据结构中最基本的数据存储方式，对于刚入门的程序员来说确实很重要，因此排在第二名和第四名的位置很好理解。
字符串是计算机软件界面最重要的展现形式，尤其是在一些商业应用软件中，随处都可以找到字符串的影子。而对字符串的理解深度和编程处理能力，是检验程序员编程经验最有效的方式，因此字符串也成为各大公司最爱出的面试题，排在CCC第三名当之无愧啊。
第五名是决策判断。
对于数据输入流来说，计算机能够做的最有效的工作就是对于输入数据根据预先设定的条件进行逻辑判断产生分流，从而形成不同的结果和分类，用计算机语言来表达，就是会有大量的IF...ELSE...和SWITCH....CASE...,这种能力和经验对于程序员来说至关重要，决策判断自然就登上了第五名。
第六名是递归编程。
在编程算法领域，递归编程相对前几名而言属于高级课题，一个函数自恋地调用自己无数次，对于初学编程的同学来说有一些难度，递归编程的题目大多在后面的难题部分。
将数据分析的范围限定在后面难题部分，我们发现19道递归编程题都落在第3题以后，10道题落在了最后一道第5题上面。换句话说，CCC把递归编程作为一个高难度出题方向，想要在CCC中获得高分的同学一定需要加强递归编程的练习啊。
下面我们以解数学题、字符串、递归编程为例来说明CCC是怎么玩的吧。
# include <stdio.h>
# include <ctype.h>
FILE * infp;
FILE * outfp;
int t, /* number of test cases */
i,j, /* indexes in array A */
A[50]; /* arrays to store the digits of a number */
char line[61]; /* a character array to store an input line */
void subtract( int i )
/* subtract A[i] from the number represented by A[0..(i-1)] */
{
int j;
if ( A[i]<=A[i-1] ) A[i-1] = A[i-1] - A[i];
else {
A[i-1] = A[i-1] - A[i] + 10;
for ( j=i-2; A[j]==0; j-- ) A[j]=9;
A[j]--;
}
}
main()
{
infp = fopen( "div.in", "r");
outfp = fopen( "div.out", "w");
fscanf(infp, "%d\n", &t);
while (t>0) {
fgets(line, 60, infp); /* get number */
fprintf(outfp,"%s",line); /* print number once */
/* convert from characters to digits */
for (i=0; isdigit(line[i]); i++ ) A[i]=line[i]-'0';
while ((A[0]!=0 && i>2) || (A[0]==0 && i>3)) {
i--;
subtract(i);
if (A[0]!=0) fprintf(outfp,"%d",A[0]); /* don't print leading zero */
for (j=1; j<i; j++) fprintf(outfp,"%d",A[j]);
fprintf(outfp,"\n");
}
line[strlen(line)-1]='\0'; /* remove end-of-line */
fprintf(outfp, "The number %s ", line);
if ((A[0]!=0 && ((A[0]*10 + A[1])%11==0)) ||
(A[0]==0 && ((A[1]*10 + A[2])%11==0)))
fprintf(outfp,"is divisible by 11.\n");
else fprintf( outfp, "is not divisible by 11.\n");
t--; fprintf(outfp, "\n");
}
}
substract()函数完成的是A-B的过程，其他都是控制台上读取输入指令和返回输出结果的操作。
通过此题我们看到，良好的数学功底对于CCC还是比较重要的。
鉴于商业软件系统使用字符串处理非常频繁，CCC也在其中大作文章，因为可以用来出题的商业应用场景比比皆是。
例如2009年初级组第4题，写好代码的同学基本上可以直接拿到真实环境中去用：
题目原文翻译如下：学生会需要在显示屏上用多行显示诸如"WELCOME TO CCC GOOD LUCK TODAY"字样，每一行最多可以容纳w个字符。你需要按照如下规则来显示这些文字：
1、每一行尽可能多的显示单词，且不能超过w个字符；
2、第一个词出现在行开头，如有多个词在该行，最后一个词显示在最后；
3、每行多余的空格需要显示在词与词中间并尽可能相同；
4、如果词与词中间的空格没有办法保持相同，最多的空格应该放在前面；
简单的翻译就是：如何对一段长文字美观地拆分到多行进行显示。
程序逻辑大概是这样：
接收一段文字；
通过检测字符串中的空格将其分割成一个一个的词，并用字符串数组存起来；
启动一个循环，到字符串数组中按照顺序找到前面的一些词，总长度刚刚小于w(每个词后面都追加一个空格);
在循环块中按照算法要求的4条规则将这些词排列好；
输出最终排列的结果；
限于篇幅，具体的代码略过，感兴趣的同学可以自己完成。
计算机相对人来说最大的优势是计算能力，用程序员的观点来看，就是计算机能够快速地通过循环来执行代码。
在计算机编程中，会写循环是最基本的技能。
在CCC竞赛中，为了检测参赛选手对于计算机语言的理解能力和逻辑思维能力，往往会采用比基础循环语句更高一级的自恋循环，之所以把它叫自恋循环，是因为它会无限次地调用自己，专业术语叫做递归编程。
递归编程容易理解，缺点是如果程序员一旦搞不清楚一个函数自恋自己到什么程度，边界条件稍微处理不当，就有可能造成无限循环，无休止自恋的结果就是堆栈溢出。
我们还是拿一道例题来说明吧，这是2015年初级组的最后一题：
题目原文翻译如下：一般3月14日叫做 π日，因为3.14正好是π的近似值。数学家用吃饼的方式来进行庆祝。假设你有n个饼，有k个数学家排着队来分饼吃，你需要写一个算法来把这n个饼分给这k个数学家，需要满足如下两个条件：
1.每个数学家至少有1个饼；
2.每个数学家分得的饼不能少于队列中前面的人分得的饼数。换句话说，饼数是一个递增序列；
此题看起来像是一道数学题，估计读友会觉得我有点特意往数学题方向上靠，其实不然，我们没有把这道题归为解数学题这一出题方向，尽管里面有数学家，也用到了数学逻辑的分类思维方法。
这是一道典型的递归算法编程题。
整个编程逻辑其实比较简单,借鉴了数学归纳法的一些递推思想：
1.定义一个递归函数getPiNo(int pieNo,int peopleNo,int firstPersonMinPieNo),有三个输入参数：
int pieNo:表示饼的总数；
int peopleNo：表示分饼的总人数；
int firstPersonMinPieNo：表示第一个人分得的饼数最小值；
2.如果要计算getPiNo(n,k,1),可以按照第一个人得到饼的数量进行分类；
第一类:第一个人分得1个饼，也就是后面k-1个人正好分得n-1个饼，并且k-1个人的第一个人最小可以分得1个饼。按照函数定义，正好有getPiNo(n-1,k-1,1)。程序走到这一分支直接返回getPiNo(n-1,k-1,1)即可；
第二类:第一个人分得2个饼，也就是后面k-1个人正好分得n-2个饼，并且k-1个人的第一个人最小需要分得2个饼。按照函数定义，正好有getPiNo(n-2,k-1,2)。程序走到这一分支直接返回getPiNo(n-2,k-1,2)即可；
......以此类推......
第n/k类:这是最后一个分类，因为如果第一个人超过n/k+1个饼，后面每个人都会超过n/k+1个饼，加起来就超过n个饼啦！第一个人分得n/k个饼，也就是后面k-1个人正好分得n-n/k个饼，并且k-1个人的第一个人最小需要分得n/k个饼。按照函数定义，正好有getPiNo(n-n/k,k-1,n/k)。程序走到这一分支直接返回getPiNo(n-n/k,k-1,n/k)即可；
在getPiNo(n,k,1)函数体内启动一个循环对前面所有类的得数求和后返回即可。因为在每个类里面都递归地调用了自己，只要控制好何时停止递归，算出答案不难。
只要把递归逻辑理解清楚，翻译成代码不难，需要注意哪些分类是叶子节点，在这些节点应该立即返回，终止递归。
同时为了提高程序运行的效率和性能，对于一些中间运行结果需要保留，以避免重复计算消耗CPU。
代码略过，感兴趣的同学可以根据上述逻辑完成编码。
"计算机要从娃娃抓起",三十多年前,邓小平高瞻远瞩地说出了这句名言。
三十多年后，看看我们的身边，3、4岁的娃娃们手机、电脑玩得溜溜的。
计算机上有太多好玩的东东，吸引着不少小朋友很早就进入这一领域，从小就开始学编程了，部分同学甚至觉得只要把编程学好了就可以独步武林天下，其他的学科例如数学可以不用花太多时间。
于是很多家长问我是不是可以只要把编程学好就行了。
我想上面的这份CCC数据分析报告其实已经给出了答案。
CCC让我们看到，没有扎实的数学功底，要想解决稍稍复杂一点的现实问题会比较困难，更不用说牵涉到复杂数学逻辑的算法了。
软件及互联网行业已经进入了开源软件盛行的时代，只要你能够想到的应用，一般都能够找到有人在做了，并且还是开源免费的，拿过来就能用。Rootofmath.com就很感恩这些开源软件的贡献者，他们大大地缩短了我们的研发周期。
开源软件让初级程序员进入的门槛大大减低，但如果没有扎实的数学功底，程序员向上发展的空间十分有限，其核心价值和竞争力会大打折扣。未来的程序员需要能够真正吃透开源软件才会比较吃香，否则碰到问题解决不了，也很难实现技术创新，在未来的时代可能会成为代码的搬运工。
滑铁卢计算机竞赛CCC让我们再次看到了数学教育的重要性。在参加数学竞赛学习的过程中，有些家长担心如果孩子在数学学习上花了时间却出不了成绩怎么办，CCC其实给我们指出了道路之一。数学好的孩子，可以东方不亮西方亮，即便没有在数学竞赛中拔尖，仍然可以在计算机、物理、经济、统计等领域拔得头筹。
至于选择什么编程语言参加CCC的问题，如果你已经学了某种语言很多年，有相当多的经验，尽管放心选择你熟悉的语言，因为每一种语言都有它适用的应用场景，自它诞生那天起，它就在为其所擅长的领域服务，今天很多人依然在用它，说明它具备了顽强的生命力。
如果你刚刚开始学习编程，如下经验供你参考：
如果你希望以后在一些科研院校做研究，建议你用Python。Python是一种脚本语言，门槛低，上手快，特别适合做科学研究和数值计算，缺点也恰恰来自于它的优点，因为过于简单，规范性不好，很少用来做大型商业应用系统；
如果你对自己的定位是以后进入大公司从事商业应用系统的研发，建议你用Java。虽然前期投入大一点，但是值得。尤其是Java 8引入的Stream API可以帮助你快速重用已有数据结构和组件完成排序和查找，瞬间实现大量代码，这一点在CCC中如果利用得当比较容易在编码时间上胜出；
如果你比较挑剔，控制欲望比较强烈，希望控制代码的方方面面，建议你用C/C++。C/C++的指针可以让你随心所欲地控制你的代码，出现诸如内存泄漏等性能问题也比较容易解决。缺点也同样来自于它的优点，因为控制得太细，你需要比别人花更多的时间来实现相同功能的代码。
计算机语言是相通的，熟悉一门语言再切换到另一门语言都不难,一通百通。
2020年滑铁卢CCC的初赛时间是2月12日。你，准备好了吗?
往期数据分析报告原创文章链接：
Leave your comment