Java 程式設計(一)  第 七章 陣列  上一頁    

 

7-7 專題 研討:陣列運用

內容:

  • 7-7-1 範例研討:二分搜尋演算法

  • 7-7-2 自我挑戰:大樂透對獎系統

7-7-1 範例研討:二分搜尋演算法

『二分搜尋法』是由已排序(由大到小或由小到大排列)的陣列裡,搜尋某一筆資料,圖 7-10 為其運作程序。假設 a 陣列已由小到大排序完成(a[low] ~ a[high]),key 變數儲存欲尋找的資料,首先比對 a 陣列的中間元素(mid)的內容,如果 key = a [mid],則資料找到;如果 key < a[mid],則表示資料位於a[low] a[mid] 之間,則 mid 取代 high;如果 key > a[mid],則資料位於 a[mid] ~ a[high] 之間,mid 取代 low 內容。沒有找到資料的話,則將搜尋目標移到前半段或後半段繼續尋找,但還是由 a[low] ~ a[high] 搜尋(low high 可能會改變);如此依此類推,一直到找到資料或搜尋完畢為止。由此可見,此演算法每次將所有陣列資料缺切一半,再決定位於前段或後段,因此稱之為『二分搜尋法』。

此演算法較困難的地方是,如果找不到資料,如何去判斷與結束。其實,我們可以掌握一個重點,當 high 還是大於 low 的時候,表示還有資料未搜尋到;如果 high 小於或等於 low 時,表示已搜尋完所有資料,還未找到資料,則表示沒有該筆資料。

7-15 二分搜尋法

A)程式功能:Ex7_10.java

數學老師利用一個二維陣列 score[][] 儲存某一班級學生的成績,陣列第一個元素score[k][0]  存放學生學號,由 411101 ~ 411150;第二個元素 score[k][1] 存放數學成績,由 00 ~ 100 分,如:{411101, 70}, {411102, 80}, {411103, 75}, {411104, 90}, {411105, 85}, {4111106, 65}, {411107, 83}, {411108, 78}, {411109, 67}, (411110, 72)...等等。陣列是依照學號由低到高排列。請編寫一程式,允許輸入學生學號,則輸出該學生的成績。程式中先寫一小程式填入陣列內每一位同學的學號與成績,成績採 00 ~ 100 之間的亂數,之後印出全班成績,接著再編寫一個二分搜尋程式。期望操作介面如下:

D:\Java1_book\chap7>java Ex7_10

=== 411101 ~ 411150 成績列印 ===

  90  67  81  51  97  73  56  59  19  57

  93  10  80  89  80  79  84  41  81  75

  89  28  86  71  75  34   3  74  79  83

  32  36  84  57  60  41  17  41  29  76

  88  70  64  94  99  49  36  58  58  56

請輸入欲尋找的學生學號 => 411102

學號 411102 成績是 67

B)製作技巧研討:

本程式大略分為 3 個部分。第 1 部分填入學號與成績(產生亂數),第 2 部分是列印全班成績,第 3 部分,讀入尋找學號,再利用二分搜尋法找出該學號的成績。

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

//Ex7_6.java

 

import java.util.Scanner;

import java.lang.Math;

public class Ex7_6 {

     public static void main(String args[]) {

          Scanner keyin = new Scanner(System.in);

          int a[][], value, flag, low, high, mid;

          a = new int[50][2];

          int number = 411101;

          for(int i=0; i<a.length; i=i+1){

              a[i][0] = number + i;

              a[i][1] = (int)(Math.random()*100);

          }

 

          /* 列印全班成績 */

          System.out.printf("=== 411101 ~ 411150 成績列印 ===\n");

          for(int i=0; i<a.length; i++) {

               System.out.printf("%4d", a[i][1]);

               if((i+1) % 10 == 0)

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

          }       

 

          System.out.printf("請輸入欲尋找的學生學號 => ");

          value = keyin.nextInt();

 

          /*   二分搜尋法 */

          low = 0; high = 49;mid=0;

          flag=0;                     // 設定是否找到旗號

          while((low+1) < high) {        // 陣列是否搜尋完

              mid = (low + high)/2;

              if (value == a[mid][0]) {    // 比對陣列中間元素

                   flag = 1;           // 找到了, 設定旗號並離開

                   break;

              }

              else if (value > a[mid][0])    // 在陣列的後半段

                    low = mid;

              else                     // 在陣列的前半段

                    high = mid;

          }

          

          if (flag == 1)

            System.out.printf("學號 %d 成績是 %d\n", a[mid][0], a[mid][1]);

          else

            System.out.printf("沒有 %d 學號學生\n", value);

    }

}

(D)程式重點分析:

(1) 28~41 二分搜尋演算法

(2) 29 low=0; high=49;。設定原陣列搜尋範圍。

(3) 30 flag=0。設定搜尋旗號為否(還未找到)。

(4) 31~41 while((low+1) < high) { ….}。其中 (low+1) < high 表示元素較高的指標 high 還是高於較低的 low,則陣列還未搜尋完畢。

(5) 32 mid = (high + low)/2。陣列元素索引 high low 之間的中間元素的索引 mid

(6) 33 if(value == a[mid] { …}。成立的話,表示找到該資料,則設定旗號並中斷離開。

(7) 37 else if (value > a[mid][0]) { …}。如未找到,但比中間值 a[mid] 大的話,則設定搜尋後半段(low = mid,但 high 未改變)。

(8) 39 else high = mid。都不是的話,則設定搜尋前半段(low 未改變)。

7-7-2 自我挑戰:大樂透對獎系統

A)程式功能:PM7_11.java

許多客戶買了大樂透彩券,一直不瞭解開獎辦法,再說彩券購買太多的話,每次對獎都要花費許多時間。彩券公司為了方便客戶對獎,於是在網路上公布一套對獎系統,客戶可輸入當期開獎號碼,或觀察當期號碼,也可輸入所購買號碼,系統會告知是否得獎,或簽中哪一獎,大樂透開獎辦法是:利用氣球吹出 6 1~ 49 之間不重複的號碼,另外多一個特別號;中獎種類有:

中獎獎項

開獎辦法

頭講

六個號碼相同者。

貳獎

簽中五個號碼與特別號。

參獎

簽中五個號碼。

肆獎

簽中四個號碼與特別號。

伍獎

簽中四個號碼。

陸獎

簽中三個號碼與特別號。

普獎

簽中三個號碼。

期望操作介面格式如下:

期望操作介面格式如下:

G:\Examples\chap7>java PM7_9

 

== 歡迎光臨  大樂透對獎系統 ==

(1) 輸入開獎號碼 (2) 顯示開獎號碼

(3) 輸入對獎號碼 (4) 離開系統

         請選擇工作項目 =>1

請輸入 6 個開獎號碼 =>11 22 27 29 35 40

請輸入特別號碼 =>48

 

== 歡迎光臨  大樂透對獎系統 ==

(1) 輸入開獎號碼 (2) 顯示開獎號碼

(3) 輸入對獎號碼 (4) 離開系統

         請選擇工作項目 =>2

本期開獎號碼: 11 22 27 29 35 40

特別號: 48

 

== 歡迎光臨  大樂透對獎系統 ==

(1) 輸入開獎號碼 (2) 顯示開獎號碼

(3) 輸入對獎號碼 (4) 離開系統

         請選擇工作項目 =>3

請輸入 6 個對獎號碼 =>11 15 18 22 27 48

3 個對中號碼:11  22  27

特別號 = 48

恭喜您, 陸獎

 

== 歡迎光臨 大樂透對獎系統 ==

(1) 輸入開獎號碼 (2) 顯示開獎號碼

(3) 輸入對獎號碼 (4) 離開系統

         請選擇工作項目 =>

B)製作技巧提示:

吾人將開獎號碼與中獎號碼的陣列宣告成靜態變數,利用 4 個函數(方法)來製作整個系統。虛擬碼提示如下:

虛擬碼提示如下:

宣告開獎號碼、特別號變數(static int spaNum[], special;);

宣告中獎號碼、特別號與數目(static int winNum[], wining, winSpa;);

主方法範圍(main()):

宣告對獎號碼陣列(int[] num = new int[6];);

顯示及讀入工作項目(select);

While (select !=4) {

switch(select) {

case 1:

讀入六個開獎號碼(spaNum[0], .. spaNum[5]);

讀入特別號(special);

case 2:

顯示開獎號碼(spa_disp());

case 3:

讀入六個對獎號碼(num[]

                                   /* 對獎程式 */

                                  wining = 0; winSpa=0; int k=0;

                                  for(int i=0; i<6; i++) {      // 6 個對獎號碼

                                        for(int j=0; j<6; j++) {   // 6 個開獎號碼

                                            if(num[i] == spaNum[j]) {

                                                  winNum[k] = num[i]; // 存入中獎陣列

                                                  wining = wining+1;  // 累增中獎數

                                                  k = k+1;

                                            }

                                          }

                                    if(num[i] == special)      // 1 個特別號

                                    winSpa = num[i];

                                    }

                                    /* 比對對獎數目

                                  switch(wining) {

                                            case 0:

顯示全沒簽中;

                                             case 1:

呼叫顯示中獎號碼(win_disp()

顯示沒有簽中;

case 2:

呼叫顯示中獎號碼(win_disp()

顯示沒有簽中;

case 3:

呼叫顯示中獎號碼(win_disp()

if (winSpa == 0)

顯示簽中普獎;

else {

顯示簽中陸獎;

case 4:

呼叫顯示中獎號碼(win_disp()

if (winSpa == 0)

顯示簽中伍獎;

else {

顯示簽中肆獎;

case 5:

呼叫顯示中獎號碼(win_disp()

if (winSpa == 0)

顯示簽中參獎;

else {

顯示中貳獎;

case 6

呼叫顯示中獎號碼(win_disp());

顯示簽中頭講;

}

 Default:

顯示錯誤輸入, 請重新選擇;

}

顯示及讀入工作項目(select);

}

宣告顯示工作項目方法(static void disp_menu());

宣告顯示開獎號碼及特別號方法(static void spa_disp());

宣告顯示中獎號碼及特別號方法(static void win_disp());

 

翻轉工作室:粘添壽

 

Java 程式設計(一) 含程式邏輯

 

 

翻轉電子書系列: