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

Presentation on theme: "鄭士康 國立台灣大學 電機工程學系/電信工程研究所/ 資訊網路與多媒體研究所"— Presentation transcript:

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

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

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

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

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

6 程式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]); }

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

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

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

10 複利公式

11 程式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]);

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

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

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

15 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];

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

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

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

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

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

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

22 決定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 }

23 第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;

24 第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);

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

26 亂數產生四位數字都不同的四位數: 虛擬碼 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] }

27 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;

28 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];

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

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

31 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);

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

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

34 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;

35 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]); }

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

37 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改變

38 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倒轉

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

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

41 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];

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

43 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;

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

45 處理列 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) { . . . }

46 處理行 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) { . . . }

47 處理列 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) { . . . }

48 處理行 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) { . . . }

49 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];

50 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]);

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

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

53 井字遊戲

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

55 虛擬碼 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 輸出棋盤及訊息

56 判斷使用者或電腦獲勝的演算法 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’ )

57 決定新位置列索引與行索引的 虛擬碼 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

58 顯示棋盤的程式片段 char[,] board = { {' ', ' ', ' '}, {' ', 'o', ' '},
{' ', ' ', ' '} }; Console.WriteLine(" "); 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]);

59 由使用者輸入決定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';

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

61 判斷使用者是否獲勝 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') );

62 注意事項 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]進行==運算

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

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

65 對稱矩陣與下三角矩陣

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

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

68 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;

69 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();

70 不規則二維陣列記憶配置 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]

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

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

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

74 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();

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

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

77 用多層迴圈的寫法 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] + " "); }