目錄
- 一、背景
- 二、猜數字游戲
- 2.1 游戲規則
- 2.2 猜數字游戲原始碼
- 2.3 猜數字游戲技巧
- 三、分治演算法
- 3.1 思想與策略
- 3.2 適用的特征
- 3.3 分治演算法的典型應用
- 3.3.1 歸并排序的原理
- 3.3.2 自頂向下的歸并排序原始碼
- 四、總結
一、背景
分治演算法是計算機五大常用演算法之一，也是在JAVA編程中經常用到的演算法之一，對于分治演算法的理解，往往會停留在一些枯燥的概念上，比如“分而治之”，“問題原子分解”等，該文將會通過一個猜數字的游戲入手，引出對于分治演算法基本思想的思考，
二、猜數字游戲
2.1 游戲規則
- 由電腦生成一個在【1-100】之間的隨機整數；
- 人類每輪只能猜測一個數字；
- 電腦根據人類給出的數字進行反饋：
-- 人類給出的數字比電腦給出的數字大，則反饋“比這個數字要大”；
-- 人類給出的數字比電腦給出的數字小，則反饋“比這個數字要小”；
-- 人類給出的數字等同于電腦給出的數字，則反饋“猜中了”， - 不限猜數輪次，以猜中為準
2.2 猜數字游戲原始碼
- 根據游戲規則，我們先形成編碼：
/**
* 猜數字游戲
*
* @author zhuhuix
* @date 2020-06-11
*/
public class Guess {
public static void main(String[] args) throws IOException {
int num = generateRandomInteger(1, 100);
int guessNum = 0;
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
System.out.println("已生成一個【1-100】的整數，請開始猜數...");
while (num != guessNum) {
String s = bufferedReader.readLine();
if (!s.matches("[0-9]+")) {
System.out.println("請輸入一個整數..");
continue;
}
guessNum=Integer.parseInt(s);
if (guessNum > 100 || guessNum < 1) {
System.out.println("請輸入一個【1-100】整數..");
continue;
}
if (guessNum<num){
System.out.println("Sorry,比這個數字要大，請繼續...");
}
if (guessNum>num){
System.out.println("Sorry,比這個數字要小，請繼續...");
}
}
System.out.println("恭喜您猜中了!!!");
}
/**
* 產生一個在規定范圍內的亂數
*
* @param left 起始數字
* @param right 終止數字
* @return 亂數
*/
private static int generateRandomInteger(int left, int right) {
Random random = new Random();
return left + random.nextInt(right - left + 1);
}
}
2.3 猜數字游戲技巧
- 看看人類是怎么猜的：
--有沒有發現規律？
- 人類猜數字的技巧：
-- 先猜50這個中位數，
-- 根據電腦“大”或“小”的反饋將數字范圍對半拆分
--回圈重復以上分解程序，直至找到對應的數字為止
三、分治演算法
3.1 思想與策略
將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之，
- 注意：是相同問題，就象猜數字游戲一樣，原來的問題是【1-100】的數，分割成的是【1-49】，【50-100】，【50-75】...這些縮小了規模的數，問題的性質始終沒變，
3.2 適用的特征
- 問題縮小到一定規模就容易解決：比如猜數字游戲數字范圍從【1-100】縮小到【56-62】，就容易猜中，
- 問題縮小規模后形成的子問題是相互獨立的，
- 問題規模不管怎么縮小，性質不能改變，
- 利用該問題分解出的子問題的解可以合并為該問題的解
3.3 分治演算法的典型應用
3.3.1 歸并排序的原理
歸并排序就是一種典型的分治演算法：將N個數字的一個大規模表分成1個數字的N個小規模表，再通過數字從小到大的順序從1個數字的N個小規模表合并成N個數字的一個大規模表
3.3.2 自頂向下的歸并排序原始碼
/**
* 整型陣列排序統一介面定義
*
* @author zhuhuix
* @date 2020-06-06
*/
public interface Sort <T extends Comparable<? super T>> {
/**
* 整型排序
* @param arr 待排序陣列
*/
void sort(T[] arr);
}
/**
* 歸并排序
*
* @author zhuhuix
* @date 2020-06-11
*/
public class MergeSort<T extends Comparable<? super T>> implements Sort<T> {
@Override
public void sort(T[] arr) {
mergeSort(arr,0,arr.length-1);
}
private void mergeSort(T[]arr,int l,int r){
// 遞回退出條件：分到最小規模為止
if (r-l<=0){
return;
}
// 取到當前規模的中值
int mid = (l+r)/2;
// 中值的左邊遞回分解
mergeSort(arr,l,mid);
// 中值的右邊遞回分解
mergeSort(arr,mid+1,r);
// 排序合并
if (arr[mid].compareTo(arr[mid + 1]) > 0) {
merge(arr, l, mid, r);
}
}
private void merge(T[]arr,int l,int mid,int r){
T[]aux=Arrays.copyOf(arr,r-l+1);
for (int i = l; i <= r; i++) {
aux[i - l] = arr[i];
}
int i = l, j = mid + 1;
for (int k = l; k <= r; k++) {
if (i > mid) {
arr[k] = aux[j - l];
j++;
} else if (j > r) {
arr[k] = aux[i - l];
i++;
} else if (aux[i - l].compareTo( aux[j - l])<0) {
arr[k] = aux[i - l];
i++;
} else {
arr[k] = aux[j - l];
j++;
}
}
}
}
四、總結
- 分治演算法的難點就是”如何分“：每個分解出來的子問題需獨立存在；比如整數陣列排序時需要從N個數分到1個數...
- 分治演算法一般會涉及遞回程式；
- 分治演算法在從小規模問題合并成大規模問題的程序中，一般需要開辟輔助空間處理，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/164440.html
標籤：Java