編程的關(guān)鍵在于選擇數(shù)據(jù)結(jié)構(gòu)和算法，數(shù)據(jù)結(jié)構(gòu)用于描述問題，算法用于描述解決問題的方法和步驟。

描述問題的數(shù)據(jù)除了各數(shù)據(jù)元素本身，還要考慮各元素的邏輯關(guān)系，主要是一對一的線性關(guān)系，一對多的樹型關(guān)系和多對多的圖形關(guān)系。另外，內(nèi)存中對各數(shù)據(jù)元素的存儲只有順序存儲和鏈?zhǔn)酱鎯煞N方式，所以數(shù)據(jù)結(jié)構(gòu)還要考慮數(shù)據(jù)的存儲結(jié)構(gòu)，并考慮邏輯結(jié)構(gòu)與數(shù)據(jù)結(jié)構(gòu)如何有效地結(jié)合到一起。

用算法描述問題，當(dāng)問題比較復(fù)雜時，通常的思路是分而治之，并輔以適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。

1 分治法Divide and Conquer

分治法通常描述為以下三步：

Divide the problem into more subproblems（分解問題為眾多的子問題）;

Conuqe(solve) the subproblems（解決各子問題）;

Combine(merge) the solution of subproblems(if need)（合并各子問題的解（如果需要））.

如用分治法來計算2^10?

2^10＝2^5*x^5=2^2*x^3*x^5=32*32=1024

相對于順序查找，二分查找有更高的效率，前提是二分查找需要事先排好序：

int binarySearchLoop(int arr[], int len, int findData){  if(arr==NULL || len <=0)    return -1;  int start = 0;  int end = len-1;  while(start<=end)  {    int mid = start+(end-start)/2;    if(arr[mid] == findData)      return mid;    else if(findData < arr[mid])      end = mid-1;    else      start = mid+1;  }  return -1;}

2 枚舉法也是一種暴力縮小問題規(guī)模的算法

簡單的枚舉算法也是可以優(yōu)化的，即盡可能縮小搜索的空間，如判斷質(zhì)數(shù)：

質(zhì)數(shù)（prime number）又稱素數(shù)，有無限個。質(zhì)數(shù)定義為在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。

判斷質(zhì)數(shù)的函數(shù)：

int isPrime(int n){  if(n<= 1)// 小于等于1的整數(shù)不可能是素數(shù)    return 0;  if(n == 2); // 2 是素數(shù)    return 1;  if(n%2 == 0); // 能被2整除的其他整數(shù)都不是素數(shù)    return 0;  int limit = (int)sqrt((double)n)+1;  for(int i = 3; i <= limit; i=i+2)  {    if(n % i == 0)      return 0;  }  return 1;}

isPrime()沒有必要枚舉所有的因子。

I 只要發(fā)現(xiàn)任何一個大于1小于n的因子，就能停下來報告n不是素數(shù)。

II 如果n能被2整除，直接報告n不是素數(shù)。如果n不能被2整除，那么它也不可能被4或6或其他偶數(shù)整除。因此，isPrime只需要檢查2和奇數(shù)（由3開始，步長為2）。但注意有個特例，2能被2整除，但2是素數(shù)。

III 如果n不是素數(shù)，則必有一個因子小于√n 。因此不需要檢查到n為止。只需檢查到√n（n=√n*√n） 。

因為如果n能被2~n-1之間任一整數(shù)整除，其二個因子必定有一個小于或等于√n，另一個大于或等于√n。例如24可以表示為：2*12、3*8、4*6，前面的因子小于√24，后面的因子大于√24，檢驗出了小因子，即可判斷n是否為素數(shù)，就像邏輯運算的短路求值。

3 程序的模塊化

分治法在程序思想中的應(yīng)用就是實現(xiàn)程序的模塊化，包括面向過程的函數(shù)化和面向?qū)ο蟮膶ο蠡?br>

許多原因都促使我們將應(yīng)用程序分解成函數(shù)，下面僅列舉其中三個：

函數(shù)一般小而具體。用一系列函數(shù)來寫程序，勝于一氣呵成寫完整個程序。這稱為“分而治之”，使你的精力一次集中在一個函數(shù)上。

包含許多小函數(shù)的應(yīng)用程序比單一的長程序更容易閱讀和調(diào)試。

函數(shù)可以重用。函數(shù)寫好后可在程序的其他任何地方調(diào)用。這減少了編碼量，提高了開發(fā)效率。

4 函數(shù)調(diào)用與棧

首先討論一個從a點出發(fā)去f點，然后回到a點的問題（中間的b、c、d、e都有多個分岔口）：

a→b2→c1→d3→e2→f，每個分岔口都有一個信封，告訴你應(yīng)該走哪一個分支，為了能夠正確地回到起點a，正確的做法是拿到一個信封后，即將這個信封疊在上一次拿到的信封的上面，回去時，依次從上面拿取信封，按提示即可正確返回。

其做法就是依次放入，依次取出，信封之間是順序關(guān)系，只在一端操作，也就是不管是放入還是取出都不在中間操作。這樣一種思路在計算機(jī)上用數(shù)據(jù)來描述就是后進(jìn)先出的棧，函數(shù)的調(diào)用、返回，遞歸、回溯算法都需要使用棧這種數(shù)據(jù)結(jié)構(gòu)（由程序員或遞歸時由編譯器來實現(xiàn)）。

在C++中，函數(shù)不能嵌套定義，但可以嵌套調(diào)用，在函數(shù)調(diào)用時，編譯器需要確保在逐級調(diào)用后能夠回歸到最初的調(diào)用點，編譯器會隱式實現(xiàn)一個堆棧，用來保存每一級函數(shù)調(diào)用時的函數(shù)返回地址和局部變量，依次入棧和出棧。

C++也支持遞歸函數(shù)的遞歸調(diào)用，同樣是由編譯器隱式地實現(xiàn)了一個堆棧。

5 深度搜索與廣度搜索

如果將上述的問題稍微擴(kuò)展一點，要從源點到目標(biāo)點，中間的節(jié)點可能有多個分叉，這樣的問題可以用一個樹或圖來描述。

而探路的方法可以分為兩種，一種是深度優(yōu)先搜索（下一點、下一點……回溯……），一種是廣度優(yōu)先搜索（下一點的全部分叉、下一點的全部分叉……）：

5.1 深度優(yōu)先搜索用棧（stack）來實現(xiàn)，整個過程可以想象成一個倒立的樹形：

1）把根節(jié)點壓入棧中。

2）每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。并把這個元素記為它下一級元素的前驅(qū)。

3）找到所要找的元素時結(jié)束程序。

4）如果遍歷整個樹還沒有找到，結(jié)束程序。

5.2 廣度優(yōu)先搜索使用隊列（queue）來實現(xiàn)，整個過程也可以看做一個倒立的樹形：

1）把根節(jié)點放到隊列的末尾。

2）每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。并把這個元素記為它下一級元素的前驅(qū)。（取出的元素也可以保存到一個隊列）

3）找到所要找的元素時結(jié)束程序。

4）如果遍歷整個樹還沒有找到，結(jié)束程序。

廣度優(yōu)先搜索相對于深度優(yōu)先搜索，因為是逐層探索的，可以確保以較少的點到達(dá)目標(biāo)點，缺點是存儲量較大。

6 遞歸算法

遞歸就是某個函數(shù)直接或間接的調(diào)用自身。

語法形式上: 在一個函數(shù)的運行過程中, 調(diào)用這個函數(shù)自己：

直接調(diào)用: 在fun()中直接執(zhí)行fun()；

間接調(diào)用: 在fun1()中執(zhí)行fun2(); 在fun2()中又執(zhí)行fun1() ；

問題的求解過程是劃分成許多相同性質(zhì)的子問題的求解，而小問題的求解過程可以很容易的求出。這些子問題的解就構(gòu)成里原問題的解。

待求解問題的解可以描述為輸入變量x的函數(shù)f(x)。

通過尋找函數(shù)g( )，使得f(x) = g(f(x-1))。

且已知f(0)的值, 就可以通過f(0)和g( )求出f(x)的值。

擴(kuò)展到多個輸入變量x, y, z等, x-1也可以推廣到 x - x1 , 只要遞歸朝著 “出口” 的方向即可。

遞歸算法分解出的子問題與原問題之間是縱向的, 同類的關(guān)系（枚舉分解出的子問題之間是橫向的, 同類的關(guān)系）。

遞歸的三個要點:

遞歸式：如何將原問題劃分成子問題；

遞歸出口：遞歸終止的條件, 即最小子問題的求解,可以允許多個出口；

界函數(shù)：問題規(guī)模變化的函數(shù), 它保證遞歸的規(guī)模向出口條件靠攏。

如一個求階乘的遞歸程序，給定n, 求階乘n!

階乘的棧：

二分搜索的遞歸實現(xiàn)：

int binarySearchRecursion(int arr[], int findData, int start, int end){  if(arr==NULL || start>end)    return -1;    int mid = start+(end-start)/2;    if(arr[mid] == findData)      return mid;    else if(findData < arr[mid])      binarySearchRecursion(arr, findData, start, mid-1);    else      binarySearchRecursion(arr, findData, mid+1, end);

7 歸并排序

歸并排序（merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是分治法（Divide and Conquer）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并（2-way or binary merges sort）。

歸并排序在1945年由馮·諾伊曼首次提出。

2-路歸并的基本思路就是將數(shù)組分成二組A，B，如果這二組組內(nèi)的數(shù)據(jù)都是有序的，那么就可以很方便的將這二組數(shù)據(jù)進(jìn)行排序。如何讓這二組組內(nèi)數(shù)據(jù)有序？

可以將A，B組各自再分成二組。依次類推，當(dāng)分出來的小組只有一個數(shù)據(jù)時，可以認(rèn)為這個小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的二個小組就可以了。這樣通過先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。

歸并排序的效率是比較高的，設(shè)數(shù)列長為N，將數(shù)列分開成小數(shù)列一共要logN步，每步都是一個合并有序數(shù)列的過程，時間復(fù)雜度可以記為O(N)，故一共為O(N*logN)。因為歸并排序每次都是在相鄰的數(shù)據(jù)中進(jìn)行操作，所以歸并排序在O(N*logN)的幾種排序方法（快速排序，歸并排序，希爾排序，堆排序）也是效率比較高的。

歸并排序的實現(xiàn)分為遞歸實現(xiàn)與非遞歸(迭代)實現(xiàn)。遞歸實現(xiàn)的歸并排序是算法設(shè)計中分治策略的典型應(yīng)用，我們將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題。非遞歸(迭代)實現(xiàn)的歸并排序首先進(jìn)行是兩兩歸并，然后四四歸并，然后是八八歸并，一直下去直到歸并了整個數(shù)組。

7.1 歸并排序分解

可以看到這種結(jié)構(gòu)很像一棵完全二叉樹，分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為log2n。

7.2 歸并排序合并相鄰有序子序列

再來看看并階段，我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經(jīng)有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現(xiàn)步驟。

• 申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列；

• 設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置；

• 比較兩個指針?biāo)赶虻脑?，選擇相對小的元素放入到合并空間，并移動指針到下一位置；temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];

• 重復(fù)步驟3直到某一指針到達(dá)序列尾；

• 將另一序列剩下的所有元素直接復(fù)制到合并序列尾；

7.3 歸并排序動圖演示

7.4 歸并排序代碼

8 回溯法和分書問題

回溯算法實際上是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件時，就“回溯“返回，嘗試別的路徑。可以參考一下走迷宮的過程，一開始會隨機(jī)選擇一條道路前進(jìn)，一直到走不通之后就會回頭直到找到另外一條沒有試過的道路前進(jìn)。實際上，走迷宮的算法就是回溯法的經(jīng)典問題。

回溯法實際上也是一種試錯的思路，通過不斷嘗試解的組合來達(dá)到求解可行解和最優(yōu)解的目的。雖然都有窮搜的概念蘊含其中，但是回溯法和窮舉查找法是不同的。對于一個問題的所有實例，窮舉法注定都是非常緩慢的，但應(yīng)用回溯法至少可以期望對于一些規(guī)模不是很小的實例，計算機(jī)在可接受的時間內(nèi)對問題求解。

許多復(fù)雜的規(guī)模的問題都可以使用回溯法，有”通用解題方法”的美稱。分書問題和八皇后都是典型的回溯法問題。

分書問題能夠較有代表性地表現(xiàn)數(shù)據(jù)描述、遞歸、回溯的算法思路。

有編號為0，1，2，3，4的5本書，準(zhǔn)備分給5個人A，B，C，D，E，寫一個程序，輸出所有皆大歡喜的分書方案。

每個人的閱讀興趣用一個二維數(shù)組like描述：

Like[i][j] = true i喜歡書j

Like[i][j] = false i不喜歡書j

設(shè)計一個函數(shù)trynext(int i)給第i個人分書。

用一個一維數(shù)組take表示某本書分給了某人。take[j]=i+1;//把第j本書分配給第i個人

依次嘗試把書j分給人i。

如果第i個人不喜歡第j本書，則嘗試下一本書，如果喜歡，并且第j本書尚未分配，則把書j分配給i。

如果i是最后一個人，則方案數(shù)加1，輸出該方案。否則調(diào)用trynext(i+1)為第i+1個人分書。

如果對第i個人枚舉了他喜歡的所有的書，都沒有找到可行的方案，那就回到前一個狀態(tài)i-1，讓i-1把分到的書退回去，重新找喜歡的書，再遞歸調(diào)用函數(shù)，尋找可行的方案。

#include <iostream>#include <conio.h>using namespace std;int like[5][5]={{0,0,1,1,0},{1,1,0,0,1},{0,1,1,0,1},{0,0,0,1,0},{0,1,0,0,1}};int take[5]={0,0,0,0,0};//記錄每一本書的分配情況int n;//n表示分書方案數(shù)void trynext(int i);int main(){n=0;trynext(0);getch();return 0;}//對第 i 個人進(jìn)行分配void trynext(int i){int j,k;for(j=0;j<5;j++){if(like[i][j]&&take[j]==0){take[j]=i+1;//把第j本書分配給第i個人if(i==4)//第5個人分配結(jié)束，也即所有的書已經(jīng)分配完畢，可以將方案進(jìn)行輸出{n++;cout<<'第'<<n<<'種分配方案'<<endl;for(k=0;k<5;k++)cout<<'第'<<k<<'本書分配給'<<(char)(take[k]+'A'-1)<<endl;cout<<endl;}elsetrynext(i+1);//遞歸，對下一個人進(jìn)行分配take[j]=0;//回溯，尋找下一種方案}}}

當(dāng)like矩陣的值為

附歸并排序的代碼：

－END－