《信息学奥赛课课通C第5单元电子课件》由会员分享，可在线阅读，更多相关《信息学奥赛课课通C第5单元电子课件（119页珍藏版）》请在金锄头文库上搜索。
1、 高等教育出版社高等教育出版社 第第 5 单元单元 数组数组作者：林厚从作者：林厚从信息学奥赛课课通（信息学奥赛课课通（C+C+）高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 1 课课 一维数组的定义一维数组的定义学习目标学习目标1. 理解数组的含义。理解数组的含义。2. 学会一维数组的定义。学会一维数组的定义。3. 掌握一维数组的元素引用和物理存储方式。掌握一维数组的元素引用和物理存储方式。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）数组数组数组就是一组相同类型的变量，它们往往都是为了表示数组就是一组相同类型的变量，它们往往都是为了表示
2、同一批对象的统一属性，如一个班级所有同学的身高、全球同一批对象的统一属性，如一个班级所有同学的身高、全球所有国家的人口数等。所有国家的人口数等。数组可以是一维的，也可以是二维或多维的。数组可以是一维的，也可以是二维或多维的。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1. 一维数组的定义一维数组的定义定义一维数组的格式如下：定义一维数组的格式如下：类型标识符类型标识符 数组名数组名 常量表达式常量表达式 ;其中，类型标识符可以是任何基本数据类型，也可以是其中，类型标识符可以是任何基本数据类型，也可以是结构体等构造类型，相同类型的数组可以一起定义。数组名结构体等构造类型
3、，相同类型的数组可以一起定义。数组名必须是合法的标识符。常量表达式的值即为数组元素的个数。必须是合法的标识符。常量表达式的值即为数组元素的个数。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）2. 一维数组的元素引用一维数组的元素引用数组定义好后，就可以引用（调用）其中的任意一个元数组定义好后，就可以引用（调用）其中的任意一个元素。引用格式为：素。引用格式为：数组名数组名 下标下标 如如：h5h5、hhi i*2+1*2+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); /
8、 将将a数组所有元素均赋值为数组所有元素均赋值为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，所以只能确定，所以只能确定
9、c0 /等于等于0，其他元素值不确定，其他元素值不确定 for(i = 0; i 9; i+) 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 级，小苏同学从下往上走，一步可以跨一级，级，小苏同学从下往上走，一
10、步可以跨一级，也可以跨两级。问：他走到第也可以跨两级。问：他走到第 n 级楼梯有多少种走法？级楼梯有多少种走法？【输入格式输入格式】一行一个整数一行一个整数 n，02)级级楼梯有两种可能：一种是从第楼梯有两种可能：一种是从第 i-1级楼梯走过来；另一种是从级楼梯走过来；另一种是从第第 i-2 级楼梯走过来。级楼梯走过来。根据加法原理，根据加法原理，f (i) = f (i-1) + f (i-2)，边界条件为：，边界条件为：f (1) = 1，f (2) = 2。具体实现时，定义一维数组具体实现时，定义一维数组 f，用赋值语句从前往后对数，用赋值语句从前往后对数组的每一个元素逐个赋值。本质上，
11、组的每一个元素逐个赋值。本质上，f (i) 构成了斐波那契数构成了斐波那契数列。列。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/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;高等教育出版社高等教育出版社信息
12、学奥赛课课通（信息学奥赛课课通（C+）例例3、幸运数的划分、幸运数的划分【问题描述问题描述】判断一个正整数判断一个正整数 n 是否能被一个是否能被一个“幸运数幸运数”整除。幸运数是整除。幸运数是指一个只包含指一个只包含 4 或或 7 的正整数，如的正整数，如 7、47、477 等都是幸运数，等都是幸运数，17、42 则不是幸运数。则不是幸运数。【输入格式输入格式】一行一个正整数一行一个正整数 n，1n1000。【输出格式输出格式】一行一个字符串，如果能被幸运数整除输出一行一个字符串，如果能被幸运数整除输出“YES”；否则，；否则，输出输出“NO”。【输入样例输入样例】47【输出样例输出样例】Y
13、ES高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-2-3#includeusing namespace std;int main() int n,lucky14 = 4,7,44,47,74,77,444,447,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 ” ); e
14、lse printf( “ NOn ” ); return 0;【问题分析问题分析】分析发现，分析发现，11000 范围内的幸运数只有范围内的幸运数只有 14 个。于是，将这个。于是，将这 14 个个幸运数直接存储到一个数组幸运数直接存储到一个数组 lucky 中，再穷举判断其中有没有一个数能中，再穷举判断其中有没有一个数能整除整除 n。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、陶陶摘苹果、陶陶摘苹果【问题描述问题描述】陶陶家的院子里有一棵苹果树，每到秋天树上就会结出陶陶家的院子里有一棵苹果树，每到秋天树上就会结出 10 个苹果。苹果个苹果。苹果成熟的时候，
15、陶陶就会跑去摘苹果。陶陶有一张成熟的时候，陶陶就会跑去摘苹果。陶陶有一张 30 厘米高的板凳，当她厘米高的板凳，当她不能直接用手摘到苹果的时候，就会踩到板凳上再试试。不能直接用手摘到苹果的时候，就会踩到板凳上再试试。现在已知现在已知 10 个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的个苹果到地面的高度，以及陶陶把手伸直的时候能够达到的最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，最大高度，请帮陶陶算一下她能够摘到的苹果的数目。假设她碰到苹果，苹果就会掉下来。苹果就会掉下来。【输入格式输入格式】第一行包含第一行包含 10 个个 100200 之间（包括之间（包括 100
16、 和和 200）的整数（以厘米为单）的整数（以厘米为单位）分别表示位）分别表示 10 个苹果到地面的高度，两个整数之间用一个空格隔开。个苹果到地面的高度，两个整数之间用一个空格隔开。第二行只包括一个第二行只包括一个 100120 之间（包含之间（包含 100 和和 120）的整数（以厘米为单）的整数（以厘米为单位），表示陶陶把手伸直的时候能够达到的最大高度。位），表示陶陶把手伸直的时候能够达到的最大高度。【输出格式输出格式】一行一个整数，表示陶陶能够摘到的苹果的数目。一行一个整数，表示陶陶能够摘到的苹果的数目。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入
17、样例】100 200 150 140 129 134 167 198 200 111110【输出样例输出样例】5【问题分析问题分析】定义一个数组保存定义一个数组保存 10 个苹果到地面的高度，再根据陶陶踩在板凳上的个苹果到地面的高度，再根据陶陶踩在板凳上的高度来统计她能够摘到的苹果数目。高度来统计她能够摘到的苹果数目。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-2-4#includeusing namespace std;int main() int apple11,i,h,ans = 0; for(int i = 1; i applei; cin h; fo
18、r(i = 1; i = applei) ans+; cout ans endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 3 课课 一维数组的插入删除一维数组的插入删除学习目标学习目标1. 学会一维数组的元素插入和删除操作。学会一维数组的元素插入和删除操作。2. 应用一维数组的插入和删除操作解决一些实际问题。应用一维数组的插入和删除操作解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的插入一维数组的插入插入
19、一个元素，需要先找到插入的位置插入一个元素，需要先找到插入的位置(假设下标为假设下标为 x)，将这个元素及其之后的所有元素依次往后移一位将这个元素及其之后的所有元素依次往后移一位(注意要从后注意要从后往前进行操作往前进行操作)，再将给定的元素插入，再将给定的元素插入(覆盖覆盖)到位置到位置 x，如图，如图 5.3-1 所示。所示。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的删除一维数组的删除删除某一个元素，也需要先找到删除的位置删除某一个元素，也需要先找到删除的位置(假设下标为假设下标为 x)，将下标为，将下标为 x+1 及其之后的所有元素依次向前移一位，覆
20、及其之后的所有元素依次向前移一位，覆盖原来位置上的元素，如图盖原来位置上的元素，如图 5.3-2 所示。所示。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、插队问题、插队问题【问题描述问题描述】有有 n 个人（每个人有一个唯一的编号，用个人（每个人有一个唯一的编号，用 1n 之间的整数表之间的整数表示）在一个水龙头前排队准备接水，现在第示）在一个水龙头前排队准备接水，现在第 n 个人有特殊情个人有特殊情况，经过协商，大家允许他插队到第况，经过协商，大家允许他插队到第 x 个位置。输出第个位置。输出第 n 个个人插队后的排队情况。人插队后的排队情况。【输入格式输入
21、格式】第一行第一行 1 个正整数个正整数 n，表示有，表示有 n 个人，个人，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示排在队个正整数，之间用一个空格隔开，表示排在队伍中的第伍中的第 1 第第 n 个人的编号。个人的编号。第三行包含第三行包含 1 个正整数个正整数 x，表示第，表示第 n 个人插队的位置，个人插队的位置，1xn。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输出格式输出格式】一行包含一行包含 n 个正整数，之间用一个空格隔开，表示第个正整数，之间用一个空格隔开，表示第 n 个人个人插队后的排队情况。插队后的排队情况。【输入
22、样例输入样例】77 2 3 4 5 6 13【输出样例输出样例】7 2 1 3 4 5 6【问题分析问题分析】 n个人的排队情况可以用数组个人的排队情况可以用数组 q 表示，表示，qi表示排在第表示排在第 i 个个位置上的人。定义数组时多定义一个位置，然后重复执行：位置上的人。定义数组时多定义一个位置，然后重复执行：qi+1 = qi，其中，其中，i 从从 n x。最后再执行。最后再执行 qx = qn+1，输，输出出 q1 qn。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-3-1#includeusing namespace std;int main() i
23、nt 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 个人（每个人有一个唯一的编号，用个人（每个人有一个唯一的编号，用 1n 之间的整数表之间的整数表示）在一个水龙头前排队准备接水，现在第示）在一个水龙头前排队准备接水，现在第
24、 x 个人有特殊情个人有特殊情况离开了队伍，求第况离开了队伍，求第 x 个人离开队伍后的排队情况。个人离开队伍后的排队情况。【输入格式输入格式】第一行第一行 1 个正整数个正整数 n，表示有，表示有 n 个人，个人，2n100。第二行包含第二行包含n个正整数，之间用一个空格隔开，表示排在队伍个正整数，之间用一个空格隔开，表示排在队伍中的第中的第1个到第个到第n个人的编号。个人的编号。第三行包含第三行包含 1 个正整数个正整数 x，表示第，表示第 x 个人离开队伍，个人离开队伍，1xn。【输出格式输出格式】一行包含一行包含 n-1 个正整数，之间用一个空格隔开，表示第个正整数，之间用一个空格隔开
25、，表示第 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( “ %d ” ,&n); for(i = 1; i = n; i+) scanf( “ %d ” ,&qi); scanf( “ %d ” ,&x); for(i
26、= 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. 熟练应用查找和统计操作解决一些实际问题。熟练应用查找和统计操作解决一些实际问题。高
27、等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的查找统计一维数组的查找统计一维数组的查找操作，就是在一维数组中查找有没有一维数组的查找操作，就是在一维数组中查找有没有某个元素，它的值等于指定的值某个元素，它的值等于指定的值 x。查找操作的结果可能。查找操作的结果可能是一个没找到、找到一个或者找到很多个。常见的查找算是一个没找到、找到一个或者找到很多个。常见的查找算法有法有“顺序顺序”查找和查找和“二分二分”查找。查找。顺序查找就是按照从前往后的顺序，将数组中的元素顺序查找就是按照从前往后的顺序，将数组中的元素依次与要查找的数依次与要查找的数 x 进行比较。进行比较
28、。二分查找又称二分查找又称“折半折半”查找，其优点是比较次数少、查找，其优点是比较次数少、查找速度快。但是要求数据是递增或递减排序的。查找速度快。但是要求数据是递增或递减排序的。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）二分查找二分查找int left = 0，right = n - 1; int find = n;/find标记找到的位置，初始化为标记找到的位置，初始化为n，表示没找到，表示没找到while(left = right)int mid = (left + right) / 2;if(amid = x)/找到了，就标记位置，并退出循环找到了，就标记位置
29、，并退出循环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【问题描述问题描述】公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会的每位员工都有一张带有号码的抽奖券。现在，主持人依次的每位员工
30、都有一张带有号码的抽奖券。现在，主持人依次公布公布 n 个不同的获奖号码，小谢看着自己抽奖券上的号码个不同的获奖号码，小谢看着自己抽奖券上的号码 num，无比紧张。请编写一个程序，如果小谢获奖了，请输，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中的是第几个号码；如果没有中奖，请输出出他中的是第几个号码；如果没有中奖，请输出 0。【输入格式输入格式】第一行一个正整数第一行一个正整数 n，表示有，表示有 n 个获奖号码，个获奖号码，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示依次公个正整数，之间用一个空格隔开，表示依次公布的布的 n 个获奖号码。个获奖号码。第三
31、行一个正整数第三行一个正整数 num，表示小谢抽奖券上的号码。，表示小谢抽奖券上的号码。1获奖号码，获奖号码，num10000。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输出格式输出格式】一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为如果没有中奖，则为 0。【输入样例输入样例】717 2 3 4 9555 6 13【输出样例输出样例】3高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-4-1#includeusing namespace std;int ma
32、in() 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【问题描述问题描述】公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚会公司举办年会，为了活跃气氛，设置了摇奖环节。参加聚
33、会的每位员工都有一张带有号码的抽奖券。现在，主持人从小的每位员工都有一张带有号码的抽奖券。现在，主持人从小到大依次公布到大依次公布 n 个不同的获奖号码，小谢看着自己抽奖券上个不同的获奖号码，小谢看着自己抽奖券上的号码的号码 win，无比紧张。请编写一个程序，如果小谢获奖了，无比紧张。请编写一个程序，如果小谢获奖了，请输出他中奖的是第几个号码；如果没有中奖，请输出请输出他中奖的是第几个号码；如果没有中奖，请输出 0。【输入格式输入格式】第一行一个正整数第一行一个正整数 n，表示有，表示有 n 个获奖号码，个获奖号码，2n100。第二行包含第二行包含 n 个正整数，之间用一个空格隔开，表示依次公
34、个正整数，之间用一个空格隔开，表示依次公布的布的 n 个获奖号码。个获奖号码。第三行一个正整数第三行一个正整数 win，表示小谢抽奖券上的号码。，表示小谢抽奖券上的号码。1获奖号码，获奖号码，win10000。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输出格式输出格式】一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；一行一个整数，如果小谢中奖了，表示中奖的是第几个号码；如果没有中奖，则为如果没有中奖，则为 0。【输入样例输入样例】71 2 3 4 6 17 95553【输出样例输出样例】3高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）
35、/p5-4-2#includeusing namespace std;int main() 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;
36、if(gmid win) left = mid + 1; printf( “ %dn ” ,f); return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、比身高、比身高【问题描述问题描述】有有 N 个人排成一排，假设他们的身高均为正整数，请找出其个人排成一排，假设他们的身高均为正整数，请找出其中符合以下条件的人：排在他前面且比他高的人数与排在他中符合以下条件的人：排在他前面且比他高的人数与排在他后面且比他高的人数相等。后面且比他高的人数相等。【输入格式输入格式】第一行为一个正整数第一行为一个正整数 N，1N1000，表示有多少个人。，表示有多少个人。下
37、面下面 N 行，每行一个正整数，表示从前往后每个人的身高，行，每行一个正整数，表示从前往后每个人的身高，假设每个人的身高假设每个人的身高10000。【输出格式输出格式】一行一个整数，表示满足这个条件的人数。一行一个整数，表示满足这个条件的人数。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】41213【输出样例输出样例】2【样例说明样例说明】第第 3、第、第 4 个人满足条件。个人满足条件。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-4-3#includeusing namespace std;int h1001,n,
38、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) t1+;/ 排在他前面且比他高的人数排在他前面且比他高的人数 for(j = i + 1; j hi) t2+;/ 排在他后面且比他高的人数排在他后面且比他高的人数 if(t1 = t2) ans+; printf( “ %dn ” ,ans); return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥
39、赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 5 课课 一维数组的元素排序一维数组的元素排序学习目标学习目标1. 掌握选择排序、冒泡排序和插入排序。掌握选择排序、冒泡排序和插入排序。2. 应用排序算法解决一些实际问题。应用排序算法解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）一维数组的元素排序一维数组的元素排序“排序排序”就是按照某个关键字的大小，将若干对象从小就是按照某个关键字的大小，将若干对象从小到大或者从大到小进行重新排列。关键字是对象的某一个属到大或者从大到小进行重新排列。关键字是对
40、象的某一个属性，它可以是任何基本数据类型，甚至结构体等。性，它可以是任何基本数据类型，甚至结构体等。例如，体育课上我们会按照身高从矮到高站队，这就是例如，体育课上我们会按照身高从矮到高站队，这就是“升序升序”排序，身高是我们每个人的一个属性，也就是排序排序，身高是我们每个人的一个属性，也就是排序的关键字。再如，将所有单词按照的关键字。再如，将所有单词按照“字典序字典序”倒过来排序，倒过来排序，如如zoo,yes,most,key,computer,book,bad,apple等，就是等，就是“降降序序”排序，关键字的类型就是字符串。排序，关键字的类型就是字符串。 排序算法非常多，其中最基本的有
41、选择排序、冒泡排序排序算法非常多，其中最基本的有选择排序、冒泡排序和插入排序三种。其本质上都是通过数组中的元素比较和交和插入排序三种。其本质上都是通过数组中的元素比较和交换来实现的，关键是数组下标的分析。换来实现的，关键是数组下标的分析。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、站队、站队【问题描述问题描述】给出给出 n 个同学的身高，请根据他们的身高升序排列并输出排个同学的身高，请根据他们的身高升序排列并输出排序结果。序结果。【输入格式输入格式】第一行第一行 1 个正整数个正整数 n，表示有，表示有 n 个同学的身高，个同学的身高，2n100。第二行包含第
42、二行包含 n 个正整数，之间用一个空格隔开，表示个正整数，之间用一个空格隔开，表示 n 个同个同学的身高。每个同学的身高都在学的身高。每个同学的身高都在 150200 厘米之间。厘米之间。【输出格式输出格式】一行一行 n 个正整数，之间用一个空格隔开，表示个正整数，之间用一个空格隔开，表示 n 个同学根据个同学根据身高升序排列的结果。身高升序排列的结果。【输入样例输入样例】7180 170 176 160 155 150 160【输出样例输出样例】150 155 160 160 170 176 180高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】算法
43、算法1、选择排序、选择排序选择排序的基本思想是：每一趟从待排序的数据中，通选择排序的基本思想是：每一趟从待排序的数据中，通过过“打擂台打擂台”比较选出最小元素，放在这些数据的最前面。比较选出最小元素，放在这些数据的最前面。这样，第一趟把这样，第一趟把 n 个数中（第个数中（第 1 个到第个到第 n 个）最小的放在第个）最小的放在第一个位置，第二趟把剩余的一个位置，第二趟把剩余的 n-1 个数中（第个数中（第 2 个到第个到第 n 个）个）最小的放在第二个位置，第三趟把剩余的最小的放在第二个位置，第三趟把剩余的 n-2 个数中（第个数中（第 3 个到第个到第 n 个）最小的放在第三个位，个）最小
44、的放在第三个位，第第 n-1 趟把剩下的趟把剩下的 2 个数中（第个数中（第 n-1 个到第个到第 n 个）最小的放在第个）最小的放在第 n-1 个位置，剩个位置，剩下的最后一个数（第下的最后一个数（第 n 个）一定最大，自然落在了第个）一定最大，自然落在了第 n个位个位置。置。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-5-1a，选择排序，选择排序#includeusing namespace std;int main() int n,i,j,k,temp,h101; cin n; for
45、(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 “ “ ; cout hn endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）算法算法2、冒泡排序、冒泡排序冒泡排序的基本思想是：从第一个数开始，
46、依次不断比冒泡排序的基本思想是：从第一个数开始，依次不断比较相邻的两个元素，如果较相邻的两个元素，如果“逆序逆序”就交换。这样，一趟排序就交换。这样，一趟排序结束后，最大的元素就放在了第结束后，最大的元素就放在了第 n 个位置了。对于样例数据，个位置了。对于样例数据，第一趟冒泡排序的过程如下：第一趟冒泡排序的过程如下：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）用同样的方法，第二趟把剩余的前用同样的方法，第二趟把剩余的前 n-1 个数中最大的交换个数中最大的交换到第到第 n-1 个位置，第三趟把剩余的前个位置，第三趟把剩余的前 n-2 个数中最大的交换到个数中最大的交
47、换到第第 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; hj = hj+1; hj+1 = temp; for(i = 1; i n; i+) cout hi “ “ ; cout hn endl; r
48、eturn 0; 对于冒泡排序，我对于冒泡排序，我们还可以做些算法们还可以做些算法“优优化化”。如果一趟排序下。如果一趟排序下来，都没有任何来，都没有任何“逆序逆序”数对，即没有发生数对，即没有发生“交换交换”操作，则说明已操作，则说明已经排好序了。此时，就经排好序了。此时，就可以立刻退出循环。可以立刻退出循环。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-5-1c，优化后的冒泡排序，优化后的冒泡排序#includeusing namespace std;int main() int n,i,j,temp,h101; cin n; for(i = 1; i hi
49、; 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、插入排序、插入排序插入排序的基本思想是：把所有待排序元素分成前后两段，插入排序的基本思想是：把所有待排序元素分成前后两段，前一段是已经排好序的，后一段是待排
50、序的。每一趟都是把后前一段是已经排好序的，后一段是待排序的。每一趟都是把后一段的第一个数一段的第一个数“插入插入”到前一段的某一个位置，保证前一段到前一段的某一个位置，保证前一段仍然是有序的。开始时，第仍然是有序的。开始时，第 1 个数作为前一段肯定是有序的；个数作为前一段肯定是有序的；第一趟，把第第一趟，把第 2 个数插入进去，保证前个数插入进去，保证前 2个数有序；第二趟，个数有序；第二趟，把第把第 3 个数插入进去，保证前个数插入进去，保证前 3 个数有；个数有；第第 n-1 趟，把第趟，把第 n 个数插入进去，保证个数插入进去，保证 n 个数都有序。个数都有序。高等教育出版社高等教育出
51、版社信息学奥赛课课通（信息学奥赛课课通（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;高等教育出版社高等教育出版社信息学奥赛课课通（信息
52、学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 6 课课 一维数组的应用举例一维数组的应用举例学习目标学习目标1. 学会跟踪数组元素调试程序。学会跟踪数组元素调试程序。2. 综合应用一维数组的基本操作解决一些实际问题。综合应用一维数组的基本操作解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、学习对象、学习对象【问题描述问题描述】n 个信息学选手站在一排，每个选手的位置依次用个信息学选手站在一排，每个选手的位置依次用 1n 表示，第表示，第 i 个信息学选手的编程能力用一个整数个信息学
53、选手的编程能力用一个整数 H i 表示。表示。每个信息学选手都希望找一个编程能力比自己高但又与自己每个信息学选手都希望找一个编程能力比自己高但又与自己编程能力最接近的选手学习，如果有多个符合条件的选手则编程能力最接近的选手学习，如果有多个符合条件的选手则选择位置在最前面的选手学习。请编程输出每位选手学习对选择位置在最前面的选手学习。请编程输出每位选手学习对象的位置，如果没有学习对象，则输出象的位置，如果没有学习对象，则输出 0。【输入格式输入格式】第第 1 行一个正整数行一个正整数 n，1n1000；第第 2n+1 行共行共 n 个正整数，依次表示每位选手的编程能个正整数，依次表示每位选手的编
54、程能力，力，1H i 1000000。【输出格式输出格式】n 行，每行输出一个整数表示每个选手学习对象的位置。行，每行输出一个整数表示每个选手学习对象的位置。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】6326112【输出样例输出样例】310221高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】第第i个选手的学习对象就是从前往后查找一个选手个选手的学习对象就是从前往后查找一个选手j，要求，要求HiHj且且Hj要要尽可能小（打擂台），如果尽可能小（打擂台），如果j可以取多个值，则选取最小的值（保留前面）。可以
55、取多个值，则选取最小的值（保留前面）。/p5-6-1#includeusing namespace std;int n,i,j,ans,maxh,h1001;int main() cin n; for(i = 1; i hi; for(i = 1; i = n; i+) ans = 0; maxh = 1000001; for(j = 1; j hi & hj maxh) ans = j; maxh = hj; cout ans endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、商品排序、商品排序【问题描述问题描述】某商场的仓库中有某商
56、场的仓库中有 n 件商品，每件商品的价格在件商品，每件商品的价格在 01000 之间（价格为之间（价格为 0 的商品为赠品）。的商品为赠品）。现在商场经理要求将这现在商场经理要求将这 n 件商品按价格由低到高排序。件商品按价格由低到高排序。请编程输出请编程输出 n 件商品排序后的情况。件商品排序后的情况。【输入格式输入格式】第一行一个正整数第一行一个正整数 n，表示有，表示有 n 件商品，件商品，1n100000。接下来的接下来的 n 行，每行一个整数，表示第行，每行一个整数，表示第 i 件商品的价格。件商品的价格。【输出格式输出格式】n 行，每行输出一个整数。行，每行输出一个整数。高等教育出
57、版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】518122【输出样例输出样例】11228高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】本题可以选用学过的任意一种排序算法实现，但是测本题可以选用学过的任意一种排序算法实现，但是测试程序发现会试程序发现会“超时超时”，因为本题最多有，因为本题最多有 100000 件商品，件商品，三种排序都需要两层循环嵌套。三种排序都需要两层循环嵌套。其实，分析数据发现一个重要特征：数据虽然很多，其实，分析数据发现一个重要特征：数据虽然很多，但是数据范围比较小。这种情况下，可以使用另外一种
58、排但是数据范围比较小。这种情况下，可以使用另外一种排序算法序算法桶排序。定义一个桶排序。定义一个 int 型数组型数组 num1001，numx记录整数记录整数 x 出现的次数，初始化都为出现的次数，初始化都为 0，每读到一个，每读到一个数数 x，就执行，就执行 numx = numx+1。输出时，从。输出时，从 0 1000 穷穷举举 x，每个，每个 x 输出输出 numx次。次。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-6-2，桶排序，桶排序#includeusing namespace std;int n,i,j,number,num1001;int
59、main() cin n; for(i = 1; i number; numnumber+;/ 记录整数记录整数 number 出现的次数出现的次数 for(i = 0; i 1001; i+) for(j = 1; j = numi; j+) cout i endl;/ 输出输出 numi 次次 i return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、素数大酬宾、素数大酬宾【问题描述问题描述】某商场的仓库中有某商场的仓库中有 n 种商品，每件商品按种商品，每件商品按 1n 依次编依次编号。现在商场经理突发奇想，决定将编号为素数（质数）号。现在商场经
60、理突发奇想，决定将编号为素数（质数）的所有商品拿出来搞优惠酬宾活动。请编程帮助仓库管理的所有商品拿出来搞优惠酬宾活动。请编程帮助仓库管理员将编号为素数的商品选出来。员将编号为素数的商品选出来。【输入格式输入格式】一行一个正整数一行一个正整数 n，表示有，表示有 n 种商品，种商品，2n100000。【输出格式输出格式】一行若干个正整数，表示若干种商品编号且每个编号一行若干个正整数，表示若干种商品编号且每个编号均为素数，请从小到大输出，每两个数之间有一个空格。均为素数，请从小到大输出，每两个数之间有一个空格。【输入样例输入样例】20【输出样例输出样例】2 3 5 7 11 13 17 19高等教
61、育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】算法算法1、穷举法、穷举法穷举商品编号穷举商品编号 2n，判断每个编号是否为素数。这种方法效率不高，判断每个编号是否为素数。这种方法效率不高，一旦一旦 n 过大，程序就会超时。过大，程序就会超时。/p5-6-3a#include#includeusing namespace std;int main() int n,i,j; bool flag; cin n; cout 2; for(i = 3; i = n; i+) flag = true; for(j = 2; j = sqrt(i); j+) if(i
62、% j = 0)flag = false;break; if(flag) cout “ “ i; cout endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）算法算法2、筛选法、筛选法筛选法又称为筛法，是由希腊著名数学家埃拉托色尼筛选法又称为筛法，是由希腊著名数学家埃拉托色尼 （Eratosthenes） 提出的。相比穷举法，筛选法的效率更高。以求提出的。相比穷举法，筛选法的效率更高。以求 120 之内素数为例，具体步骤如下：之内素数为例，具体步骤如下：（1） 将所有数（将所有数（2n）放入）放入“筛子筛子”中，把中，把 1 删除；删除；（2）
63、 2 在筛中，将在筛中，将 2 的倍数的倍数 2，4，20 删除（筛去）；删除（筛去）；（3） 3 在筛中，将在筛中，将 3 的倍数的倍数 6，9，18 删除（筛去）；删除（筛去）；（4） 4 不在筛中，不执行删除（筛去）操作；不在筛中，不执行删除（筛去）操作； （10） 10 不在筛中，不执行删除（筛去）操作。不在筛中，不执行删除（筛去）操作。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）输出输出 20 以内的素数，筛子中的元素变化情况如下：以内的素数，筛子中的元素变化情况如下：高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-6-3b#i
64、nclude#includeusing namespace std;int main() int n,i,j; bool p100001; for(i = 0; i n; cout 2; for(i = 2; i = sqrt(n); i+) if(pi) for(j = 2; i*j = n; j+) pi*j = false; for(i = 3; i = n; i+) if(pi) cout “ “ i; cout endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、约瑟夫问题、约瑟夫问题【问题描述问题描述】有有 m 个人，其编号分
65、别为个人，其编号分别为 1m。按顺序围成。按顺序围成一个圈，现在给定一个数一个圈，现在给定一个数 n，从第一个人开始依次，从第一个人开始依次报数，报到报数，报到 n 的人出圈，然后再从下一个人开始，的人出圈，然后再从下一个人开始，继续从继续从 1 开始依次报数，报到开始依次报数，报到 n 的人再出圈，的人再出圈，如此循环，直到最后一个人出圈为止。编程输出所如此循环，直到最后一个人出圈为止。编程输出所有人出圈的顺序。有人出圈的顺序。【输入格式输入格式】一行两个正整数一行两个正整数 m 和和 n，之间用一个空格隔，之间用一个空格隔开，开，1m100，1n32767。【输出格式输出格式】输出输出 m
66、 行，每行一个正整数，表示依次出圈行，每行一个正整数，表示依次出圈的人的编号。的人的编号。【输入样例输入样例】8 5【输出样例输出样例】52871463高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】定义定义 bool 型数组型数组 p，表示每个人在圈中的状态。假设，表示每个人在圈中的状态。假设 p i为为 true 表示第表示第 i 个人还在圈中，个人还在圈中，pi为为 false 表示第表示第 i 个人个人已出圈。模拟报数的过程，从第一个人（已出圈。模拟报数的过程，从第一个人（i = 1）开始报数，）开始报数，定义计数器定义计数器 j，初始化为，初
67、始化为 0，如果，如果 pi为为 true，则，则 j 加加 1，当，当 j 为为 n 时，报到的这个人出圈（时，报到的这个人出圈（pi = false，且，且j=0），），直到所有人都已出圈。程序实现时，另外设计一个计数器直到所有人都已出圈。程序实现时，另外设计一个计数器 t，记录圈中的剩余人数，初始化为，记录圈中的剩余人数，初始化为 m。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-6-4#includeusing namespace std;int main() int m,n,i,j,t; bool p100; cin m n; for(i = 0; i
68、 0) i+; if(i = m+1) i = 1;/ 实现圈的效果实现圈的效果 if(pi) j+; if(j = n) cout i endl; pi = false; j = 0; t-; return 0;结合本题，学结合本题，学会跟踪一维数会跟踪一维数组，调试代码。组，调试代码。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 7 课课 二维数组的定义和操作二维数组的定义和操作学习目标学习目标1. 理解二维数组及其存储结构。理解二维数组及其存储结构。2. 掌握二维数组的初始
69、化、输入输出等基本操作。掌握二维数组的初始化、输入输出等基本操作。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1. 二维数组的定义和初始化二维数组的定义和初始化定义二维数组的一般格式为：定义二维数组的一般格式为：类型标识符类型标识符 数组名数组名 常量表达式常量表达式 1 常量表达式常量表达式 2;常量表达式常量表达式 1 的值表示第一维大小，常量表达式的值表示第一维大小，常量表达式 2 的值的值表示第二维大小，常量表达式表示第二维大小，常量表达式 1 和常量表达式和常量表达式 2 的乘积就是的乘积就是二维数组的元素个数。二维数组的元素个数。 一维数组的元素可以是任何
70、基本数据类型，也可以是结一维数组的元素可以是任何基本数据类型，也可以是结构体。那么，如果一维数组的每一个元素又是一个一维数组构体。那么，如果一维数组的每一个元素又是一个一维数组呢？我们称这种数组为呢？我们称这种数组为“二维数组二维数组”。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）1. 二维数组的定义和初始化二维数组的定义和初始化 在定义二维数组时，可以省略第一维的大小，但是第二维的大小不在定义二维数组时，可以省略第一维的大小，但是第二维的大小不能省略。例如，能省略。例如，“int a5;”是允许的，被省略的第一维大小根据初值是允许的，被省略的第一维大小根据初值的个数
71、由系统来确定。例如：的个数由系统来确定。例如： int a4 = 1,2,3,4,5,6,7,8,9,10,11,12; 系统根据系统根据 中的元素个数，自动确定中的元素个数，自动确定a数组的第一维大小为数组的第一维大小为3。 在二维数组定义的同时，可以进行初始化赋值。例如：在二维数组定义的同时，可以进行初始化赋值。例如： int a23 = 1,2,3,4,5,6;/分行初始化分行初始化 也可以给数组中的部分元素初始化。例如：也可以给数组中的部分元素初始化。例如： int a23 = 1,2,4; 第一行只有第一行只有2个初值个初值, 按顺序分别赋值给按顺序分别赋值给a00和和a01,第二行
72、的初值第二行的初值4赋给赋给a10，其它元素默认为，其它元素默认为0。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）2. 二维数组的存储及元素引用二维数组的存储及元素引用二维数组本质上是一维数组的每一个元素又是一个一二维数组本质上是一维数组的每一个元素又是一个一维数组，而计算机内部存储一维数组采用的是连续存储单维数组，而计算机内部存储一维数组采用的是连续存储单元。所以，二维数组的存储方式是元。所以，二维数组的存储方式是“行优先行优先”的连续存储，的连续存储，先逐个存储第先逐个存储第 0 行上的所有元素，再逐个存储第行上的所有元素，再逐个存储第 1 行上的行上的所有元素，
73、依此类推。所有元素，依此类推。引用二维数组的某一个元素，格式为：引用二维数组的某一个元素，格式为：数组名数组名下标下标1下标下标2高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）3. 二维数组的输入输出二维数组的输入输出二维数组的输入、输出操作也是针对每一个元素二维数组的输入、输出操作也是针对每一个元素进行，结合两个维度的下标变化，用循环嵌套实现。进行，结合两个维度的下标变化，用循环嵌套实现。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、回型方阵、回型方阵【问题描述问题描述】输入一个正整数输入一个正整数 n，输出，输出 nn 的回型方阵。例
74、如，的回型方阵。例如，n=5 时，输出：时，输出：1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 1 1 1 1【输入格式输入格式】一行一个正整数一行一个正整数 n，2n9。【输出格式输出格式】共共 n 行，每行包含行，每行包含 n 个正整数，之间用一个空格隔开。个正整数，之间用一个空格隔开。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】5【输出样例输出样例】1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 1 1 1 1高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题
75、分析问题分析】定义一个二维数组定义一个二维数组 ann 存储回型方阵。存储回型方阵。方法方法1、先给左上角的、先给左上角的 an/2n/2 赋值，赋值，aij = min(i，j)，右上角、左下角、右下角三部分，通过下标的对称性复制过，右上角、左下角、右下角三部分，通过下标的对称性复制过去即可。例如，去即可。例如，ain+1-j = an+1-ij = an+1-i n+1-j = aij。方法方法2、通过、通过“一圈一圈一圈一圈”赋值的方法做，先给赋值的方法做，先给 a11 ann 全部赋值全部赋值 1，然后给，然后给 a22 an-1n-1 全部赋值全部赋值 2，共共 n/2 圈圈(如果如
76、果 n 是奇数，则最后一圈就是一个数是奇数，则最后一圈就是一个数)。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-7-1a#includeusing namespace std;int n,i,j,k,mi,ma,a1010;int main() cin n; for(i = 1; i = (n+1)/2; i+) for(j = 1; j = (n+1)/2; j+) aij = min(i,j); ain+1-j=an+1-ij=an+1-in+1-j=aij; for(i = 1; i = n; i+) for(j = 1; j = n-1; j+) co
77、ut aij “ “ ; cout ain endl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）/p5-7-1b#includeusing namespace std;int n,i,j,k,a1010;int main() cin n; for(k = 1; k = (n+1)/2; k+) for(i = k; i = n+1-k; i+) for(j = k; j = n+1-k; j+) aij = k; for(i = 1; i = n; i+) for(j = 1; j n; j+) cout aij “ “ ; cout ain e
78、ndl; return 0;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 8 课课 二维数组应用举例二维数组应用举例学习目标学习目标综合应用二维数组的基本操作解决一些实际问题。综合应用二维数组的基本操作解决一些实际问题。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、杨辉三角形、杨辉三角形【问题描述问题描述】输入正整数输入正整数 n，输出杨辉三角形的前，输出杨辉三角形的前 n 行。例如，行。例如，n=5 时，时，杨辉三角形如下：杨辉三角形如下： 1
79、1 1 1 2 1 1 3 3 1 1 4 6 4 1【输入格式输入格式】一行一个正整数一行一个正整数 n，1n20。【输出格式输出格式】共共 n 行，第行，第 i 行包含行包含 i 个正整数，之间用一个空格隔开。个正整数，之间用一个空格隔开。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【输入样例输入样例】5 5【输出样例输出样例】1 11 11 11 2 11 2 11 3 3 11 3 3 11 4 6 4 11 4 6 4 1【问题分析问题分析】定义一个二维数组定义一个二维数组 tri 存储杨辉三角形（其实只用到二维存储杨辉三角形（其实只用到二维数组的左下部分）
80、。对于第数组的左下部分）。对于第 i 行（行（1in），共有），共有 i 个数，其个数，其中第一个数和最后一个数都是中第一个数和最后一个数都是 1，其他数，其他数 triij = trii-1j-1 + trii-1j。具体实现，采用。具体实现，采用“递推法递推法”，逐行逐列给每，逐行逐列给每个数组元素赋值。参考程序见教材个数组元素赋值。参考程序见教材171页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、数字三角形、数字三角形【问题描述问题描述】读入一个正整数读入一个正整数 n，输出如下形式的数字三角形（具体，输出如下形式的数字三角形（具体见样例）。见样例
81、）。【输入格式输入格式】一行一个正整数一行一个正整数 n，1n100。【输出格式输出格式】共共 n 行，第行，第 i 行包含行包含 i 个正整数，每个正整数占个正整数，每个正整数占 5 列。列。【输入样例输入样例】5【输出样例输出样例】1 2 3 4 51 2 3 41 2 31 21高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】定义二维数组定义二维数组 a 存储所求的数字三角形，初始化为存储所求的数字三角形，初始化为 0。对。对于右上角的每一个元素于右上角的每一个元素 aij，分析发现：，分析发现：aij = j-i+1。具。具体实现采用体实现采用
82、“赋值法赋值法”。参考程序见教材参考程序见教材172页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、奖学金、奖学金问题描述见教材问题描述见教材172页。页。【问题分析问题分析】本题涉及本题涉及“多关键字多关键字”排序。用一个二维数组排序。用一个二维数组 stu 保存保存 n 位同学的学号、语文、数学位同学的学号、语文、数学 、英语、总分成绩，然后以、英语、总分成绩，然后以总分成绩为第一关键字（降序）、语文成绩为第二关键字总分成绩为第一关键字（降序）、语文成绩为第二关键字（降序）、学号为第三关键字（升序）排序。最后输出排（降序）、学号为第三关键字（升序）排序
83、。最后输出排序后的前序后的前 5 个同学的学号和总分。个同学的学号和总分。参考程序见教材参考程序见教材173-174页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）第第 9 课课 数字方阵数字方阵学习目标学习目标应用二维数组解决一些数字方阵问题，体会数组的下应用二维数组解决一些数字方阵问题，体会数组的下标运算。标运算。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）数字方阵数字方阵数字方阵就是一个行列数相等的二维数组，其中的每数字方阵就是一个行列数相等的二维
84、数组，其中的每个元素都是数字。解决数字方阵问题，一般有两种方法：个元素都是数字。解决数字方阵问题，一般有两种方法：解析法和模拟法。解析法和模拟法。解析法解析法就是找出每一个方阵元素就是找出每一个方阵元素 f ij 与与 i、j 和数组和数组规模规模n的通项公式，然后直接用两重循环给数组元素赋值，的通项公式，然后直接用两重循环给数组元素赋值，相对比较容易，一般用在初始化等场合。相对比较容易，一般用在初始化等场合。模拟法模拟法就是把数字方阵看成一个动态的填数过程，把就是把数字方阵看成一个动态的填数过程，把 n2 个数依次填入数组中，每填好一个数，就定位好下一个数依次填入数组中，每填好一个数，就定位
85、好下一个数的位置个数的位置 i 和和 j。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、n 阶奇数幻方阶奇数幻方【问题描述问题描述】行列数相等的矩阵称为方阵。把正整数行列数相等的矩阵称为方阵。把正整数 1n 2 （n 为奇数）为奇数）排成一个排成一个 nn 方阵，使得方阵中的每一行、每一列以及两条方阵，使得方阵中的每一行、每一列以及两条对角线上的数之和都相等，这样的方阵称为对角线上的数之和都相等，这样的方阵称为“n 阶奇数幻方阶奇数幻方”。编程输入编程输入 n，输出，输出 n 阶奇数幻方。阶奇数幻方。【输入格式输入格式】一行一个正整数一行一个正整数 n，1n l
86、etter；用用 cin 逐个元素输入：逐个元素输入：cin letter0；用用 gets 读入整个数组：读入整个数组：gets（letter）；）；用用 getchar 逐个读入：逐个读入：letter0=getchar（）；（）；高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）字符数组输出方法字符数组输出方法用用 cout 输出整个数组：输出整个数组：cout letter；用用 cout 逐个元素输出：逐个元素输出：cout letter0；用用 printf 输出整个数组：输出整个数组：printf （%s，letter）；）；用用 printf 逐个元素输出：
87、逐个元素输出：printf （%c，letter0）；）；用用 puts 输出整个数组：输出整个数组：puts（letter）；）；用用 putchar 逐个元素输出：逐个元素输出：putchar（letter0）；）；高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例1、阅读以下程序，体会各种字符串输入输出方式的区别。、阅读以下程序，体会各种字符串输入输出方式的区别。p5-10-1a#includeusing namespace std;int main() char s120,s220; scanf( “ %s ” ,s1); scanf( “ %s ” ,s2);
88、 printf( “ %sn ” ,s1); printf( “ %sn ” ,s2); return 0;运行程序，输入运行程序，输入“Hello world!”。输出为：输出为：Helloworld!高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】scanf 函数读取一个字符串时，是把回车符、空格符、函数读取一个字符串时，是把回车符、空格符、Tab 符作为字符作为字符串的结束符号。所以，输入符串的结束符号。所以，输入“Hello world!”，第一个，第一个 scanf 语句只会读语句只会读取取“Hello”，而第二个，而第二个 scanf 语句
89、会接着读入语句会接着读入“world!”。 如果程序改为用如果程序改为用 gets 输入、输入、puts 输出：输出：/p5-10-1b#includeusing namespace std;int main() char s120,s220; gets(s1); gets(s2); puts(s1); puts(s2); return 0;运行程序，输入：运行程序，输入：Hello world!Test2则输出为：则输出为：Hello world!Test2高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）如果程序改为用如果程序改为用 getchar 输入、输入、putc
90、har 输出：输出：/p5-10-1c#includeusing namespace std;int main() char s120,s220,i; i = 0; while(s1i = getchar() != n ) i+; s1i = 0 ; i = 0; while(s1i != 0 ) putchar(s1i); i+; 高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+） putchar( n ); i = 0; while(s2i = getchar() != n ) i+; s2i = 0 ; i = 0; while(s2i != 0 ) putchar(
91、s2i); i+; putchar( n ); return 0;对比、测试、分析以上程序，对比、测试、分析以上程序，总结字符数组的输入操作。总结字符数组的输入操作。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）快速读入数字字符串函数快速读入数字字符串函数int scan() int res = 0, flag = 0; char ch; if(ch = getchar() = -) flag = 1; else if(ch = 0 & ch = 0 & ch = 9) res = res * 10 + (ch - 0); return flag ? -res : re
92、s;高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例2、数字和、数字和【问题描述问题描述】输入一个整数输入一个整数 n，求各位上的数字和。，求各位上的数字和。【输入格式输入格式】一行一个整数一行一个整数 n，n 最多最多 200 位。位。【输出格式输出格式】一行一个整数，表示整数一行一个整数，表示整数 n 的各位数字之和。的各位数字之和。【输入样例输入样例】1234【输出样例输出样例】10高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）【问题分析问题分析】由于由于n可能到可能到200位，任何整数类型都是不可能存储的。位，任何整数类型都是不可能存储
93、的。因此，定义一个一维字符数组读取、存储这个超大数，然因此，定义一个一维字符数组读取、存储这个超大数，然后把每个字符转换成数值累加求和。后把每个字符转换成数值累加求和。参考程序见教材参考程序见教材185页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例3、扫雷游戏、扫雷游戏【问题描述问题描述】 参见教材参见教材186页。页。【问题分析问题分析】定义一个二维字符数组存储雷区，再定义一个二维整型定义一个二维字符数组存储雷区，再定义一个二维整型数组存储每个位置周围地雷的个数。输入雷区时，可以用数组存储每个位置周围地雷的个数。输入雷区时，可以用 gets 逐行读入，也可
94、以用逐行读入，也可以用 getchar 逐个读入字符。输出字符逐个读入字符。输出字符数组时，可以用数组时，可以用 putchar 逐个字符输出。逐个字符输出。参考程序见教材参考程序见教材186-187页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）例例4、最大整数、最大整数【问题描述问题描述】 参见教材参见教材187页。页。【问题分析问题分析】字符串比较函数：字符串比较函数：strcmp（s1，s2），当），当 s1 s2 时，时，返回一个正整数。返回一个正整数。字符串复制函数：字符串复制函数：strcpy（a，b），表示将字符串），表示将字符串 b 的的值复制给
95、字符串值复制给字符串 a，当然字符串，当然字符串 b的长度不能超过字符串的长度不能超过字符串 a。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）使用以上两个函数时均要加上头文件使用以上两个函数时均要加上头文件 cstring 或或 string.h。再介绍字符串的再介绍字符串的“连接连接”方法：方法： “13”+“132”就等于就等于“13132”。本题很容易想到把本题很容易想到把 n 个数当成字符串处理，然后把这个数当成字符串处理，然后把这 n 个字符串按个字符串按从大到小排序之后输出。但是，这个方法是不对的，举个反例：从大到小排序之后输出。但是，这个方法是不对的，举
96、个反例：s1 =“31”，s2 =“312”，最大值是，最大值是 31312，而按照，而按照strcmp（s1，s2）比较是输出）比较是输出 31231。其实，应该以两个数字串连接后的大小来决定两个数字串的先后。其实，应该以两个数字串连接后的大小来决定两个数字串的先后顺序。也就是：如果顺序。也就是：如果 s1+s2 s2+s1，则，则 s1 排在前面，即认为排在前面，即认为 s1 s2；若；若是是 s1+s2 s2+s1，则认为，则认为 s1 s2。按照这个比较规则对所有数字字符串进行排序并输出即可。按照这个比较规则对所有数字字符串进行排序并输出即可。参考程序见教材参考程序见教材188页。页。高等教育出版社高等教育出版社信息学奥赛课课通（信息学奥赛课课通（C+）实践巩固实践巩固
