信息学奥赛课课通(C++)第5单元-电子课件.ppt

1、 高等教育出版社高等教育出版社 第第 5 单元单元 数组数组作者：林厚从作者：林厚从信息学奥赛课课通（信息学奥赛课课通（C+C+）高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 1 课课 一维数组的定义一维数组的定义学习目标学习目标1.理解数组的含义。理解数组的含义。2.学会一维数组的定义。学会一维数组的定义。3.掌握一维数组的元素引用和物理存储方式。掌握一维数组的元素引用和物理存储方式。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）数组数组数组就是一组相同类型的变量，它们往往都是为了表示数组就是一组相同类型的变量，它们往往都是为了表示同一批

2、对象的统一属性，如一个班级所有同学的身高、全球同一批对象的统一属性，如一个班级所有同学的身高、全球所有国家的人口数等。所有国家的人口数等。数组可以是一维的，也可以是二维或多维的。数组可以是一维的，也可以是二维或多维的。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1.一维数组的定义一维数组的定义定义一维数组的格式如下：定义一维数组的格式如下：类型标识符类型标识符 数组名数组名 常量表达式常量表达式;其中，类型标识符可以是任何基本数据类型，也可以是其中，类型标识符可以是任何基本数据类型，也可以是结构体等构造类型，相同类型的数组可以一起定义。数组结构体等构造类型，相同类型的

3、数组可以一起定义。数组名必须是合法的标识符。常量表达式的值即为数组元素的名必须是合法的标识符。常量表达式的值即为数组元素的个数。个数。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）2.一维数组的元素引用一维数组的元素引用数组定义好后，就可以引用（调用）其中的任意一个元数组定义好后，就可以引用（调用）其中的任意一个元素。引用格式为：素。引用格式为：数组名数组名 下标下标 如如：h5h5、hhi i*2+12+1等。其中，下标只能为整型常量或等。其中，下标只能为整型常量或整型表达式，值必须在数组定义的下标范围内，否则会出整型表达式，值必须在数组定义的下标范围内，否则会出现现

4、“下标越界错误下标越界错误”。需要注意的是，不能一次引用整个数组，只能逐个引用需要注意的是，不能一次引用整个数组，只能逐个引用数组的单个元素。数组的单个元素。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）3.一维数组的存储结构一维数组的存储结构数组在计算机内存单元中是连续存储的。程序一旦执行数组在计算机内存单元中是连续存储的。程序一旦执行到数组的定义语句，就会开辟出若干字节的内存单元。到数组的定义语句，就会开辟出若干字节的内存单元。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥

5、赛课课通（C+）第第 2 课课 一维数组的输入与输出一维数组的输入与输出学习目标学习目标1.熟练掌握一维数组的输入与输出操作。熟练掌握一维数组的输入与输出操作。2.学会应用一维数组解决一些实际问题。学会应用一维数组解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的输入与输出一维数组的输入与输出一维数组的输入、输出等操作，都是采用循环语句结合一维数组的输入、输出等操作，都是采用循环语句结合下标变化，逐个元素进行。下标变化，逐个元素进行。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）批量数据一次性输入到一维数组中批量数据一次性

6、输入到一维数组中（1）键盘逐个读入数组元素值；键盘逐个读入数组元素值；（2）给每个数组元素直接赋值；给每个数组元素直接赋值；高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）给数组给数组“整体整体”赋值赋值（1）memset 函数函数 memset 函数是给数组函数是给数组“按字节按字节”进行赋值，一般用在进行赋值，一般用在 char 型数组中，如果是型数组中，如果是 int 类型的数组，一般赋值为类型的数组，一般赋值为 0 和和-1。使用前需要包含头文件：。使用前需要包含头文件：#include。（2）fill 函数函数 fill 函数是给数组函数是给数组“按元素按元素”

7、进行赋值，可以是整个进行赋值，可以是整个数组，也可以是部分连续元素，可以赋任何值。使用前需数组，也可以是部分连续元素，可以赋任何值。使用前需要包含头文件：要包含头文件：#include。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、阅读并上机调试程序，体会、阅读并上机调试程序，体会 memset 和和 fill 函数的作用。函数的作用。/p5-2-1#include#includeusing namespace std;int main()int a10,b10,c10,d10,i;memset(a,0,sizeof(a);/将将a数组所有元素均赋值为数组所有元

8、素均赋值为0 for(i=0;i 9;i+)cout ai “;cout a9 endl;memset(b,1,sizeof(b);/将将 b 数组所有元素均赋值为数组所有元素均赋值为 /二进制数二进制数 20+28+216+224=16843009高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）for(i=0;i 9;i+)cout bi “;cout b9 endl;memset(c,0,5);/将将 c 数组前数组前 5 个字节都赋值为个字节都赋值为 0，所以只能确定，所以只能确定 c0 /等于等于0，其他元素值不确定，其他元素值不确定 for(i=0;i 9;i+

9、)cout ci “;cout c9 endl;fill(d,d+5,8);/将将 d 数组前数组前 5 个元素都赋值为个元素都赋值为 8，其他元素值不确定，其他元素值不确定 for(i=0;i 9;i+)cout di “;cout d9 endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、走楼、走楼梯梯【问题描述问题描述】一个楼梯有一个楼梯有 n 级，小苏同学从下往上走，一步可以跨一级，级，小苏同学从下往上走，一步可以跨一级，也可以跨两级。问：他走到第也可以跨两级。问：他走到第 n 级楼梯有多少种走法？级楼梯有多少种走法？【输入格式输入

10、格式】一行一个整数一行一个整数 n，02)级楼级楼梯有两种可能：一种是从第梯有两种可能：一种是从第 i-1级楼梯走过来；另一种是从第级楼梯走过来；另一种是从第 i-2 级楼梯走过来。级楼梯走过来。根据加法原理，根据加法原理，f(i)=f(i-1)+f(i-2)，边界条件为：，边界条件为：f(1)=1，f(2)=2。具体实现时，定义一维数组具体实现时，定义一维数组 f，用赋值语句从前往后对数组，用赋值语句从前往后对数组的每一个元素逐个赋值。本质上，的每一个元素逐个赋值。本质上，f(i)构成了斐波那契数列。构成了斐波那契数列。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/

11、p5-2-2#includeusing namespace std;int main()int n,i,f31;scanf(“%d”,&n);f1=1;f2=2;for(i=3;i=n;i+)fi=fi-1+fi-2;for(i=1;i n;i+)printf(“%d “,fi);printf(“%dn”,fn);return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、幸运数的划分、幸运数的划分【问题描述问题描述】判断一个正整数判断一个正整数 n 是否能被一个是否能被一个“幸运数幸运数”整除。幸运数是整除。幸运数是指一个只包含指一个只包含 4 或或 7

12、的正整数，如的正整数，如 7、47、477 等都是幸运等都是幸运数，数，17、42 则不是幸运数。则不是幸运数。【输入格式输入格式】一行一个正整数一行一个正整数 n，1n1000。【输出格式输出格式】一行一个字符串，如果能被幸运数整除输出一行一个字符串，如果能被幸运数整除输出“YES”；否则，；否则，输出输出“NO”。【输入样例输入样例】47【输出样例输出样例】YES高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-2-3#includeusing namespace std;int main()int n,lucky14=4,7,44,47,74,77,444,4

13、47,474,477,744,747,774,777;/在数组定义时给数组赋值在数组定义时给数组赋值 scanf(“%d”,&n);bool flag=false;for(int i=0;i 14;i+)if(n%luckyi=0)flag=true;if(flag)printf(“YESn”);else printf(“NOn”);return 0;【问题分析问题分析】分析发现，分析发现，11000 范围内的幸运数只有范围内的幸运数只有 14 个。于是，将这个。于是，将这 14 个幸运个幸运数直接存储到一个数组数直接存储到一个数组 lucky 中，再穷举判断其中有没有一个数能整除中，再穷举判

14、断其中有没有一个数能整除 n。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、陶陶摘苹果陶陶摘苹果【问题描述问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 10 个苹果。苹果个苹果。苹果成熟的时候，陶陶就会跑去摘苹果。陶陶有一张成熟的时候，陶陶就会跑去摘苹果。陶陶有一张 30 厘米高的板凳，当她厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知现在已知 10 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的个苹果到地面的高度，

15、以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。苹果就会掉下来。【输入格式输入格式】第一行包含第一行包含 10 个个 100200 之间（包括之间（包括 100 和和 200）的整数（以厘米为单）的整数（以厘米为单位）分别表示位）分别表示 10 个苹果到地面的高度，两个整数之间用一个空格隔开。个苹果到地面的高度，两个整数之间用一个空格隔开。第二行只包括一个第二行只包括一个 100120 之间（包含之间（包含 100 和和 120）的整数（以厘米为）的整数（以厘米为单位

16、），表示陶陶把手伸直的时候能够达到的最大高度。单位），表示陶陶把手伸直的时候能够达到的最大高度。【输出格式输出格式】一行一个整数，表示陶陶能够摘到的苹果的数目。一行一个整数，表示陶陶能够摘到的苹果的数目。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】100 200 150 140 129 134 167 198 200 111110【输出样例输出样例】5【问题分析问题分析】定义一个数组保存定义一个数组保存 10 个苹果到地面的高度，再根据陶陶踩在板凳上的个苹果到地面的高度，再根据陶陶踩在板凳上的高度来统计她能够摘到的苹果数目。高度来统计她能够摘到的苹

17、果数目。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-2-4#includeusing namespace std;int main()int apple11,i,h,ans=0;for(int i=1;i applei;cin h;for(i=1;i=applei)ans+;cout ans endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 3 课课 一维数组的插入删除一维数组的插入删除学习目标学习目标1.学会一维数组的元

18、素插入和删除操作。学会一维数组的元素插入和删除操作。2.应用一维数组的插入和删除操作解决一些实际问题。应用一维数组的插入和删除操作解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的插入一维数组的插入插入一个元素，需要先找到插入的位置插入一个元素，需要先找到插入的位置(假设下标为假设下标为 x)，将这个元素及其之后的所有元素依次往后移一位将这个元素及其之后的所有元素依次往后移一位(注意要从注意要从后往前进行操作后往前进行操作)，再将给定的元素插入，再将给定的元素插入(覆盖覆盖)到位置到位置 x，如，如图图 5.3-1 所示。所示。高等教育出版社高等

19、教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的删除一维数组的删除删除某一个元素，也需要先找到删除的位置删除某一个元素，也需要先找到删除的位置(假设下标为假设下标为 x)，将下标为，将下标为 x+1 及其之后的所有元素依次向前移一位，覆及其之后的所有元素依次向前移一位，覆盖原来位置上的元素，如图盖原来位置上的元素，如图 5.3-2 所示。所示。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、插队问题、插队问题【问题描述问题描述】有有 n 个人（每个人有一个唯一的编号，用个人（每个人有一个唯一的编号，用 1n 之间的整数表之间的整数表示）在一个水龙头前

20、排队准备接水，现在第示）在一个水龙头前排队准备接水，现在第 n 个人有特殊情个人有特殊情况，经过协商，大家允许他插队到第况，经过协商，大家允许他插队到第 x 个位置。输出第个位置。输出第 n 个个人插队后的排队情况。人插队后的排队情况。【输入格式输入格式】第一行第一行 1 个正整数个正整数 n，表示有，表示有 n 个人，个人，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示排在队个正整数，之间用一个空格隔开，表示排在队伍中的第伍中的第 1 第第 n 个人的编号。个人的编号。第三行包含第三行包含 1 个正整数个正整数 x，表示第，表示第 n 个人插队的位置，个人插队的位置

21、，1xn。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输出格式输出格式】一行包含一行包含 n 个正整数，之间用一个空格隔开，表示第个正整数，之间用一个空格隔开，表示第 n 个人个人插队后的排队情况。插队后的排队情况。【输入样例输入样例】77 2 3 4 5 6 13【输出样例输出样例】7 2 1 3 4 5 6【问题分析问题分析】n个人的排队情况可以用数组个人的排队情况可以用数组 q 表示，表示，qi表示排在第表示排在第 i 个个位置上的人。定义数组时多定义一个位置，然后重复执行：位置上的人。定义数组时多定义一个位置，然后重复执行：qi+1=qi，其中，其中，i 从

22、从 n x。最后再执行。最后再执行 qx=qn+1，输，输出出 q1 qn。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-3-1#includeusing namespace std;int main()int n,i,x,q102;scanf(“%d”,&n);for(i=1;i=x;i-)qi+1=qi;qx=qn+1;for(i=1;i n;i+)printf(“%d “,qi);printf(“%dn”,qn);return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、队伍调整、队伍调整【问题描述问题描述】有有 n

23、个人（每个人有一个唯一的编号，用个人（每个人有一个唯一的编号，用 1n 之间的整数表之间的整数表示）在一个水龙头前排队准备接水，现在第示）在一个水龙头前排队准备接水，现在第 x 个人有特殊情个人有特殊情况离开了队伍，求第况离开了队伍，求第 x 个人离开队伍后的排队情况。个人离开队伍后的排队情况。【输入格式输入格式】第一行第一行 1 个正整数个正整数 n，表示有，表示有 n 个人，个人，2n100。第二行包含第二行包含n个正整数，之间用一个空格隔开，表示排在队个正整数，之间用一个空格隔开，表示排在队伍中的第伍中的第1个到第个到第n个人的编号。个人的编号。第三行包含第三行包含 1 个正整数个正整数

24、 x，表示第，表示第 x 个人离开队伍，个人离开队伍，1xn。【输出格式输出格式】一行包含一行包含 n-1 个正整数，之间用一个空格隔开，表示第个正整数，之间用一个空格隔开，表示第 x 个个人离开队伍后的排队情况。人离开队伍后的排队情况。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】77 2 3 4 5 6 13【输出样例输出样例】7 2 4 5 6 1高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-3-2#includeusing namespace std;int main()int n,i,x,q102;scanf

25、(“%d”,&n);for(i=1;i=n;i+)scanf(“%d”,&qi);scanf(“%d”,&x);for(i=x;i n;i+)qi=qi+1;n-;for(i=1;i n;i+)printf(“%d “,qi);printf(“%dn”,qn);return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 4 课课 一维数组的查找统计一维数组的查找统计学习目标学习目标1.学会在一维数组中进行顺序查找和二分查找。学会在一维数组中进行顺序查找和二分查找。2.熟练应用

26、查找和统计操作解决一些实际问题。熟练应用查找和统计操作解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的查找统计一维数组的查找统计一维数组的查找操作，就是在一维数组中查找有没有一维数组的查找操作，就是在一维数组中查找有没有某个元素，它的值等于指定的值某个元素，它的值等于指定的值 x。查找操作的结果可能。查找操作的结果可能是一个没找到、找到一个或者找到很多个。常见的查找算是一个没找到、找到一个或者找到很多个。常见的查找算法有法有“顺序顺序”查找和查找和“二分二分”查找。查找。顺序查找就是按照从前往后的顺序，将数组中的元素顺序查找就是按照从前往后的顺

27、序，将数组中的元素依次与要查找的数依次与要查找的数 x 进行比较。进行比较。二分查找又称二分查找又称“折半折半”查找，其优点是比较次数少、查找，其优点是比较次数少、查找速度快。但是要求数据是递增或递减排序的。查找速度快。但是要求数据是递增或递减排序的。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）二分查找二分查找int left=0，right=n-1;int find=n;/find标记找到的位置，初始化为标记找到的位置，初始化为n，表示没找到，表示没找到while(left=right)int mid=(left+right)/2;if(amid=x)/找到了，就标

28、记位置，并退出循环找到了，就标记位置，并退出循环find=mid;break;if(x amid)right=mid-1;/x只能在左半部分只能在左半部分if(amid x)left=mid+1;/x只能在右半部分只能在右半部分if(find!=n)printf(%dn,find);else printf(not findn);高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、抽奖、抽奖1【问题描述问题描述】公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人依次的每

29、位员工都有一张带有号码的抽奖券。现在，主持人依次公布公布 n 个不同的获奖号码，小谢看着自己抽奖券上的号码个不同的获奖号码，小谢看着自己抽奖券上的号码 num，无比紧张。请编写一个程序，如果小谢获奖了，请输，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中的是第几个号码；如果没有中奖，请输出出他中的是第几个号码；如果没有中奖，请输出 0。【输入格式输入格式】第一行一个正整数第一行一个正整数 n，表示有，表示有 n 个获奖号码，个获奖号码，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示依次公个正整数，之间用一个空格隔开，表示依次公布的布的 n 个获奖号码。个获奖号码

30、。第三行一个正整数第三行一个正整数 num，表示小谢抽奖券上的号码。，表示小谢抽奖券上的号码。1获奖号码，获奖号码，num10000。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输出格式输出格式】一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为如果没有中奖，则为 0。【输入样例输入样例】717 2 3 4 9555 6 13【输出样例输出样例】3高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-4-1#includeusing namespace std;int

31、 main()int n,i,num,f,g101;scanf(“%d”,&n);for(i=1;i=n;i+)scanf(“%d”,&gi);scanf(“%d”,&num);f=0;for(i=1;i=n;i+)if(gi=num)f=i;break;printf(“%dn”,f);return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、抽奖、抽奖2【问题描述问题描述】公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人从小的每位员工都有一张带有号码的

32、抽奖券。现在，主持人从小到大依次公布到大依次公布 n 个不同的获奖号码，小谢看着自己抽奖券上个不同的获奖号码，小谢看着自己抽奖券上的号码的号码 win，无比紧张。请编写一个程序，如果小谢获奖了，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中奖的是第几个号码；如果没有中奖，请输出请输出他中奖的是第几个号码；如果没有中奖，请输出 0。【输入格式输入格式】第一行一个正整数第一行一个正整数 n，表示有，表示有 n 个获奖号码，个获奖号码，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示依次公个正整数，之间用一个空格隔开，表示依次公布的布的 n 个获奖号码。个获奖号码。第三

33、行一个正整数第三行一个正整数 win，表示小谢抽奖券上的号码。，表示小谢抽奖券上的号码。1获奖号码，获奖号码，win10000。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输出格式输出格式】一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为如果没有中奖，则为 0。【输入样例输入样例】71 2 3 4 6 17 95553【输出样例输出样例】3高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-4-2#includeusing namespace std;int ma

34、in()int n,i,win,f,left,right,mid,g101;scanf(“%d”,&n);for(i=1;i=n;i+)scanf(“%d”,&gi);scanf(“%d”,&win);f=0;left=1;right=n;while(left=right)mid=(left+right)/2;if(gmid=win)f=mid;break;if(win gmid)right=mid-1;if(gmid win)left=mid+1;printf(“%dn”,f);return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、比身、比身高高【问

35、题描述问题描述】有有 N 个人排成一排，假设他们的身高均为正整数，请找出其个人排成一排，假设他们的身高均为正整数，请找出其中符合以下条件的人：排在他前面且比他高的人数与排在他中符合以下条件的人：排在他前面且比他高的人数与排在他后面且比他高的人数相等。后面且比他高的人数相等。【输入格式输入格式】第一行为一个正整数第一行为一个正整数 N，1N1000，表示有多少个人。，表示有多少个人。下面下面 N 行，每行一个正整数，表示从前往后每个人的身高，行，每行一个正整数，表示从前往后每个人的身高，假设每个人的身高假设每个人的身高10000。【输出格式输出格式】一行一个整数，表示满足这个条件的人数。一行一个

36、整数，表示满足这个条件的人数。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】41213【输出样例输出样例】2【样例说明样例说明】第第 3、第、第 4 个人满足条件。个人满足条件。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-4-3#includeusing namespace std;int h1001,n,i,j,ans,t1,t2;int main()scanf(“%d”,&n);for(i=1;i=n;i+)scanf(“%d”,&hi);for(i=1;i=n;i+)t1=t2=0;for(j=1;j hi)t

37、1+;/排在他前面且比他高的人数排在他前面且比他高的人数 for(j=i+1;j hi)t2+;/排在他后面且比他高的人数排在他后面且比他高的人数 if(t1=t2)ans+;printf(“%dn”,ans);return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 5 课课 一维数组的元素排序一维数组的元素排序学习目标学习目标1.掌握选择排序、冒泡排序和插入排序。掌握选择排序、冒泡排序和插入排序。2.应用排序算法解决一些实际问题。应用排序算法解决一些实际问题。高等教育出

38、版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的元素排序一维数组的元素排序“排序排序”就是按照某个关键字的大小，将若干对象从小就是按照某个关键字的大小，将若干对象从小到大或者从大到小进行重新排列。关键字是对象的某一个到大或者从大到小进行重新排列。关键字是对象的某一个属性，它可以是任何基本数据类型，甚至结构体等。属性，它可以是任何基本数据类型，甚至结构体等。例如，体育课上我们会按照身高从矮到高站队，这就是例如，体育课上我们会按照身高从矮到高站队，这就是“升序升序”排序，身高是我们每个人的一个属性，也就是排排序，身高是我们每个人的一个属性，也就是排序的关键字。再如，将所有单词

39、按照序的关键字。再如，将所有单词按照“字典序字典序”倒过来排倒过来排序，如序，如zoo,yes,most,key,computer,book,bad,apple等，就是等，就是“降序降序”排序，关键字的类型就是字符串。排序，关键字的类型就是字符串。排序算法非常多，其中最基本的有选择排序、冒泡排序排序算法非常多，其中最基本的有选择排序、冒泡排序和插入排序三种。其本质上都是通过数组中的元素比较和和插入排序三种。其本质上都是通过数组中的元素比较和交换来实现的，关键是数组下标的分析。交换来实现的，关键是数组下标的分析。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、站队、

40、站队【问题描述问题描述】给出给出 n 个同学的身高，请根据他们的身高升序排列并输出排个同学的身高，请根据他们的身高升序排列并输出排序结果。序结果。【输入格式输入格式】第一行第一行 1 个正整数个正整数 n，表示有，表示有 n 个同学的身高，个同学的身高，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示个正整数，之间用一个空格隔开，表示 n 个同个同学的身高。每个同学的身高都在学的身高。每个同学的身高都在 150200 厘米之间。厘米之间。【输出格式输出格式】一行一行 n 个正整数，之间用一个空格隔开，表示个正整数，之间用一个空格隔开，表示 n 个同学根据个同学根据身高升

41、序排列的结果。身高升序排列的结果。【输入样例输入样例】7180 170 176 160 155 150 160【输出样例输出样例】150 155 160 160 170 176 180高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】算法算法1、选择排序、选择排序选择排序的基本思想是：每一趟从待排序的数据中，通过选择排序的基本思想是：每一趟从待排序的数据中，通过“打擂台打擂台”比较选出最小元素，放在这些数据的最前面。这比较选出最小元素，放在这些数据的最前面。这样，第一趟把样，第一趟把 n 个数中（第个数中（第 1 个到第个到第 n 个）最小的放在第一个）

42、最小的放在第一个位置，第二趟把剩余的个位置，第二趟把剩余的 n-1 个数中（第个数中（第 2 个到第个到第 n 个）最个）最小的放在第二个位置，第三趟把剩余的小的放在第二个位置，第三趟把剩余的 n-2 个数中（第个数中（第 3 个个到第到第 n 个）最小的放在第三个位，个）最小的放在第三个位，第第 n-1 趟把剩下的趟把剩下的 2 个数中（第个数中（第 n-1 个到第个到第 n 个）最小的放在第个）最小的放在第 n-1 个位置，剩个位置，剩下的最后一个数（第下的最后一个数（第 n 个）一定最大，自然落在了第个）一定最大，自然落在了第 n个位个位置。置。高等教育出版社高等教育出版社信息学奥赛课课

43、通（信息学奥赛课课通（C+）高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-5-1a，选择排序，选择排序#includeusing namespace std;int main()int n,i,j,k,temp,h101;cin n;for(i=1;i hi;for(i=1;i=n;i+)k=i;for(j=i+1;j=n;j+)if(hj hk)k=j;/在在 in 之间的最小元素之间的最小元素 temp=hi;hi=hk;hk=temp;/将将 in 之间的最小元素放到第之间的最小元素放到第 i 个位置个位置 for(i=1;i n;i+)cout hi “

44、;cout hn endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）算法算法2、冒泡排序、冒泡排序冒泡排序的基本思想是：从第一个数开始，依次不断比冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果较相邻的两个元素，如果“逆序逆序”就交换。这样，一趟排序就交换。这样，一趟排序结束后，最大的元素就放在了第结束后，最大的元素就放在了第 n 个位置了。对于样例数据，个位置了。对于样例数据，第一趟冒泡排序的过程如下：第一趟冒泡排序的过程如下：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）用同样的方法，第二趟把剩余

45、的前用同样的方法，第二趟把剩余的前 n-1 个数中最大的交换个数中最大的交换到第到第 n-1 个位置，第三趟把剩余的前个位置，第三趟把剩余的前 n-2 个数中最大的交换到个数中最大的交换到第第 n-2 个位置，个位置，经过经过 n-1 趟，排序结束。趟，排序结束。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-5-1b，冒泡排序，冒泡排序#includeusing namespace std;int main()int n,i,j,temp,h101;cin n;for(i=1;i hi;for(i=1;i n;i+)for(j=1;j hj+1)temp=hj;

46、hj=hj+1;hj+1=temp;for(i=1;i n;i+)cout hi “;cout hn endl;return 0;对于冒泡排序，我对于冒泡排序，我们还可以做些算法们还可以做些算法“优优化化”。如果一趟排序下。如果一趟排序下来，都没有任何来，都没有任何“逆序逆序”数对，即没有发生数对，即没有发生“交换交换”操作，则说明已操作，则说明已经排好序了。此时，就经排好序了。此时，就可以立刻退出循环。可以立刻退出循环。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-5-1c，优化后的冒泡排序，优化后的冒泡排序#includeusing namespace st

47、d;int main()int n,i,j,temp,h101;cin n;for(i=1;i hi;for(i=1;i n;i+)bool flag=true;for(j=1;j hj+1)temp=hj;hj=hj+1;hj+1=temp;flag=false;if(flag)break;for(i=1;i n;i+)cout hi “;cout hn endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）算法算法3、插入排序、插入排序插入排序的基本思想是：把所有待排序元素分成前后两段，插入排序的基本思想是：把所有待排序元素分成前后两段，前一段是

48、已经排好序的，后一段是待排序的。每一趟都是把后前一段是已经排好序的，后一段是待排序的。每一趟都是把后一段的第一个数一段的第一个数“插入插入”到前一段的某一个位置，保证前一段到前一段的某一个位置，保证前一段仍然是有序的。开始时，第仍然是有序的。开始时，第 1 个数作为前一段肯定是有序的；个数作为前一段肯定是有序的；第一趟，把第第一趟，把第 2 个数插入进去，保证前个数插入进去，保证前 2个数有序；第二趟，个数有序；第二趟，把第把第 3 个数插入进去，保证前个数插入进去，保证前 3 个数有；个数有；第第 n-1 趟，把第趟，把第 n 个数插入进去，保证个数插入进去，保证 n 个数都有序。个数都有序

49、。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-5-1d，插入排序，插入排序#includeusing namespace std;int main()int n,i,j,k,temp,h101;cin n;for(i=1;i hi;for(i=2;i=n;i+)temp=hi;k=1;while(hk=temp&k=k;j-)hj+1=hj;hk=temp;for(i=1;i n;i+)cout hi “;cout hn endl;return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版

50、社信息学奥赛课课通（信息学奥赛课课通（C+）第第 6 课课 一维数组的应用举例一维数组的应用举例学习目标学习目标1.学会跟踪数组元素调试程序。学会跟踪数组元素调试程序。2.综合应用一维数组的基本操作解决一些实际问题。综合应用一维数组的基本操作解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、学习对象、学习对象【问题描述问题描述】n 个信息学选手站在一排，每个选手的位置依次用个信息学选手站在一排，每个选手的位置依次用 1n 表示，表示，第第 i 个信息学选手的编程能力用一个整数个信息学选手的编程能力用一个整数 H i 表示。每个信表示。每个信息学选手