算法分析與設計實驗(一)之分治算法

實驗目的

（1）基本掌握分治算法的原理。

（2）掌握遞歸算法及遞歸程式的設計。

（3）能用程式設計語言求解相關問題。

實驗要求

（1）用分治法求解問題；

（2）分析算法的時間性能，設計實驗程式驗證分析結論。

預習要求

（1）了解用分治法求解的問題：當要求解一個輸入規模為n，且n的取值相當大的問題時，如果問題可以分成k個不同子集合，得到k個不同的可獨立求解的子問題，其中1<k≤n，而且子問題與原問題性質相同，原問題的解可由這些子問題的解合并得出。那末，對于這類問題分治法是十分有效的。

（2）掌握分治法的一般控制流程。

DanC(p,q)

global n，A[1:n]; integer m,p,q; // 1pqn

if Small(p,q) then return G(p,q);

else m=Divide(p,q); // pm<q

return Combine(DanC(p,m),DanC(m+1,q));

endif

end DanC

（3）實作典型的分治算法的程式設計與上機實驗，驗證算法的時間複雜性函數。

實驗内容

（1）仔細閱讀備選實驗的題目，選擇一個（可選多個）作為此次實驗題目，設計的程式要滿足正确性，代碼中有關鍵的注釋，書寫格式清晰，簡潔易懂，效率較高，設計的程式通用性好，适合各種合理輸入，并能對不合理輸入做出正确的提示。

（2）采用分治法完成如下任務：

i.中位數問題

問題描述

設X[ 0 : n - 1]和Y[ 0 : n – 1 ]為兩個數組，每個數組中含有n個已排好序的數。找出X和Y的2n個數的中位數。

程式設計任務

利用分治政策試設計一個O (log n)時間的算法求出這2n個數的中位數。

資料輸入

由檔案input.txt提供輸入資料。檔案的第1行中有1個正整數n（n<=200），表示每個數組有n個數。接下來的兩行分别是X，Y數組的元素。

結果輸出

程式運作結束時，将計算出的中位數輸出到檔案output.txt中。

輸入檔案示例 輸出檔案示例

input.txt

3
5 15 18
3 14 21	
           

output.txt

14
           

實作提示

比較兩個序列的中位數大小，如果兩個數相等，則該數為整個2n個資料的中位數，否則通過比較，分别減少兩個序列的查找範圍，确定查找的起止位置，繼續查找。

做法1：（自己的做法，通過找中間的數，将兩者進行比較來确定中位數的位置并遞歸）

#include<iostream>
using namespace std;
int n;
int search(int a[],int b[],int s,int t){
	//cout<<a[s]<<b[t]<<endl;
	if(a[s]>b[t]&&(a[s]<b[t+1]||b[t+1]==0)) return b[t];
	else if(a[s]<b[t]&&(b[t]<a[s+1]||a[s+1]==0)) return a[s];
	else if(a[s]>b[t]) return search(a,b,(s+1)/2,(t+n)/2);
	else if(a[s]<b[t]) return search(a,b,(s+n)/2,(t+1)/2);
	else return a[s];
}
int main(){
	freopen("input.txt","r",stdin); 
	int a[205]={0},b[205]={0};
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	for(int i=0;i<n;i++) cin>>b[i];
	fclose(stdin);
	freopen("output.txt","w",stdout); 
	cout<<search(a,b,n/2,n/2)<<endl;
	fclose(stdout);
	return 0;
} 
           

做法2： CSDN大佬的做法

原址連結： 在兩個有序數組中找到中位數

PS：中位數在總數為偶數的情況下難道不是取最中間的兩個的平均值麼？！

ii. Gray碼問題

問題描述

Gray碼是一個長度為2n的序列。序列中無相同的元素，每個元素都是長度為n位的串，相鄰元素恰好隻有一位不同。用分治政策設計一個算法對任意的n構造相應的Gray碼。

程式設計任務

利用分治政策試設計一個算法對任意的n構造相應的Gray碼。

資料輸入

由檔案input.txt提供輸入資料n。

結果輸出

程式運作結束時，将得到的所有編碼輸出到檔案output.txt中。

輸入檔案示例 輸出檔案示例

input.txt

3
           

output.txt

0   0   0
0   0   1
0   1   1
0   1   0
1   1   0
1   1   1
1   0   1
1   0   0
           

實作提示

把原問題分解為兩個子問題，分别對兩個子問題的每個數組後一位加0和1。

這一題自己能做出來，也多半借鑒了CSDN大佬的做法，大佬源碼裡注視很詳細，在此附上傳送門

原址連結： 構造Gray碼的分治算法

唯一一點需要注意的是，大佬最後輸出的時候是順序輸出，是以得到的結果和樣例不一樣，如果要得到和樣例一樣的結果，需要采用如下代碼将每一個gray碼逆序輸出。

for(int i=0;i<(int)pow(2,n);i++){//構造n位格雷碼，a[i][j]表示第i個格雷碼的第j位
		for(int j=n-1;j>=0;j--){
			cout<<a[i][j];
		}
		cout<<endl;
	}