目 录
青少年信息学奥林匹克竞赛情况简介 ................. 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
3.2.1 iostream类库的头文件 .............................................................................................. 34 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－
程序设计
信息学奥赛培训教程C++版
