走进OI魅力无限.ppt

走进OI 魅力无限,教练：熊永成 电话汉诺塔游戏,/flash/293_1.htm 玩后的体会 当木块过多时，很麻烦，耗费大量时间 能否寻求计算机的帮助,关于汉诺塔,传说在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 不论这个传说的可信度有多大，我们可以用科学的方法计算移动时间。不难证明移动n片金片要经过次数为f(n)=2n-1。n=64时，假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，需要18446744073709551615/31556952=584554049253.855年这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。,什么是OI,OI是Olympiad in Informatics的简称,指的是“信息学奥林匹克竞赛”，是一项在中学生中广泛开展的一门学科竞赛，和物理、数学竞赛性质相同。考的内容主要是计算机编程。OI的比赛有NOIP，NOI，IOI等。 1、NOIP：全国青少年信息学奥林匹克竞赛分区联赛 复赛定于每年11月的第二个星期六举行，两试共7小时个小时完成。 全国一等奖的选手具有名校自主招生优先录取、参加夏令营、冬令营资格。部分优秀选手高考上重本即可录取。 2、NOI：全国青少年信息学奥林匹克竞赛全国决赛 每年7月份，全国各省（含香港、澳门）30多个队约300人参加； 奖项：一等奖即金牌50人清华、北京大学直接点招（保送，不用参加保送考试） 二等奖即银牌50人签订协议，高考上重本线即可录取 三等奖即铜牌100人签订协议，高考上重本线即可录取 3、IOI：国家代表队参加国际信息学奥林匹克竞赛（每年8月份）,绵阳中学历年信息学竞赛成绩,以上数据均为全国一等奖，获奖者均已保送清华、北大、复旦、上交、浙大等名牌大学。,OI的特点,难、挫折感强 NOIP：6道题，每题100分，共600分，2012年一等分数线275分，分数线最低一年是130分(满分400) 计算机评分，只看结果，没有过程分。这就要求同学们在编程时一定非常小心细致，绝不能出让测评机找到一点瑕疵。 磨练意志，成就感强 攻克难题的那种快感是无与伦比的 文成明：高中参加信息学竞赛，只得到三等奖，进入电子科大，参加acm获亚洲区金牌，被保送至中国科学院研究生院数学科学学院研究生,学会选择,OI，不是雪中送炭，而是锦上添花。 处理好OI与常规课程的关系， 完成常规课后一定花时间OI， 养成好习惯，多想、多问、多练， 遵守纪律、抵制网络诱惑。,课程安排,上课安排 每周一、周五第二三节晚自习到机房一上课 课程进度 高一上：C+语法和简单算法 高一下：数据结构、搜索、动态规划、图论 高二上：备战NOIP 高二下：备战省选及NOI 高三上：备战NOIP,加法乘法原理,加法原理和乘法原理在信息学竞赛中有着非常广泛的应用，尤其是它把事情按性质“分类、分步”的思想。 1.加法原理： 做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn 种不同的方法。 2.乘法原理： 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。 3.两个原理的区别： 一个与分类有关，一个与分步有关； 加法原理是“分类完成”，乘法原理是“分步完成”。,加法原理,生活中的例子： 从学校回到家，有3类方法： 走路：有1种方法 坐汽车：有2种方法，（公共汽车、小汽车） 坐飞机：有2种方法，（小飞机，大飞机） 从学校回到家的不同方法总数=1+2+2=5,乘法原理,生活中的例子： 从教室经过学校大门回到家： 从教室到校门口有2条路 从校门口回到家有3条路 从教室经过学校大门回到家共有2*3=6种不同的方法 乘法原理可由加法原理得到： 从教室经过学校大门回到家可分为2类方法 走第1条路到校门口，再回到家，共3种方法 走第2条路到校门口，再回到家，共3种方法 由加法原理：从教室经过学校大门回到家共有3+3=6种不同的方法。 3+3=2*3,例1.由数字1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？,分3步完成:用乘法原理 第1步确定百位数字：有12345共5种方法， 第2步确定十位数字：有12345共5种方法， 第3步确定个位数字：有12345共5种方法， 方法总数5*5*5=125,例2.由数字0、1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？,分3步完成:用乘法原理 第1步确定百位数字：有12345共5种方法， 第2步确定十位数字：有012345共6种方法， 第3步确定个位数字：有012345共6种方法， 方法总数5*6*6=180,例3.由数字0，1，2，3，4，5可以组成多少个十位数字大于个位数字的两位数？,十位数字共有12345共分5类方法完成,用加法原理 当十位数字为1,个位数只能是0，共有1种方法 当十位数字为2,个位数只能是01，共有2种方法 当十位数字为3,个位数只能是012，共有3种方法 当十位数字为4,个位数只能是0123，共有4种方法 当十位数字为5,个位数只能是01234，共有5种方法 方法总数1+2+3+4+5=15,发射导弹,一枚地空导弹的命中率为50%，要击落一架敌机，要求命中率达到90%，最少需同时发射几枚这样的地空导弹？ 问题可等价转换为：连续发射N枚均不命中的概率为多少？ 发射第1枚不命中概率：1/2 发射第2枚也不命中概率：1/2 *1/2 发射第3枚也不命中概率：1/2 *1/2*1/2 发射第4枚也不命中概率：1/2 *1/2*1/2*1/2,走楼梯,从第0级台阶出发，要恰好走到第10级台阶，每次最多只能走2级台阶，共有多少种不同的方法？ 到达台阶i，共有2类不同的方法： 0i-1i或0i-2i 设f(i)表示走到第i级台阶的方法总数 由加法原理：f(i)=f(i-1)+f(i-2) 边界：f(1)=1;f(2)=2,求路径,求从V1到V10的路径总数 从V1-V10有两类方法： 从V1-V8-V10和V1-V9-V10。 设fi表示从V1到达Vi的路径数，则由加法原理得f10=f8+f9。 f9=f5+f6+f7 f8=f5+f6 边界：f1=1,信息学与数学的关系,信息学与数学有着莫大的关系，可以说数学是信息学的基石，信息学是数学的实现方式。 学好信息学必须具备良好的数学功底和逻辑思维能力。 要用计算机来完成以上题目，我们还得先学习计算机语言，下面我们正式进入C+语言的学习。,计算机的工作原理,根据计算机的工作原理可知，我们的程序也必须包含输入、处理、输出三步曲,例题演示,程序1-1 printf函数 程序1-4 定义变量 scanf函数,C+中数据的存储,天下万物皆数字0、1，保存在不同的容器中 整数：int(-231231-1)、long long(-263263-1) 实数：double(-1.7*103081.7*10308) 字符：