信息学奥赛培训教程C++版.doc

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：1.42M 资料格式：doc 举报版权申诉

kakashishi-6242735-4744300845212625864.doc.pdf-第1页.png

第1页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第2页.png

第2页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第3页.png

第3页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第4页.png

第4页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第5页.png

第5页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第6页.png

第6页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第7页.png

第7页 / 共229页

kakashishi-6242735-4744300845212625864.doc.pdf-第8页.png

第8页 / 共229页

青少年信息学奥林匹克竞赛情况简介

第一章计算机基础知识

1.1 计算机的基本常识

1.1.1 计算机的产生与发展

1.1.2 计算机系统及工作原理

1.1.3 计算机中有关数及编码的知识

1.1.4 原码、反码与补码

1.1.5 逻辑运算

1.2 操作系统

1.2.1 DOS(Disk Operating System)的组成

1.2.2 DOS的文件和目录

1.2.3 DOS命令

1.2.4 Windows简介

1.3 计算机网络常识

1.3.1 网络基础知识

1.3.2 Internet简介

1.4 计算机信息安全基础知识

1.4.1 计算机的网络安全

1.4.2 计算机病毒

1.4.3 病毒的分类

第2章C++编程简介

2.1 机器语言、汇编语言和高级语言

2.2 C语言与C++的历史

2.3 C++标准库

2.4 结构化编程

2.5 简单程序

2.6 简单程序：两个整数相加

2.7 算术运算

2.8 判断：相等与关系运算符

2.9 新型头文件与名字空间

第3章 C++输入/输出流

3.1 简介

3.2 流

3.2.1 iostream类库的头文件

3.2.2 输入/输出流类和对象

3.3 输出流

3.3.1 流插入运算符

3.3.2 连续使用流插入/流读取运算符

3.3.3 输出char*类型的变量

3.3.4 用成员函数put输出字符和put函数的连续调

3. 4 输入流

3.4.1 流读取运算符

3.4.2 成员函数get和getline

3.5 成员函数read、gcount和write的无格式输入/输出

3.6 流操纵算子

3.6.1 整数流的基数：流操纵算子dec、oct、hex和setbase

3.6.2 设置浮点数精度(precision、setprecision)

3.6.3 设置域宽(setw、width)

3.6.4 用户自定义的流操纵算子

3.7 流格式状态

3.7.1 格式状态标志

3.7.2 尾数零和十进制小数点(ios::showpoint)

3.7.3 对齐(ios::left、ios::right、ios::internal)

3.7.4 设置填充字符(fill、setfill)

3.7.5 整数流的基数：(ios::dec、ios::oct、ios::hex、ios::sho

3.7.6 浮点数和科学记数法(ios::scientific、ios::fixed)

3.7.7 大/小写控制(ios::upercase)

3.7.8 设置及清除格式标志(flags、setiosflags、resetosflags)

3.8 流错误状态

第4章文件处理

4.1 简介

4.2 文件和流

4.3 建立并写入文件

4.4 读取文件中的数据

4.5 更新访问文件

第5章 C++的字符串流

5.1 流的继承关系

5.2 字串流的输入操作

5.3 字串流的输出操作

5.4 字串流在数据类型转换中的应用

5.5 输入/输出的状态标志

第6章控制结构

6.1 简介

6.2 算法

6.3 控制结构

6.4 if选择结构

6.5 if/else选择结构

6.6 while重复结构

6.7 构造算法：实例研究1(计数器控制重复)

6.8 构造算法与自上而下逐步完善：实例研究2(标记控制重复)

6.9 构造算法与自上而下逐步完善：实例研究3(嵌套控制结构)

6.10 赋值运算符

6.11 自增和自减运算符

6.12 计数器控制循环的要点

6.13 for重复结构

6.14 for结构使用举例

6.15 switch多项选择结构

6.16 do/while重复结构

6.17 break和continue语句

6.18 逻辑运算符

6.19 混淆相等(==)与赋值(=)运算符

6.20 结构化编程小结

第7章函数

7.1 简介

7.2 数学函数库

7.3 函数

7.4 函数定义

7.5 头文件

7.6 作用域规则

7.7 递归

7.8 使用递归举例，Fibonacci数列

7.9 递归与迭代

7.10 带空参数表的函数

7.11 内联函数

7.12 函数重载

第8章数组

8.1 简介

8.2 数组

8.3 声明数组

8.4 使用数组的举例

8.5 将数组传递给函数

8.6 排序数组

8.7 查找数组：线性查找与折半查找

8.8 多维数组

第9章指针与字符串

9.1 简介

9.2 指针变量的声明与初始化

9.3 指针运算符

9.4 按引用调用函数

9.5 指针与常量限定符

9.6 按引用调用的冒泡排序

9.7 指针表达式与指针算法

9.8 指针与数组的关系

9.9 指针数组

9.10 函数指针

9.11 字符与字符串处理简介

9.11.1 字符与字符串基础

9.11.2 字符串处理库的字符串操作函数

第10章信息学奥赛中的常用算法

10.1 算法简介

10.2 枚举算法

10.3 回溯算法

10.4 递归算法

10.5 递推算法

10.6 分治算法

10.7 贪心算法

10.8 搜索算法一（深度优先）

10.9 搜索算法二（广度优先）

10.10 动态规划法

10.11 高精度计算

附录

ASCII表

目录青少年信息学奥林匹克竞赛情况简介 .................. 5 第一章计算机基础知识 ............................ 7 1.1 计算机的基本常识 ................................................................................................................... 7 1.1.1 计算机的产生与发展 ...................................................................................................... 7 1.1.2 计算机系统及工作原理 ..................................................................................................7 1.1.3 计算机中有关数及编码的知识 ......................................................................................8 1.1.4 原码、反码与补码 ........................................................................................................ 10 1.1.5 逻辑运算 ........................................................................................................................ 10 1.2 操作系统....................................................................................................................................11 1.2.1 DOS(Disk Operating System)的组成 .............................................................................11 1.2.2 DOS 的文件和目录 ........................................................................................................ 11 1.2.3 DOS 命令 ........................................................................................................................ 12 1.2.4 Windows 简介 ................................................................................................................. 12 1.3 计算机网络常识....................................................................................................................... 13 1.3.1 网络基础知识 ................................................................................................................ 13 1.3.2 Internet 简介 ....................................................................................................................14 1.4 计算机信息安全基础知识....................................................................................................... 16 1.4.1 计算机的网络安全 ........................................................................................................ 16 1.4.2 计算机病毒 .................................................................................................................... 17 1.4.3 病毒的分类 .................................................................................................................... 17 第 2 章 C++编程简介 ............................... 19 2.1 机器语言、汇编语言和高级语言 .........................................................................................19 2.2 C 语言与 C++的历史............................................................................................................. 20 2.3 C++标准库 .............................................................................................................................. 20 2.4 结构化编程 ............................................................................................................................. 21 2.5 简单程序 ................................................................................................................................. 22 2.6 简单程序：两个整数相加 .....................................................................................................25 2.7 算术运算 ................................................................................................................................. 27 2.8 判断：相等与关系运算符 .....................................................................................................29 2.9 新型头文件与名字空间 ......................................................................................................... 31 第 3 章 C++输入/输出流 ............................ 33 3.1 简介 ......................................................................................................................................... 33 3.2 流 ............................................................................................................................................. 33 iostream 类库的头文件 ............................................................................................... 34 3.2.1 3.2.2 输入/输出流类和对象 .................................................................................................34 3.3 输出流 ..................................................................................................................................... 35 －1－

3.3.1 流插入运算符 .............................................................................................................. 35 3.3.2 连续使用流插入/流读取运算符 .................................................................................37 3.3.3 输出 char*类型的变量................................................................................................ 37 3.3.4 用成员函数 put 输出字符和 put 函数的连续调 ....................................................... 38 3. 4 输入流 .................................................................................................................................... 39 3.4.1 流读取运算符 .............................................................................................................. 39 3.4.2 成员函数 get 和 getline............................................................................................... 41 3.5 成员函数 read、gcount 和 write 的无格式输入/输出 ..........................................................44 3.6 流操纵算子 ............................................................................................................................. 45 3.6.1 整数流的基数：流操纵算子 dec、oct、hex 和 setbase...........................................45 3.6.2 设置浮点数精度(precision、setprecision)................................................................. 46 3.6.3 设置域宽(setw、width)...............................................................................................47 3.6.4 用户自定义的流操纵算子..........................................................................................48 3.7 流格式状态 ............................................................................................................................. 49 3.7.1 格式状态标志 .............................................................................................................. 50 3.7.2 尾数零和十进制小数点(ios::showpoint)....................................................................50 3.7.3 对齐(ios::left、ios::right、ios::internal)..................................................................... 51 3.7.4 设置填充字符(fill、setfill) ..........................................................................................53 3.7.5 整数流的基数：(ios::dec、ios::oct、ios::hex、ios::showbase)............................... 54 3.7.6 浮点数和科学记数法(ios::scientific、ios::fixed)...................................................... 55 3.7.7 大/小写控制(ios::upercase)......................................................................................... 56 3.7.8 设置及清除格式标志(flags、setiosflags、resetosflags)........................................... 57 3.8 流错误状态 ............................................................................................................................. 58 第 4 章文件处理 .................................. 61 4.1 简介 ......................................................................................................................................... 61 4.2 文件和流 ................................................................................................................................. 61 4.3 建立并写入文件 ..................................................................................................................... 61 4.4 读取文件中的数据 ................................................................................................................. 65 4.5 更新访问文件 ......................................................................................................................... 67 第 5 章 C++的字符串流 ............................. 68 5.1 流的继承关系......................................................................................................................... 68 5.2 字串流的输入操作 ................................................................................................................. 68 5.3 字串流的输出操作 ................................................................................................................. 69 5.4 字串流在数据类型转换中的应用 .........................................................................................70 5.5 输入/输出的状态标志 ............................................................................................................71 第 6 章控制结构 ................................. 74 6.1 简介 ......................................................................................................................................... 74 6.2 算法 ......................................................................................................................................... 74 6.3 控制结构 ................................................................................................................................. 74 6.4 if 选择结构 ..............................................................................................................................75 6.5 if/else 选择结构 ...................................................................................................................... 76 －2－

6.6 while 重复结构....................................................................................................................... 78 6.7 构造算法：实例研究 1(计数器控制重复)........................................................................... 78 6.8 构造算法与自上而下逐步完善：实例研究 2(标记控制重复)...........................................80 6.9 构造算法与自上而下逐步完善：实例研究 3(嵌套控制结构)...........................................85 6.10 赋值运算符........................................................................................................................... 88 6.11 自增和自减运算符 ............................................................................................................... 88 6.12 计数器控制循环的要点 ....................................................................................................... 91 6.13 for 重复结构 ..........................................................................................................................92 6.14 for 结构使用举例 ..................................................................................................................94 6.15 switch 多项选择结构 ............................................................................................................97 6.16 do/while 重复结构 .............................................................................................................. 101 6.17 break 和 continue 语句 ....................................................................................................... 102 6.18 逻辑运算符......................................................................................................................... 104 6.19 混淆相等(==)与赋值(=)运算符.........................................................................................105 6.20 结构化编程小结................................................................................................................. 106 第 7 章函数 ..................................... 108 7.1 简介 ....................................................................................................................................... 108 7.2 数学函数库 ........................................................................................................................... 108 7.3 函数 ....................................................................................................................................... 109 7.4 函数定义 ............................................................................................................................... 109 7.5 头文件 ....................................................................................................................................112 7.6 作用域规则 ........................................................................................................................... 113 7.7 递归 ........................................................................................................................................116 7.8 使用递归举例，Fibonacci 数列 .......................................................................................... 118 7.9 递归与迭代 ........................................................................................................................... 120 7.10 带空参数表的函数 ............................................................................................................. 121 7.11 内联函数 ............................................................................................................................. 122 7.12 函数重载 ............................................................................................................................. 123 第 8 章数组 ..................................... 125 8.1 简介 ....................................................................................................................................... 125 8.2 数组 ....................................................................................................................................... 125 8.3 声明数组 ............................................................................................................................... 126 8.4 使用数组的举例 ................................................................................................................... 126 8.5 将数组传递给函数 ............................................................................................................... 137 8.6 排序数组 ............................................................................................................................... 141 8.7 查找数组：线性查找与折半查找 .......................................................................................142 8.8 多维数组 ............................................................................................................................... 147 第 9 章指针与字符串 ............................. 153 9.1 简介 ....................................................................................................................................... 153 9.2 指针变量的声明与初始化 ................................................................................................... 153 9.3 指针运算符 ........................................................................................................................... 154 －3－

9.4 按引用调用函数 ................................................................................................................... 156 9.5 指针与常量限定符 ............................................................................................................... 158 9.6 按引用调用的冒泡排序 ....................................................................................................... 163 9.7 指针表达式与指针算法 ....................................................................................................... 167 9.8 指针与数组的关系 ............................................................................................................... 169 9.9 指针数组 ............................................................................................................................... 173 9.10 函数指针 ............................................................................................................................. 173 9.11 字符与字符串处理简介 ..................................................................................................... 177 9.11.1 字符与字符串基础.................................................................................................. 177 9.11.2 字符串处理库的字符串操作函数..........................................................................179 第 10 章信息学奥赛中的常用算法 ................. 185 10.1 算法简介 ............................................................................................................................. 185 10.2 枚举算法 ............................................................................................................................. 187 10.3 回溯算法 ............................................................................................................................. 191 10.4 递归算法 ............................................................................................................................. 193 10.5 递推算法 ............................................................................................................................. 196 10.6 分治算法 ............................................................................................................................. 200 10.7 贪心算法 ............................................................................................................................. 202 10.8 搜索算法一（深度优先）................................................................................................. 205 10.9 搜索算法二（广度优先）................................................................................................. 209 10.10 动态规划法....................................................................................................................... 212 10.11 高精度计算 ....................................................................................................................... 215 附录 ......................................... 228 ASCII 表.........................................................................................................................................228 －4－

青少年信息学奥林匹克竞赛情况简介信息学奥林匹克竞赛是一项旨在推动计算机普及的学科竞赛活动，重在培养学生能力，使得有潜质有才华的学生在竞赛活动中锻炼和发展。近年来，信息学竞赛活动组织逐步趋于规范和完善，基本上形成了“地级市——省(直辖市)——全国——国际”四级相互接轨的竞赛网络。现把有关赛事情况简介如下：全国青少年信息学（计算机）奥林匹克分区联赛：在举办 1995 年 NOI 活动之前，为了扩大普及的面，并考虑到多数省、直辖市、自治区已经开展了多年省级竞赛，举办了首届全国青少年信息学（计算机）奥林匹克分区联赛。考虑到不同年级学生的知识层次，也为了鼓励更多的学生积极参与，竞赛设提高组、普及组，并分初、复赛进行，这样可以形成一个梯队，确保每年的竞赛活动有比较广泛扎实的基础。从 1995 年起，至 2001 年共举办了七届全国青少年信息学奥林匹克分区联赛，每年举办一次（下半年十月左右），有选手个人奖项（省、国家级）、选手等级证书、优秀参赛学校奖项。安徽省青少年信息学（计算机）奥林匹克复决赛（简称 AHOI）：省级信息学奥赛是一个水平较高的、有较大影响力的学科竞赛。由各市组织代表队参赛，参赛名额实行动态分配制度，每年举办一次（上半年五月左右）。从 1984 年起安徽省奥林匹克竞赛活动得到了蓬勃发展。奖项有个人一、二、三等奖，女选手第一、二、三名，奖励学校团体总分 1-8 名、市团体总分 1-8 名。全国青少年信息学（计算机）奥林匹克竞赛（简称 NOI）：由中国算机学会主办的、并与国际信息学奥林匹克接轨的一项全国性青少年学科竞赛活动。 1984 年举办首届全国计算机竞赛。由各省市组织参赛，每年举办一次。奖项有个人一、二、三等奖，女选手第一、二、三名，各省队团体总分名次排队。国际青少年信息学（计算机）奥林匹克竞赛（简称 IOI）：每年举办一次，由各参赛国家组队参赛。全国青少年信息学（计算机）奥林匹克分区联赛竞赛大纲一、初赛内容与要求：（#表示普及组不涉及，以下同）计基算本机常的识计基算本机操的作程序设计基本知 *在现代社会中的应用 *计算机中的数的表示 *计算机网络 *特点 * 诞生与发展 * 计算机系统的基本组成 * 计算机的工作原理# * 计算机信息安全基础知识 * MS DOS 与 Windows 的使用基础 * 常用输入/输出设备的种类、功能、使用 * 汉字输入/输出方法 * 常用计算机屏示信息程序的表示 * 自然语言的描述 * PASCAL 或 BASIC 语言数据结构的类型 * 简单数据的类型程序设计 * 构造类型：数组、字符串 * 了解基本数据结构（线性表、队列与栈） * 结构化程序的基本概念 * 阅读理解程序的基本能力－5－

识基本算法处理 * 具有完成下列过程的能力：现实世界（指知识范畴的问题） —>信息世界（表达解法） —>计算机世界（将解法用计算机能实现的数据结构和算法描述出来） * 简单搜索 * 字串处理 * 排序 * 统计 * 简单的回溯算法 * 简单的递归算法 * 查找 * 分类 * 合并二、复赛内容与要求：计算机软件数据结构程序设计算法处理 *操作系统的使用知识 *编程语言的使用 *结构类型中的记录类型 *指针类型 *文件（提高组必须会使用文本文件输入） *链表 *树 *图# *程序设计能力 *设计测试数据的能力 *运行时间和占用空间的估算能力# *排列组合的应用 *进一步加深回溯算法、递归算法 *分治法 *搜索算法：宽度、深度优先算法 *表达式处理：计算、展开、化简等# *动态规划# 在初赛的内容上增加以下内容(2008 年修改稿)：三、初赛试题类型：注：试题语言两者选一（程序设计语言： FREE PASCAL、C、C++） *判断 *填空 *完善程序 *读程序写运行结果 *问答四、推荐读物： *分区联赛辅导丛书 *学生计算机世界报及少年电世界杂志－6－

第一章计算机基础知识 1.1 计算机的基本常识 1.1.1 计算机的产生与发展计算机的产生是 20 世纪最重要的科学技术大事件之一。世界上的第一台计算机（ENIAC）于 1946 年诞生在美国宾夕法尼亚大学，到目前为止，计算机的发展大致经历了四代： ① 第一代电子管计算机，始于 1946 年，结构上以 CPU 为中心，使用计算机语言，速度慢，存储量小，主要用于数值计算； ② 第二代晶体管计算机，始于 1958 年，结构上以存储器为中心，使用高级语言，应用范围扩大到数据处理和工业控制； ③ 第三代中小规模集成电路计算机，始于 1964 年，结构上仍以存储器为中心，增加了多种外部设备，软件得到了一定的发展，文字图象处理功能加强； ④ 第四代大规模和超大规模集成电路计算机，始于 1971 年，应用更广泛，很多核心部件可集成在一个或多个芯片上，从而出现了微型计算机。我国从 1956 年开始电子计算机的科研和教学工作，1983 年研制成功 1 亿/秒运算速度的“银河”巨型计算机，1992 年 11 月研制成功 10 亿/秒运算速度的“银河 II”巨型计算机，1997 年研制了每秒 130 亿运算速度的“银河 III”巨型计算机。目前计算机的发展向微型化和巨型化、多媒体化和网络化方向发展。计算机的通信产业已经成为新型的高科技产业。计算机网络的出现，改变了人们的工作方式、学习方式、思维方式和生活方式。 1.1.2 计算机系统及工作原理 1.计算机的系统组成计算机系统由软件和硬件两部分组成。硬件即构成计算机的电子元器件；软件即程序和有关文档资料。 (1) 计算机的主要硬件输入设备：键盘、鼠标、扫描仪等。输出设备：显示器、打印机、绘图仪等。中央处理器（CPU）：包括控制器和运算器运算器，可以进行算术运算和逻辑运算；控制器是计算机的指挥系统，它的操作过程是取指令——分析指令——执行指令。存储器：具有记忆功能的物理器件，用于存储信息。存储器分为内存和外存 ①内存是半导体存储器(主存）：它分为只读存储器(ROM)和随机存储器(RAM)和高速缓冲存储器（Cache)； ROM:只能读，不能用普通方法写入，通常由厂家生产时写入，写入后数据不容易丢失，也可以用特殊方法（如紫外线擦除（EPROM)或电擦除(EEPROM_)存储器)； RAM:可读可写，断电后内容全部丢失； Cache:因为 CPU 读写 RAM 的时间需要等待，为了减少等待时间，在 RAM 和 CPU 间需要设置－7－

高速缓存 Cache,断电后其内容丢失。 ②外存：磁性存储器——软盘和硬盘；光电存储器——光盘，它们可以作为永久存器； ③存储器的两个重要技术指标：存取速度和存储容量。内存的存取速度最快(与 CPU 速度相匹配)，软盘存取速度最慢。存储容量是指存储的信息量，它用字节(Byte)作为基本单位， 1 字节用 8 位二进制数表示，1KB=1024B，1MB=1024KB，lGB=1024MB (2)计算机的软件计算机的软件主要分为系统软件和应用软件两类： ①系统软件：为了使用和管理计算机的软件，主要有操作系统软件如，WINDOWS 95／98／ 2000／NT4．0、DOS 6．0、UNIX 等；WINDOWS 95／98／2000／NT4．0 是多任务可视化图形界面，而 DOS 是字符命令形式的单任务的操作系统。 ②应用软件：为了某个应用目的而编写的软件，主要有辅助教学软件(CAI)、辅助设计软件 (CAD)、文字处理软件、工具软件以及其他的应用软件。 2.计算机的工作原理到目前为止,电子计算机的工作原理均采用冯.若依曼的存储程序方式,即把程序存储在计算机内, 由计算机自动存取指令（计算机可执行的命令=操作码+操作数）并执行它。工作原理图如下： 1.1.3 计算机中有关数及编码的知识 1.计算机是智能化的电器设备计算机就其本身来说是一个电器设备，为了能够快速存储、处理、传递信息，其内部采用了大量的电子元件，在这些电子元件中，电路的通和断、电压高低，这两种状态最容易实现，也最稳定、也最容易实现对电路本身的控制。我们将计算机所能表示这样的状态，用 0，1 来表示、即用二进制数表示计算机内部的所有运算和操作。 2.二进制数的运算法则二进制数运算非常简单，计算机很容易实现，其主要法则是： 0*0=0 0*1=0 1*0=0 1*1=1 0+0=0 0+1=1 1+0=1 1+1=0 由于运算简单，电器元件容易实现，所以计算机内部都用二进制编码进行数据的传送和计算。 3.十进制与二进制、八进制、十六进制数之间的相互转换 (1)数的进制与基数计数的进制不同，则它们的基数也不相同，如表 1-1 所示。进制二进制八进制基数 0 ,1 0,1,2,3,4,5,6,7 －8－特点逢二进一逢八进一

分享到：

赞收藏

资料库

信息学奥赛培训教程C++版.doc

相关推荐

课程资源

热门标签

最新资料