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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2020-2021学年信息学奥赛资料-第十四课-二维数组(适用于高中)课件,2020-2021学年信息学奥赛资料-第十四课-二维数组(适,目,标,01,、,理解二维数组及其存储结构。,02,、,掌握二维数组的初始化、输入输出等基本操作,目 标01、理解二维数组及其存储结构。02、掌握二维数组,定义二维数组的一般格式为：,类型标识符 数组名,常量表达式,1,常量表达式,2;,常量表达式,1,的值表示第一维大小，常量表达式,2,的值表示第二维大小，常量表达式,1,和常量表达式,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;,第一行只有,2,个初值,按顺序分别赋值给,a00,和,a01,第二行的初值,4,赋给,a10,，其它元素默认为,0,。,1.二维数组的定义和初始化 在定义二维数组时,2.,二维数组的存储及元素引用,二维数组本质上是一维数组的每一个元素又是一个一维数组，而计算机内部存储一维数组采用的是连续存储单元。所以，二维数组的存储方式是“行优先”的连续存储，先逐个存储第,0,行上的所有元素，再逐个存储第,1,行上的所有元素，依此类推。,引用二维数组的某一个元素，格式为：,数组名,下标,1,下标,2,2.二维数组的存储及元素引用二维数组本质上是一维数组的每一,3.,二维数组的输入输出,二维数组的输入、输出操作也是针对每一个元素进行，结合两个维度的下标变化，用循环嵌套实现。,3.二维数组的输入输出二维数组的输入、输出操作也是针对每一,例,1,、回型方阵,【,问题描述,】,输入一个正整数,n,，输出,nn,的回型方阵。例如，,n=5,时，输出：,1 1 1 1 1,1 2 2 2 1,1 2 3 2 1,1 2 2 2 1,1 1 1 1 1,【,输入格式,】,一行一个正整数,n,，,2n9,。,【,输出格式,】,共,n,行，每行包含,n,个正整数，之间用一个空格隔开。,例1、回型方阵【问题描述】,【,输入样例,】,5,【,输出样例,】,1 1 1 1 1,1 2 2 2 1,1 2 3 2 1,1 2 2 2 1,1 1 1 1 1,【输入样例】,【,问题分析,】,定义一个二维数组,ann,存储回型方阵。,方法、通过“一圈一圈”赋值的方法做，先给,a11 ann,全部赋值,1,，然后给,a22 an-1n-1,全部赋值,2,，,共,n/2,圈,(,如果,n,是奇数，则最后一圈就是一个数,),。,【问题分析】,#include,using 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+),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,【,输出样例,】,1,1 1,1 2 1,1 3 3 1,1 4 6 4 1,【,问题分析,】,定义一个二维数组,tri,存储杨辉三角形（其实只用到二维数组的左下部分）。对于第,i,行（,1in,），共有,i,个数，其中第一个数和最后一个数都是,1,，其他数,triij=trii-1j-1+trii-1j,。具体实现，采用“递推法”，逐行逐列给每个数组元素赋值。参考程序见教材,171,页。,【输入样例】【问题分析】,例,2,、数字三角形,【,问题描述,】,读入一个正整数,n,，输出如下形式的数字三角形（具体见样例）。,【,输入格式,】,一行一个正整数,n,，,1n100,。,【,输出格式,】,共,n,行，第,i,行包含,i,个正整数，每个正整数占,5,列。,【,输入样例,】,5,【,输出样例,】,1 2 3 4 5,1 2 3 4,1 2 3,1 2,1,例2、数字三角形【问题描述】,【,问题分析,】,定义二维数组,a,存储所求的数字三角形，初始化为,0,。对于右上角的每一个元素,aij,，分析发现：,aij=j-i+1,。具体实现采用“赋值法”。,【问题分析】,数字方阵,数字方阵就是一个行列数相等的二维数组，其中的每个元素都是数字。解决数字方阵问题，一般有两种方法：解析法和模拟法。,解析法,就是找出每一个方阵元素,f ij,与,i,、,j,和数组规模,n,的通项公式，然后直接用两重循环给数组元素赋值，相对比较容易，一般用在初始化等场合。,模拟法,就是把数字方阵看成一个动态的填数过程，把,n2,个数依次填入数组中，每填好一个数，就定位好下一个数的位置,i,和,j,。,数字方阵数字方阵就是一个行列数相等的二维数组，其中的每个元素,例,3,、,n,阶奇数幻方,【,问题描述,】,行列数相等的矩阵称为方阵。把正整数,1n,2,（,n,为奇数）排成一个,nn,方阵，使得方阵中的每一行、每一列以及两条对角线上的数之和都相等，这样的方阵称为“,n,阶奇数幻方”。,编程输入,n,，输出,n,阶奇数幻方。,【,输入格式,】,一行一个正整数,n,，,1n20,，,n,为奇数。,【,输出格式,】,共,n,行，每行,n,个正整数，每个正整数占,5,列。,例3、n 阶奇数幻方【问题描述】,【,输入样例,】,5,【,输出样例,】,17 24 1 8 15,23 5 7 14 16,4 6 13 20 22,10 12 19 21 3,11 18 25 2 9,【输入样例】,【,问题分析,】,定义一个二维数组模拟填数的过程。分析样例发现，,n,阶奇数幻方可以按下列方法生成：先把数字,1,填在第,1,行的正中间,a1n/2+1,，然后用一个循环穷举,k,，填入数字,2 n,2,，每次先找位置再填数，找位置的规律如下：如果数,k,填在第,i,行第,j,列，那么一般情况下，下一个数,k+1,应该填在它的右上方，即第,i-1,行第,j+1,列。但是，有两种特殊情况：如果右上方无格子，也就是越界了（,i-1=0,或,j+1=n+1,），那么就应该把下一个数放到第,n,行或者第,1,列；如果右上方已经有数了（,aij,不等于初值），那么下一个数,k+1,就应该填在第,k,个数的正下方。,【问题分析】,作业：螺旋方阵,【,问题描述,】,一个,n,行,n,列的螺旋方阵按如下方法生成：从方阵的左上角（第,1,行第,1,列）出发，初始时向右移动；如果前方是未曾经过的格子，则继续前进；否则，右转。重复上述操作直至经过方阵中所有格子。根据经过顺序，在格子中依次填入,1,，,2,，,3,，,，,n,，便构成了一个螺旋方阵。下面是一个,n=4,的螺旋方阵。,作业：螺旋方阵【问题描述】,编程输入一个正整数,n,，生成一个,nn,的螺旋方阵。,【,输入格式,】,一行一个正整数,n,，,1n20,。,【,输出格式,】,共,n,行，每行,n,个正整数，每个正整数占,5,列。,【,输入样例,】,5,【,输出样例,】,1 2 3 4 5,16 17 18 19 6,15 24 25 20 7,14 23 22 21 8,13 12 11 10 9,编程输入一个正整数 n，生成一个 nn 的螺,【,问题分析,】,定义一个二维数组模拟填数的过程。根据题意，设置一个变量,d,用来表示填数的方向，,d=04,，依次表示向右、向下、向左、向上填数。再定义两个常量数组，表示各个方向上前进一步带来的行、列坐标的变化值。把数字,1,填在第,1,行第,1,列，然后向右填数字,2,，,填到不能填的位置（越界或者已经填了数），就换个方向（,+d%4,）接着填。,【问题分析】,感谢聆听,感谢聆听,