2020-2021学年信息学奥赛资料-第十四课-二维数组(适用于高中)课件

1、2020-2021学年信息学奥赛资料-第十四课-二维数组(适用于高中)课件2020-2021学年信息学奥赛资料-第十四课-二维数组(适目 标01、理解二维数组及其存储结构。02、 掌握二维数组的初始化、输入输出等基本操作目 标01、理解二维数组及其存储结构。02、 掌握二维数组定义二维数组的一般格式为：类型标识符 数组名 常量表达式 1 常量表达式 2;常量表达式 1 的值表示第一维大小，常量表达式 2 的值表示第二维大小，常量表达式 1 和常量表达式 2 的乘积就是二维数组的元素个数。 一维数组的元素可以是任何基本数据类型，也可以是结构体。那么，如果一维数组的每一个元素又是一个一维数组呢？我

2、们称这种数组为“二维数组”。1. 二维数组的定义和初始化定义二维数组的一般格式为： 一维数组的元素可以1. 二维数组的定义和初始化 在定义二维数组时，可以省略第一维的大小，但是第二维的大小不能省略。例如，“int a5;”是允许的，被省略的第一维大小根据初值的个数由系统来确定。例如： 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;

3、第一行只有2个初值, 按顺序分别赋值给a00和a01,第二行的初值4赋给a10，其它元素默认为0。1. 二维数组的定义和初始化 在定义二维数组时2. 二维数组的存储及元素引用二维数组本质上是一维数组的每一个元素又是一个一维数组，而计算机内部存储一维数组采用的是连续存储单元。所以，二维数组的存储方式是“行优先”的连续存储，先逐个存储第 0 行上的所有元素，再逐个存储第 1 行上的所有元素，依此类推。引用二维数组的某一个元素，格式为：数组名下标1下标22. 二维数组的存储及元素引用二维数组本质上是一维数组的每一3. 二维数组的输入输出二维数组的输入、输出操作也是针对每一个元素进行，结合两个维度的下

4、标变化，用循环嵌套实现。3. 二维数组的输入输出二维数组的输入、输出操作也是针对每一例1、回型方阵【问题描述】输入一个正整数 n，输出 nn 的回型方阵。例如，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 个正整数，之间用一个空格隔开。例1、回型方阵【问题描述】【输入样例】5【输出样例】1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 1 1 1 1【输入样例】【问题分析】定义一个二维数组 ann 存储回型方阵。方法、通过“一圈一

5、圈”赋值的方法做，先给 a11 ann 全部赋值 1，然后给 a22 an-1n-1 全部赋值 2，共 n/2 圈(如果 n 是奇数，则最后一圈就是一个数)。【问题分析】 #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-

6、1; j+) cout aij “ “ ; cout ain endl; return 0; #include例2、杨辉三角形【问题描述】输入正整数 n，输出杨辉三角形的前 n 行。例如，n=5 时，杨辉三角形如下： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1【输入格式】一行一个正整数 n，1n20。【输出格式】共 n 行，第 i 行包含 i 个正整数，之间用一个空格隔开。例2、杨辉三角形【问题描述】【输入样例】5【输出样例】11 11 2 11 3 3 11 4 6 4 1【问题分析】定义一个二维数组 tri 存储杨辉三角形（其实只用到二维数组的左下部分）。对于第 i 行（1

7、in），共有 i 个数，其中第一个数和最后一个数都是 1，其他数 triij = trii-1j-1 + trii-1j。具体实现，采用“递推法”，逐行逐列给每个数组元素赋值。参考程序见教材171页。【输入样例】【问题分析】例2、数字三角形【问题描述】读入一个正整数 n，输出如下形式的数字三角形（具体见样例）。【输入格式】一行一个正整数 n，1n100。【输出格式】共 n 行，第 i 行包含 i 个正整数，每个正整数占 5 列。【输入样例】5【输出样例】1 2 3 4 51 2 3 41 2 31 21例2、数字三角形【问题描述】【问题分析】定义二维数组 a 存储所求的数字三角形，初始化为 0

8、。对于右上角的每一个元素 aij，分析发现：aij = j-i+1。具体实现采用“赋值法”。【问题分析】数字方阵数字方阵就是一个行列数相等的二维数组，其中的每个元素都是数字。解决数字方阵问题，一般有两种方法：解析法和模拟法。解析法就是找出每一个方阵元素 f ij 与 i、j 和数组规模n的通项公式，然后直接用两重循环给数组元素赋值，相对比较容易，一般用在初始化等场合。模拟法就是把数字方阵看成一个动态的填数过程，把 n2 个数依次填入数组中，每填好一个数，就定位好下一个数的位置 i 和 j。数字方阵数字方阵就是一个行列数相等的二维数组，其中的每个元素例3、n 阶奇数幻方【问题描述】行列数相等的矩

9、阵称为方阵。把正整数 1n 2 （n 为奇数）排成一个 nn 方阵，使得方阵中的每一行、每一列以及两条对角线上的数之和都相等，这样的方阵称为“n 阶奇数幻方”。编程输入 n，输出 n 阶奇数幻方。【输入格式】一行一个正整数 n，1n20，n 为奇数。【输出格式】共 n 行，每行 n 个正整数，每个正整数占 5 列。例3、n 阶奇数幻方【问题描述】【输入样例】5【输出样例】17 24 1 8 1523 5 7 14 16 4 6 13 20 2210 12 19 21 311 18 25 2 9【输入样例】【问题分析】定义一个二维数组模拟填数的过程。分析样例发现，n 阶奇数幻方可以按下列方法生成

10、：先把数字 1 填在第 1 行的正中间 a1n/2+1 ，然后用一个循环穷举 k，填入数字 2 n2 ，每次先找位置再填数，找位置的规律如下：如果数 k 填在第 i 行第 j 列，那么一般情况下，下一个数 k+1 应该填在它的右上方，即第 i-1 行第 j+1 列。但是，有两种特殊情况：如果右上方无格子，也就是越界了（i-1=0 或 j+1=n+1），那么就应该把下一个数放到第 n 行或者第 1 列；如果右上方已经有数了（aij 不等于初值），那么下一个数 k+1 就应该填在第 k 个数的正下方。 【问题分析】作业：螺旋方阵【问题描述】一个 n 行 n 列的螺旋方阵按如下方法生成：从方阵的左上

11、角（第 1 行第 1 列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进；否则，右转。重复上述操作直至经过方阵中所有格子。根据经过顺序，在格子中依次填入 1，2，3，n，便构成了一个螺旋方阵。下面是一个 n=4 的螺旋方阵。作业：螺旋方阵【问题描述】 编程输入一个正整数 n，生成一个 nn 的螺旋方阵。【输入格式】一行一个正整数 n，1n20。【输出格式】共 n 行，每行 n 个正整数，每个正整数占 5 列。【输入样例】5【输出样例】 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9 编程输入一个正整数 n，生成一个 nn 的螺【问题分析】定义一个二