算法之分治算法

1       分治思想

 （Divide-and-Conquer）

分治算法的基本思想是将一個規模為N的問題分解為K個規模較小的子問題，這些子問題互相獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。

2       分治法解題的一般步驟

（1）分解（ Divide  ）：，将要解決的問題劃分成若幹規模較小的同類問題；

（2）求解（ Conquer）：，當子問題劃分得足夠小時，用較簡單的方法解決；

（3）合并（Combine）：，按原問題的要求，将子問題的解逐層合并構成原問題的解。

 通用架構：用遞歸的方式劃分到一定程度

   分解 → 直接或遞歸求解子問題 → 組合

在遞歸求解子問題時同樣要注意理清遞歸關系、遞歸出口、參數設定等問題。

divide_and_conquer(data)

{
            if(data資料量較小）直接處理data得到結果，或者有個結束的判斷，因為這個是在遞歸；
            else
            {
                       A.将data分為多個部分data1,data2,.....datan
                       并分别遞歸調用divide_and_conquer處理各個部分!
                       B.合并data1,data2,....datan處理之後的結果！
             }
}
           

3       執行個體1---歸并排序

思想：分而治之

每個遞歸過程涉及三個步驟：

1、 分解：把待排序的n個元素的序列分解成兩個子序列，每個子序列包括n/2個元素。

2、 治理：把每個子序列分别調用歸并排序MergeSort，進行遞歸操作。

3、 合并：合并兩個排好序的子序列，生成排序結果

歸并排序的工作原理：

1、 申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并後的序列。

2、 設定兩個指針，最初位置分别為兩個已經排序序列的起始位置

3、 比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一個位置

4、 重複步驟3直到某一指針達到序列尾

5、 将另一序列剩下的所有元素直接複制到合并序列尾

代碼：

//我認為此題的關鍵時了解了temparray 這個數組，它是臨時的存放每一次的排序結果
           

//分治還有個明顯的特點是left和right的下标，也就是說有一個分的标志
void Merge(int* array, int* tempararay, int left, int middle, int right)
{
	//左指針尾
	int leftend = middle-1;
	//右指針頭
	int rightstart = middle;
	int tempIndex = left;
	//數組合并後的length長度
	int tempLength = right - left + 1;
	//相當于排序，把臨時的結果放入到tempararay中
	while( (left <= leftend) && (rightstart <= right) )
	{
		if(array[left]<array[rightstart])
		{
			tempararay[tempIndex++] = array[left++];
		}
		else
		{
			tempararay[tempIndex++] = array[rightstart++];
		}
	}	
	//判斷左序列是否結束
	while(left <= leftend)
		tempararay[tempIndex++] = array[left++];

	while(rightstart <= right)
		tempararay[tempIndex++] = array[rightstart++];
	
	//交換臨時排序的資料
	for(int i=0; i<tempLength; i++)
	{
		array[right] = tempararay[right];
		cout<<array[right]<<" ";
		right--;
	}
	if(tempLength)
		cout<<endl;
}
void MergeSort(int* array, int* temparray, int left, int right)
{
	if(left < right)
	{
		//1、分解劃分成前後兩部分
		int middle = (left+right)/2;
		//2、對分解治理
		MergeSort(array, temparray, left, middle);
		//2、對分解治理
		MergeSort(array, temparray, middle+1, right);
		//3、合并
		Merge(array, temparray, left, middle+1, right);
	}
}
int main()
{
	int a[] = {13,7,8,3,60,50,4};
	int len = sizeof(a)/sizeof(int);
	//需要申請一塊臨時的記憶體儲存排序結果
	int* b = new int[len]; 
	MergeSort(a,b,0,len-1);
	for(int i=0; i<len; i++)
	{
		cout<<a[i]<<",";
	}
}
           

4       快速排序

 分而治之

//一趟排序，每一次一趟之後，前半部分是小的，後半部分是大的
int Partition(int *array, int low, int high)
{
	//*array = *(array+low);
	int pivotKey = *(array+low);

	while(low<high)
	{
		while(low<high && *(array+high)>pivotKey)
			--high;
		*(array+low) = *(array+high);
		while(low<high && *(array+low)<pivotKey)
			++low;
		*(array+high) = *(array+low);
	}
	*(array+low) = pivotKey;

	return low;
}
//再寫分治法的代碼：
void QSort(int *array, int low, int high)
{
	if(low<high)
	{
		//1. 分解
		int middle = Partition(array, low, high);
		//2. 遞歸求解
		QSort(array, low , middle-1);
		QSort(array, middle+1, high);
		//3. 合并：由于分解出的兩個字序列是就地進行的，是以不需要再次合并
	}
}
void BinarySort(int *array, int length, int data)
{
	QSort(array,0,length-1);
}
           

5       循環賽日程

n個選手的比賽日程可以通過n/2個選手的比賽日程來确定，遞歸調用，直到剩下兩個選手的時候，比賽日程就可以很容易的确定

先計算出一部分，然後另一部分指派

/// <param name="index">起始選手編号</param> 
/// <param name="num">選手的人數(因為是分治，是以每次砍半)</param>
void GameCal(int index, int num)
{
	if( num == 2)
	{
		GameList[index-1,0] = index;
		GameList[index-1,1] = index+1;
		GameList[index,0] = index+1;
		GameList[index,1] = index;
	}
	else
	{
		//分而遞歸
		GameCal(index, num/2);
		GameCal(index + num/2, num/2);
		//合并
		//将“左下角”填充到“右上角”

		//控制橫坐标
		for(int i=index; i<index+num/2; i++)
		{
			//控制縱坐标
			for(int j=num/2; j<num; j++)
			{
				GameList[i-1][j] = GameList[(i-1) + num/2][j - num/2];
			}
		}

		//用于将“左上角”填充到“右下角”
		//控制橫
		for(int i=index+num/2; i<index+num; i++)
		{
			//控制縱坐标
			for(int j=num/2; j<num; j++)
			{
				//對角指派                        
				GameList[i - 1][j] = GameList[(i - 1) - num / 2][j - num / 2];
			}
		}
	}
}
           

6        二分搜尋法

int BinarySearch(int a[], int &x, int left, int right)
{
	while(left < right)
	{
		int middle = (left + right)/2;
		if(a[middle] == x) return middle;
		if(a[middle] < x) right = middle - 1;
		else left = middle + 1;
	}
}
           

7   最近點對問題

1）蠻力法：

計算每兩個之間的距離，然後比較，也就是計算(n-1)與n個元素之間的比較

2）分治法：

     a.  找中線把n個元素分成左右兩部分分别求得兩邊的最短距離，然後取兩者中的最小者，計為len

     b.  在中線兩邊分别取len的距離。記錄該距離範圍内點的個數，中線左邊有L個元素，右邊有R個元素。

     c.  求左邊元素到右邊元素的距離看其是否小于之前記錄的len，小則記錄下來。

     d.  此時的右邊元素隻取y值和左邊元素y值距離小于1的（減少循環次數）。

     e.  循環結束即可找到最小的距離

8   Strassen矩陣乘法

9 大整數乘法