常用演算法指南(一)基本演算法思想

05-24

常用演算法指南(一)基本演算法思想

近期看了《Java常用演算法手冊》，來總結一下。想看原書的，在這裡提供原書鏈接:Java常用演算法手冊.pdf

前言

對於程序來說，演算法是一個程序的設計核心，不論什麼項目、什麼編程語言。要實現一個程序，都離不開演算法。而選擇合理的演算法，可以大大提高我們程序的運行效率。所以，掌握常用的演算法，便是作為一個程序員的重要基本技能。

由於本人主要用的是Java語言，所以，本文中說到的各種演算法代碼示例，均採用Java語言來實現，JDK版本為1.8

1.什麼是演算法

從字面上來說，演算法也就是用於計算的方法。是用來解決某些問題的方法。通過這個方法，可以達到想要的計算結果。它就像我們小時候學些的一些數學公式和解題步驟。

演算法，一般有5個特徵：

有窮性：
演算法的執行步驟、時間、都是有限的。不會無休止的一直執行下去。
確切性：
演算法的每一步都必須有明確的定義和描述。
輸入：
一個演算法應該有相應的輸入條件，就像我們小時候做的應用題，已知什麼什麼。來求某個結果，已知部分便是輸入條件。
輸出：
演算法必須有明確的結果輸出。沒有結果，那這個演算法是沒有任何意義的。
可行性：
演算法的步驟必須是可行的，無法執行的則沒有意義，也解決不了任何問題

2.演算法的分類

按照演算法的應用來分：演算法可以分為基本演算法、幾何演算法、加密/解密演算法、查找演算法、圖標數據分析演算法等。

按照演算法的思路來分：演算法可以分為遞推演算法、遞歸演算法、窮舉演算法、分治演算法等。

下面，我們就來講我們的重點之一：也就是演算法思想：

3.常用演算法思想

窮舉演算法思想;
遞推演算法思想;
遞歸演算法思想;
分治演算法思想;
概率演算法思想;

3.1 窮舉演算法思想

窮舉，言下之意便是根據題目的部分條件確定範圍，並在次範圍內對所有情況逐一窮盡驗證，直到找到那個最符合的解。我們常用的循環遍歷，就是用的窮舉思想。在此我們用一個經典的雞兔同籠問題來作為示例。

雞兔同籠問題

這個問題源於1500年前的《孫子算經》原文如下：

今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾何？

/** * 窮舉演算法思想 * 今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾何？ * 解法：通過題目可以知道，雞和兔的總數量為0-35隻(每個動物都是一個腦袋，這就不用說了吧)， * 我們可以假設雞為0，兔子為35，用雞的個數*2+兔子的個數*4就可以得到總的腳的數量，如果等於94，那麼便是答案， * 如果不等，則雞的數量+1，兔子數量-1，依次類推，窮舉所有情況直到得到答案 */ public static void enumeratingAlgorithm() { int head = 35, foot = 94; int j; for (int i = 0; i <= 35; i++) {//i代表雞的數量 j = head - i;//j代表兔子的數量 if (i * 2 + j * 4 == foot) { System.out.printf("雞的個數為[ %d ]只,兔子的個數為[ %d ]只。", i, j); return; } } System.out.printf("此題無解！你家雞和兔子有三隻腳的吧？"); }

在main方法中調用：

enumeratingAlgorithm();

輸出：

雞的個數為[ 23 ]只,兔子的個數為[ 12 ]只。

3.2 遞推演算法思想

遞推演算法是一種理性思維模式的代表，根據已有的數據和關係，逐步推導而得到結果，通常是根據前面的一些項得到後面的一些項

在此我們用一個經典的兔子產仔問題來作為示例。

兔子產仔問題

這個問題癩子13世紀義大利數學家斐波那契的《算盤書》，問題的大意如下：

如果一對兩個月大的兔子以後每一個月都可以生一對小兔子，而一對新生的兔子初剩兩個月後才可以生小兔子。也就是說，1月份出生，3月份才可以產仔。那麼假定一年沒有產生兔子死亡事件，問一年後共有多少對兔子？

/** * 遞推演算法 * 如果一對兩個月大的兔子以後每一個月都可以生一對小兔子，而一對新生的兔子初剩兩個月後才可以生小兔子。 * 那麼假定一年沒有產生兔子死亡事件，問一年後共有多少對兔子？ * 解法： * 頭兩個月，兔子都是只有一對，第三個月食2對，第四個月食3對，第五個月食5對。。。 * 由此可以看出。從第三個月開始，每個月的兔子對數，等於前兩個月之和。 * 所以第n個月的兔子對數為 f? = f??? + f??? * * @param month 月份 */ public static int recursiveDeduceAlgorithm(int month) { int f1, f2; if (month == 1 || month == 2) { return 1; } f1 = recursiveDeduceAlgorithm(month - 1);//遞歸調用 f2 = recursiveDeduceAlgorithm(month - 2);//遞歸調用 return f1 + f2;//根據f???和f???，推導出f?}

調用：

int month = 12; int num = recursiveDeduceAlgorithm(month); System.out.println("經過 " + month + " 個月，共有 " + num + " 對兔子。");

輸出：

經過 12 個月，共有 144 對兔子。

3.3 遞歸演算法思想

程序調用自身的編程技巧稱為遞歸（ recursion）。它通常把一個複雜的問題轉換為與原問題相似的規模較小的問題來求解。

遞歸分為直接遞歸和間接遞歸。

直接遞歸，在方法中調用自身。
間接遞歸，間接的調用一個方法。比如方法a調用方法b，方法b又調用方法a。

遞歸方法在編寫時，要注意使用if語句來在某些情況下強制退出遞歸返回結果。否則，會形成死循環。無法結束，當然也無法得到實際問題的解

使用遞歸，可以是代碼更簡潔清晰，可讀性更好。

如：八皇后問題、漢諾塔問題，階乘計算，都是很遞歸適宜的應用場景。在此，我們以求階乘為例

求階乘問題

所謂階乘，就是從1到指定數之間的所有自然數相乘的結果。n的階乘為：

n! = n * (n-1) * (n-2) * ······ * 2 * 1

/** * 遞歸演算法思想 * 求階乘(factorial)問題 * n的階乘為：n! = n * (n-1) * (n-2) * ······ * 2 * 1 * 解法，每一項都等於前一項-1，結果也等於之前的結果*前一項-1 * 我們這裡用int，要注意int的取值範圍，不要超過int的上限。 * @param n 求n的階乘 * @return n的階乘 */ public static int recursiveAlgorithm(int n) { if (n <= 1) { return 1; } return n * recursiveAlgorithm(n - 1);//遞歸調用}

調用：

int n = 8; int result = recursiveAlgorithm(n); System.out.println(n + " 的階乘為： " + result)

輸出：

8 的階乘為： 40320

3.4 分治演算法思想

分治演算法的基本思想是將一個計算複雜的問題分為規模較小，計算簡單的小問題求解，然後綜合各個小問題，從而得到最終答案。例如我們常說的合併排序、二分法查找、堆排序、快速排序等，就是典型的分治思想的應用。

在此，我們以合併排序為例

合併排序

將待排序數據序列看做有n個長度為1的有序字表組成，他們兩兩合併，得到長度為2的坐桿有序字表。然後再將這些字表兩兩合併，得到長度為4的有序子表，直重複到最後字表長度為n，完成排序。

/** * 合併排序 * 將待排序數據序列看做有n個長度為1的有序字表組成， * 將他們兩兩合併，得到長度為2的坐桿有序字表 * 然後再將這些字表兩兩合併，得到長度為4的有序子表， * 一直重複到最後字表長度為n，完成排序。 * 此合併方法以二路合併為例，這種排序演算法往往需要申請較大的輔助空間，這個輔助空間和待排序原始序列空間一樣多。 */ public static void mergeSort(int a[], int n) { int count = 0;//排序步驟 int len = 1;//有序序列的長度 int f = 0;//變數f做標誌 int[] p = new int[n]; while (len < n) { if (f == 1) { mergeOne(p, a, n, len);//p合併到a } else { mergeOne(a, p, n, len);//a合併到p } len *= 2;//增加有序序列長度 f = 1 - f; count++; System.out.print("第" + count + "步排序結果："); for (int anA : a) { System.out.print(" " + anA); } System.out.print(" "); } if (f == 1) {// for (int h = 0; h < n; h++) {//將p中的數據複製回數組a// a[h] = p[h];// } System.arraycopy(p, 0, a, 0, n);//將p中的數據複製回數組a } } /** * 合併一次，合併一次後的結果主要看b，因為是從a合併到b * * @param a 待合併的序列a,從a合併到b * @param b 待合併的序列b，從a合併到b * @param n 原數組的長度 * @param len 有序序列的長度 */ static void mergeOne(int a[], int b[], int n, int len) { int s = 0; while (s + len < n) { int e = s + 2 * len - 1; if (e >= n) {//最後一段可能少於len個節點 e = n - 1; } //相鄰有序段合併 int k = s, i = s, j = s + len; while (i < s + len && j <= e) {//如果兩個有序表都未結束時，循環比較 if (a[i] <= a[j]) {//將較小的元素複製的b中 b[k++] = a[i++]; } else { b[k++] = a[j++]; } } while (i < s + len) {//未合併的部分複製到數據b中 b[k++] = a[i++]; } while (j <= e) { b[k++] = a[j++]; } s = e + 1; } if (s < n) { for (; s < n; s++) { b[s] = a[s]; } } }

main方法中調用：

int a[] = {118, 101, 105, 127, 112}; mergeSort(a, a.length);

輸出：

第1步排序結果： 118 101 105 127 112第2步排序結果： 101 105 118 127 112第3步排序結果： 101 105 118 127 112

3.5 概率演算法思想

概率演算法依照概率統計的思路來求解問題，其往往不能得到問題的精確解，但是在數值計算領域得到了廣泛的應用。因為很多數學問題，往往需要通過數值計算來求解近似值。比如，求圓周率π。

概率演算法大致分為如下4種形式：

數值概率演算法;
蒙特卡羅(Monte Carlo)演算法;
拉斯維加斯(Las Vegas)演算法;
舍伍德(Sherwood)演算法;

這裡，我們以蒙特卡羅演算法求圓周率為例

蒙特卡羅演算法

/** * 蒙特卡羅演算法 * 蒙特卡羅演算法計算圓周率 * 一個半徑為1的圓，（如圖6-23）陰影部分面積，也就是四分之一的圓的面積 * 計算公式，s?=s/4=(π*r2)/4=π/4 * 而圖中的正方形面積為S?=r2=1； * 按照圖中建議一個坐標系，均勻的向正方形內撒點，那麼落入陰影部分的點數比上全部的點數應該就是s?/S?=π/4 * 根據概率統計的規律，只要撒點足夠多，那麼將得到近似的結果。這就是蒙特卡羅演算法 * * @param n 撒點數 */ public static void monteCarloPI(int n){ double PI;//圓周率π int valid = 0;//有效點數，也就是落入陰影部分的點數 Random random=new Random(); for(int i = 0; i < n; i++){ double x = random.nextDouble();//產生0~1之間的一個隨機數 double y = random.nextDouble(); if((x * x + y * y) <= 1){//點在有效區域內，根據圖，有效點距離原點的距離小於等於1，也就是x2+y2<=1 valid++; } } PI = 4.0 * valid/n; System.out.printf("撒點數：%d,有效點數%d,圓周率π ≈ %12.10f ", n, valid, PI); }

調用：

for(int i = 500000; i < 800000; i+=50000){ monteCarloPI(i); }

輸出：

撒點數：500000,有效點數392927,圓周率π ≈ 3.1434160000撒點數：550000,有效點數432508,圓周率π ≈ 3.1455127273撒點數：600000,有效點數471560,圓周率π ≈ 3.1437333333撒點數：650000,有效點數510239,圓周率π ≈ 3.1399323077撒點數：700000,有效點數549782,圓周率π ≈ 3.1416114286撒點數：750000,有效點數589209,圓周率π ≈ 3.1424480000

可以多次執行程序，會發現撒點數越多，圓周率π的精確度也就越高，同時，這種計算方法有很大的隨機性，每次運行，即使撒點數相同，結算的結果也不盡相同。

基本演算法思想就些，下一章，我們將會總結排序演算法。