当前位置:首页 >> 经济/市场 >>

NOIP培训讲义1


第一次 NOIP 培训简介
培训目的 此培训班是为了帮助同学参加信息学奥林匹克竞赛(简称 OI) ,培养一些高素质的信息 技术人才,激励对计算机有热爱的同学,促进其能力的发展;给那些有才华的学生提供相互 交流和学习的机会;通过竞赛和相关的活动培养和选拔优秀的计算机人才。 信息学奥林匹克竞赛是智力和能力的竞赛,注重考查全面素质与创新能力。 1.国际信息学奥林匹克竞赛(IOI)是计算机知识在世界范围内青少年中普及的产物, 始于 1989 年,与数学、物理和化学奥赛相同,也是一门国际性的中学生学科奥林匹克竞赛。 2.全国青少年信息学奥林匹克竞赛(NOI)和联赛(NOIP)是由教育部、中国科协批 准和举办的面向全国青少年在校学生的一项赛事,每年在全国各省、市举行。该项赛事已成 为我国青少年校外计算机活动中最具有代表性的形式, 每年都吸引着数以万计的青少年投身 到这一活动中。 3.NOI 和 NOIP 在试题难度上有一个层次关系,NOI 注重提高,难度较大,而 NOIP 注重普及,普及面较广,参加的人也较多;具体来说有这样三层:先举办全国信息学奥林匹 克分区联赛(NOIP) ,联赛分为高中级和初中组进行,以普及为主;在分区联赛的基础上, 各省市组成自己的代表队,参加第二层次的比赛,即全国信息学奥林匹克竞赛(NOI) ;第 三个层次是从 NOI 中选拔优秀选手,经过考试选拔,组成国家队,再参加国际信息学奥林 匹克竞赛(IOI) ,这个是国际性的最高水平的竞赛。 培训内容 整个信息奥赛内容可分三个层次,第一是基础篇,主要介绍计算机软硬件基础知识、算 法概述、简单数据结构和结构化编程;第二是语言篇,主要介绍竞赛编程语言 Pascal 的环 境、语句和程序结构;第三是提高篇,主要是深入介绍算法和数据结构。其中 Pascal 语言 会首先开设,旨在让同学尽快对信息奥赛入门,学会一种程序设计语言和结构化编程风格, 打下基础。 1.竞赛形式。联赛分两个年龄组:初中组和高中组。每组竞赛分两轮:初试和复试。 初试形式为笔试, 侧重考察学生的计算机基础知识和编程的基本能力, 并对知识面的广度进 行测试。程序设计的描述语言采用 Pascal 或 Basic, 各省市初试成绩在本赛区前百分之十五 的学生进入复赛。复试形式为上机,侧重考察学生对问题的分析理解能力,数学抽象能力, 驾驭编程语言的能力和编程技巧、想象力和创造性等。程序设计语言可采用 Pascal、Basic、 C/C++或 Java。各省市参加联赛 的等第奖在复试的优胜者中产生。 2.试题形式。每次联赛的试题分四组:初中组初试赛题;初中组复试赛题;高中组初 试赛题;高中组复试赛题。其中,初中组初试赛题和高中组初试赛题类型相同,初中组复试 赛题和高中组复试赛题类型相同,但初中组和高中组的题目不完全相同,高中组难度略高。 3.初复赛试题的知识范围(见大纲) 培训要求 1.思想准备。要有刻苦钻研和知难而进的精神。尽管学生头脑都很聪明, 接受新知识 的能力很强, 基础也不错,但遇到难题时, 如果尝试几次不成功,便等待别人指点, 其实某些 难题按他们的能力是可以独立解决的,不解决这些问题, 他们很难达到较高的层次。 一个 优秀的选手, 必须具有良好的心理素质。 2.自学能力、实践动手能力和创新能力。 3.正确处理好培训和其他功课之间的关系。 4.上课前做好预习,上课时做好笔记,课后认真完成作业。

绪论
一.程序和算法的一些基本概念 1. 程序 程序(program)是指能使计算机完成特定任务并且计算机能够执行的指令的 有序集合。 2. 算法 算法指计算机解决问题的方法和思路。任何问题都有相应的算法,比如寄信过 程、以及一天的学习计划等等。 3. 算法的性质 算法的性质。 a) 能行性。 算法中的每一个操作都应是计算机可以执行的, 这些操作通常是 计算机基本运算所包含的内容,例如算术运算、关系运算、逻辑运算等。 b) 确定性。 算法中的每一步必须有清楚的定义, 不能有二义性或模棱两可的 解释。例如“增加 X 的值” ,并没有说明增加多少,不符合确定性原则。 c) 有穷性。一个算法必须在执行有限次后结束。就是说,一个算法应在有限 的时间内完成,执行时间要合理。因此,算法中不能含有无限循环。 d) 输出。算法执行完毕,至少要有一个输出。 e) 输入。算法执行前应有若干个输入量,也可以没有输入量。 4. 算法的优化 算法的优化。对于同一个问题,可以有不同的算法。例如求 1+2+3+…+100 的 和,可以采用累加的方法:先求 1+2,再加 3,再加 4,一直加到 100,最后得 到结果 5050。也可以采用公式的方法:1+2+3+…+100=(1+100)+(2+99)+ (3+98)+…+(50+51)= 50101 = 5050。无论是累加的方法,还是公式的方 法,对于计算机而言都是适用的。但采用不同的方法,对应的和运算效率往往 会有所不同。因此,为了有效的进行解题,不仅要保证算法正确,还要选择方 法简单、运算步骤少、能尽快得出正确结果的算法。 5. 程序与算法的关系。算法是程序的灵魂 算法是程序的灵魂,程序是算法的外在的表示形式,任何 算法是程序的灵魂 一个程序都可以认为是实现了某种算法,只不过有的算法过于简单而无须指 明。一个算法可以有多种程序代码表现形式。 例:1。交换两个变量的数据 2.求出三个不相同数的最大数 3.求两个正整数 a,b 的最大公约数 二.算法的描述 前面几个例子的算法基本上是用自然语言描述的。 用自然语言描述算法比较容易理 解,但是叙述较繁琐和冗长,并且容易出现“歧义” 。比如“这个人连老张都不认识” , 因此需用一个科学规范的方法来描述算法,常用的有流程图、N-S 图、伪码等。 流程图、 伪码 流程图 流程图是用一组几何图形表示各种类型的操作, 在图形上用简明扼要的文字和符号 流程图 表示具体的操作, 并用带有箭头的流线表示操作的先后次序。 1 列出了流程图的基本 表 符号及其含义。 用流程图描述算法, 能够将所要解决问题的步骤清晰、 直观地表示出来, 所以本章采用流程图描述算法。 表1 图形符号 名
起止框 输入、输出框 处理框


表示算法的开始或结束 表示输入输出操作 表示处理或运算的功能





用来根据给定的条件是否满足决定执行两条路径中的某一 判断框 流线 连接符 路径 表示程序执行的路径,箭头代表方向 表示算法流向的出口连接点或入口连接点,同一对出口与 入口的连接符内必须标以相同的数字或字母

例:用流程图给出下面几个例子的算法 1. 画出看电影的流程图。(买票 入场 找座位 坐下 看电影 出场) 2. 交换两个变量的数据 3. 求出三个不相同数的最大数 4. 求两个正整数 a,b 的最大公约数

三.注意几个问题: ⑴ 刚接触算法时,由于不了解,往往会产生一种错误认识,以为只要把问题原封不动的交 给计算机,计算机就会自动得出结果或结论。例如,若要从南京乘车到西安,希望选择一条 中转次数最少的路线,以为只要把地图扫描进计算机,计算机就会自动给出这样一条路线。 这是一种很常见的错误认识,至少目前是这样的。计算机并不能代替人做所有事情,现在使 用的计算机还只能按照人们事先给定的步骤工作。因此,拿到一个问题后,首先要搞清楚做 什么,再设计好一步一步怎么做,也就是设计解决这个问题的算法,最后选择一种合适的计 算机语言编写程序,使计算机工作,得到正确的结果。所以,解决任何问题,都必须设计算 解决任何问题, 解决任何问题 编写程序。 法、编写程序。 ⑵ 本节介绍的问题均不复杂,相应算法也较简单,学生拿到题目后,往往不认真考虑算法, 一开始就把注意力集中到语言的语法规则和语句上。 学习程序设计, 如果只知道计算机语言 的语法规则,不知道解决问题的算法,就不可能编写出好的程序。语言只是工具,算法才是 程序设计的灵魂。只要算法正确,流程图无误,就可以用任何一种语言编写程序。因此,在

学生刚开始学习程序设计时, 就要注意加强算法设计和流程图设计, 而把计算机语言作为程 序设计的载体。 四.作业: 1) 画出用洗衣机洗衣服的流程图。(提示:用水浸泡衣物,加洗衣粉,判断有无洗干净,直 到最后洗干净为止,最后脱水再晾晒) 2)画出打电话的流程图。(提示:先拿起听筒;判断有无拔号声;再判断有无忙音;再判断 有没有人,直到打通电话为止) 2) 画出解决下列问题的流程图: ① 输入三角形的底 a 和高 h,计算三角形面积 s。 ② 求 10 的阶乘(即 10!=1×2×3×…×10)。 ③ 判断一个数 N 是否为素数

开 始 1→p 1→i i<=10
Y N

p*i→p i+1→i 图2 输出 p 结 束 图3 开始

图1

输入 N

A(被除数) N

B(除数) 2

A 被 B 整除 or B>N-1

B 取下一个整数

B>N-1

输出“N 不是素数”

输出“N 不是素数”

结束


相关文章:
Noip 2013 Day1 解题报告
Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目,答案明显是(x+10^km) mod n,化简一下,就成了(x + m (10^k mod n) ...
NOIP阅读程序1
NOIP 阅读程序(c 语言练习与讲解 1)首先:在做此份练习之前,你应该知道以下内容: 1.数组 2.函数 3.结构体与共用体(联合) 4.指针 5.其他基础内容 1.对比...
NOIP初赛复习整理(1)
NOIP初赛复习整理(1)_学科竞赛_高中教育_教育专区。NOIP初赛复习整理(1)分区联赛初赛复习初赛考的知识点就是计算机基本常识、 基本操作和程序设计基础知识。 其中选择...
NOIP初赛复习——算法1
NOIP初赛复习——算法1_理学_高等教育_教育专区。OK 备战 NOIP2010 提高组初赛复习——算法篇之算法设计的常用策略程序设计主要包括两个方面 ? 结构特性的设计(...
noip普及组复赛入门训练1答案
noip普及组复赛入门训练1答案_学科竞赛_初中教育_教育专区。PASCAL 复习 2 1. 字符统计(文件名 ZFTJ.PAS) 读入一组字符,以“?”作为结束标志,统计其中元音字母...
noip初赛试题1
1, 4, 3, 7, 2 【答案】C。栈操作。 3. 完全二叉树共有 2*N-1 个结点,则它的叶节点数是( )。(NOIP2008) A.N-1 B.N C.2*N D.2 -1 【...
NOIP2011提高组解题报告day1
NOIP2011提高组解题报告day1_学科竞赛_高中教育_教育专区。NOIP2011提高组解题报告day1NOIP2011 提高组解题报告 day1 (2011-12-13 09:29:54) 标签: 杂谈 铺地...
NOIP2001提高组解题报告1
NOIP2001提高组解题报告1_初三数学_数学_初中教育_教育专区。NOIP2001提高组( 第七届 2001) ) 分区联赛复赛解题报告 提 ( 高组) 高组) 俞玮 赵爽 第一题:...
NOIP 初赛理论知识复习资料1
NOIP 初赛理论知识复习资料计算机的诞生与发展,及其特点计算机基本常识 一、计算机的概念: 是一种能迅速而高效的自动完成信息处理的电子设备,它能按照程序对信息进行...
NOIP模拟1
NOIP模拟1_IT/计算机_专业资料。NOIP 信息学 复赛 模拟题 NOIP 普及组复赛模拟题 1.冰壶比赛(curling.pas/c/cpp) .冰壶比赛【问题描述】 在冰壶比赛中,给出...
更多相关标签: