| |
7-7 專題
研討：陣列運用
內容：
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 程式設計(一) 含程式邏輯
翻轉電子書系列：
|
