Ch02 陣列 JAVA程式設計入門(II).

Presentation on theme: "Ch02 陣列 JAVA程式設計入門(II)."— Presentation transcript:

1 Ch02 陣列 JAVA程式設計入門(II)

2 本章大綱 一維陣列宣告與配置 二維陣列宣告與配置 陣列的應用 1/2/2019

3 何謂陣列 生活上的例子:一汽車旅館有六間房間,某天住宿的情形 0號房間有3個房客 1號房間有2個房客 2號房間有2個房客 3號房間有0個房客
我們可以記錄成: 以陣列表示成: 0號房間有3個房客 1號房間有2個房客 2號房間有2個房客 3號房間有0個房客 4號房間有4個房客 5號房間有1個房客 1/2/2019

4 何謂陣列 陣列-「多個擁有相同名稱且同型別的變數集合」 陣列是一段連續的區域，裡面由數個相同型別的陣列元素組成
陣列元素有相同的名稱，為了區別每個陣列元素，它們有各自的位置編號 陣列元素以陣列名稱，後接一對中括弧“[]”，中括弧內放入位置編號。 位置編號一般也稱為索引，索引一律由0開始，接著是1、2、3…至元素個數減一。 陣列的索引必須是大於或等於0的整數，或結果為整數的運算式。 1/2/2019

5 陣列的宣告與配置(I) 陣列的宣告方式： 同時宣告兩個int型別 配置陣列：(陣列初始化) 宣告與配置陣列的方法一:
資料型別　陣列名稱[]; 資料型別 [] 陣列名稱; 同時宣告兩個int型別 int[] arr1, arr2; 配置陣列：(陣列初始化) 陣列名稱 = new 資料型別[元素個數]; 宣告與配置陣列的方法一: char cArr[]; cArr = new char[3]; 1/2/2019

6 陣列的宣告與配置(II) 宣告並配置： 宣告與配置一陣列的方法二: char cArr[] = new char[3];
1/2/2019

7 陣列的宣告與配置 陣列變數其實是一種參照變數（reference variable） 陣列名稱是指向陣列實體的一個參照變數
JVM中陣列的宣告與配置 陣列變數其實是一種參照變數(reference variable). 當宣告cArr陣列後, 其實只佔32bits(4bytes)用來存參照,由於沒有配置的關係所以不知道陣列有多大. 當cArr完成配置後(即作了cArr = new char[3]), cArr會參考到(refer, 指向)3個相連的char型別空間. 也就是說, 配置陣列時, JVM會配給一塊指定的記憶體空間,並使陣列變數(為參照變數)指向陣列實體. 所以,陣列名稱雖然代表陣列,實際上是指向陣列實體的一個參照變數 1/2/2019

8 使用陣列元素 使用陣列元素的語法： 使用陣列的敘述： 取得陣列的長度 陣列名稱[索引]
int iArr[] = new int[3]; //宣告並配置陣列 iArr[1] = 123; //設定第2個元素值為123 iArr[2] = 456; //設定第3個元素值為456 //將第2和第3個元素值相加後設定給第1個元素 iArr[0] = iArr[1] + iArr[2]; 陣列名稱.length 1/2/2019

9 使用陣列元素 元素預設值 陣列在配置後，元素的內容就會被填入預設值。 陣列的基底型態為整數者預設值為0。 浮點數則為0.0f或0.0d。
boolean型別為false。 物件為null。 1/2/2019

10 範例1:Ch06_01.java:以迴圈設值並列出 int[] a = new int[5];
for(int i=0; i<a.length; i++) a[i] = a.length-i; System.out.println("a[" + i + "]=" + a[i]); 程式於程式區\java(1)\Ch06\Ch06_01.java 1/2/2019

11 以大括號配置陣列並設值 宣告並設定陣列內容 例子: 宣告並設定初值時，勿在中括號內填入元素的個數 已宣告的陣列不可以使用大括號配置陣列及設值
法一:資料型別　陣列名稱[] = new 資料型別[] {元素值1, 元素2,..., 元素值N}; 法二:資料型別　陣列名稱[] = {元素值1,元素值2,...,元素值N}; int myArray[] = new int[] {10, 20, 30, 40, 50, 60}; int myArray[] = {10, 20, 30, 40, 50, 60}; int myArray[3] = {1, 2, 3}; // 錯誤 int myArray[]; myArray = {1, 2, 3}; //錯誤 1/2/2019

12 範例2:Ch06_02.java:以大括號設值與陣列預設值
int[] a = {10, 20, 30, 40, 50, 60}; int[] b = new int[3]; for(int i=0; i<a.length; i++) System.out.print("a[" + i + "]=" + a[i] +"\t"); System.out.print("\n"); for(int i=0; i<b.length; i++) System.out.print("b[" + i + "]=" + b[i] +"\t"); 程式於程式區/java(1)/Ch06/Ch06_02.java 1/2/2019

13 二維陣列 二維陣列可以想成有好幾列的房間 13 1/2/2019

14 二維陣列的宣告與配置 宣告二維陣列的語法 配置陣列： 宣告並配置的例子： 資料型別 陣列名稱[][ ]; 資料型別[]陣列名稱[ ];
資料型別　陣列名稱[][ ]; 資料型別[]陣列名稱[ ]; 資料型別[][ ]陣列名稱; 陣列名稱 = new 資料型別[列數][行數]; int[][] arr = new int[3][5]; 14 1/2/2019

15 使用元素 元素的表示法： 行0 行1 行2 行3 列0 a[0][0] a[0][1] a[0][2] a[0][3] 列1 a[1][0]
int[][] a = new int[3][4]; 行0 行1 行2 行3 列0 a[0][0] a[0][1] a[0][2] a[0][3] 列1 a[1][0] a[1][1] a[1][2] a[1][3] 列2 a[2][0] a[2][1] a[2][2] a[2][3] 15 1/2/2019

16 JVM中的二維陣列 建立陣列實體，再指定給參照變數 16 1/2/2019

17 範例2:Ch06_06.java使用二維陣列 int[][] a = new int[3][4];
for(int i=0; i<a.length; i++) for(int j=0; j<a[i].length; j++) 　　　a[i][j] = i*10 + j; { 　　　for(int j=0; j<a[i].length; j++) System.out.print("a["+i+"]["+j+"]="+a[i][j]+"\t"); System.out.print("\n"); } System.out.println("\na=\t" +a); System.out.println("a[0]=\t"+a[0]); System.out.println("a[1]=\t"+a[1]); System.out.println("a[2]=\t"+a[2]); 程式於程式區/java(1)/Ch06/Ch06_06.java 17 1/2/2019 17

18 範例2:Ch06_06.java結果 18 1/2/2019

19 使用大括號建立二維陣列 非矩形二維陣列 行0 行1 行2 行3 列0 1 3 5 列1 2 4 列2 9 8 7 6
int[][] a = {{1, 3, 5}, {2, 4}, {9, 8, 7, 6}}; 行0 行1 行2 行3 列0 1 3 5 列1 2 4 列2 9 8 7 6 19 1/2/2019

20 使用大括號建立二維陣列 若某列只有一個元素時，同樣必須以大括號包起來
int[][] a = {{1, 3, 5}, {2, 4}, {9}}; int[][] a = {{1, 3, 5}, {2, 4}, 9}; //錯誤 20 1/2/2019

21 範例3:Ch06_07.java使用非矩形的二維陣列
int[][] a = {{1, 3, 5}, {2, 4}, {9, 8, 7, 6}}; int b[][] = new int[3][]; b[0] = a[2]; b[1] = new int[2]; b[2] = new int[3]; 21 1/2/2019

22 範例3:Ch06_07.java使用非矩形的二維陣列
int[][] a = {{1, 3, 5}, {2, 4}, {9, 8, 7, 6}}; int b[][] = new int[3][]; b[0] = a[2]; b[1] = new int[2]; b[2] = new int[3]; b[0][0] = 10; for(int i=0; i<a.length; i++) { for(int j=0; j<a[i].length; j++) 　System.out.print("a["+i+"]["+j+"]="+a[i][j]+"\t"); System.out.print("\n"); } for(int i=0; i<b.length; i++) for(int j=0; j<b[i].length; j++) System.out.print("b["+i+"]["+j+"]="+b[i][j]+"\t"); 22 1/2/2019

23 範例3:Ch06_07.java結果 23 1/2/2019

24 多維陣列 N維陣列的宣告 配置陣列： 使用元素 建立三維陣列的例子： 資料型別 陣列名稱[][]…[]; 資料型別[][]…[]陣列名稱;
資料型別　陣列名稱[][]…[]; 資料型別[][]…[]陣列名稱; 陣列名稱 = new 資料型別[個數1][個數2]…[個數N]; 陣列名稱[索引1][索引2]…[索引N] int[][][]ar = new int[3][4][5]; int[]b[][] = {{{9}}}; 24 1/2/2019

25 範例一：求三階行列式的值 本程式的學習目標：學會宣告及配置陣列，並且可以使用每一個陣列中的元素 class 行列式 {
public static void main(String [] args) int [][] A ={{1,2,3}, {5,7,9}, {10,5,8}}; int result = 0; result = A[0][0]*A[1][1]*A[2][2]+A[0][1]*A[1][2]*A[2][0]+A[0][2]*A[1][0]*A[2][1]- A[0][2]*A[1][1]*A[2][0]-A[1][2]*A[2][1]*A[0][0]-A[2][2]*A[1][0]*A[0][1]; System.out.println("行列式的值=" + result); } 1/2/2019

26 範例二：求三階行列式的值＿呼叫方法 本程式的學習目標：學會建立一個方法（函數），並且呼叫方法及傳送參數 class 行列式1
{ public static void main(String [] args) { int [][] A ={{1,2,3}, {5,7,9}, {10,5,8}}; //int result = 0; //result = A[0][0]*A[1][1]*A[2][2]+A[0][1]*A[1][2]*A[2][0]+A[0][2]*A[1][0]*A[2][1]- // A[0][2]*A[1][1]*A[2][0]-A[1][2]*A[2][1]*A[0][0]-A[2][2]*A[1][0]*A[0][1]; System.out.println("行列式的值=" + 三階行列式(A)); } static int 三階行列式(int [][] A) {　int result = 0; 　result = A[0][0]*A[1][1]*A[2][2]+A[0][1]*A[1][2]*A[2][0]+A[0][2]*A[1][0]*A[2][1]- 　　 A[0][2]*A[1][1]*A[2][0]-A[1][2]*A[2][1]*A[0][0]-A[2][2]*A[1][0]*A[0][1]; 　return result; 1/2/2019

27 練習一：求一個四階行列式的值 參考範例一及範例二建立一個程式求一個四階行列式的值 四階行列式請自行設定
四階行列式的值必須經過降階為三階或二階行列式計算 程式必須使用呼叫方法（函數）的方式處理 1/2/2019

28 專題討論-矩陣的應用 補充教材(選擇性閱讀)

29 大綱 矩陣運算 高斯消去法 圖形的最短路徑

30 摘要 矩陣的操作是科學和工程計算的核心，很多線性代數的問題都可以利用矩陣操作來求得答案
除了基礎的入門介紹，再討論可降低矩陣相乘時間的Strassen 演算法，最後再介紹如何利用矩陣的操作，來解決線性方程式的問題

31 矩陣基本性質 矩陣與向量 矩陣操作的定義 反矩陣

32 矩陣 矩陣（matrix）是數字所排列的陣列 轉置矩陣（transpose）AT是把行列互換

33 向量 所謂的向量（vector）則是數字的一維陣列 單位向量（unit vector）就是指第i個元素為1，其他皆為0的向量
零矩陣（zero matrix）則是指所有的元素都為0的矩陣

34 正方形的矩陣n×n的基本特性 對角線矩陣（diagonal matrix）是指除了對角線上的元素之外，其他元素皆為0 的矩陣
n×n 單位矩陣（identity matrix）In 是指對角線上的元素都是1，其他都是0 的對角線矩陣

35 正方形的矩陣n×n的基本特性(續) 三對角線矩陣（tridiagonal matrix）T 是一種帶狀的對角線矩陣，其除了對角線、對角線正上方一排與對角線正下方一排之外，其他元素皆為0 的矩陣

36 正方形的矩陣n×n的基本特性(續) 上三角矩陣（upper-triangular matrix）U是對角線上方元素不為0，其下方元素全為0的一種矩陣

37 正方形的矩陣n×n的基本特性(續) 下三角矩陣（lower-triangular matrix）L則和上三角矩陣相反，是指對角線以下元素不為0，對角線以上都為0的矩陣

38 正方形的矩陣n×n的基本特性(續) 排列組合矩陣（permutation matrix）P在每一列或是每一行只有一個1，其他都是0
對稱矩陣（symmetric matrix）A滿足A=AT的條件

39 矩陣操作的定義 矩陣加法（matrix addition） 矩陣減法（matrix subtraction）
如果A=(aij)與B=(bij)是m×n的矩陣，則矩陣C=(cij)=A+B，也是m×n的矩陣，則表示為 cij= aij+ bij，其中i=1,2…,m，j=1,2,…,n。 矩陣減法（matrix subtraction） 就是加上一個負的矩陣，例如： B=A+(-B)

40 矩陣操作的定義 (續) 矩陣乘法（matrix multiplication）
假設A與B矩陣為兩個相容矩陣，也就是說A的行數等於B的列數，如果A=(aij)為一個m×n的矩陣，B=(bjk)為一個n×p的矩陣，則矩陣乘積C=AB=(cik)為一個m×p的矩陣，其表示為 其中i=1,2,…,m，k=1,2,…,p

41 反矩陣 n×n矩陣A的反矩陣也是n×n矩陣，並且表示為A-1，而且AA-1=A-1A，例如：
不過並非每個n×n矩陣都有反矩陣，如果A具有反矩陣，我們說A是可反轉（invertible）或非奇異（non-singular）矩陣； 否則，則說A是不可反轉（non-invertible）或奇異（singular）矩陣。 如果A與B是非奇異n×n矩陣，則(BA)-1=A-1B-1

42 Strassen演算法 假設A與B矩陣皆為矩陣，且n為2的冪次方（也就是說n為1、2、4、8、16…），如果n=1，則矩陣乘積就是直接A與B相乘，若我們考慮n>1，則我們可以把這個矩陣分成4個的小矩陣，表示如下：

43 Strassen演算法 (續) 採用Strassen方法來得到7個小矩陣D、E、….、J，其分別定義為：

44 Strassen演算法 (續) 矩陣D到J需要7次矩陣乘法，6次矩陣加法，和4次矩陣減法運算才能得到。這時候我們可以計算C矩陣，如下：

45 時間複雜度 假設t(n)為Strassen演算法所需要的運算時間，因為大的矩陣都會被分割成小的矩陣，直到每個矩陣小於或等於k（k至少為8或是更大），其次數的遞迴公式表示如下： 其中cn2表示完成矩陣加減法及把大矩陣分割成小矩陣所需的時間。 Strassen演算法可以在O(n2.81)時間內執行完，因此當n足夠大的時候，其會比直接計算的O(n3)還要來的快。

46 線性方程式 假設我們有n個未知數x1,x2,…,xn，它的線性方程式如下 則我們可以很方便的重寫成

47 線性方程式 (續) 或是用簡潔一點的表示法，讓A=(aij)，x=(xi)，以及b=(bi)，則 Ax=b
如果A不是奇異矩陣，則A具有反轉矩陣A-1，則可得 x=A-1b 這就是解答。

48 LUP分解 LUP分解是找出3個n×n的矩陣L、U、P，讓 PA=LU
其中L是一個單位下三角矩陣，U是上三角矩陣，P是一個排列組合矩陣。我們將滿足此方程式的矩陣L、U、P稱為A矩陣的LUP分解 因此當我們將Ax=b兩邊同乘上P，可以得到PAx=Pb，然後把PA分解成LU矩陣，可以得到 LUx=Pb 讓我們定義y=Ux，其中x是我們所要的解答

49 LUP分解 (續) 正向取代的方式來解決未知向量y的下三角系統： 反向取代的方式來解決未知數x的上三角系統： 這樣就會得到我們要的x向量。
Ly=Pb 反向取代的方式來解決未知數x的上三角系統： Ux=y 這樣就會得到我們要的x向量。 證明如下： Ax=P-1Lux =P-1Ly =P-1Pb =b

50 高斯消去法 如果A為一個n×n非奇異矩陣，P為單位矩陣，我們只需要找到A=LU，此稱L與U為A的LU分解。執行LU分解的過程稱為高斯消去法（Gaussian elimination）

51 高斯消去法演算法 如果n=1，則此運算結束，此時L=I1、U=A。如果n>1，我們可將A分割成4個部分：

52 高斯消去法演算法 (續) 透過因式分解法，我們可以得到
其中 稱為Schur補數。如果Schur補數也可以找出LU分解的話，就證明矩陣A可以透過遞迴方式找出LU分解。

53 高斯消去法演算法 (續) 假設Schur補數是非奇異矩陣，則我們說： 其中L’是單位下三角矩陣，而U’為上三角。則我們可以表示矩陣A為

54 高斯消去法演算法 (續) 在此必須注意當a11=0時，會產生除以0的錯誤，所以依此類推，其對角線的元素都不可以為0，因為它在分解的過程中都會當作分母。 這個在分解時會被當作分母的元素，我們稱為中樞（pivot）。所以在LUP分解過程中所使用的P矩陣就是為了避免讓我們除以0，而這個重新排列的過程則稱為迴旋（pivoting）。

55 時間複雜度 LU分解法受歡迎的原因是其不需要儲存LU中的0與1，而且原矩陣A能表示成LU兩個矩陣，所以我們採用重複迴圈的方式來取代遞迴，因為L的對角線都是1，而對角線之上都為0，U的對角線之下也都為0，所以根本不需要去記錄。 計算的時候需要三層迴圈，所以這個演算法所需要的時間為 。

56 結論 矩陣操作的基本演算法，其包含了矩陣乘法與解線性聯立方程式。
一開始我們先說明基本的矩陣知識，包括各種矩陣的性質與定義。接著，我們舉出矩陣乘法計算的方式，由於直接計算的方式會耗費許多時間，因此我們利用Strassen演算法來降低時間複雜度。 其次，我們介紹利用矩陣來解決線性聯立方程式的問題，並且利用LU分解的方式，與透過規律的遞迴分解，可以解出線性聯立方程式的解。