鄭士康 國立台灣大學 電機工程學系/電信工程研究所/ 資訊網路與多媒體研究所 陣列 鄭士康 國立台灣大學 電機工程學系/電信工程研究所/ 資訊網路與多媒體研究所

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

前五個質數 p1 = 2; p2 = 3; p3 = 5; p4 = 7; p5 = 11; p[0] = 2; p[1] = 3; . . . Console.WriteLine(p[i-1]);

一維陣列 一維陣列與陣列索引 p[0] p[1] p[2] p[3] p[4] int[] p = new int [5];

程式Array1D.Program片段 const int N = 5; int[] p = new int[N]; p[0] = 2; int i; for (i = 0; i < N; ++i) { Console.WriteLine(p[i]); }

注意事項 「索引在陣列的界限之外」 錯誤 語意錯誤 需要仔細閱讀程式碼，或以偵錯器追蹤索引的變化過程

陣列元素宣告並設值的兩種寫法 int[] p = new int[5] { 2, 3, 5, 7, 11 };

程式Array1D2.Program片段 int[] p = { 2, 3, 5, 7, 11 }; int i; for (i = 0; i < p.Length; ++i) { Console.WriteLine(p[i]); }

複利公式

程式Array1D3.Program片段 Console.Write("輸入年數: "); int n = Int32.Parse(Console.ReadLine()); double[] m = new double[n]; int i; for (i = 0; i < n; ++i) { m[i] = c*Math.Pow(1.0 + p, i+1); } Console.WriteLine("第{0}年後的本利和為{1}", i+1, m[i]);

練習 寫一程式，用迴圈輸入3位同學成績到一維陣列，再用迴圈把所有成績顯示出來. 修改上述程式, 使同學人數可以在程式執行時決定.

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

亂數 依一定機率分佈隨機產生的數 均勻分佈之亂數通常以整數除法的餘數產生 亂數產生器 亂數種子與亂數數列

UsingRandom.Program片段 int seed = 123; Random rand = new Random(seed); int[] count = new int[10]; for (k = 0; k < 10; ++k) { count[k] = 0; } const int N = 1000; for (i = 0; i < N; ++i) k = rand.Next() % 10; ++count[k];

產生不固定的亂數數列 Random rand = new Random();

練習 產生一萬個0到9之間的亂數，統計各點數出現次數，以星號繪出對應長條圖, 每個星號代表出現50次 例如： 0 ******************** ********************* ******************* ******************** ***************** ********************** ****************** . . . 9 *********************

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

遊戲規則 電腦先隨機產生一個四個位數都不同的四位數作為謎底 接著使用者猜測一個四位數 電腦比較所猜的數字與謎底 使用者產生下一次所猜的數字 最高位數字(千位數)可以是0 接著使用者猜測一個四位數 電腦比較所猜的數字與謎底 假設使用者所猜的四個位數中有m位數，不論位置，在謎底中出現；而其中n位數，其數值與位置都與謎底相同，則電腦告知使用者nAmB的訊息 使用者產生下一次所猜的數字

nAmB一例 謎底為0567 所猜數字為5566 5、5、6、6均出現在謎底中，所以m等於4 電腦顯示2A4B

虛擬碼 1 利用亂數產生一個四位數字都不同的四位數x 2 x的四個位數為xd[0]~xd[3] 3 do { 3.1 使用者輸入所猜四位數y 3.2 決定並輸出nAnB 3.3 if( n == 4 ) 3.3.1 輸出猜對訊息 3.3.2 break } } while ( 猜測次數未達上限 ) 4 輸出謎底與猜測次數

決定nAmB虛擬碼 // 謎底xd[0]~xd[3] // 使用者輸入yd[0]~yd[3] for(i=0; i<4; ++i) { for(j=0; j<4; ++j) if( yd[i] != xd[j] ) continue ++m if( i == j ) ++n break }

第0版GuessingNumber.Program 片段 (1/3) xd[0] = '0'; xd[1] = '5'; xd[2] = '6'; xd[3] = '7'; char[] yd = new char[4]; do { Console.Write("猜一個四位數: "); yd = Console.ReadLine().ToCharArray(); ++nGuess; n = 0; m = 0;

第0版GuessingNumber.Program 片段 (2/3) for(i=0; i<4; ++i) { for(j=0; j<4; ++j) if( yd[i] != xd[j] ) continue; ++m; if( i == j ) ++n; break; } Console.WriteLine("{0}A{1}B", n, m);

第0版GuessingNumber.Program 片段 (3/3) if( n == 4 ) { Console.WriteLine("恭喜!您猜對了"); break; } } while( nGuess < maxNGuess );

亂數產生四位數字都不同的四位數: 虛擬碼 1 設定陣列d[0]~d[9]為’0’~’9’ 2 for(i=0; i<4; ++i) { do 產生一個0到9之間的亂數k 檢查d[k]是否與先前的xd元素重複 } while( d[k]已出現過 ) xd[i] = d[k] }

GuessingNumber.Program片段 (1/2) char[] d = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' }; bool again; Random rand = new Random(); for (i = 0; i < 4; ++i) { do { k = rand.Next() % 10; again = false;

GuessingNumber.Program片段 (2/2) for(j=0; j<i; ++j){ if (d[k] != xd[j]) continue; again = true; break; } } while( again ); xd[i] = d[k];

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

排序、倒排、搜尋 進階課程如演算法與資料結構討論的對象 一般程式設計的書籍也常介紹初步的方法，作為陣列處理的範例 大多現代的程式語言，包括C#，都已有現成的函式庫來完成這些工作 只說明如何利用這類函式，而不觸及它們背後的演算法

UsingArrayProcessingFunctions片段 // 排序 Array.Sort(a); // 倒排 Array.Reverse(a); // 搜尋1與2的位置 int idx = Array.IndexOf(a, 1); Console.WriteLine("First index of 1 in a is {0}", idx); idx = Array.IndexOf(a, 2); Console.WriteLine("First index of 2 in a is {0}", idx); idx = Array.LastIndexOf(a, 1);

某班學期成績表 學號 學期成績 B645330 88 B645331 92 B645332 86

鍵(Key)與項(Item) 鍵 排序所根據的一維陣列 項 跟著鍵同時變動，同樣多元素的一維陣列

SortingDataArray片段 (1/2) int N_STUDENTS = 3; string[] registerNumber = new string[N_STUDENTS]; registerNumber[0] = "B645330"; registerNumber[1] = "B645331"; registerNumber[2] = "B645332"; int[] score = new int[N_STUDENTS]; score[0] = 88; score[1] = 92; score[2] = 86;

SortingDataArray片段 (2/2) Array.Sort(score, registerNumber); Array.Reverse(registerNumber); Array.Reverse(score); Console.WriteLine("名次 \t 學號 \t 成績"); for (k = 0; k < N_STUDENTS; ++k) { Console.WriteLine( (k+1) + "\t" + registerNumber[k] + "\t" + score[k]); }

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

ArrayAssignmentAndCopy片段 int seed = 123; Random rand = new Random(seed); const int N = 10; int[] a = new int[N]; for (k = 0; k < N; ++k) { a[k] = rand.Next() % 10; } // 陣列直接設值的副作用:以偵錯器觀察b和a的變化 int[] b = a; Array.Sort(b); //a已隨b改變

ArrayAssignmentAndCopy片段 // 陣列複製的效果:以偵錯器觀察c和a的變化 int[] c = new int[N]; for (k = 0; k < N; ++k) { c[k] = a[k]; } Array.Reverse(c); //a不隨c倒轉 // 陣列複製的效果:以偵錯器觀察d和a的變化 int[] d = new int[N]; Array.Copy(a, d, N); Array.Reverse(d); //a不隨d倒轉

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

某班學生各科成績表 學號\科目 計算機概論 計算機程式設計 B645330 90 84 B645331 88 86 B645332 92

Array2D.Program片段 (1/3) const int N_STUDENTS = 3; const int N_SUBJECTS = 2; string[] registerNumber = new string[N_STUDENTS]; registerNumber[0] = "B645330"; registerNumber[1] = "B645331"; registerNumber[2] = "B645332"; string[] subject = new string[N_SUBJECTS]; subject[0] = "計算機概論"; subject[1] = "計算機程式設計"; int[,] score = new int[N_STUDENTS, N_SUBJECTS];

Array2D.Program片段 (2/3) score[0, 0] = 90; score[0, 1] = 84; double[] individualAverage = new double[N_STUDENTS]; double[] subjectAverage = new double[N_SUBJECTS];

Array2D.Program片段 (3/3) for (int i = 0; i < N_STUDENTS; i++) { int sum = 0; for (int j = 0; j < N_SUBJECTS; j++) { sum += score[i,j]; } individualAverage[i] = (double)sum / N_SUBJECTS;

矩形陣列 int[ , ] score = new int [3, 2]; score[0,0] score[0,1] score[1,0]

處理列 for(i=0; i<N_STUDENTS; ++i) { for(j=0; j<N_SUBJECTS; ++j) { score[0,0] i = 0 score[0,1] i = 1 score[1,0] score[1,1] i = 2 score[2,0] score[2,1] j = 0 j = 1 for(i=0; i<N_STUDENTS; ++i) { for(j=0; j<N_SUBJECTS; ++j) { . . . }

處理行 for(j=0; j<N_SUBJECTS; ++j) { for(i=0; i<N_STUDENTS; ++i) { score[0,0] i = 0 score[0,1] i = 1 score[1,0] score[1,1] i = 2 score[2,0] score[2,1] j = 0 j = 1 for(j=0; j<N_SUBJECTS; ++j) { for(i=0; i<N_STUDENTS; ++i) { . . . }

處理列 j=0 j i=0 i data[i,j] for(i=0; i<data.GetUpperBound(0); ++i) { for(j=0; j<data.GetUpperBound(1); ++j) { . . . }

處理行 j j=0 i=0 i data[i,j] for(j=0; j<data.GetUpperBound(1); ++j) { for(i=0; i<data.GetUpperBound(0); ++i) { . . . }

Array2D2.Program片段 (1/2) string[] registerNumber = { "B645330", "B645331", "B645332" }; int[,] score = { {90, 84}, {88, 86}, {86, 92} }; int nStudents = score.GetUpperBound(0)+1; int nSubjects = score.GetUpperBound(1)+1; double[] individualAverage = new double[nStudents]; double[] subjectAverage = new double[nSubjects];

Array2D2.Program片段 (2/2) Console.WriteLine( "學號\\科目\t計算機概論\t計算機程式設計\t兩科平均成績"); for (int i = 0; i < nStudents; ++i) { Console.Write(registerNumber[i]+" \t"); for(int j=0; j<nSubjects; ++j) { Console.Write(score[i,j]+" \t\t"); } Console.WriteLine("{0:F2}", individualAverage[i]);

練習 寫一程式，設值及印出3階魔方陣(河圖洛書)

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

井字遊戲

棋盤 1 2 1 2 1 2 1 3 4 5 2 6 7 8

虛擬碼 1 board[0,0]~board[2,2]設為' '(引號內是一個空白) 2 do { 2.1 顯示棋盤 2.1 顯示棋盤 2.2 使用者輸入'x'位置 2.3 if( 使用者獲勝 || board已無空格) break 2.4 以亂數決定一個'o'位置 2.5 if( 電腦獲勝 ) break } while( board仍有空格 ) 3 輸出棋盤及訊息

判斷使用者或電腦獲勝的演算法 1 設使用者或電腦最新位置在i0, j0 2 檢查是否成列 2 檢查是否成列 ( board[i0, 0] == board[i0, 1] == board[i0, 2] ) 3 檢查是否成行 ( board[0, j0] == board[1, j0] == board[2, j0] ) 4 檢查主對角線是否均為‘x’ 或 ‘o’ ( board[0, 0] == board[1, 1] == board[2, 2] == ‘x’ 或 ‘o’ ) 5 檢查次對角線是否均為‘x’ 或 ‘o’ ( board[0, 2] == board[1, 1] == board[2, 0] == ‘x’ 或 ‘o’ )

決定新位置列索引與行索引的 虛擬碼 1 do { 1.1 產生一個0到8的亂數k 1.2 io = k / 3 1.3 jo = k % 3 } while( board[io, jo] 不是空白 ) 1 2 1 2 3 4 5 1 2 6 7 8

顯示棋盤的程式片段 char[,] board = { {' ', ' ', ' '}, {' ', 'o', ' '}, {' ', ' ', ' '} }; Console.WriteLine(" 0 1 2 "); Console.WriteLine(" "); Console.WriteLine("0 {0} | {1} | {2} ", board[0, 0], board[0, 1], board[0, 2]); Console.WriteLine(" ---+---+---"); Console.WriteLine("1 {0} | {1} | {2} ", board[1, 0], board[1, 1], board[1, 2]); Console.WriteLine("2 {0} | {1} | {2} ", board[2, 0], board[2, 1], board[2, 2]);

由使用者輸入決定X位置 的程式片段 Console.Write( "輸入x位置的座標, 以逗點分隔: "); string[] input = new string[2]; input = Console.ReadLine().Split(','); int ix = Convert.ToInt16(input[0]); int jx = Convert.ToInt16(input[1]); board[ix, jx] = 'x';

加入迴圈 bool hasVacancies = true; do { //此註解代表先前的兩段程式敘述 } while( hasVacancies );

判斷使用者是否獲勝 userWin = ( (board[ix, 0] == board[ix, 1]) && ( (board[0, jx] == board[1, jx]) && (board[1, jx] == board[2, jx]) ) || ( (board[0, 0] == 'x') && (board[1, 1] == 'x') && (board[2, 2] == 'x') ) || ( (board[0, 2] == 'x') && (board[2, 0] == 'x') );

注意事項 board[i0, 0] == board[i0, 1] == board[i0, 2]不可以直接翻譯成 會被解讀為 board[ix, 0] == board[ix, 1] == board[ix, 2] 會被解讀為 ( board[ix, 0] == board[ix, 1] ) == board[ix, 2] 括弧內的比較結果為bool型別，無法與字元型別的board[ix, 2]進行==運算

檢查是否仍有空格 hasVacancies = false; for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) if (board[i, j] == ' ') hasVacancies = true; break; }

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

對稱矩陣與下三角矩陣

程式 Array2DA /* * 以下三角矩陣 * * / x \ * | x x | * | x x x | * | x x x x | * 示範不規則二維陣列之使用 * 9/29/2008 */

不規則二維陣列 int[][] a = new int [3][]; a[0]= new int[1]; a[1]= new int[2];

Array2DA.Program片段 (1/2) const int N_ROW = 5; int[][] lowerTriangularMatrix = new int[N_ROW][]; for (int i = 0; i < N_ROW; ++i) { lowerTriangularMatrix[i] = new int[i + 1]; } lowerTriangularMatrix[0][0] = 1; lowerTriangularMatrix[1][0] = 2; lowerTriangularMatrix[1][1] = 21;

Array2DA.Program片段 (2/2) for (int i = 0; i < N_ROW; i++) { for (int j = 0; j < lowerTriangularMatrix[i].Length; j++) { Console.Write( lowerTriangularMatrix[i][j] + "\t"); } Console.WriteLine();

不規則二維陣列記憶配置 lowerTriangularMatrix[0] [0][0] lowerTriangularMatrix[1] [1][0] [1][1] lowerTriangularMatrix[2] [2][0] [2][1] [2][2] lowerTriangularMatrix[3] [3][0] [3][1] [3][2] [3][3] lowerTriangularMatrix[4] [4][0] [4][1] [4][2] [4][3] [4][4]

練習 宣告如下稀疏矩陣(sparse matrix),分別設定各列長度為3、2、4、3、1，再設各元素的值後輸出

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

三維陣列 k j 1 2 1 1 2 3 i

Array3D.Program片段 int[,,] a = { { {1, 2}, {-1, 1}, {0, 5} }, { {2, 4}, {1, 3}, {3, 7} }, { {4, 0}, {8, -3}, {9, 6} }, { {-2, 3}, {5, -2}, {1, 1} } }; for (int i=0;i<a.GetUpperBound(0)+1;++i) { for (int j=0;j<a.GetUpperBound(1)+1;++j) { for (int k=0;k<a.GetUpperBound(2)+1;++k) { Console.Write("a[{0}, {1}, {2}] = {3} \t", i, j, k, a[i, j, k]); } Console.WriteLine();

綱要 一維陣列 亂數產生器 猜數字遊戲 一維陣列的排序、倒排、搜尋 整個陣列的設值與複製 矩形二維陣列 井字遊戲Tic-tac-toe *不規則二維陣列 *高維陣列 foreach 敘述

UsingForEach.Program 片段 string[,] strArray = { {"Demonstrating", "the", "use", "of", "foreach"}, {"\nGood", "for", "high", "dimensional", "array"} }; foreach (string str in strArray) { Console.Write(str+" "); } Console.WriteLine();

用多層迴圈的寫法 for (int i = 0; i<strArray.GetUpperBound(0)+1; ++i) { for (int j = 0; j<strArray.GetUpperBound(1)+1; ++j) { Console.Write(strArray[i, j] + " "); }