“江西省信息学奥赛辅导”讲座课件.ppt

祝贺江西省信息学奥赛辅导员班开班,力争成为一名优秀的辅导老师白似雪2005.9.26下午,现状分析：1、信息学竞赛很多学校不够重视；2、学生不敢重视，怕影响高考；3、对辅导老师的要求高；4、参与竞赛的学生中优秀学生偏少。,原因：急功近利思想严重。高考不考的科目，担心花了时间得不到奖。有兴趣者多，但投入者少。缺乏一定的条件。误区：影响高考，对高考无帮助。认为可以突击，竞赛前匆忙准备一下。,选好苗子、重点栽培：应在理科尤其是数学成绩好的学生中发现、寻找，重点栽培。最好要从初中甚至可以从小学开始，要拿大奖，非一朝一夕之功。做到有所为有所不为。做好学生家长的工作。力争他们的配合。,基础知识数据结构程序设计语言（C/C+/Pascal语言）编译原理结构化程序设计算法设计算法的复杂性分析与估算数学知识（集合论、排列组合、简单图论、数理逻辑、容斥原理与鸽巢原理、Polya原理）扎实的基础是获大奖的必要条件,一、信息学竞赛涉及的几个重要问题,3.不能操之过急，应循序渐进应根据学生的特点，安排好辅导内容。上述基础知识的掌握，可以交叉进行。正确安排好学习时间，不但不会影响其他课程的正常学习，反而会有促进作用。在辅导过程中，应注重保护学生的创造性思维。,算法：求解问题的步骤或规则的描述。特点：1、确定性；2、有穷性；3、可行性；4、输入；5、输出。,二、算法,算法评估：对算法复杂性进行评估。1时间复杂性2空间复杂性例：计算：,算法一：y=a0;for(i=1;i=n;i+)t=ai;for(j=1;j=0;i-)y=y*x+ai;printf(“f(x)=%f”,y);,这两个算法复杂性差别很大。启示：解决问题的算法应该推敲，这对竞赛极为重要。尤其是NOI竞赛或IOI竞赛。一个虽然正确的算法可能在竞赛中得不到分。由此可见，对算法进行复杂性估算也相当重要。不会估算算法的复杂性，拿高分困难,常见复杂性量级估计：,注：应努力追求O(1)和O(n)的算法。,三、算法的分类,排序算法：冒泡法、插入排序、合并排序、快速排序、堆排序、拓扑排序、选择排序等。查找算法：顺序查找、二分法查找、深度优先查找、广度优先查找等。初等算法：计数算法、统计算法、大数运算算法、其他数学运算算法等。,4.回溯算法5.递归算法6.分治算法7.枚举算法8.模拟算法9.贪心算法10.动态规划算法。今天，我们不能就任何算法展开讨论，因为我们的时间太短，希望各位认真研究上述诸算法。,四、重点与难点,根据近几年竞赛的情况及竞赛大纲，我认为应把重点放在如下几类算法上。1、搜索类算法2、动态规划类算法该算法比较难掌握，但是竞赛的重点。几乎每年都有用此算法来解的题。,五：举例,例：乘数最大设有一个长度为n的数字串，要求使用k个乘号将它分成k1个部分，找出一种分法，使得这k1个部分的乘积最大（其中：2N40,1k6）。比如有一个数字串312，当n3，k1时有两种分法，即：31236和31262符合题目的要求是62。请编写程序求正确答案。,解：由于n的上限为40，乘号数k的上限为6，因此最大乘积位数的上限接近42位。显然，用计算机运算，任何整数类型都无法表达如此大的数，只能采用高精度(大数)运算。关于高精度运算也是我们竞赛要掌握的内容，限于时间，我们就不多说了。高精度运算相对于竞赛是比较容易的。,程序如下：for(i=1;i=n;i+)ansi,0=数字s1s2si构成的整数;for(i=2;i=n;i+)for(j=1;j=min(i-1,k);j+)ansi,j=0;for(m=j;m=i-1;m+)t=数字sm+1sm+2si构成的整数;,ansi,j=maxansi,j,ansm,j-1*t;下面我们用动态规划来思考一下：假设在数字串s1si(2=i=n)中要插入j个*，我们可以这样思考，先在s1sm中插入了j-1个*，即第j+1项为：,有了上述分析，接下来就只需直接写程序了。写程序是比较简单的工作。见前面。用动态规划解