計算機算法設計及分析習題和答案解析-資料下載頁
2025-06-23 17:33本頁面
【正文】 復雜性為O(logn)2. 利用分治算法寫出合并排序的算法，并分析其時間復雜度 void MergeSort(Type a[], int left, int right) { if (leftright) {//至少有2個元素 int i=(left+right)/2。 //取中點 mergeSort(a, left, i)。 mergeSort(a, i+1, right)。 merge(a, b, left, i, right)。 //合并到數組b copy(a, b, left, right)。 //復制回數組a } }算法在最壞情況下的時間復雜度為O(nlogn)。bool Queen::Place(int k){ //檢查x[k]位置是否合法 for (int j=1。jk。j++) if ((abs(kj)==abs(x[j]x[k]))||(x[j]==x[k])) return false。 return true。} void Queen::Backtrack(int t){ if (tn) sum++。 else for (int i=1。i=n。i++) {x[t]=i。 if ( 約束函數 ) Backtrack(t+1)。 }}void Clique::Backtrack(int i) // 計算最大團{ if (i n) { // 到達葉結點 for (int j = 1。 j = n。 j++) bestx[j] = x[j]。 bestn = 。 return。} // 檢查頂點 i 與當前團的連接 int OK = 1。 for (int j = 1。 j i。 j++) if (x[j] amp。amp。 a[i][j] == 0) // i與j不相連 {OK = 0。 break。} if (OK ) { // 進入左子樹 x[i] = 1。 ++。 Backtrack(i+1)。 x[i] = 0。 。 } if (+nibestn) { // 進入右子樹 x[i] = 0。 Backtrack(i+1)。 }}5. 順序表存儲表示如下：typedef struct{RedType r[MAXSIZE+1]。 //順序表 int length。 //順序表長度}SqList。編寫對順序表L進行快速排序的算法。int Partition(SqList amp。L,int low,int high) //(b) {//[low..high]的記錄,樞軸記錄到位,并返回其所在位置, //此時在它之前(后)的記錄均不大(小)于它. int pivotkey。 [0]=[low]。 //用子表的第一個記錄作樞軸記錄 pivotkey=[low].key。 //樞軸記錄關鍵字 while (lowhigh) //從表的兩端交替地向中間掃描 {while (lowhighamp。amp。[high].key=pivotkey) high。 [low]=[high]。 //將比樞軸記錄小的記錄移到低端 while (lowhighamp。amp。[low].key=pivotkey) ++low。 [high]=[low]。 //將比樞軸記錄大的記錄移到高端 } [low]=[0]。 //樞軸記錄到位 return low。 //返回樞軸位置}void QSort(SqList amp。L,int low,int high){//[low..high]作快速排序 int pivotloc。 if (lowhigh) //長度1 {pivotloc=Partition(L,low,high)。 //[low..high]一分為二 QSort(L,low,pivotloc1)。 //對低子表遞歸排序,pivotloc是樞軸位置 QSort(L,pivotloc+1,high)。 //對高子表遞歸排序 }}void QuickSort(SqList amp。L){//對順序表L作快速排序 QSort(L,1,)。 } 整理分享
語文相關推薦
鄂ICP備17016276號-1