20xx計算機算法設(shè)計與分析習(xí)題及答案-資料下載頁
2025-06-24 04:01本頁面
【正文】 /2。 //取中點 mergeSort(a, left, i)。 mergeSort(a, i+1, right)。 merge(a, b, left, i, right)。 //合并到數(shù)組b copy(a, b, left, right)。 //復(fù)制回數(shù)組a } }算法在最壞情況下的時間復(fù)雜度為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 ( 約束函數(shù) ) Backtrack(t+1)。 }}void Clique::Backtrack(int i) // 計算最大團{ if (i n) { // 到達葉結(jié)點 for (int j = 1。 j = n。 j++) bestx[j] = x[j]。 bestn = 。 return。} // 檢查頂點 i 與當(dāng)前團的連接 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)。 }}：一本書的頁碼從自然數(shù)1開始順序編碼直到自然數(shù)n。書的頁碼按照通常的習(xí)慣編排，每個頁碼都不含多余的前導(dǎo)數(shù)字0。例如，第6頁用數(shù)字6表示，而不是06或006等。數(shù)字計數(shù)問題要求對給定書的總頁碼n(1≤n≤109)，計算出書的全部頁碼中分別用到多少次數(shù)字0，1，2，…，9。輸入數(shù)據(jù)、輸出結(jié)果示例輸入數(shù)據(jù)：11 輸出結(jié)果：數(shù) 字: 0 1 2 3 4 5 6 7 8 9用到次數(shù): 1 4 1 1 1 1 1 1 1 1 void count(int n,int a[10]){int i,x,y。 for (i=0。i=9。i++) a[i]=0。 for (i=1。i=n。i++) {x=i。 while (x) {y=x%10。 a[y]++。 x/=10。 } }}6. 順序表存儲表示如下：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。 //樞軸記錄關(guān)鍵字 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,)。 }7. 順序表存儲表示如下：typedef struct{RedType r[MAXSIZE+1]。 //順序表 int length。 //順序表長度}SqList。編寫對順序表L進行2_路歸并排序的算法。void Merge(RedType SR[],RedType TR[],int i,int m,int n){//將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n] int l,j,k。 for (j=m+1,k=i。 i=mamp。amp。j=n。 ++k) //將SR中記錄由小到大地并入TR if (LQ(SR[i].key,SR[j].key)) TR[k]=SR[i++]。 else TR[k]=SR[j++]。 if (i=m) for (l=i。 l=m。 l++,k++) TR[k]=SR[l]。 //將剩余的SR[i..m]復(fù)制到TR if (j=n) for (l=j。 l=n。 l++,k++) TR[k]=SR[l]。 //將剩余的SR[j..n]復(fù)制到TR}void MSort(RedType SR[],RedType TR1[],int s,int t){//將SR[s..t]歸并排序為TR1[s..t]. int m。 RedType TR2[MAXSIZE+1]。 if (s==t) TR1[s]=SR[s]。 else {m=(s+t)/2。 //將SR[s..t]平分為SR[s..m]和SR[m+1..t] MSort(SR,TR2,s,m)。 //遞歸地將SR[s..m]歸并為有序的TR2[s..m] MSort(SR,TR2,m+1,t)。 //遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t] Merge(TR2,TR1,s,m,t)。 //將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t] }}void MergeSort(SqList amp。L){//對順序表L作歸并排序 MSort(, , 1, )。 }15
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1