最新計算機算法設(shè)計與分析習(xí)題及答案-wenkub.com
2025-06-23 15:15 本頁面
【正文】 //對高子表遞歸排序 }}void QuickSort(SqList amp。L,int low,int high){//[low..high]作快速排序 int pivotloc。 [high]=[low]。 [low]=[high]。 //用子表的第一個記錄作樞軸記錄 pivotkey=[low].key。編寫對順序表L進行快速排序的算法。 Backtrack(i+1)。 Backtrack(i+1)。 a[i][j] == 0) // i與j不相連 {OK = 0。 for (int j = 1。 j++) bestx[j] = x[j]。i++) {x[t]=i。 return true。 //復(fù)制回數(shù)組a } }算法在最壞情況下的時間復(fù)雜度為O(nlogn)。 //取中點 mergeSort(a, left, i)。 if (xa[middle]) left=middle+1。 x, int n){//在a[0:n]中搜索x，找到x時返回其在數(shù)組中的位置，否則返回1 Int left=0。39。(maze[x1][y]==39。O39。)) MazePath(++x,y)。 //東鄰方格是通路,向東嘗試 if ((!success)amp。(y==y1)) success=1。 //出口點void MazePath(int x,int y){//遞歸求解:求迷宮maze從入口(x,y)到出口(x1,y1)的一條路徑 maze[x][y]=39。H39。}templateclass Typevoid QuickSort (Type a[], int p, int r){ if (pr) {int q=Partition(a,p,r)。i=n。 ； //一旦某個區(qū)段和為負(fù)，則從下一個位置累和 if(bsum) sum=b。 x[i]=1。 float c=M。 Sort(n,v,w)。，該問題的解空間結(jié)構(gòu)為 子集樹 結(jié)構(gòu)。 劃分的對稱性 。 隊列式（FIFO） 分支限界法和 優(yōu)先隊列式 分支限界法。1 貪心選擇性質(zhì) 是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。15. 動態(tài)規(guī)劃算法的基本思想是將待求解問題分解成若干 子問題 ，先求解 子問題 ，然后從這些 子問題 的解得到原問題的解。1使用回溯法進行狀態(tài)空間樹裁剪分支時一般有兩個標(biāo)準(zhǔn)：約束條件和目標(biāo)函數(shù)的界，N皇后問題和0/1背包問題正好是兩種不同的類型，其中同時使用約束條件和目標(biāo)函數(shù)的界進行裁剪的是 0/1背包問題 ，只使用約束條件進行裁剪的是 N皇后問題 。問題的 最優(yōu)子結(jié)構(gòu)性質(zhì) 是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。算法的“確定性”指的是組成算法的每條 指令 是清晰的，無歧義的。 if (legal(t)) backtrack(t+1)。 }}void backtrack (int t){ if (tn) output(x)。 else for (int i=0。i=1。 if (legal(t)) backtrack(t+1)。void backtrack (int t){ if (tn) output(x)。 hanoi(n1, C, B, A)。 move(n,a,b)。由此設(shè)計出解Hanoi塔問題的遞歸算法正確的為：（B）Hanoi塔B. void hanoi(int n, int A, int B, int C) { if (n 0) { hanoi(n1, A, C, B)。 hanoi(n1, C, B, A)。BA、重疊子問題 B、最優(yōu)子結(jié)構(gòu)性質(zhì) C、貪心選擇性質(zhì) D、定義最優(yōu)解42．采用貪心算法的最優(yōu)裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故算法的時間復(fù)雜度為 ( B ) 。 C、貪心法A、分支界限法A、O（n2n） B、O（nlogn） C、O（2n） D、O（n）廣度優(yōu)先是（A、分治策略 B、動態(tài)規(guī)劃法 C、貪心法 D、回溯法（ C ）。B ）
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號-1