走进OI魅力无限.ppt

《走进OI魅力无限.ppt》由会员分享，可在线阅读，更多相关《走进OI魅力无限.ppt（22页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、走进OI魅力无限 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望汉诺塔游戏nhttp:/ 传说在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消

2、灭，而梵塔、庙宇和众生也都将同归于尽。n 不论这个传说的可信度有多大，我们可以用科学的方法计算移动时间。不难证明移动n片金片要经过次数为f(n)=2n-1f(n)=2n-1。n=64时，假如每秒钟一次，共需多长时间呢？一个平年365天有31536000 秒，闰年366天有31622400秒，平均每年31556952秒，计算一下，需要18446744073709551615/31556952=584554049253.855年这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同

3、梵塔、庙宇等，都早已经灰飞烟灭。什么是OIn OI是Olympiad in Informatics的简称,指的是“信息学奥林匹克竞赛”，是一项在中学生中广泛开展的一门学科竞赛，和物理、数学竞赛性质相同。考的内容主要是计算机编程。OI的比赛有NOIP，NOI，IOI等。n 1 1、NOIPNOIP：全国青少年信息学奥林匹克竞赛分区联赛：全国青少年信息学奥林匹克竞赛分区联赛n 复赛定于每年11月的第二个星期六举行，两试共7小时个小时完成。全国一等奖的选手具有名校自主招生优先录取、参加夏令营、冬令营资格。部分优秀选手高考上重本即可录取。n 2 2、NOINOI：全国青少年信息学奥林匹克竞赛全国决赛：

4、全国青少年信息学奥林匹克竞赛全国决赛n 每年7月份，全国各省（含香港、澳门）30多个队约300人参加；奖项：一等奖即金牌50人清华、北京大学直接点招（保送，不用参加保送考试） 二等奖即银牌50人签订协议，高考上重本线即可录取 三等奖即铜牌100人签订协议，高考上重本线即可录取 n 3 3、IOIIOI：国家代表队参加国际信息学奥林匹克竞赛（每年：国家代表队参加国际信息学奥林匹克竞赛（每年8 8月份）月份）绵阳中学历年信息学竞赛成绩200420052006200720082009201020112012全市5人绵中2人全市7人绵中6人全市18人绵中6人全市20人绵中13人全市30人绵中20人全市

5、41人绵中26人 全市19人绵中5人 全市17人绵中7人全市25人绵中10人n 以上数据均为全国一等奖，获奖者均已保送清华、北大、复旦、上交、浙大等名牌大学。OI的特点n 难、挫折感强n NOIP：6道题，每题100分，共600分，2012年一等分数线275分，分数线最低一年是130分(满分400)n 计算机评分，只看结果，没有过程分。这就要求同学们在编程时一定非常小心细致，绝不能出让测评机找到一点瑕疵。n 磨练意志，成就感强n 攻克难题的那种快感是无与伦比的n 文成明：高中参加信息学竞赛，只得到三等奖，进入电子科大，参加acm获亚洲区金牌，被保送至中国科学院研究生院数学科学学院研究生学会选择

6、nOI，不是雪中送炭，而是锦上添花。n处理好OI与常规课程的关系，完成常规课后一定花时间OI，养成好习惯，多想、多问、多练，遵守纪律、抵制网络诱惑。课程安排n 上课安排n 每周一、周五第二三节晚自习到机房一上课n 课程进度n 高一上：C+语法和简单算法高一下：数据结构、搜索、动态规划、图论高二上：备战NOIP高二下：备战省选及NOI高三上：备战NOIP加法乘法原理n 加法原理和乘法原理在信息学竞赛中有着非常广泛的应用，尤其是它把事情按性质“分类、分步”的思想。n 1.加法原理： n 做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n

7、类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn 种不同的方法。 n 2.乘法原理： n 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。 n 3.两个原理的区别：n 一个与分类有关，一个与分步有关；n 加法原理是“分类完成”，乘法原理是“分步完成”。加法原理n 生活中的例子：n 从学校回到家，有3类方法：n 走路：有1种方法n 坐汽车：有2种方法，（公共汽车、小汽车）n 坐飞机：有2种方法，（小飞机，大飞机）n 从学校回到家的不同

8、方法总数=1+2+2=5教室家乘法原理n 生活中的例子：n 从教室经过学校大门回到家：n 从教室到校门口有2条路n 从校门口回到家有3条路n 从教室经过学校大门回到家共有2*3=6种不同的方法n 乘法原理可由加法原理得到：n 从教室经过学校大门回到家可分为2类方法 走第1条路到校门口，再回到家，共3种方法 走第2条路到校门口，再回到家，共3种方法n 由加法原理：从教室经过学校大门回到家共有3+3=6种不同的方法。n 3+3=2*3教室校门家例1.由数字1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？n 分分3步完成步完成:用乘法原理乘法原理n 第1步确定百位数字：有12345共

9、5种方法，第2步确定十位数字：有12345共5种方法，第3步确定个位数字：有12345共5种方法，n 方法总数5*5*5=125341253412534125百位十位个位例2.由数字0、1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？n 分分3 3步完成步完成:用乘法原理乘法原理n 第1步确定百位数字：有12345共5种方法，n 第2步确定十位数字：有012345共6种方法，n 第3步确定个位数字：有012345共6种方法，n 方法总数5*6*6=180例3.由数字0，1，2，3，4，5可以组成多少个十位数字大于个位数字的两位数？n 十位数字共有12345共分分5 5类类方法完

10、成,用加法原理加法原理n 当十位数字为1,个位数只能是0，共有1种方法n 当十位数字为2,个位数只能是01，共有2种方法n 当十位数字为3,个位数只能是012，共有3种方法n 当十位数字为4,个位数只能是0123，共有4种方法n 当十位数字为5,个位数只能是01234，共有5种方法n 方法总数1+2+3+4+5=15发射导弹n 一枚地空导弹的命中率为50%，要击落一架敌机，要求命中率达到90%，最少需同时发射几枚这样的地空导弹？n 问题可等价转换为：连续发射N枚均不命中的概率为多少？n 发射第1枚不命中概率：1/2 n 发射第2枚也不命中概率：1/2 *1/2n 发射第3枚也不命中概率：1/2

11、 *1/2*1/2n 发射第4枚也不命中概率：1/2 *1/2*1/2*1/2走楼梯n 从第0级台阶出发，要恰好走到第10级台阶，每次最多只能走2级台阶，共有多少种不同的方法？ n 到达台阶i，共有2类不同的方法：n 0i-1i或0i-2in 设f(i)表示走到第i级台阶的方法总数n 由加法原理：f(i)=f(i-1)+f(i-2)n 边界：f(1)=1;f(2)=2ii-1i-2求路径n 求从V1到V10的路径总数n 从V1-V10有两类方法：n 从V1-V8-V10和V1-V9-V10。n 设fi表示从V1到达Vi的路径数，则由加法原理得f10=f8+f9。f9=f5+f6+f7f8=f5

12、+f6n 边界：f1=1信息学与数学的关系n信息学与数学有着莫大的关系，可以说数学是信息学的基石，信息学是数学的实现方式。n学好信息学必须具备良好的数学功底和逻辑思维能力。n要用计算机来完成以上题目，我们还得先学习计算机语言，下面我们正式进入C+语言的学习。计算机的工作原理n 根据计算机的工作原理可知，我们的程序也必须包含输入、处理、输出三步曲例题演示n程序1-1nprintf函数n程序1-4n定义变量nscanf函数C+中数据的存储n 天下万物皆数字0、1，保存在不同的容器中n 整数：int(-231231-1)、long long(-263263-1)实数：double(-1.7*103081.7*10308)字符：charn 为什么这些数据都有范围大小？n 内存限制。n 以int为例。它是4个字节(B)，1B=8b。在内存中，规定1b是一个存储单元，即可以放一个0或一个1。那么int型的数就是32位的二进制数，除去符号。还剩31位，那么它的范围就是-231231-1。自学+实践完成例题n程序1-1程序1-10n遇到问题及时提问。n星期一晚课结束前必须提交。