編程的關鍵在于選擇數據結構和算法，數據結構用于描述問題，算法用于描述解決問題的方法和步驟。

描述問題的數據除了各數據元素本身，還要考慮各元素的邏輯關系，主要是一對一的線性關系，一對多的樹型關系和多對多的圖形關系。另外，內存中對各數據元素的存儲只有順序存儲和鏈式存儲兩種方式，所以數據結構還要考慮數據的存儲結構，并考慮邏輯結構與數據結構如何有效地結合到一起。

用算法描述問題，當問題比較復雜時，通常的思路是分而治之，并輔以適當的數據結構。

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 枚舉法也是一種暴力縮小問題規模的算法

簡單的枚舉算法也是可以優化的，即盡可能縮小搜索的空間，如判斷質數：

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

判斷質數的函數：

int isPrime(int n)
{
	if(n<= 1)// 小于等于1的整數不可能是素數
		return 0;
	if(n == 2); // 2 是素數
		return 1;
	if(n%2 == 0); // 能被2整除的其他整數都不是素數
		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 只要發現任何一個大于1小于n的因子，就能停下來報告n不是素數。

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

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

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

3 程序的模塊化

分治法在程序思想中的應用就是實現程序的模塊化，包括面向過程的函數化和面向對象的對象化。

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

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

包含許多小函數的應用程序比單一的長程序更容易閱讀和調試。

函數可以重用。函數寫好后可在程序的其他任何地方調用。這減少了編碼量，提高了開發效率。

4 函數調用與棧

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

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

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

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

C++也支持遞歸函數的遞歸調用，同樣是由編譯器隱式地實現了一個堆棧。

5 深度搜索與廣度搜索

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

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

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

1）把根節點壓入棧中。

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

3）找到所要找的元素時結束程序。

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

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

1）把根節點放到隊列的末尾。

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

3）找到所要找的元素時結束程序。

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

廣度優先搜索相對于深度優先搜索，因為是逐層探索的，可以確保以較少的點到達目標點，缺點是存儲量較大。

6 遞歸算法

遞歸就是某個函數直接或間接的調用自身。

語法形式上: 在一個函數的運行過程中, 調用這個函數自己：

直接調用: 在fun()中直接執行fun()；

間接調用: 在fun1()中執行fun2(); 在fun2()中又執行fun1() ；

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

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

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

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

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

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

遞歸的三個要點:

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

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

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

如一個求階乘的遞歸程序，給定n, 求階乘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）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并（2-way or binary merges sort）。

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

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

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

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

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

7.1 歸并排序分解

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

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

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

• 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列；
• 設定兩個指針，最初位置分別為兩個已經排序序列的起始位置；
• 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置；temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];
• 重復步驟3直到某一指針到達序列尾；
• 將另一序列剩下的所有元素直接復制到合并序列尾；

7.3 歸并排序動圖演示

7.4 歸并排序代碼

8 回溯法和分書問題

回溯算法實際上是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就“回溯“返回，嘗試別的路徑?？梢詤⒖家幌伦呙詫m的過程，一開始會隨機選擇一條道路前進，一直到走不通之后就會回頭直到找到另外一條沒有試過的道路前進。實際上，走迷宮的算法就是回溯法的經典問題。

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

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

分書問題能夠較有代表性地表現數據描述、遞歸、回溯的算法思路。

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

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

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

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

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

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

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

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

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

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

#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表示分書方案數

void trynext(int i);

int main()

{

n=0;

trynext(0);

getch();

return 0;

}

//對第 i 個人進行分配

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個人分配結束，也即所有的書已經分配完畢，可以將方案進行輸出

{

n++;

cout<<"第"<<n<<"種分配方案"<<endl;

for(k=0;k<5;k++)

cout<<"第"<<k<<"本書分配給"<<(char)(take[k]+'A'-1)<<endl;

cout<<endl;

}

else

trynext(i+1);//遞歸，對下一個人進行分配

take[j]=0;//回溯，尋找下一種方案

}

}

}

當like矩陣的值為

附歸并排序的代碼：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 分類 -------------- 內部比較排序
// 數據結構 ---------- 數組
// 最差時間復雜度 ---- O(nlogn)
// 最優時間復雜度 ---- O(nlogn)
// 平均時間復雜度 ---- O(nlogn)
// 所需輔助空間 ------ O(n)
// 穩定性 ------------ 穩定
// 合并兩個已排好序的數組A[left...mid]和A[mid+1...right]
void Merge(int A[], int left, int mid, int right)
{
	int len = right - left + 1;
	int *temp = new int[len]; // 輔助空間O(n)
	int index = 0;
	int i = left; // 前一數組的起始元素
	int j = mid + 1; // 后一數組的起始元素
	while (i <= mid && j <= right)
	{
		temp[index++] = A[i] <= A[j] ? A[i++] : A[j++]; // 帶等號保證歸并排序的穩定性
	}
	while (i <= mid)
	{
		temp[index++] = A[i++];
	}
	while (j <= right)
	{
		temp[index++] = A[j++];
	}
	for (int k = 0; k < len; k++)
	{
		A[left++] = temp[k];
	}
}
// 遞歸實現的歸并排序(自頂向下)
void MergeSortRecursion(int A[], int left, int right) 
{
	if (left == right) // 當待排序的序列長度為1時，遞歸開始回溯，進行merge操作
		return;
	int mid = (left + right) / 2;
	MergeSortRecursion(A, left, mid); //左半部分排好序
	MergeSortRecursion(A, mid + 1, right); //右半部分排好序
	Merge(A, left, mid, right); //合并左右部分
}
// 非遞歸(迭代)實現的歸并排序(自底向上)
void MergeSortIteration(int A[], int len) 
{
	int left, mid, right;// 子數組索引,前一個為A[left...mid]，后一個子數組為A[mid+1...right]
	for (int i = 1; i < len; i *= 2) // 子數組的大小i初始為1，每輪翻倍
	{
		left = 0;
		while (left + i < len) // 后一個子數組存在(需要歸并)
		{
			mid = left + i - 1;
			right = mid + i < len ? mid + i : len - 1;// 后一個子數組大小可能不夠
			Merge(A, left, mid, right);
			left = right + 1; // 前一個子數組索引向后移動
		}
	}
}
int main()
{
	int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 從小到大歸并排序
	int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 };
	int n1 = sizeof(A1) / sizeof(int);
	int n2 = sizeof(A2) / sizeof(int);
	MergeSortRecursion(A1, 0, n1 - 1); // 遞歸實現
	MergeSortIteration(A2, n2); // 非遞歸實現
	printf("遞歸實現的歸并排序結果：");
	for (int i = 0; i < n1; i++)
	{
		printf("%d ", A1[i]);
	}
	printf("
		");
		printf("非遞歸實現的歸并排序結果：");
	for (i = 0; i < n2; i++)
	{
		printf("%d ", A2[i]);
	}
	printf("
		");
		system("pause");
	return 0;
}

－End－