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