CCF青少年计算机程序设计评级标准

导言

这是我最近在网上看到的关于青少年程序设计能力的评级标准。粗略看完这些标准的我老泪纵横，堂堂大学生，程序设计能力居然如此之低，实在惭愧（至于目前真实的水平如何，我就是不告诉你）。新的一年，要有新的目标，我就以此篇博客开启我新的一年，与君共勉。同学们也可以对号入座，看一下自己的水平如何（是不是被初、高中生吊打）。

这里贴出的是简化版本，一些过长的例题就不贴出来了。

一级标准

定义：了解什么是计算机程序，能够编写计算机程序解决简单问题。

知识要求：

1、 程序的基本结构。

2、 标识符和关键字。

3、 基本数据类型。

4、 常量和变量。

5、 算术表达式和关系表达式。

6、 整除，求余运算，常用数学函数。

7、 赋值语句，输入输出语句，复合语句，条件语句（不嵌套），循环语句（不嵌 套）。

能力要求：

1、 能用自然语言描述解决简单问题的方法和步骤。

2、 能用顺序，分支，循环语句实现知识要求中的方法和步骤，编写完整程序。

3、 初步理解算法的意义。

题例

给出N个数，请找出这N个数中的最小数和最大数。（so easy，我想每个刚学会写程序的人都会吧。）

二级标准

定义：了解什么是算法，能够用程序设计语言实现简单算法，解决问题。

知识要求：

1、 逻辑表达式。

2、 条件嵌套，循环嵌套，数组。

3、 枚举，简单排序，简单查找算法。

4、 素数与合数，最大公约数，最小公倍数，互质数。

能力要求：

1、 能用简单枚举算法解决实际问题，能对数据进行简单排序和查找。

2、 具备独立编写和调试简短程序的能力。

题例

试题描述：给出N个数，请找出第K小的数并输出该数值。（放在这里倒也不难，注意言外之意）

三级标准

三级标准

定义：具有较强的程序实现能力，使用一种计算机程序设计语言编写程序，解决问题。

知识要求：

1、 数制及其转化，信息编码，位运算。

2、 字符串类型。

3、 子程序。

4、 递归。

5、 逻辑运算，整数的质因数分解，随机函数。

6、 筛选法，欧几里得算法

能力要求：

1、 全面掌握一种计算机程序设计语言。

2、 具有运用简单数学知识编写程序解决问题的能力。

题例

试题描述： 给一个整数N，将N写成质因数的乘积（数据范围也小，对大家来说只是入门水平）

到这为止只是入门水平，相信所有已经掌握一门语言的同学都没有问题，我们接着看基础水准（4~5级）

四级标准 （NOIP普及组全国前70%）

定义：了解几种常用的算法，并运用这些算法编写程序，解决问题。

知识要求：

1、 结构类型，文件操作。

2、 数据类型的内在含义。

3、 贪心法，递推，回溯法，模拟算法。

4、 简单的字符串处理。

5、 集合及集合的运算，加法原理和乘法原理，简单的排列和组合。

能力要求：

1、 能根据实际额问题选择合适的数据类型。

2、 能运用贪心、递推、回溯、模拟等算法解决实际问题。

3、 能独立设计简单的测试数据，测试自己程序的正确性。

题例

，据说是一道模拟题，没做过，改天做一下。

接下来的标准对于我校绝大多数的普通学生来说，就是一种挑战了（我校平均程序设计能力可想而知，叹气……对了，我也属于人民群众的行列），题例就不全给出来了

五级标准（NOIP普及组全国前40%）

定义：掌握简单数据结构知识，并结合已学算法和数学知识编写程序，解决问题。

知识要求：

1、 指针类型。

2、 一般线性表，队列，堆栈，二叉树的存储和遍历。

3、 排列和组合，高精度数值的处理。

4、 二分算法，快速排序，深度优先搜索，宽度优先搜索，简单动态规划。

5、 圆排列，可重集排列，鸽笼原理，素因数分解，幂函数，指数函数，对数函数， 三角函数，模运算，不等式基础知识。

能力要求：

1、 能运用常用算法和简单数据结构解决实际问题。

2、 能从算法本质出发，分析相关算法之间的本质联系。

3、 具备初步的数学建模能力。

我们来看一下这一个等级的题目是怎么样的，对于我校大多数普通学生可能这辈子都忘尘莫及（悲哀）

题例

试题描述：

小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号从小到大的顺序依次摆列。试编程计算，一共有多少种不同的摆花方案。

输入数据：

输入共2行。

第一行包含两个正整数n和m，中间用一个空格隔开。

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a1、a2、…….an。

输出数据：

输出只有一行，一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对1000007取模的结果。

输入样例：

2 4

3 2

输出样例：

2

样例说明：有2种摆花的方案，分别是（1,1,1,2），（1,1,2,2）。括号里的1和2表示两种花，比如第一个方案是前三个位置摆第一种花，第四个位置摆第二种花。

参考题解：

本题可采用简单动态规划（能熟练掌握动态规划的人在我校就是人才啊）。设f[i,j]表示前i种花放在前j个花盆里的最大方案数，那么：

f[i,j]=sum(f[i-1,j-x]) (0<=x<=min(a[i],j))

状态转移方程的含义为：前j个花盆里，第i种花最少放0个，最多放min{a[i],j}个。

其中min{a[i],j}表示第i种花的数目和花盆的数目中较少的那一个。

边界条件：f[1,j]=1 (i<=a[1])。

接下来就不给题例了，不是我们的能力可以处理的，让我们看一下高手级水平（6~7级）

六级标准（NOIP提高组全国前50%）

定义：掌握基本的数据结构知识，能够根据实际需求设计算法编写程序，解决问题。

知识要求：

1、 树、图的存储。

2、 哈希表、集合数据结构。

3、 图的最短路，生成树算法，有向图的拓扑排序算法。

4、 动态规划的常见模型，分治策略，各种排序算法。

5、 可重集组合，二项式定理，数列与级数，归纳与递推，容斥原理，函数的连续 性、函数的单调性和极值。

能力要求：

1、 能对一些算法和数据结构估算时间复杂度和空间复杂度。

2、 能根据实际问题的模型选择合适的算法和数据结构来解决问题。

3、 具备知识收集和知识管理的能力。

七级标准（NOIP提高组全国前20%）

定义：综合运用算法和数据结构编写程序，解决问题。

知识要求：

1、 并查集，线段树，哈弗曼树，二叉排序树，二叉堆。

2、 图的连通性算法，最短路，最小生成树的优化算法，二分图的构造、判定及匹 配，搜索算法的优化，扩展欧几里得算法。

3、 中国剩余定理，剩余类，概率基础知识，解析几何基础知识。

能力要求：

1、 能根据时间和空间复杂度的要求灵活构造算法和数据结构解决实际问题。

2、 具备较强的程序代码实现能力。

3、 具备较强的归纳、总结和表达能力。

在信息安全的数学基础这门课的实验中，光一个中国剩余定理的实现对同学们来说已经够呛了（当然竞赛中的代码实现的要求会低一些），接下来是大师级（8~10级）

八级标准（NOI铜牌）

定义：掌握高级数据结构知识，能运用恰当算法编写程序，解决较复杂问题。

知识要求：

1、 树状数组，字典树，优先队列，平衡树。

2、 网络流算法，复杂的分治思想，树形动态规划，状态压缩动态规划，二分 图的匹配，启发式搜索。

3、 矩阵概念及其基本运算，线性方程组的解法，迭代法，费马小定理和欧拉 定理，母函数。

能力要求：

1、 能针对复杂问题建立清晰的数学模型。

2、 能运用数学知识、高级数据结构和算法解决复杂的问题。

3、 能根据需要，开展基于写作的学习和研究。

九级标准（NOI银牌）

定义：具有对问题进行抽象和数学建模能力，能选用合适的数据结构和算法编写程序，解决较难问题。

知识要求：

1、 块状链表，后缀数组，后缀树，复杂的线段树。

2、 动态规划优化，模拟退火算法。

3、 计算几何基础知识（点积、叉积、凸包、半平面等知识及应用），数学期望

能力要求：

1、 能针对疑难问题建立清晰的数学模型。

2 、 能灵活运用数学知识、高级数据结构和算法解决疑难问题。

3、 具备发现问题、解决问题的探索研究能力。

十级标准 （NOI金牌）

定义：具有一定的提出问题、解决问题的研究能力，能构造算法与数据结构，解决开放性问题。

知识要求：

1、 最小树形图，自动机，动态树，树套树，一般图的匹配。

2、 双重动态规划，基于连通性的动态规划，线性规划，极大极小搜索算法。

3、 三维计算几何，组合游戏中的NIM问题和SG函数，群的概念，置换群，Burnside 引理，Polya原理，莫比乌斯反演定理，FFT（我都学完复变函数与积分变换，老师都没讲过快速傅里叶变换）。

能力要求

1、 具备创造性地运用数据结构和算法解决开放性问题的能力。

2、 具备很强的代码编写能力。

3、 具备提出问题、并开展相关研究的创新能力。

总结

看完了这些标准，相信大家对自己的编程能力应该有个大概的定位了吧（没错，你是个菜鸟）。新的一年里，祝愿大家好好学习，好好努力，通过自己的不断修炼，最后达到大师水平（如果有生之年可以的话……笑）。