资源简介

(共101张PPT)
信息学竞赛培训课程
第一期：走进信息竞赛与C++
www..cn
关于课程
ABOUT
I. 上课时间：每周四下午 16:05-17:35
每周一 ~ 周四晚 18:10-18:50
II. 预期进度：七年级上学期：语法基础
七年级下学期：算法
01、关于时间
02、检测方式
① 期末测验
② 编程技能大赛
③ NOIP全国赛
④ CSP-J/S 全国赛
www..cn
课程内容
CONENTS
01、第一个C++程序
02、简单程序设计
03、选择结构
04、循环结构
赋值语句
运算符与表达式
常量与变量
标准数据类型
数据输入输出
顺序结构实例
if-else语句
switch语句
for语句
while语句
do-while语句
循环嵌套
if语句
www..cn
课程内容
CONENTS
05、数组
06、函数
07、结构体
递推
函数
www..cn
二维数组
字符串
一维数组
递归
08、基础算法
数据排序
高精度算法
贪心算法
信息学竞赛，梦开始的地方
www..cn
学生可以参加的竞赛多，大大小小的竞赛令人眼花瞭乱，但大多都是没用的。只有数学、物理学、化学、信息学、生物学的全国奥林匹克分区联赛、全国奥林匹克竞赛是由国家教育部主办的。
一般来说，在奥赛中获奖的同学才能得到国家教育部的表彰，才能得到著名大学的青睐。 青少年信息学奥林匹克联赛省级赛区中获得全国一等奖或全国青少年信息学奥林匹克竞赛获得一、二、三等奖的初中生都有保送一级达标校的资格。
www..cn
走进信息学竞赛与c++
00
信息学竞赛
简介
信息学竞赛就是计算机竞赛，考的是学生用计算机高级语言，利用各种算法解决问题的能力。其中的联赛是由中国国家教育部、中国信息学奥林匹克竞赛委员会、中国科协、中国计算机协会联合主办，面向所有学生的，是普及性的。
它分初赛及复赛两个形式。初赛每年10月举行，形式为笔试，主要考计算机基础知识、数学知识、算法描述、程序阅读能力等。复赛在11月举行，形式为上机试，一般4个题目，只有在初赛中取得较好成绩的选手才能进入复赛。
www..cn
走进信息学竞赛与c++
00
信息学竞赛
简介
参与信息学竞赛的好处
参与信息学奥赛就是为了拿奖，为了保送上高中吗？
绝对不是的，学习的过程才是最重要的。接受这个培训的收获往往是终生受用的。
www..cn
走进信息学竞赛与c++
00
1、开发智力，提高思维。
　　
2、学到一门对日后发展有极大好处的基础本领。 　
　
3、培养沉稳坚韧的性格，严密谨慎的处世方式。 　
　
4、培养积极进取, 勇于拼博的精神。 　　
几个常见问题
的解答
www..cn
走进信息学竞赛与c++
00
1、参加奥赛跟学习有冲突吗？ 　　
2、需要很高的智商吗？
3、会很累很大压力吗？
强调
www..cn
走进信息学竞赛与c++
00
1、信息学是竞赛，不是社团。
2、参加信息学不是不完成其他科目作业的借口。
3、要求每个同学带一个笔记本，一个u盘。
第一个C++程序
01
编译工具：DEV-c++
打开界面：文件——新建——源代码（快捷键：ctrl+n）
编译运行：下图箭头处（快捷键：F11）
保存：文件——另存为cpp文件（快捷键：ctrl+s）
www..cn
第一个C++程序
01
www..cn
默写“第一个c++程序”代码，要求输出 “ Hello World! ”
简单程序设计 顺序结构实例
02
刚才的简单程序已体现出处理问题
的步骤的顺序关系，每条语句按自
上而下的顺序依次执行一次，这种
自上而下依次执行的程序称为顺序
结构程序。
例2-1 已知一位小朋友的电影票价是10元，
计算x位小朋友的总票价是多少？
www..cn
简单程序设计 赋值语句
02
在C++语言中，“=”作为赋值运算符，而不表示“等于”判断。
变量=表达式；
注意：
I. 变量=变量=…=表达式 是成立的
例如，“a=b=c=d=e=5 ;”，它实际上等价于：e=5 ; d=e ; c=d ; b=c ; a=b ;
II.如果赋值运算符两边的数据类型不同，系统将会自动进行类型转换，
即将赋值运算符右边的数据类型转换成左边的变量类型。
例2-2 输入两个正整数A和B，试交换A、B的值
（使A的值等于B，B的值等于A）。
www..cn
简单程序设计 运算符和表达式
02
1.算术运算符
用于各类数值运算。包括加(+)、减(-)、乘(*)、除(/)、
求余(或称模运算，%)、自增(++)、自减(--)共七种。
2.关系运算符
用于比较运算。包括大于(>)、小于(<)、等于(==)、大
于等于(>=)、小于等于(<=)和不等于(!=)六种。
3.逻辑运算符
用于逻辑运算。包括与(&&)、或(||)、非(!)三种。
例2-3 输入两个正整数a和b，
试求a与b之间的和、差、积、商以及余数（a在前）。
www..cn
mouth_age √
s2 √
m.k.jack ×
a<=9b ×
9y ×
简单程序设计 常量和变量
02
常量是指在程序中使用的一些具体的数、字符。在程序运行过程中，其值不能被更改。
常量的定义：const 符号常量=常量字串; 例如：const int PI=3;
变量代表了一个存储单元，其中的值是可以改变的，因此称为变量。
变量的定义：数据类型 变量名
注意：变量名只能由数字、字母及下划线（ _ )组成，且数字不能放在开头。
例2-4 下列变量名中，不符合命名规范的有哪些？
mouth_age
s2
m.k.jack
a<=9b
9y
√
√
×
×
×
www..cn
简单程序设计 标准数据类型
02
整型 [long] int -231～231-1 4(32位)
单精度实型 float -3.4E-38～3.4E+38 4(32位) 6～7位
双精度实型 double -1.7E+308～1.7E+308 8(64位) 15～16位
布尔变量 bool 真true或假false之一 1(8位)
字符变量 char 1(8位)
数据类型 定义标识符 数值范围 占字节数 有效位数
暂时要求掌握
C++语言提供了丰富的数据类型 , 现在介绍几种基本的数据类型：整型、实型、字符型。
它们都是系统定义的简单数据类型，称为标准数据类型。
www..cn
简单程序设计 标准数据类型
02
在C++语言中，整型类型标识符为 int 。根据整型变量的取值范围又可将整型变量定义为以下8种整型类型：
数据类型 定义标识符 占字节数 数值范围 数值范围
短整型 short [int] 2(16位) -32768～32767 -215～215-1
整型 [long] int 4(32位) -2147483648～2147483647 -231～231-1
长整型 long [int] 4(32位) -2147483648～2147483647 -231～231-1
超长整型 long long [int] 8(64位) -9223372036854775808～9223372036854775807 -263～263-1
无符号整型 unsigned [int] 2(16位) 0～65535 0～216-1
无符号短整型 unsigned short [int] 2(16位) 0～65535 0～216-1
无符号长整型 unsigned long [int] 4(32位) 0～4294967295 0～232-1
无符号超长整型 unsigned long long 8(64位) 0～18446744073709551615 0～264-1
www..cn
简单程序设计 数据输入输出
02
cin/cout流
cin>>a;
cout<格式化输入输出
scanf(“%d”,&a);
printf(“%d”,a);
例2-5 输出保留3位小数的浮点数
读入一个单精度浮点数，保留3位小数输出这个浮点数。
输入:
只有一行，一个单精度浮点数。
输出:
也只有一行，读入的单精度浮点数。
样例输入:
12.34521
样例输出:
12.345
www..cn
简单程序设计 练习
02
练习1 温度表达转化
利用公式C = 5*(F-32)/9(其中C表示摄氏温度，F表示华氏温度)进行计算转化,
输入华氏温度f，输出摄氏温度c，要求精确到小数点后5位。
输入:
输入一行，包含一个实数f，表示华氏温度。
（f >= -459.67）
输出:
输出一行，包含一个实数，表示对用的摄氏温度，
要求精确到小数点后5位。
样例输入:
41
样例输出:
5.00000
www..cn
简单程序设计 练习
02
练习2 输入一个三位数，要求把这个数的百位数与个位数对调，输出对调后的数。
样例输入:
234
样例输出:
432
www..cn
简单程序设计 练习
02
练习3 等差数列末项计算
给出一个等差数列的前两项a1，a2，求第n项是多少。
输入:
输入仅一行，包括 a1, a2 ,n (-100<=a1,a2<=100,0<=n<=1000)。
输出:
一个整数，即n的值。
样例输入:
1 4 100
样例输出:
298
www..cn
选择结构 概述
03
程序由若干条语句组成，各语句按照顺序一条一条地执行，这种顺序结构是简洁的。
但在现实世界中，在解决问题的过程中，不可避免地遇到需要进行选择、或需要循
环工作的情况。这时，程序执行的顺序需要发生变化，而非从前向后逐一执行。
因此，程序中除了顺序结构以外，通常还有选择结构、循环结构以及转移机制。
C++提供三种选择结构，即if选择结构、if-else选择结构和switch选择结构。
www..cn
选择结构 if语句
03
if语句格式：
if (条件表达式)
语句1；
条件表达式
语句1
false
true
例3-1 读入一个整数a，如果a为偶数在屏幕上输出yes 。
www..cn
选择结构 if-else语句
03
if-else语句格式：
if (条件表达式)
语句1；
else
语句2；
例3-2 输入温度t的值，判断是否适合晨练。
(25<=t<=30，则适合晨练yes，否则不适合no)
条件表达式
语句块2
flase
true
语句块1
www..cn
选择结构 switch语句
03
语句格式：
switch（表达式）
{
case 常量表达式1：
语句序列1；
break;
case 常量表达式2：
语句序列2；
break;
……
case 常量表达式n：
语句序列n；
break;
default:
语句序列n+1；
}
在使用switch语句时，还应注意以下几点：
1.case语句后的各常量表达式的值不能相同，否则会出现错误码。
2.每个case或default后，可以包含多条语句，不需要使用“{”和“}”括起来。
3.各case和default子句的先后顺序可以变动，这不会影响程序执行结果。
4. default子句可以省略，default后面的语句末尾可以不必写break。
程序设计风格提示：写switch语句时，switch（表达式）单独一行，
各case分支和default分支要缩进两格并对齐，分支处理语句要相对再缩
进两格，以体现不同层次的结构。
应用条件语句可以很方便地使程序实现分支，但是出现分支比较多的时候，虽然可以用嵌套的if语句来
解决，但是程序结构会显得复杂，其至凌乱。为方便实现多情况选择，C++提供了一种switch开关语句。
例3-3 根据从键盘上输入的表示星期几的数字，对应输出它的英文名称。
www..cn
选择结构 练习
03
练习4 晶晶赴约会
晶晶的朋友贝贝约晶晶下周一起去看展览，但晶晶每周的1、3、5有课必须上课，
请帮晶晶判断她能否接受贝贝的邀请，如果能输出YES；如果不能则输出NO。注意YES和NO都是大写字母！
输入:
输入有一行，贝贝邀请晶晶去看展览的日期，用数字1到7表示从星期一到星期日。
输出:
输出有一行，如果晶晶可以接受贝贝的邀请，输出YES，否则，输出NO。注意YES和NO都是大写字母！
样例输入:
2
样例输出:
YES
www..cn
选择结构 练习
03
练习4 晶晶赴约会
晶晶的朋友贝贝约晶晶下周一起去看展览，但晶晶每周的1、3、5有课必须上课，
请帮晶晶判断她能否接受贝贝的邀请，如果能输出YES；如果不能则输出NO。注意YES和NO都是大写字母！
输入:
输入有一行，贝贝邀请晶晶去看展览的日期，用数字1到7表示从星期一到星期日。
输出:
输出有一行，如果晶晶可以接受贝贝的邀请，输出YES，否则，输出NO。注意YES和NO都是大写字母！
样例输入:
2
样例输出:
YES
www..cn
选择结构 练习
03
练习5 骑车与走路
在长郡校园里，没有自行车，上课办事会很不方便。但实际上。并非去办任何事情都是骑车快,
因为骑车总要找车、开锁、停车、锁车等,这要耽误一些时间。假设找到自行车，开锁并车上自
行车的时间为27秒；停车锁车的时间为23秒；步行每秒行走1.2米，骑车每秒行走3.0米。请判断走
不同的距离去办事,是骑车快还是走路快。
如果骑车快，输出一行"Bike"；如果走路快，
输出一行"Walk"；如果一样快，输出一行"All"。
输入:
输入一行，包含一个整数，
表示一次办事要行走的距离,单位为米。
输出:
输出一行,如果骑车快,输出一行"Bike";
如果走路快,输出一行"Walk";
如果一样快,输出一行"All"。
样例输入:
120
样例输出:
Bike
www..cn
选择结构 练习
03
练习6 最大数输出
输入三个整数，数与数之间以一个空格分开。 输出一个整数，即最大的整数。
输入:
输入为一行，包含三个整数（大小不同），数与数之间以一个空格分开。
输出:
输出一行，包含一个整数，即最大的整数。
样例输入:
10 20 56
样例输出:
56
www..cn
循环结构 概述
04
在解决问题的过程中，有时候我们需要将同一语句重复执行，这个时候我们可以用到循环结构。
C++提供三种选择结构，即for语句，while语句，do-while语句。
www..cn
循环结构 for语句
04
for语句格式：
for（控制变量初始化表达式；条件表达式；增量表达式）{
语句块（循环体）
}
例：将控制变量从1变到100，增量为1
for(int i=1;i<=100;i++)
例4-1 计算1+2+3+...+100的和。
www..cn
循环结构 while/do-while语句
04
while语句格式：
while（条件表达式）{
语句块（循环体）
}
例4-2 求1+2+3+...+n的和大于100时，n的最小值。
do-while语句格式：
do{
语句块（循环体）
}
while（条件表达式）
思考？
www..cn
循环结构 循环嵌套
04
例4-3 对于给定的自然数n(n<20)，在屏幕上输出仅由“*”构成的n行的直角三角形。
例如：当n=5时，输出：
*
**
***
****
*****
www..cn
循环结构 练习
04
练习7 求平均年龄
班上有学生若干名，给出每名学生的年龄（整数），求班上所有学生的平均年龄，保留到小数点后两位。
输入:
第一行有一个整数n（1<= n <= 100），表示学生的人数。
其后n行每行有1个整数，表示每个学生的年龄，取值为15到25。
输出:
输出一行，该行包含一个浮点数，为要求的平均年龄，
保留到小数点后两位。
样例输入:
2 18 17
样例输出:
17.50　
www..cn
循环结构 练习
04
练习8 满足条件的数
将正整数m和n之间(包括m和n)能被17整除的数累加，其中0输入:
一行，包含两个整数m和n，其间，以一个空格间隔。
输出:
输出一行，包行一个整数，表示累加的结果。
样例输入:
50 85
样例输出:
204
www..cn
循环结构 练习
04
练习9 求100－999中的水仙花数。
若三位数ABC，ABC=A^3+B^3+C^3，则称ABC为水仙花数。
例如153，1^3+5^3+3^3=1+125+27=153，则153是水仙花数。
输入：
无
输出：
水仙花数，中间用空格隔开。
样例：
153　370　371　407
www..cn
数组
05
例5-1 输入50个学生的某门课程的成绩，打印出低于平均分的学生序号与成绩。
www..cn
如果，用简单变量a1，a2,…，a50存储这些数据，要用50个变量保存输入的数据，程序片断如下：
　　cin>>a1>>a2>>…>>a10;
　　…
　　cin>>a41>>a42>>…>>a50;
我们需要把一大批具有相同性质的数据组合成一个新类型的变量，可以用简单的
程序（比如循环50次）对这个新变量的各个分量进行相同的处理，每个分量仍然
保留单个变量的所有性质（在上面的例子中，各分量是整型变量或实型变量的性
质）。
数组 一维数组
05
www..cn
一维数组的定义
当数组中每个元素只带有一个下标时，我们称这样的数组为一维数组。
　　数组的定义格式如下：
　　　类型标识符 数组名[常量表达式]
　　说明：
　　①数组名的命名规则与变量名的命名规则一致。
　　②常量表达式表示数组元素的个数。可以是常量和符号常量，但不能是变量。
　　例如：
　　int a[10]; //数组a定义是合法的
int b[n]; //数组b定义是非法的
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
数组 一维数组
05
www..cn
一维数组的初始化
可以在定义时完成：
　　　类型标识符 数组名[常量表达式]={值1，值2，…}
int a[5]={1,2,3,4,5} //写出全部
int a[5]={1,2,3} //写出部分
int a[5]={}; //初始化为0
例5-2 输入10个数,要求程序按输入时的逆序把这10个数打印出来。
一维数组的输入输出
一般用循环输入输出：
　　　for(int i=1;i<=n;i++)
cin>>a[i];
数组 一维数组
05
www..cn
例5-1 输入50个学生的某门课程的成绩，
打印出低于平均分的学生序号与成绩。
数组 一维数组
05
www..cn
例5-3 输入n个学生的某门课程的成绩，
打印出低于平均分的学生序号与成绩。
(n<=100)
数组 一维数组
05
www..cn
例5-4 陶陶摘苹果 【Noip2005普及组第1题】
陶陶家的院子里有一棵苹果树，每到秋天树上就会结出10个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有个30厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。
现在已知10个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。
输入:
包括两行数据。第一行包含10个100到200之间(包括100和200)的整
数(以厘米为单位)分别表示10个苹果到地面的高度，两个相邻的整
数之间用一个空格隔开。第二行只包括一个100到120之间(包含100
和120)的整数(以厘米为单位)，表示陶陶把手伸直的时候能够达到
的最大高度。
输出:
包括一行，这一行只包含一个整数，表示陶陶能够摘到的苹果的数目。
样例输入:
100 200 150 140 129 134 167 198 200 111
110
样例输出:
5
数组 二维数组
05
www..cn
二维数组的定义
数据类型 数组名[常量表达式1] [常量表达式2]；
int a[3][5];
二维数组的输入输出
for(int i=0;i<=2;i++){
for(int j=0;j<=4;j++){
cin>>a[i][j];
}
}
表示a是二维数组（相当于一个3*5的表格），
共有3*5=15个元素，它们是：
　　a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
　　a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
　　a[2][0] a[2][1] a[2][2] a[2][3] a[2][4]
二维数组的初始化
int a[3][5] = {{0,0,0,0,0},{1,1,1,1,1},{2,2,2,2,2}}
数组 二维数组
05
www..cn
例5-5 输入一个6*6的矩阵（方阵），把矩阵二条对角线上的元素值加上10，然后输出这个新矩阵。
数组 二维数组
05
www..cn
例5-6 矩阵交换行
给定一个5*5的矩阵(数学上，一个r×c的矩阵是一个由r行c列元素排
列成的矩形阵列)，将第n行和第m行交换，输出交换后的结果。
输入:
输入共6行，前5行为矩阵的每一行元素,元素与元素之间以一个
空格分开。
第6行包含两个整数m、n，以一个空格分开（1 <= m,n <= 5）。
输出:
输出交换之后的矩阵，矩阵的每一行元素占一行，元素之间以
一个空格分开。
样例输出:
3 0 8 2 4
5 6 7 8 3
9 3 0 5 3
7 2 1 4 6
1 2 2 1 2
样例输入:
1 2 2 1 2
5 6 7 8 3
9 3 0 5 3
7 2 1 4 6
3 0 8 2 4
1 5
数组 字符串
05
www..cn
　　
　　一、字符类型
　　字符类型为由一个字符组成的字符常量或字符变量。
　　字符常量定义:
　　　 const　字符常量=‘字符’
　　字符变量定义:
　　　　　 char 字符变量;
　　字符类型是一个有序类型, 字符的大小顺序按其ASCⅡ代码的大小而定。
数组 字符串
05
www..cn
二、字符数组
　　字符数组是指元素为字符的数组。字符数组是用来存放字符序列或字符串的。字符数组也有一维、二维和三维之分。
1、字符数组的定义格式
　　字符数组定义格式同于一般数组，所不同的是数组类型是字符型，第一个元素同样是从ch1[0]开始，而不是ch1[1]。具体格式如下：
　　 [存储类型] char 数组名[常量表达式1]…
　　例如：
char ch1[5]; //数组ch1是一个具有5个字符元素的一维字符数组
char ch2[3][5]; //数组ch2是一个具有15个字符元素的二维字符数组
2.字符数组的赋值
　　字符数组赋值类似于一维数组，赋值分为数组的初始化和数组元素的赋值。初始化的方式有用字符初始化和用字符串初始化两种，也有用初始值表进行初始化的。
　　(1).用字符初始化数组
　　例如：
char chr1[5]={‘a’,‘b’,‘c’,‘d’,‘e’};
　　初始值表中的每个数据项是一个字符，用字符给数组chr1的各个元素初始化。当初始值个数少于元素个数时，从首元素开始赋值，剩余元素默认为空字符。
　　字符数组中也可以存放若干个字符，也可以来存放字符串。两者的区别是字符串有一结束符(‘\0’)。反过来说，在一维字符数组中存放着带有结束符的若干个字符称为字符串。字符串是一维数组，但是一维字符数组不等于字符串。
　　例如：
char chr2[5]={‘a’,‘b’,‘c’,‘d’,‘\0’};
即在数组chr2中存放着一个字符串“abcd”。
数组 字符串
05
www..cn
(3).数组元素赋值
　　 字符数组的赋值是给该字符数组的各个元素赋一个字符值。
　　例如：
　　　char chr[3];
　　　chr[0]=‘a’; chr[1]=‘b’;chr[2]=‘c’;
(4).字符常量和字符串常量的区别
　　①两者的定界符不同，字符常量由单引号括起来，字符串常量由双引号括起来。
　　②字符常量只能是单个字符，字符串常量则可以是多个字符。
　　③可以把一个字符常量赋给一个字符变量，但不能把一个字符串常量赋给一个字符变量。
　　④字符常量占一个字节，而字符串常量占用字节数等于字符串的字节数加1。增加的一个字节中存放字符串结束标志‘\0’。例如：字符常量‘a’占一个字节，字符串常量“a”占二个字节。
数组 字符串
05
www..cn
三、字符串的输入与输出
　　字符串可以作为一维字符数组来处理，那么字符串的输入和输出也可以按照数组元素来处理。本节仅介绍将字符串作为一个整体进行输入和输出的语句。
　　1、输入
　　从键盘输入一个字符数组可以使用scanf语句或gets语句。
　　(1)scanf语句
　　 格式：scanf(“%s”,字符串名称);
　　说明：
　　①这里的字符串名称之前不加&这个取地址符。例如：scanf(“%s”,&s1)是错误的。
　　②系统会自动在输入的字符串常量后添加‘\0’标志，因此输入时，仅输入字符串的内容即可。
　　③输入多个字符串时，以空格分隔。
　　例如：scanf(“%s%s%s”,s1,s2,s3)；从键盘分别输入Let us go，则三个字符串分别获取了三个单词。反过来可以想到，如果仅有一个输入字符串名称的情况下，字符串变量仅获取空格前的内容。
　　例如：scanf(“%s”,s1)；从键盘分别输入Let us go，则仅有第一个单词被获取，即s1变量仅获取第一个单词Let。
(2)gets语句
　　 格式：gets(字符串名称)；
　　说明：
　　使用gets只能输入一个字符串。
　　例如：gets(s1,s2)；是错误的。
使用gets，是从光标开始的地方读到换行符也就是说读入的是一整行，而使用scanf是从光标开始的地方到空格，如果这一行没有空格，才读到行尾。
　　例如：scanf(“%s”,s1)；gets(s2)；
对于相同的输入Hello World!。
s1获取的结果仅仅是Hello，
s2获取的结果则是Hello World!
数组 字符串
05
www..cn
(2)gets语句
　　 格式：gets(字符串名称)；
　　说明：
　　使用gets只能输入一个字符串。
　　例如：gets(s1,s2)；是错误的。
使用gets，是从光标开始的地方读到换行符也就是说读入的是一整行，
而使用scanf是从光标开始的地方到空格，如果这一行没有空格，才读到行尾。
　　例如：scanf(“%s”,s1)；gets(s2)；
对于相同的输入Hello World!。
s1获取的结果仅仅是Hello，
s2获取的结果则是Hello World!
数组 字符串
05
www..cn
2、输出
　　向屏幕输出一个字符串可以使用printf语句或puts语句。
　　(1)printf语句
格式：printf(“%s”,字符串名称);
说明：
　　　①用%s格式输出时，printf的输出项只能是字符串(字符数组)名称，而不能是数组元素。例如：printf(“%s”,a[5]);是错误的。
　　　②输出字符串不包括字符串结束标志符‘\0’。
　　(2) puts语句
格式：puts(字符串名称);
说明：puts语句输出一个字符串和一个换行符。对于已经声明过的字符串a，printf(“%s\n”,a)和 puts(a)是等价的。
www..cn
例5-7 在应用计算机编辑文档的时候，我们经常遇到替换任务。如把文档中的“电脑”都替换成“计算机”。现在请你编程模拟一下这个操作。
输入两行内容，第1行是原文(长度不超过200个字符)，第2行包含以空格分隔的两个字符A和B，要求将原文中所有的字符A都替换成字符B，注意：区分大小写字母。
输入样例：
I love China. I love Beijing.
I U
输出样例：
U love China. U love Beijing.
数组 字符串
05
www..cn
例5-8 凯凯刚写了一篇美妙的作文，请问这篇作文的标题中有多少个字符？ 注意：标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字 符数时，空格和换行符不计算在内。
输入输出格式
输入格式：
输入文件只有一行，一个字符串 s。
输出格式：
输出文件只有一行，包含一个整数，即作文标题的字符数（不含空格和换行符）。
输入输出样例
输入样例
Ca 23
输出样例
4
注：2018年noip普及组第一题
数组 字符串
05
函数与递归 函数
06
www..cn
通常，在程序设计中，我们会发现一些程序段在程序的不同地方反复出现，此时可以将这些程序段作为相对独立的整体，用一个标识符给它起一个名字，凡是程序中出现该程序段的地方，只要简单地写上其标识符即可。这样的程序段，我们称之为子程序。
在一个程序中可以只有主程序而没有子程序(本章以前都是如此)，但不能没有主程序，也就是说不能单独执行子程序。
在此之前，我们曾经介绍并使用了C++提供的各种标准函数，
如abs(),sqrt()，swap()等等，这些系统提供的函数为我们编写程序提供了很大的方便。
函数与递归 函数
06
www..cn
例6-1 求：1!+2!+3!+……+n！
#include
using namespace std;
int main(){
int sum=0;
int n;
cin>>n;
for(int i=1;i<=n;i++){
int js=1;
for(int j=1;j<=i;j++){
js*=j;
}
sum+=js;
}
cout<return 0;
}
每次重复，单独拿出来
函数与递归 函数
06
www..cn
例6-1 求：1!+2!+3!+……+n！
int main(){
int sum=0;
int n;
cin>>n;
for(int i=1;i<=n;i++){
sum+=js;
}
cout<return 0;
}
#include
using namespace std;
现在的问题是：C++不提供js(x)这样
一个标准函数，这个程序是通不过的，
没关系，我们编写自己的函数。
int js(int n){
int k=1;
for(int i=1;i<=n;i++){
k*=i;
}
return k;
}
sum+=js(i);
函数与递归 函数
06
www..cn
1.函数的定义
　　1.函数定义的语法形式
数据类型 函数名（形式参数表）
{
函数体 //执行语句
}
int js(int n){
int k=1;
for(int i=1;i<=n;i++){
k*=i;
}
return k;
}
注：函数的数据类型是函数的返回值类型（若数据类型为 void ,则无返回值）
函数与递归 函数
06
www..cn
2.函数的声明和调用
#include
using namespace std;
int js(int); //函数的声明
int main()
{
int sum=0;
for (int i=1; i<=10; ++i)
sum+=js(i); //函数的调用
cout<<"sum="<return 0;
}
int js(int n) //定义的函数体
{
int s=1;
for (int i=1; i<=n; ++i)
s*=i;
return s; //函数的返回值
}
函数与递归 函数
06
www..cn
例6-2 用函数的方法，计算如图多边形的面积s，保留三位小数。
三角形a,b,c面积s求法：
p=(a+b+c)/2；
s=sqrt(p*(p-a)*(p-b)*(p-c));
输入样例：
1 1 1 1 1 1 1
输出样例：
1.299
函数与递归 函数
06
www..cn
例6-3 计算组合数C(m,n)的值(n<=m<=10)。
组合数C(m,n)可以理解为从m个数中任意取出n个数的所有情况数。求这个数值，有一个经典的计算方法：C(m,n)=m!/((m-n)!n!)。
输入两个数m,n。输出组合数C(m,n).
输入样例：
5 2
输出样例：
10
函数与递归 函数
06
www..cn
例6-4 定义一个函数check(n,d)，让它返回一个布尔值。
如果数字d在正整数n的某位中出现则送回true，否则送回false。
例如：check(325719,3)==true；check(77829,1)==false；
输入两个数n，d。输出true或者false。
输入样例：
325719 3
输出样例：
true
对所有数据，0<=n<=100,0<=d<=9.
函数与递归 递推
06
www..cn
递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。
这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。
　　递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。
#D
函数与递归 递推
06
www..cn
例6-5 现有斐波那契数列（Fibonacci），它的前若干项是1，1，2，3，5，8，13，21，34……求此数列第n项（3<=n<=100）。
#D
函数与递归 递推
06
www..cn
例6-6 楼梯有n个台阶，上楼可以一步上一阶，也可以一步上两阶。一共有多少种上楼的方法？
这是一道计数问题。在没有思路时，不妨试着找规律。
n=5时，一共有8种方法：
5=1+1+1+1+1
5=2+1+1+1
5=1+2+1+1
5=1+1+2+1
5=1+1+1+2
5=2+2+1
5=2+1+2
5=1+2+2
函数与递归 递归
06
www..cn
递归程序设计是C++语言程序设计中的一种重要的方法，它使许多复杂的问题变得简单，容易解决了。
递归特点是：函数或过程调用它自己本身。
其中直接调用自己称为直接递归；
而将A调用B，B以调用A的递归叫做间接递归。
函数与递归 递归
06
www..cn
例6-7 给定n（1<=n<=10000）,用递归的方法计算1+2+3...+n。
本题可以用递归方法求解，其原因在于它符合递归的三个条件：

(1)本题是累加问题：当前和=前一次和+当前项，而前一次和
的计算方法与其相同，只是数据不同s(n)=s(n-1)+n;
【递归公式】
(2)给定n,所以是有限次的递归调用；
【有限次数】
(3)结束条件是当n=1，则s=1。
【边界条件】
函数与递归 递归
06
www..cn
例6-8 输入n（n<=10000）个数，再输入 x ，用二分法判
断它是否在这n个数中，
如果存在则输出：“YES” 否则输出“NO”。
二分查找算法：
（1） 设有N个数，存放在A数组中，待查找数为X，用L指向数据的低端，用R指向数据的高端，MID指向中间：
（2） 若X=A[MID] 输出 “YES”；
（3）若X （4） 若X>A[MID]则到数据后半段查找：L不变，R=MID-1，计算新的MID值，并进行新的一段查找；
（5）若L>R都没有查找到，则输出“NO”。
函数与递归 递归
06
www..cn
例6-9 用递归算法求x^n 。
　
【分析】把X n 分解成：x^0 = 1 　 ( n =0 )
　　　 x^1 = x * x0 ( n =1 )
　　　 x^2 = x * x1 ( n >1 )
　　　 x^3 = x * x2 ( n >1 )
　　　 …… ( n >1 )
　　　因此将x^n 转化为：x*xn-1，，其中求xn-1 又用求xn 的方法进行求解。
①定义子程序x^n(int n)求X^n ;如果n>=1则递归调用x^n(n-1) 求x^n—1 ;
②当递归调用到达n=0时终止调用, 然后执行本“层”的后继语句;
③遇到子程序运行完，就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后继语句;
④继续执行步骤③，从调用中逐“层”返回，最后返回到主程序。
结构体
07
www..cn
　在实际问题中，一组数据往往具有不同的数据类型。例如，人口大普查时，我们需要记录每一
位公民的姓名，年龄，性别，住址，身份证号码。这些信息分别要用整型，字符型，字符串型来
记录。为了解决问题，C++语言给出了另一种构造数据类型——“结构体”，它在数据存储方面相当
于其他高级语言中的记录，但它有着面向对象的优势。
结构体
07
www..cn
结构体(struct)定义和操作
1.定义结构体及结构体变量
结构体变量的定义有两种形式：
(1)定义结构体类型的时候同时定义变量
struct 结构体类型名{ //其中struct是关键字
成员表; //可以有多个成员
成员函数; //可以有多个成员函数，也可以没有
}结构体变量表; //可以同时定义多个结构体变量，用“，”隔开
例如：
struct student{//定义类型名叫student的struct类型
string name;
int chinese,math;
int total;
} a[110]; //同时定义了a数组变量
(2)先定义结构体再定义结构体变量
struct 结构体类型名{
成员表;
成员函数;
};
结构体名 结构体变量表 //同样可以同时定义多个结构体变量
例如：
struct student{
string name;
int chinese,math;
int total;
};
student a[110];
在定义结构体变量时注意，结构体变量名和结构体名不能相同。在定义结构体时，系统对其不分配实际内存。只有定义结构体变量时，系统才为其分配内存。
结构体
07
www..cn
2.结构体变量的特点
（1）结构体变量可以整体操作，例如：
swap(a[j],a[j+1]);
（2）结构体变量的成员访问也很方便、清晰，例如：
cin>>a[i].name;
（3）结构体变量的初始化和数组的初始化类似，例如：
student op={"gaoxiang",89,90,179};
3.成员调用
结构体变量与各个成员之间引用的一般形式为：
结构体变量名.成员名
对于上面定义的结构体变量，我们可以这样操作：
cin>>a[i].name; //一般情况下不能写cin>>a[i];
a[i].total=a[i].chinese+a[i].math; //就像用整型变量一样
实际上结构体成员的操作与该成员类型所具有的操作是一致的。
成员运算符“.”在存取成员数值时使用，其优先级最高，并具有左结合性。在处理包含结构体的结构体时，可记作：
strua.strub.membb
这说明结构体变量strua有结构体成员strub；结构体变量strub有成员membb。
4.成员函数调用
结构体成员函数调用的一般形式为：
结构体变量名.成员函数
结构体成员函数默认将结构体变量作为引用参数。
结构体
07
www..cn
例7-1 输入N(0<=N<=100)个学生的姓名和语文、数学的得分，按总分从高到低输出，分数相同的按输入先后输出。
输入格式：
第1行，有一个整数N，N的范围是[1…100]；下面有N行，每行一个姓名，2个整数。姓名由不超过10个的小写字母组成，整数范围是[0…100]。
输出格式：
总分排序后的名单，共N行，每行格式：姓名 语文 数学 总分。
输入样例：
4
gaoxiang 78 96
wangxi 70 99
liujia 90 87
zhangjin 78 91
输出样例：
liujia 90 87 177
gaoxiang 78 96 174
wangxi 70 99 169
zhangjin 78 91 169
结构体
07
www..cn
例7-1 输入N(0<=N<=100)个学生的姓名和语文、数学的得分，按总分从高到低输出，分数相同的按输入先后输出。
结构体
07
www..cn
例7-2 离散化基础。以后要学习使用的离散化方法编程中，通常要知道每个数排序后的编号（rank值）。
输入格式：
第1行，一个整数N，范围在[1…10000]；第2行，有N个不相同的整数，每个数都是int范围的。
输出格式：
依次输出每个数的排名。
输入样例:
5
8 2 6 9 4
输出样例:
4 1 3 5 2
结构体
07
www..cn
例7-2 离散化基础。以后要学习使用的离散化方法编程中，通常要知道每个数排序后的编号（rank值）。
练习
05-07
www..cn
练习10 校门外的树
某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入:
第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
对于20%的数据，区域之间没有重合的部分；对于其它的数据，区域之间有重合的情况。
输出:
包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入: 样例输出:
500 3 298
150 300
100 200
470 471
练习
05-07
www..cn
练习10 校门外的树
练习
05-07
www..cn
练习11 把雌雄各一的一对新兔子放入养殖场中。
每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。
试问第n个月后养殖场中共有多少对兔子。
练习
05-07
www..cn
练习12 计数问题
试计算在区间 1 到 n 的所有整数中，数字 x(0 ≤ x ≤ 9)共出现了多少次？例如，在 1到 11中，即在 1,2,3,4,5,6,7,8,9,10,11 中，数字 1 出现了 4 次。
输入输出格式
输入格式：
2个整数n,x，之间用一个空格隔开。
输出格式：
1个整数，表示x出现的次数。
输入样例
11 1
输出样例
4
对于100%的数据，1≤ n ≤ 1,000,000 , 0 ≤ x ≤ 9。
练习
05-07
www..cn
练习12 计数问题
练习
05-07
www..cn
练习13 汉诺塔问题①
问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。
要求把a柱上n个圆盘按下述规则移到c柱上：
(1)一次只能移一个圆盘；
(2)圆盘只能在三个柱上存放；
(3)在移动过程中，不允许大盘压小盘。
问将这n个盘子从a柱移动到c柱上，
总计需要移动多少个盘次？
练习
05-07
www..cn
练习13 汉诺塔问题①
练习
05-07
www..cn
练习14 汉诺塔问题②
问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。
要求把a柱上n个圆盘按下述规则移到c柱上：
(1)一次只能移一个圆盘；
(2)圆盘只能在三个柱上存放；
(3)在移动过程中，不允许大盘压小盘。
现要求设计将A柱子上N个盘子搬移到C柱去的方法。
练习
05-07
www..cn
练习14 汉诺塔问题②
基础算法 高精度算法
08
www..cn
高精度计算
利用计算机进行数值计算，有时会遇到这样的问题：
有些计算要求精度高，希望计算的数的位数可达几十位甚至几百位，
虽然计算机的计算精度也算较高了，但因受到硬件的限制，往往达不
到实际问题所要求的精度。我们可以利用程序设计的方法去实现这样
的高精度计算。介绍常用的几种高精度计算的方法。
基础算法 高精度算法
08
www..cn
高精度计算中需要处理好以下几个问题：
(1)数据的接收方法和存贮方法
数据的接收和存贮：当输入的数很长时，可采用字符串方式输入，这样可输入数字很长的数，利用字符串函数和操作运算，将每一位数取出，存入数组中。
void init(int a[ ]) {
string s;
cin>>s;
a[0]=s.length();
for(i=1;i<=a[0];i++)
a[i]=s[a[0]-i]-'0';
}
另一种方法是直接用循环加数组方法输入数据。
基础算法 高精度算法
08
www..cn
例8-1 使用字符串输入数据，倒序输出。
基础算法 高精度算法
08
www..cn
高精度计算中需要处理好以下几个问题：
(2) 高精度数位数的确定
位数的确定：接收时往往是用字符串的，所以它的位数等于字符串的长度。
(3) 进位,借位处理
加法进位：c[i]=a[i]+b[i];
if (c[i]>=10) { c[i]%=10; ++c[i+1]; }　
减法借位：if (a[i]c[i]=a[i]-b[i];
　　
乘法进位：c[i+j-1]= a[i]*b[j] + x + c[i+j-1];
x = c[i+j-1]/10;
c[i+j-1] %= 10;
(4) 商和余数的求法
商和余数处理：视被除数和除数的位数情况进行处理.
基础算法 高精度算法
08
www..cn
例8-2-1 高精度加法。输入两个正整数，求它们的和。
8 5 6
+ 2 5 5
1 1 1 1
A3 A2 A1
+ B3 B2 B1
C4 C3 C2 C1
基础算法 高精度算法
08
www..cn
例8-2-2 高精度减法（第二个可能比第一个大）。
输入两个正整数，求它们的差。
基础算法 数据排序
08
www..cn
sort实现快速排序
sort（）函数是c++一种排序方法之一，学会了这种方法也打消了学习c++以来使用的冒泡排序和选择排序所带来的执行效率不高的问题！
因为它使用的排序方法是类似于快排的方法，时间复杂度为n*log2(n)，执行效率较高！
sort ( start , end , 排序方法 )
可不写，默认从小到大
基础算法 数据排序
08
www..cn
例8-3 输入n(n<=100)个数，将它们按照从小到大的顺序输出。
输入样例：
10
9 6 3 8 5 2 7 4 1 0
输出样例：
0 1 2 3 4 5 6 7 8 9
基础算法 数据排序
08
www..cn
例8-4 输入n(n<=100)个数，将它们按照从大到小的顺序输出。
输入样例：
10
9 6 3 8 5 2 7 4 1 0
输出样例：
9 8 7 6 5 4 3 2 1 0
基础算法 数据排序
08
www..cn
练习15 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，
他先用计算机生成了N个1到1000之间的随机整数(N≤100)，对于其中重复的数字，
只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后
再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完
成“去重”与“排序”的工作。
输入格式：
输入有两行，第1行为1个正整数，表示所生成的随机数的个数N
第2行有N个用空格隔开的正整数，为所产生的随机数。
输出格式：
输出也是两行，第1行为1个正整数M，表示不相同的随机数的个数。
第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
输入样例：
10
20 40 32 67 40 20 89 300 400 15
输出样例：
8
15 20 32 40 67 89 300 400
基础算法 数据排序
08
www..cn
练习15 明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，
他先用计算机生成了N个1到1000之间的随机整数(N≤100)，对于其中重复的数字，
只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后
再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式：
输入有两行，第1行为1个正整数，表示所生成的随机数的个数N
第2行有N个用空格隔开的正整数，为所产生的随机数。
输出格式：
输出也是两行，第1行为1个正整数M，表示不相同的随机数的个数。
第2行为M个用空格隔开的正整数，为从小到大排好序的不相同的随机数。
输入样例：
10
20 40 32 67 40 20 89 300 400 15
输出样例：
8
15 20 32 40 67 89 300 400
基础算法 贪心算法
08
www..cn
一、基本概念
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
基础算法 贪心算法
08
www..cn
例8-5 排队打水问题
有N个人排队到R个水龙头去打水，他们装满水桶的时间为T1，T2，…，Tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少？
输入样例：
4 2
2 6 4 5
输出样例：
23
基础算法 贪心算法
08
www..cn
例8-6 均分纸牌（NOIP2002）
有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的
倍数。可以在任一堆上取若干张纸牌，然后移动。
移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为
N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相
邻左边或右边的堆上。
现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。
例如 N=4，4 堆纸牌数分别为： ①　9　②　8　③　17　④　6
移动3次可达到目的：
从 ③ 取4张牌放到④（9 8 13 10）->从③取3张牌放到 ②（9 11 10 10）-> 从②取1张
牌放到①（10 10 10 10）。
【输入格式】
N（N 堆纸牌，1 <= N <= 100）
A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l<= Ai <=10000）
【输出格式】
所有堆均达到相等时的最少移动次数。
【样例输入】 【样例输出】
4 3
　 9 8 17 6
基础算法 贪心算法
08
www..cn
P1007 独木桥
谢谢大家
www..cn

展开更多......

收起↑