2020-2021學(xué)年信息學(xué)奧賽資料-第十四課-二維數(shù)組(適用于高中)課件

1、2020-2021學(xué)年信息學(xué)奧賽資料-第十四課-二維數(shù)組(適用于高中)課件2020-2021學(xué)年信息學(xué)奧賽資料-第十四課-二維數(shù)組(適目 標(biāo)01、理解二維數(shù)組及其存儲結(jié)構(gòu)。02、 掌握二維數(shù)組的初始化、輸入輸出等基本操作目 標(biāo)01、理解二維數(shù)組及其存儲結(jié)構(gòu)。02、 掌握二維數(shù)組定義二維數(shù)組的一般格式為：類型標(biāo)識符 數(shù)組名 常量表達(dá)式 1 常量表達(dá)式 2;常量表達(dá)式 1 的值表示第一維大小，常量表達(dá)式 2 的值表示第二維大小，常量表達(dá)式 1 和常量表達(dá)式 2 的乘積就是二維數(shù)組的元素個數(shù)。 一維數(shù)組的元素可以是任何基本數(shù)據(jù)類型，也可以是結(jié)構(gòu)體。那么，如果一維數(shù)組的每一個元素又是一個一維數(shù)組呢？我

2、們稱這種數(shù)組為“二維數(shù)組”。1. 二維數(shù)組的定義和初始化定義二維數(shù)組的一般格式為： 一維數(shù)組的元素可以1. 二維數(shù)組的定義和初始化 在定義二維數(shù)組時，可以省略第一維的大小，但是第二維的大小不能省略。例如，“int a5;”是允許的，被省略的第一維大小根據(jù)初值的個數(shù)由系統(tǒng)來確定。例如： int a4 = 1,2,3,4,5,6,7,8,9,10,11,12; 系統(tǒng)根據(jù) 中的元素個數(shù)，自動確定a數(shù)組的第一維大小為3。 在二維數(shù)組定義的同時，可以進(jìn)行初始化賦值。例如： int a23 = 1,2,3,4,5,6;/分行初始化 也可以給數(shù)組中的部分元素初始化。例如： int a23 = 1,2,4;

3、第一行只有2個初值, 按順序分別賦值給a00和a01,第二行的初值4賦給a10，其它元素默認(rèn)為0。1. 二維數(shù)組的定義和初始化 在定義二維數(shù)組時2. 二維數(shù)組的存儲及元素引用二維數(shù)組本質(zhì)上是一維數(shù)組的每一個元素又是一個一維數(shù)組，而計算機內(nèi)部存儲一維數(shù)組采用的是連續(xù)存儲單元。所以，二維數(shù)組的存儲方式是“行優(yōu)先”的連續(xù)存儲，先逐個存儲第 0 行上的所有元素，再逐個存儲第 1 行上的所有元素，依此類推。引用二維數(shù)組的某一個元素，格式為：數(shù)組名下標(biāo)1下標(biāo)22. 二維數(shù)組的存儲及元素引用二維數(shù)組本質(zhì)上是一維數(shù)組的每一3. 二維數(shù)組的輸入輸出二維數(shù)組的輸入、輸出操作也是針對每一個元素進(jìn)行，結(jié)合兩個維度的下

4、標(biāo)變化，用循環(huán)嵌套實現(xiàn)。3. 二維數(shù)組的輸入輸出二維數(shù)組的輸入、輸出操作也是針對每一例1、回型方陣【問題描述】輸入一個正整數(shù) 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【輸入格式】一行一個正整數(shù) n，2n9?！据敵龈袷健抗?n 行，每行包含 n 個正整數(shù)，之間用一個空格隔開。例1、回型方陣【問題描述】【輸入樣例】5【輸出樣例】1 1 1 1 11 2 2 2 11 2 3 2 11 2 2 2 11 1 1 1 1【輸入樣例】【問題分析】定義一個二維數(shù)組 ann 存儲回型方陣。方法、通過“一圈一

5、圈”賦值的方法做，先給 a11 ann 全部賦值 1，然后給 a22 an-1n-1 全部賦值 2，共 n/2 圈(如果 n 是奇數(shù)，則最后一圈就是一個數(shù))?！締栴}分析】 #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、楊輝三角形【問題描述】輸入正整數(shù) n，輸出楊輝三角形的前 n 行。例如，n=5 時，楊輝三角形如下： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1【輸入格式】一行一個正整數(shù) n，1n20。【輸出格式】共 n 行，第 i 行包含 i 個正整數(shù)，之間用一個空格隔開。例2、楊輝三角形【問題描述】【輸入樣例】5【輸出樣例】11 11 2 11 3 3 11 4 6 4 1【問題分析】定義一個二維數(shù)組 tri 存儲楊輝三角形（其實只用到二維數(shù)組的左下部分）。對于第 i 行（1

7、in），共有 i 個數(shù)，其中第一個數(shù)和最后一個數(shù)都是 1，其他數(shù) triij = trii-1j-1 + trii-1j。具體實現(xiàn)，采用“遞推法”，逐行逐列給每個數(shù)組元素賦值。參考程序見教材171頁?！据斎霕永俊締栴}分析】例2、數(shù)字三角形【問題描述】讀入一個正整數(shù) n，輸出如下形式的數(shù)字三角形（具體見樣例）?！据斎敫袷健恳恍幸粋€正整數(shù) n，1n100?！据敵龈袷健抗?n 行，第 i 行包含 i 個正整數(shù)，每個正整數(shù)占 5 列?！据斎霕永?【輸出樣例】1 2 3 4 51 2 3 41 2 31 21例2、數(shù)字三角形【問題描述】【問題分析】定義二維數(shù)組 a 存儲所求的數(shù)字三角形，初始化為 0

8、。對于右上角的每一個元素 aij，分析發(fā)現(xiàn)：aij = j-i+1。具體實現(xiàn)采用“賦值法”。【問題分析】數(shù)字方陣數(shù)字方陣就是一個行列數(shù)相等的二維數(shù)組，其中的每個元素都是數(shù)字。解決數(shù)字方陣問題，一般有兩種方法：解析法和模擬法。解析法就是找出每一個方陣元素 f ij 與 i、j 和數(shù)組規(guī)模n的通項公式，然后直接用兩重循環(huán)給數(shù)組元素賦值，相對比較容易，一般用在初始化等場合。模擬法就是把數(shù)字方陣看成一個動態(tài)的填數(shù)過程，把 n2 個數(shù)依次填入數(shù)組中，每填好一個數(shù)，就定位好下一個數(shù)的位置 i 和 j。數(shù)字方陣數(shù)字方陣就是一個行列數(shù)相等的二維數(shù)組，其中的每個元素例3、n 階奇數(shù)幻方【問題描述】行列數(shù)相等的矩

9、陣稱為方陣。把正整數(shù) 1n 2 （n 為奇數(shù)）排成一個 nn 方陣，使得方陣中的每一行、每一列以及兩條對角線上的數(shù)之和都相等，這樣的方陣稱為“n 階奇數(shù)幻方”。編程輸入 n，輸出 n 階奇數(shù)幻方?！据斎敫袷健恳恍幸粋€正整數(shù) n，1n20，n 為奇數(shù)。【輸出格式】共 n 行，每行 n 個正整數(shù)，每個正整數(shù)占 5 列。例3、n 階奇數(shù)幻方【問題描述】【輸入樣例】5【輸出樣例】17 24 1 8 1523 5 7 14 16 4 6 13 20 2210 12 19 21 311 18 25 2 9【輸入樣例】【問題分析】定義一個二維數(shù)組模擬填數(shù)的過程。分析樣例發(fā)現(xiàn)，n 階奇數(shù)幻方可以按下列方法生成

10、：先把數(shù)字 1 填在第 1 行的正中間 a1n/2+1 ，然后用一個循環(huán)窮舉 k，填入數(shù)字 2 n2 ，每次先找位置再填數(shù)，找位置的規(guī)律如下：如果數(shù) k 填在第 i 行第 j 列，那么一般情況下，下一個數(shù) k+1 應(yīng)該填在它的右上方，即第 i-1 行第 j+1 列。但是，有兩種特殊情況：如果右上方無格子，也就是越界了（i-1=0 或 j+1=n+1），那么就應(yīng)該把下一個數(shù)放到第 n 行或者第 1 列；如果右上方已經(jīng)有數(shù)了（aij 不等于初值），那么下一個數(shù) k+1 就應(yīng)該填在第 k 個數(shù)的正下方。 【問題分析】作業(yè)：螺旋方陣【問題描述】一個 n 行 n 列的螺旋方陣按如下方法生成：從方陣的左上

11、角（第 1 行第 1 列）出發(fā)，初始時向右移動；如果前方是未曾經(jīng)過的格子，則繼續(xù)前進(jìn)；否則，右轉(zhuǎn)。重復(fù)上述操作直至經(jīng)過方陣中所有格子。根據(jù)經(jīng)過順序，在格子中依次填入 1，2，3，n，便構(gòu)成了一個螺旋方陣。下面是一個 n=4 的螺旋方陣。作業(yè)：螺旋方陣【問題描述】 編程輸入一個正整數(shù) n，生成一個 nn 的螺旋方陣?！据斎敫袷健恳恍幸粋€正整數(shù) n，1n20。【輸出格式】共 n 行，每行 n 個正整數(shù)，每個正整數(shù)占 5 列?！据斎霕永?【輸出樣例】 1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9 編程輸入一個正整數(shù) n，生成一個 nn 的螺【問題分析】定義一個二