Java 程式設計(二)  ：第 二章 一維陣列  上一頁    下一頁

 

2-3 線性搜尋法

內容：

  • 2-3-1 線性搜尋演算法

  • 2-3-2 範例研討：實現線性搜尋法

  • 2-3-3 範例研討：大樂透電腦選號

2-3-1 線性搜尋演算法

從陣列內尋找某一筆資料，最簡單的方法是線性搜尋法(Linear Serach)；演算法是由陣列的起頭開始比較尋找（比較內容），如搜尋到則立即停止，否則繼續往下一個元素尋找，一直到陣列結束為止，如圖 7-5 所示。線性演算法所處理的陣列不需要特殊處理（如由大到小排列），最佳狀況是第一筆資料就找到；最差狀態是最後一筆資料才搜尋到。

圖 2-2 線性搜尋法的運作

2-3-2 範例研討：實現線性搜尋法

(A) 程式功能：Ex2_3.java

吾人利用 num[] 陣列儲存 10 個整數，輸入一個整數來查詢是否在 num  內，再顯示其執行結果，如下：

num[] = 20   13   45   24   42   34   22   89   19   70  

請輸入一個數值 =>17

17 不在 num 陣列內

num[] = 20   13   45   24   42   34   22   89   19   70  

請輸入一個數值 =>24

24 找到了

（B）程式範例：

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

17

import java.util.Scanner;

public class Ex2_3 {

    public static void main(String args[]) {

      Scanner keyin = new Scanner(System.in);

          int value, flag=0, i;              

          int[] num = {20, 13, 45, 24, 42, 34, 22, 89, 19, 70};

          System.out.printf("num[] = ");

          for (int k=0; k<10; k++)

              System.out.printf("%d   ", num[k]);

          System.out.printf("\n");

          System.out.printf("請輸入一個數值 =>");

          value = keyin.nextInt();

          i=0;

          while (i < 10) {

              if (value == num[i]){

                       flag = 1;

                       break;

              }

              i++;

          }

          if(flag == 1)

               System.out.printf("num[%d] = %d 找到了\n", i, value);

          else

          System.out.printf("%d 不在 num 陣列內", value);

    }

}

2-3-3 範例研討：大樂透電腦選號

（A）程式功能：Ex2-4.java

請製作大樂透的電腦選號系統，系統能自動選出 6 個由 01 ~ 49 號碼，但這六個號碼都不可以重複。期望操作介面如下：

（B）製作技巧研討：

編寫一個產生 6 個隨機亂數的程式並不困難，但如果要這 6 個亂數不重複的話，不加點小技巧是不行的。首先準備一個 6 個元素的陣列（int[] num = new int[6];），每次隨機選出號碼後，立即比較陣列內是否有重複號碼（之前所取的），如果沒有則加入該陣列內。第 1 次選出號碼（i=0），陣列還是空的（j=0），則幾乎不用比對；如已選出 3 個號碼，下一個選出號碼就必須比對之前 3 個號碼是否有重複，依此類推。最後再印出以選出的 6 個號碼。

（C）程式範例：

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

//Ex2-4.java

 

import java.lang.Math;

public class Ex2_4 {

    public static void main(String args[]) {

          int value;                // 隨機選取號碼

          int[] num = new int[6];     // 儲存選取號碼

          int i=0;

          while (i < 6) {

              flag=0;

              value = 1 + (int)(Math.random()*46);

              for (int j=0; j<i; j++) {      // 檢視已選出的號碼

                  if (value == num[j]) {   // 是否重複

                      flag = 1;        // 重複則放棄重來

                      break;

                 }

              }

              if (flag == 0) {

                 num[i] = value;      // 沒重複則填入陣列

                 i = i+1;

              }

          }

          System.out.printf("幸運號碼是: ");

          for (i=0; i<6; i++)

              System.out.printf("%d  ", num[i]);

          System.out.printf("\n");

    }

}

(D) 程式重點分析

(1) 第 9~16 行：『while{i<6} {…}』。選出 6 個不重複號碼。

(2) 第 11~17 行：『for(int j=0; j<i; j++) { if(value == num[j])  …}』。線性搜尋敘述句。

(3) 第 13~14 行：『if(value == num[j]) continue;』。如發現號碼重複，則放棄重來。

翻轉工作室：粘添壽

 

Java 程式設計(二) 含物件導向

 

 

翻轉電子書系列：