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

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

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

1 分治法Divide and Conquer

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

Divide the problem into more subproblems（分解問(wèn)題為眾多的子問(wèn)題）;

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

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

如用分治法來(lái)計(jì)算2^10?

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

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

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 枚舉法也是一種暴力縮小問(wèn)題規(guī)模的算法

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

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

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

int isPrime(int n){  if(n<= 1)// 小于等于1的整數(shù)不可能是素?cái)?shù)    return 0;  if(n == 2); // 2 是素?cái)?shù)    return 1;  if(n%2 == 0); // 能被2整除的其他整數(shù)都不是素?cái)?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()沒(méi)有必要枚舉所有的因子。

I 只要發(fā)現(xiàn)任何一個(gè)大于1小于n的因子，就能停下來(lái)報(bào)告n不是素?cái)?shù)。

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

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

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

3 程序的模塊化

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

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

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

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

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

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

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

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

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

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

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

5 深度搜索與廣度搜索

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

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

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

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

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

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

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

5.2 廣度優(yōu)先搜索使用隊(duì)列（queue）來(lái)實(shí)現(xiàn)，整個(gè)過(guò)程也可以看做一個(gè)倒立的樹(shù)形：

1）把根節(jié)點(diǎn)放到隊(duì)列的末尾。

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

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

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

廣度優(yōu)先搜索相對(duì)于深度優(yōu)先搜索，因?yàn)槭侵饘犹剿鞯模梢源_保以較少的點(diǎn)到達(dá)目標(biāo)點(diǎn)，缺點(diǎn)是存儲(chǔ)量較大。

6 遞歸算法

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

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

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

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

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

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

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

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

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

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

遞歸的三個(gè)要點(diǎn):

遞歸式：如何將原問(wèn)題劃分成子問(wèn)題；

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

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

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

階乘的棧：

二分搜索的遞歸實(shí)現(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）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為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)分出來(lái)的小組只有一個(gè)數(shù)據(jù)時(shí)，可以認(rèn)為這個(gè)小組組內(nèi)已經(jīng)達(dá)到了有序，然后再合并相鄰的二個(gè)小組就可以了。這樣通過(guò)先遞歸的分解數(shù)列，再合并數(shù)列就完成了歸并排序。

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

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

7.1 歸并排序分解

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

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

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

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

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

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

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

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

7.3 歸并排序動(dòng)圖演示

7.4 歸并排序代碼

8 回溯法和分書(shū)問(wèn)題

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

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

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

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

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

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

Like[i][j] = true i喜歡書(shū)j

Like[i][j] = false i不喜歡書(shū)j

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

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

依次嘗試把書(shū)j分給人i。

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

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

如果對(duì)第i個(gè)人枚舉了他喜歡的所有的書(shū)，都沒(méi)有找到可行的方案，那就回到前一個(gè)狀態(tài)i-1，讓i-1把分到的書(shū)退回去，重新找喜歡的書(shū)，再遞歸調(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};//記錄每一本書(shū)的分配情況int n;//n表示分書(shū)方案數(shù)void trynext(int i);int main(){n=0;trynext(0);getch();return 0;}//對(duì)第 i 個(gè)人進(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本書(shū)分配給第i個(gè)人if(i==4)//第5個(gè)人分配結(jié)束，也即所有的書(shū)已經(jīng)分配完畢，可以將方案進(jìn)行輸出{n++;cout<<'第'<<n<<'種分配方案'<<endl;for(k=0;k<5;k++)cout<<'第'<<k<<'本書(shū)分配給'<<(char)(take[k]+'A'-1)<<endl;cout<<endl;}elsetrynext(i+1);//遞歸，對(duì)下一個(gè)人進(jìn)行分配take[j]=0;//回溯，尋找下一種方案}}}

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

附歸并排序的代碼：

－END－