|
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 程式設計(一) 含程式邏輯
翻轉電子書系列:
|