陣 列.

Presentation on theme: "陣 列."— Presentation transcript:

1 陣 列

2 內 容 大 綱 陣列的定義與存取 陣列的應用 — 儲存矩陣 陣列的應用 — 表示多項式 陣列的應用 — 魔術方陣 陣列的應用 — 隨機漫步 陣列的排序 — 氣泡排序

3 陣列的定義與存取(1/7) 陣列(array)：
許多型別(type)相同並連續儲存的資料所構成的集合，一般我們使用註標(index)來儲存與擷取陣列中的個別資料 我們將陣列的存取方式分為：一維(one-dimension)陣列存取及多維(multi-dimension)陣列存取 一維(one-dimension)陣列存取使用一個註標(index)來存取陣列中的資料，是最簡單的陣列存取方法，一般我們使用以下的方法來描述：陣列識別名稱[註標] 圖4-1描述使用一個識別名稱為a的一維陣列在記憶體中連續儲存的情形。

4 陣列的定義與存取(2/7) 多維(multi-dimension)陣列存取使用多個(multiple)註標(index)來存取陣列中的資料，一般我們使用以下的方法來描述：陣列識別名稱[第一個註標] ... [最後一個註標] 以下我們使用多維陣列中最簡單的二維陣列存取來說明多維陣列存取的資料儲存方式。二維陣列使用二個註標來存取陣列中的資料，假設第一個註標有n個值(範圍由0至n-1)，而第二個註標有m個值(範圍由0至m-1)，則此二維陣列一共可以儲存n×m個元素。我們將第一個註標稱為列(row)註標，並將第二個註標稱為行(column)註標，我們並將此二維列稱為一個n列m行的陣列。二維陣列儲存的資料在邏輯上可以視為如圖4-2的形式。

5 陣列的定義與存取(3/7) 我們有二種方式來安排此n×m個元素在記憶體中的位置：一種為以列優先(row-major)，另一種為以行優先(column-major) 二維陣列以列優先： 儲存資料時先將列註標為0(第1個值)的所有元素儲存完畢之後，再儲存列註標為1(第2個值)的所有元素，…，最後儲存列註標為n-1(第n個值)的所有元素。 假設陣列的識別名稱為a，若陣列的啟始位址為s(即陣列a由s開始儲存)，則a[ i ][ j ]之位址為s+i×m×d+j×d。如圖4-3所示

6 陣列的定義與存取(4/7) 二維陣列以行優先：
儲存資料時先將行註標為0(第1個值)的所有元素儲存完畢之後，再儲存行註標為1(第2個值)的所有元素，…，最後儲存行註標為n-1(第n個值)的所有元素。 假設陣列的識別名稱為a，若陣列的啟始位址為s(即陣列a由s開始儲存)，則a[ i ][ j ]之位址為s+j×n×d+i×d。如圖4-4所示 上述的二維陣列資料儲存位置的推導，採用C/C++/Java程式語言的慣例，將註標的最小值限定為0。依上述的推導，若有一個二維陣列a可以自行訂定0以外的陣列註標下限值。

7 陣列的定義與存取(5/7) 例如：列的上限與下限為及，而行的上限與下限為及，則以列優先存放資料，a[ i ][ j ]的儲存位置為
依以上的二維陣列資料儲存位置推導，我們可以得到多維陣列(multi-dimension)資料儲存位置推導的公式。假設一個k維陣列a使用k個註標，第1個註標的上限與下限為l1和u1，…，第k個註標的上限與下限為Lk和Uk。我們將之表示為

8 陣列的定義與存取(6/7)

9 陣列的定義與存取(7/7)

10 陣列的應用 — 儲存矩陣(1/1) 矩陣(matrix)中含有大量連續依行與列排列整齊的資料，適合使用二維陣列來儲存，例如，對於一個的矩陣，我們可以使用一個m列n行的二維陣列來儲存。 以二維陣列的方式表示矩陣，也相當容易進行一些矩陣運算，例如，以下演算法顯示以二維陣列方式儲存的二個矩陣的乘積(product)運算 以下是以二維陣列的方式表示矩陣並進行矩陣乘積運算的範例程式 執行結果

11 陣列的應用 — 表示多項式(1/3)

12 陣列的應用 — 表示多項式(2/3)

13 陣列的應用 — 表示多項式(3/3) 以下我們介紹以儲存非0係數的方式表示多項式的情況下，執行二個多項式相加的演算法，例如
以下是以陣列儲存所有非0係數的方式表示多項式並進行多項式加法的範例程式 執行結果

14 陣列的應用 — 魔術方陣(1/1) 所謂魔術方陣(magic square) 就是一個由1到n2 的數字所組成的nn陣列，具有各對角線，各橫行與縱列的數字和都相等的性質。 以下，我們介紹如何使用n為奇數的nn二維陣列，來產生魔術方陣的演算法，例如 以下是以二維陣列產生奇數魔術方陣的範例程式 執行結果

15 陣列的應用—隨機漫步(1/2) 在數學上有一個稱為隨機漫步(random walk)的問題，這個問題很難用機率理論(probability theory)的技巧來分析解答，但是若能在電腦上使用模擬(simulation) 的技巧來解答的話，就變得非常簡單了。 隨機漫步問題，在一個nm的方格中，有一個物體置於此方格的正中央格點，假設此物體能夠以相等的機率由它所在格點移動至8個相鄰格點的任何一個格點，則平均需要多少次移動來使物體經過方格中的每一個格點？

16 陣列的應用—隨機漫步(2/2) 以下的演算法使用陣列配合模擬的技巧來解決隨機漫步問題。此演算法先使用一維陣列來對照出8種任意移動的水平位置及垂直位置的移動量，如圖4-5所示，可能的移動被賦予0至7的編號，再以這些編號為一維陣列之註標，就可以決定移動的量。 另外，再配合二維陣列的使用，來記錄每一塊磁磚被經過的次數，就可以使用模擬的方式來解決隨機漫步問題了，例如 以下是以模擬方式解決隨機漫步問題的範例程式 執行結果

17 陣列的排序 ─ 氣泡排序(Bubble Sort)(1/3)
所謂陣列的排序(sorting)是將陣列中的元素依照其值的大小以由小而大或由大而小的次序排列的一種程序 氣泡排序法是所有排序法中最著名也是最簡單的一個，又稱為交換(exchange)排序法或下沉(sinking)排序法。 使用氣泡排序法來將陣列中的元素(資料)依照其值以由小而大的次序排列，其做法為將相鄰的兩個資料加以比較，若前一筆(左邊)資料的值大於後一筆(右邊)資料的值，則將此二筆資料互相交換，否則資料的位置即維持不動。 上述的比較及交換過程一直持續進行到最後一筆資料被比對到為止，這稱為一個回合(pass)。第一個回合的比對進行到最後一筆資料為止(n-1次比對)，此時具最大值的資料已經調換至最後(最右邊)的位置了

18 陣列的排序 ─ 氣泡排序(Bubble Sort)(2/3)
第二回合的比對則進行到倒數第二筆資料為止，此時具第二大值的資料已經調換至倒數第二個位置了；…；餘依此類推。 以下為氣泡排序法的演算法，例如 假設有一個陣列具有5個元素8、5、8’、6、7，註標為0~4，其中8與8’二個元素的值都是8，但是為了區別起見，我們將之標示為8與8’。此陣列經由氣泡排序法排序的過程如下，例如 在上列的氣泡排序法執行過程值中，我們觀察到在回合3(Pass 3)執行完畢時，已經沒有任何的元素需要對調了，這是因為所有的元素已經依照順序排列妥當了。若我們能善用上列的事實，在氣泡排序法的每一個回合中均加入是否有任何元素經過對調的檢查，只要一發現某個回合中已經完全沒有元素對調，則馬上可以停止後續的回合的執行，加快排序的速度。

19 陣列的排序 ─ 氣泡排序(Bubble Sort)(3/3)
以下我們即列出這個稱為改良氣泡排序法的演算法，例如 改良氣泡排序法在最佳狀況下(此時元素完全依照大小的順序排列)，在執行完回合1(Pass 1)之後，執行了n-1次資料大小比對，發現完全沒有任何的元素對調，此時排序完成。因此，改良氣泡排序法的最佳時間複雜度為O(n)，改良氣泡排序法的最差時間複雜度為O(n2) 我們將氣泡排序法以及改良氣泡排序法的各項特色整理如下，例如 以下為「改良氣泡排序」的Java範例程式 執行結果

20 The End

21 圖4-1

22 圖4-2

23 圖4-3

24 圖4-4

25 圖4-5

26 註解:魔術方陣 魔術方陣(magic square)在中國稱為洛書、幻方或縱橫圖，傳說大約在三千年前，夏禹在治水時，於洛水裡發現了一隻大烏龜，龜背上刻有奇特的圖案，這個圖案類似排成3行3列的1至9的數(點)，這些數字有一個特徵，就是每一行、每一列以及二個對角線上的數字和都是15。當時的人們認為這是一個吉祥的象徵，將這個圖案稱為「洛書」，並將它畫在紙上攜帶，作為護身符之用。西方對於魔術方陣的研究則較晚，一直到13世紀才開始有文獻記載。

27 註解:模擬 使用電腦程式來模擬(simulation)事件(event)的發生，可用以解決許多難以直接使用機率理論(probability theory)分析解決的問題，這個技巧常常應用在各種不同的領域上。

28 範例

29 範例

30 範例

31 範例

32 範例

33 範例

34 範例

35 範例

36 範例程式

37 範例程式

38 範例程式

39 範例程式

40 範例程式

41 範例程式

42 範例程式

43 範例程式

44 範例程式

45 範例程式

46 範例程式

47 範例程式

48 範例程式

49 範例程式

50 範例程式

51 範例程式

52 範例程式

53 執行結果

54 執行結果

55 執行結果

56 執行結果

57 執行結果