1 1.1 第 1 章─概論 2 1.1.1 練習題 3 1. 下列關于演算法的說法中正確的有（ ），Ⅰ.求解某一類問題的演算法是唯一的 4 Ⅱ.演算法必須在有限步操作之后停止 5 Ⅲ.演算法的每一步操作必須是明確的，不能有歧義或含義模糊Ⅳ.演算法執行后一定產生確定的結果 6 A. 1 個 B.2 個 C.3 個 D.4 個 7 2. T(n)表示當輸入規模為 n 時的演算法效率，以下演算法效率最優的是（ ）， 8 A.T(n)= T(n-1)+1，T(1)=1 B.T(n)= 2n2 9 C.T(n)= T(n/2)+1，T(1)=1 D.T(n)=3nlog2n 10 3. 什么是演算法？演算法有哪些特征？ 11 4. 判斷一個大于 2 的正整數 n 是否為素數的方法有多種，給出兩種演算法，說明其中一種演算法更好的理由， 12 5. 證明以下關系成立： 13 （1）10n2-2n=?(n2) 14 （2）2n+1=?(2n) 15 6. 證明 O(f(n))+O(g(n))=O(max{f(n)，g(n)}) ， 16 7. 有一個含 n（n>2）個整數的陣列 a，判斷其中是否存在出現次數超過所有元素一半的元素， 17 8. 一個字串采用 string 物件存盤，設計一個演算法判斷該字串是否為回文， 18 9. 有一個整數序列，設計一個演算法判斷其中是否存在兩個元素和恰好等于給定的整數 k， 19 10. 有兩個整數序列，每個整數序列中所有元素均不相同，設計一個演算法求它們的公共元素，要求不使用 STL 的集合演算法， 20 11. 正整數 n（n>1）可以寫成質數的乘積形式，稱為整數的質因數分解，例如， 12=2*2*3，18=2*3*3，11=11，設計一個演算法求 n 這樣分解后各個質因數出現的次數，采用 vector 向量存放結果， 21 12. 有一個整數序列，所有元素均不相同，設計一個演算法求相差最小的元素對的個數，如序列 4、1、2、3 的相差最小的元素對的個數是 3，其元素對是（1，2），（2，3）， 22 （3，4）， 23 13. 有一個 map<string，int>容器，其中已經存放了較多元素，設計一個演算法求出其中重復的 value 并且回傳重復 value 的個數， 24 14. 重新做第 10 題，采用 map 容器存放最終結果， 25 15. 假設有一個含 n（n>1）個元素的 stack<int>堆疊容器 st，設計一個演算法出堆疊從堆疊頂到堆疊底的第 k（1≤k≤n）個元素，其他堆疊元素不變， 26 27 28 1.1.2 練習題參考答案 29 1. 答：由于演算法具有有窮性、確定性和輸出性，因而Ⅱ、Ⅲ、Ⅳ正確，而解決某一類問題的演算法不一定是唯一的，答案為 C， 30 2. 答：選項 A 的時間復雜度為 O(n)，選項 B 的時間復雜度為 O(n2)，選項 C 的時間復雜度為 O(log2n)，選項 D 的時間復雜度為 O(nlog2n)，答案為 C， 31 3. 答：演算法是求解問題的一系列計算步驟，演算法具有有限性、確定性、可行性、輸入性和輸出性 5 個重要特征， 32 4. 答：兩種演算法如下： 33 #include <stdio.h> #include <math.h> 34 bool isPrime1(int n) //方法 1 35 { for (int i=2;i<n;i++) 36 if (n%i==0) 37 return false; 38 return true; 39 } 40 bool isPrime2(int n) //方法 2 41 { for (int i=2;i<=(int)sqrt(n);i++) 42 if (n%i==0) 43 return false; 44 return true; 45 } 46 void main() 47 { int n=5; 48 printf("%d,%d\n",isPrime1(n),isPrime2(n)); 49 } 50 方法 1 的時間復雜度為 O(n)，方法 2 的時間復雜度為 n，所以方法 2 更好， 51 5. 答：（1）當 n 足夠大時，(10n2-2n)/( n2)=10，所以 10n2-2n=?(n2)， 52 （2）2n+1=2*2n=?(2n)， 53 6. 證明：對于任意 f1(n)∈O(f(n)) ，存在正常數 c1 和正常數 n1，使得對所有 n≥n1， 有 f1(n)≤c1f(n) ， 54 類似地，對于任意 g1(n)∈O(g(n)) ，存在正常數 c2 和自然數 n2，使得對所有 n≥n2， 有 g1(n)≤c2g(n) ， 55 令 c3=max{c1，c2}，n3=max{n1，n2}，h(n)= max{f(n)，g(n)} ，則對所有的 n≥n3，有： 56 f1(n) +g1(n)≤c1f(n) + c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n)) 57 ≤c32max{f(n)，g(n)}=2c3h(n)=O(max{f(n)，g(n)})， 58 7. 解：先將 a 中元素遞增排序，再求出現次數最多的次數 maxnum，最后判斷是否滿足條件，對應的程式如下： 59 #include <stdio.h> #include <algorithm> using namespace std; 60 61 bool solve(int a[],int n,int &x) 62 { 63 sort(a,a+n); 64 int maxnum=0; //遞增排序 65 //出現次數最多的次數 66 int num=1; 67 int e=a[0]; 68 for (int i=1;i<n;i++) 69 { if (a[i]==e) 70 { num++; 71 if (num>maxnum) 72 { maxnum=num; 73 x=e; 74 } 75 } 76 else 77 { e=a[i]; 78 num=1; 79 } 80 } 81 if (maxnum>n/2) 82 return true; 83 else 84 return false; 85 } 86 void main() 87 { int a[]={2,2,2,4,5,6,2}; 88 int n=sizeof(a)/sizeof(a[0]); 89 int x; 90 if (solve(a,n,x)) 91 printf("出現次數超過所有元素一半的元素為%d\n",x); 92 else 93 printf("不存在出現次數超過所有元素一半的元素\n"); 94 } 95 上述程式的執行結果如圖 1.1 所示， 96 圖 1.1 程式執行結果 97 8. 解：采用前后字符判斷方法，對應的程式如下： 98 #include <iostream> #include <string> using namespace std; 99 bool solve(string str) //判斷字串 str 是否為回文 100 { int i=0,j=str.length()-1; 101 while (i<j) 102 { if (str[i]!=str[j]) 103 return false; 104 105 106 i++; j--; 107 } 108 return true; 109 } 110 void main() 111 { cout << "求解結果" << endl; 112 string str="abcd"; 113 cout << " " << str << (solve(str)?"是回文":"不是回文") << endl; 114 string str1="abba"; 115 cout << " " << str1 << (solve(str1)?"是回文":"不是回文") << endl; 116 } 117 上述程式的執行結果如圖 1.2 所示， 118 圖 1.2 程式執行結果 119 9. 解：先將 a 中元素遞增排序，然后從兩端開始進行判斷，對應的程式如下： 120 #include <stdio.h> #include <algorithm> using namespace std; 121 bool solve(int a[],int n,int k) 122 { sort(a,a+n); //遞增排序 123 int i=0, j=n-1; 124 while (i<j) //區間中存在兩個或者以上元素 125 { if (a[i]+a[j]==k) 126 return true; 127 else if (a[i]+a[j]<k) 128 i++; 129 else 130 j--; 131 } 132 return false; 133 } 134 void main() 135 { int a[]={1,2,4,5,3}; 136 int n=sizeof(a)/sizeof(a[0]); 137 printf("求解結果\n"); 138 int k=9,i,j; 139 if (solve(a,n,k,i,j)) 140 printf(" 存在: %d+%d=%d\n",a[i],a[j],k); 141 else 142 printf(" 不存在兩個元素和為%d\n",k); 143 int k1=10; 144 if (solve(a,n,k1,i,j)) 145 printf(" 存在: %d+%d=%d\n",a[i],a[j],k1); 146 147 else 148 printf(" 不存在兩個元素和為%d\n",k1); 149 } 150 上述程式的執行結果如圖 1.3 所示， 151 圖 1.3 程式執行結果 152 10. 解：采用集合 set<int>存盤整數序列，集合中元素默認是遞增排序的，再采用二路歸并演算法求它們的交集，對應的程式如下： 153 #include <stdio.h> #include <set> 154 using namespace std; 155 void solve(set<int> s1,set<int> s2,set<int> &s3) //求交集 s3 156 { set<int>::iterator it1,it2; 157 it1=s1.begin(); it2=s2.begin(); 158 while (it1!=s1.end() && it2!=s2.end()) 159 { if (*it1==*it2) 160 { s3.insert(*it1); 161 ++it1; ++it2; 162 } 163 else if (*it1<*it2) 164 ++it1; 165 else 166 ++it2; 167 } 168 } 169 void dispset(set<int> s) //輸出集合的元素 170 { set<int>::iterator it; 171 for (it=s.begin();it!=s.end();++it) 172 printf("%d ",*it); 173 printf("\n"); 174 } 175 void main() 176 { int a[]={3,2,4,8}; 177 int n=sizeof(a)/sizeof(a[0]); 178 set<int> s1(a,a+n); 179 int b[]={1,2,4,5,3}; 180 int m=sizeof(b)/sizeof(b[0]); 181 set<int> s2(b,b+m); 182 set<int> s3; 183 solve(s1,s2,s3); 184 printf("求解結果\n"); 185 printf(" s1: "); dispset(s1); 186 187 188 printf(" s2: "); dispset(s2); 189 printf(" s3: "); dispset(s3); 190 } 191 上述程式的執行結果如圖 1.4 所示， 192 圖 1.4 程式執行結果 193 11. 解：對于正整數 n，從 i=2 開始查找其質因數，ic 記錄質因數 i 出現的次數，當找到這樣質因數后，將（i，ic）作為一個元素插入到 vector 容器 v 中，最后輸出 v，對應的演算法如下： 194 #include <stdio.h> #include <vector> using namespace std; 195 struct NodeType //vector 向量元素型別 196 { int p; //質因數 197 int pc; //質因數出現次數 198 }; 199 void solve(int n,vector<NodeType> &v) //求 n 的質因數分解 200 { int i=2; 201 int ic=0; 202 NodeType e; 203 do 204 { if (n%i==0) 205 { ic++; 206 n=n/i; 207 } 208 else 209 { if (ic>0) 210 { e.p=i; 211 e.pc=ic; 212 v.push_back(e); 213 } 214 ic=0; 215 i++; 216 } 217 } while (n>1 || ic!=0); 218 } 219 void disp(vector<NodeType> &v) //輸出 v 220 { vector<NodeType>::iterator it; 221 for (it=v.begin();it!=v.end();++it) 222 printf(" 質因數%d 出現%d 次\n",it->p,it->pc); 223 } 224 225 void main() 226 { vector<NodeType> v; 227 int n=100; 228 printf("n=%d\n",n); 229 solve(n,v); 230 disp(v); 231 } 232 上述程式的執行結果如圖 1.5 所示， 233 圖 1.5 程式執行結果 234 12. 解：先遞增排序，再求相鄰元素差，比較求最小元素差，累計最小元素差的個數，對應的程式如下： 235 #include <iostream> #include <algorithm> #include <vector> using namespace std; 236 int solve(vector<int> &myv) //求 myv 中相差最小的元素對的個數 237 { sort(myv.begin(),myv.end()); //遞增排序 238 int ans=1; 239 int mindif=myv[1]-myv[0]; 240 for (int i=2;i<myv.size();i++) 241 { if (myv[i]-myv[i-1]<mindif) 242 { ans=1; 243 mindif=myv[i]-myv[i-1]; 244 } 245 else if (myv[i]-myv[i-1]==mindif) 246 ans++; 247 } 248 return ans; 249 } 250 void main() 251 { int a[]={4,1,2,3}; 252 int n=sizeof(a)/sizeof(a[0]); 253 vector<int> myv(a,a+n); 254 cout << "相差最小的元素對的個數: " << solve(myv) << endl; 255 } 256 上述程式的執行結果如圖 1.6 所示， 257 258 259 圖 1.6 程式執行結果 260 13. 解：對于 map<string，int>容器 mymap，設計另外一個 map<int，int>容器 tmap， 將前者的 value 作為后者的關鍵字，遍歷 mymap，累計 tmap 中相同關鍵字的次數，一個參考程式及其輸出結果如下： 261 #include <iostream> #include <map> #include <string> using namespace std; void main() 262 { map<string,int> mymap; 263 mymap.insert(pair<string,int>("Mary",80)); 264 mymap.insert(pair<string,int>("Smith",82)); 265 mymap.insert(pair<string,int>("John",80)); 266 mymap.insert(pair<string,int>("Lippman",95)); 267 mymap.insert(pair<string,int>("Detial",82)); 268 map<string,int>::iterator it; 269 map<int,int> tmap; 270 for (it=mymap.begin();it!=mymap.end();it++) 271 tmap[(*it).second]++; 272 map<int，int>::iterator it1; 273 cout << "求解結果" << endl; 274 for (it1=tmap.begin();it1!=tmap.end();it1++) 275 cout << " " << (*it1).first << ": " << (*it1).second << "次\n"; 276 } 277 上述程式的執行結果如圖 1.7 所示， 278 圖 1.7 程式執行結果 279 14. 解：采用 map<int，int>容器 mymap 存放求解結果，第一個分量存放質因數，第二個分量存放質因數出現次數，對應的程式如下： 280 #include <stdio.h> #include <map> 281 using namespace std; 282 void solve(int n,map<int,int> &mymap) //求 n 的質因數分解 283 284 285 286 287 else 288 { if (ic>0) 289 mymap[i]=ic; 290 ic=0; 291 i++; 292 } 293 } while (n>1 || ic!=0); 294 } 295 void disp(map<int,int> &mymap) //輸出 mymap 296 { map<int,int>::iterator it; 297 for (it=mymap.begin();it!=mymap.end();++it) 298 printf(" 質因數%d 出現%d 次\n",it->first,it->second); 299 } 300 void main() 301 { map<int,int> mymap; 302 int n=12345; 303 printf("n=%d\n",n); 304 solve(n,mymap); 305 disp(mymap); 306 } 307 上述程式的執行結果如圖 1.8 所示， 308 圖 1.8 程式執行結果 309 15. 解：堆疊容器不能順序遍歷，為此創建一個臨時 tmpst 堆疊，將 st 的 k 個元素出堆疊并進堆疊到 tmpst 中，再出堆疊 tmpst 一次得到第 k 個元素，最后將堆疊 tmpst 的所有元素出堆疊并進堆疊到 st 中，對應的程式如下： 310 #include <stdio.h> #include <stack> using namespace std; 311 int solve(stack<int> &st,int k) //出堆疊第 k 個元素 312 { stack<int> tmpst; 313 int e; 314 for (int i=0;i<k;i++) //出堆疊 st 的 k 個元素并進 tmpst 堆疊 315 { e=st.top(); 316 st.pop(); 317 tmpst.push(e); 318 } 319 e=tmpst.top(); //求第 k 個元素 320 tmpst.pop(); 321 while (!tmpst.empty()) //將 tmpst 的所有元素出堆疊并進堆疊 st 322 { st.push(tmpst.top()); 323 tmpst.pop(); 324 325 326 } 327 return e; 328 } 329 void disp(stack<int> &st) //出堆疊 st 的所有元素 330 { while (!st.empty()) 331 { printf("%d ",st.top()); 332 st.pop(); 333 } 334 printf("\n"); 335 } 336 void main() 337 { stack<int> st; 338 printf("進堆疊元素 1,2,3,4\n"); 339 st.push(1); 340 st.push(2); 341 st.push(3); 342 st.push(4); 343 int k=3; 344 int e=solve(st,k); 345 printf("出堆疊第%d 個元素是: %d\n",k,e); 346 printf("st 中元素出堆疊順序: "); 347 disp(st); 348 } 349 上述程式的執行結果如圖 1.9 所示， 350 圖 1.9 程式執行結果 351 1.2 第 2 章─遞回演算法設計技術 352 1.2.1 練習題 353 1. 什么是直接遞回和間接遞回？消除遞回一般要用到什么資料結構？ 354 2. 分析以下程式的執行結果： 355 #include <stdio.h> 356 void f(int n,int &m) 357 { if (n<1) return; 358 else 359 { printf("呼叫f(%d,%d)前,n=%d,m=%d\n",n-1,m-1,n,m); 360 n--; m--; 361 f(n-1,m); 362 printf("呼叫f(%d,%d)后:n=%d,m=%d\n",n-1,m-1,n,m); 363 } 364 365 } 366 void main() 367 { int n=4,m=4; 368 f(n,m); 369 } 370 3. 采用直接推導方法求解以下遞回方程： 371 T(1)=1 372 T(n)=T(n-1)+n 當 n>1 373 4. 采用特征方程方法求解以下遞回方程： 374 H(0)=0 375 H(1)=1 376 H(2)=2 377 H(n)=H(n-1)+9H(n-2)-9H(n-3) 當 n>2 378 5. 采用遞回樹方法求解以下遞回方程： 379 T(1)=1 380 T(n)=4T(n/2)+n 當 n>1 381 6. 采用主方法求解以下題的遞回方程， 382 T(n)=1 當 n=1 383 T(n)=4T(n/2)+n2 當 n>1 384 7. 分析求斐波那契 f(n)的時間復雜度， 385 8. 數列的首項 a1=0，后續奇數項和偶數項的計算公式分別為 a2n=a2n-1+2，a2n+1=a2n- 1+a2n-1，寫出計算數列第 n 項的遞回演算法， 386 9. 對于一個采用字符陣列存放的字串 str，設計一個遞回演算法求其字符個數（長度）， 387 10. 對于一個采用字符陣列存放的字串 str，設計一個遞回演算法判斷 str 是否為回文， 388 11. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法正序輸出所有結點值， 389 12. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法逆序輸出所有結點值， 390 13. 對于不帶頭結點的非空單鏈表 L，設計一個遞回演算法回傳最大值結點的地址（假設這樣的結點唯一）， 391 14. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法回傳第一個值為 x 的結點的地址，沒有這樣的結點時回傳 NULL， 392 15. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法洗掉第一個值為 x 的結點， 393 16. 假設二叉樹采用二叉鏈存盤結構存放，結點值為 int 型別，設計一個遞回演算法求二叉樹 bt 中所有葉子結點值之和， 394 17. 假設二叉樹采用二叉鏈存盤結構存放，結點值為 int 型別，設計一個遞回演算法求二叉樹 bt 中所有結點值大于等于 k 的結點個數， 395 18. 假設二叉樹采用二叉鏈存盤結構存放，所有結點值均不相同，設計一個遞回演算法求值為 x 的結點的層次（根結點的層次為 1），沒有找到這樣的結點時回傳 0， 396 397 398 1.2.2 練習題參考答案 399 1. 答：一個 f 函式定義中直接呼叫 f 函式自己，稱為直接遞回，一個 f 函式定義中呼叫 g 函式，而 g 函式的定義中呼叫 f 函式，稱為間接遞回，消除遞回一般要用堆疊實作， 400 2. 答：遞回函式f(n，m)中，n是非參考引數，m是參考引數，所以遞回函式的狀態為 401 （n），程式執行結果如下： 402 呼叫f(3,3)前,n=4,m=4 呼叫f(1,2)前,n=2,m=3 呼叫f(0,1)后,n=1,m=2 呼叫f(2,1)后,n=3,m=2 403 3. 解：求 T(n)的程序如下： 404 T(n)=T(n-1)+n=[T(n-2)+n-1)]+n=T(n-2)+n+(n-1) 405 =T(n-3)+n+(n-1)+(n-2) 406 =… 407 =T(1)+n+(n-1)+…+2 408 =n+(n-1)+ +…+2+1=n(n+1)/2=O(n2)， 409 4. 解：整數一個常系數的線性齊次遞推式，用 xn 代替 H(n)，有：xn=xn-1+9xn-2-9xn-3， 兩邊同時除以 xn-3，得到：x3=x2+9x-9，即 x3-x2-9x+9=0， 410 x3-x2-9x+9=x(x2-9)-(x2-9)=(x-1)(x2-9)=(x-1)(x+3)(x-3)=0，得到 r1=1，r2=-3，r3=3 411 則遞回方程的通解為：H(n)=c1+c2(-3)n+c33n 代入 H(0)=0，有 c1+c2+c3=0 412 代入 H(1)=1，有 c1-3c2+3c3=1 413 代入 H(2)=2，有 c1+9c2+9c3=2 414 415 ( ? 1)n ? 1 416 417 418 419 n ? 1 1 420 421 422 求出：c1=-1/4，c2=-1/12，c3=1/3，H(n)=c1+c2(-3)n+c33n=( 4 + 1)3 423 424 ? 4， 425 426 5. 解：構造的遞回樹如圖 1.10 所示，第 1 層的問題規模為 n，第 2 的層的子問題的問題規模為 n/2，依此類推，當展開到第 k+1 層，其規模為 n/2k=1，所以遞回樹的高度為log2n+1， 427 第1層有1個結點，其時間為n，第2層有4個結點，其時間為4(n/2)=2n，依次類推，第k 層有4k-1個結點，每個子問題規模為n/2k-1，其時間為4k-1(n/2k-1)=2k-1n，葉子結點的個數為n 個，其時間為n，將遞回樹每一層的時間加起來，可得： 428 T(n)=n+2n+…+ 2k-1n+…+n≈?? ? 2log2n=O(n2)， 429 430 431 432 (n/2) 433 434 n n 435 436 (n/2) (n/2) (n/2) 2n 437 438 439 440 高度h為log 2n+1 441 442 (n/22) 443 444 (n/22) 445 446 (n/22) 447 448 (n/22) 449 450 451 22n 452 453 … … … … 454 455 1 1 1 1 n 456 457 圖 1.10 一棵遞回樹 458 6. 解：采用主方法求解，這里 a=4，b=2，f(n)=n2， 459 logba log24 2 460 461 因此，?? 462 logba 463 464 =?? 465 2 466 467 =n ，它與 f(n)一樣大，滿足主定理中的情況（2），所以 T(n)=O( 468 469 ?? log2n)=O(n log2n)， 470 7. 解：設求斐波那契 f(n)的時間為 T(n)，有以下遞推式： 471 T(1)=T(2) 472 T(n)=T(n-1)+T(n-2)+1 當 n>2 473 其中，T(n)式中加 1 表示一次加法運算的時間， 474 不妨先求 T1(1)=T1(2)=1，T1(n)=T1(n-1)+T1(n-2)，按《教程》例 2.14 的方法可以求 475 476 出： 477 1 ? 1 ? 478 479 480 5 ?n 481 482 483 1 ? 1 ? 484 485 486 5 ?n 487 488 489 1 ? 1 ? 490 491 492 5 ?n 493 494 T1(n)= 495 496 ???? ? ???? ≈ 497 498 ???? = 499 500 ? ? ? 501 ? ? ? 502 1 ? 1 ? 503 504 ? ? ? 505 ? ? ? 506 5 ?n 507 508 所以 T(n)=T1(n)+1≈ 509 510 ???? 511 512 +1=O(φn)，其中 φ= ， 513 514 ? ? 515 ? ? 516 8. 解：設 f(m)計算數列第 m 項值， 517 當 m 為偶數時，不妨設 m=2n，則 2n-1=m-1，所以有 f(m)=f(m-1)+2， 518 當 m 為奇數時，不妨設 m=2n+1，則 2n-1=m-2，2n=m-1，所以有 f(m)=f(m-2)+f(m- 519 1)-1， 520 對應的遞回演算法如下： 521 int f(int m) 522 { if (m==1) return 0; 523 if (m%2==0) 524 return f(m-1)+2; 525 else 526 return f(m-2)+f(m-1)-1; 527 } 528 9. 解：設 f(str)回傳字串 str 的長度，其遞回模型如下： 529 f(str)=0 當*str='\0'時 530 f(str)=f(str+1)+1 其他情況 531 對應的遞回程式如下： 532 533 534 #include <iostream> using namespace std; 535 int Length(char *str) //求str的字符個數 536 { if (*str=='\0') 537 return 0; 538 else 539 return Length(str+1)+1; 540 } 541 void main() 542 { char str[]="abcd"; 543 cout << str << "的長度: " << Length(str) << endl; 544 } 545 上述程式的執行結果如圖 1.11 所示， 546 圖 1.11 程式執行結果 547 10. 解：設 f(str，n)回傳含 n 個字符的字串 str 是否為回文，其遞回模型如下： 548 f(str，n)=true 當 n=0 或者 n=1 時 549 f(str，n)=flase 當 str[0]≠str[n-1]時 550 f(str，n)=f(str+1，n-2) 其他情況 551 對應的遞回演算法如下： #include <stdio.h> #include <string.h> 552 bool isPal(char *str,int n) //str 回文判斷演算法 553 { if (n==0 || n==1) 554 return true; 555 if (str[0]!=str[n-1]) 556 return false; 557 return isPal(str+1,n-2); 558 } 559 void disp(char *str) 560 { int n=strlen(str); 561 if (isPal(str,n)) 562 printf(" %s是回文\n",str); 563 else 564 printf(" %s不是回文\n",str); 565 } 566 void main() 567 { printf("求解結果\n"); 568 disp("abcba"); 569 disp("a"); 570 disp("abc"); 571 } 572 573 上述程式的執行結果如圖 1.12 所示， 574 圖 1.12 程式執行結果 575 11. 解：設 f(L)正序輸出單鏈表 L 的所有結點值，其遞歸模型如下： 576 f(L) ≡ 不做任何事情 當 L=NULL f(L) ≡ 輸出 L->data; f(L->next); 當 L≠NULL 時對應的遞回程式如下： 577 #include "LinkList.cpp" //包含單鏈表的基本運算演算法 578 void dispLink(LinkNode *L) //正序輸出所有結點值 579 { if (L==NULL) return; 580 else 581 { printf("%d ",L->data); 582 dispLink(L->next); 583 } 584 } 585 void main() 586 { int a[]={1,2,5,2,3,2}; 587 int n=sizeof(a)/sizeof(a[0]); 588 LinkNode *L; 589 CreateList(L,a,n); //由a[0..n-1]創建不帶頭結點的單鏈表 590 printf("正向L: "); 591 dispLink(L); printf("\n"); 592 Release(L); //銷毀單鏈表 593 } 594 上述程式的執行結果如圖 1.13 所示， 595 圖 1.13 程式執行結果 596 12. 解：設 f(L)逆序輸出單鏈表 L 的所有結點值，其遞回模型如下： 597 f(L) ≡ 不做任何事情 當 L=NULL f(L) ≡ f(L->next); 輸出 L->data 當 L≠NULL 時對應的遞回程式如下： 598 #include "LinkList.cpp" //包含單鏈表的基本運算演算法 599 void Revdisp(LinkNode *L) //逆序輸出所有結點值 600 { if (L==NULL) return; 601 602 603 else 604 { Revdisp(L->next); 605 printf("%d ",L->data); 606 } 607 } 608 void main() 609 { int a[]={1,2,5,2,3,2}; 610 int n=sizeof(a)/sizeof(a[0]); 611 LinkNode *L; 612 CreateList(L,a,n); 613 printf("反向L: "); 614 Revdisp(L); printf("\n"); 615 Release(L); 616 } 617 上述程式的執行結果如圖 1.14 所示， 618 圖 1.14 程式執行結果 619 13. 解：設 f(L)回傳單鏈表 L 中值最大結點的地址，其遞回模型如下： 620 f(L) = L 當 L 只有一個結點時 621 f(L) = MAX{f(L->next)，L->data} 其他情況 622 對應的遞回程式如下： 623 #include "LinkList.cpp" //包含單鏈表的基本運算演算法 624 LinkNode *Maxnode(LinkNode *L) //回傳最大值結點的地址 625 { if (L->next==NULL) 626 return L; //只有一個結點時 627 else 628 { LinkNode *maxp; 629 maxp=Maxnode(L->next); 630 if (L->data>maxp->data) 631 return L; 632 else 633 return maxp; 634 } 635 } 636 void main() 637 { int a[]={1,2,5,2,3,2}; 638 int n=sizeof(a)/sizeof(a[0]); 639 LinkNode *L,*p; 640 CreateList(L,a,n); 641 p=Maxnode(L); 642 printf("最大結點值: %d\n",p->data); 643 Release(L); 644 645 } 646 上述程式的執行結果如圖 1.15 所示， 647 圖 1.15 程式執行結果 648 14. 解：設 f(L，x)回傳單鏈表 L 中第一個值為 x 的結點的地址，其遞回模型如下： 649 f(L，x) = NULL 當 L=NULL 時 650 f(L，x) = L 當 L≠NULL 且 L->data=https://www.cnblogs.com/JUSTDOINS/p/x 時 651 f(L，x) = f(L->next，x) 其他情況 652 對應的遞回程式如下： 653 #include "LinkList.cpp" //包含單鏈表的基本運算演算法 654 LinkNode *Firstxnode(LinkNode *L,int x) //回傳第一個值為 x 的結點的地址 655 { if (L==NULL) return NULL; 656 if (L->data=https://www.cnblogs.com/JUSTDOINS/p/=x) 657 return L; 658 else 659 return Firstxnode(L->next,x); 660 } 661 void main() 662 { int a[]={1,2,5,2,3,2}; 663 int n=sizeof(a)/sizeof(a[0]); 664 LinkNode *L,*p; 665 CreateList(L,a,n); 666 int x=2; 667 p=Firstxnode(L,x); 668 printf("結點值: %d\n",p->data); 669 Release(L); 670 } 671 上述程式的執行結果如圖 1.16 所示， 672 圖 1.16 程式執行結果 673 15. 解：設 f(L，x)洗掉單鏈表 L 中第一個值為 x 的結點，其遞回模型如下： 674 f(L，x) ≡ 不做任何事情 當 L=NULL 675 f(L，x) ≡ 洗掉 L 結點，L=L->next 當 L≠NULL 且 L->data=https://www.cnblogs.com/JUSTDOINS/p/x f(L，x) ≡ f(L->next，x) 其他情況 676 對應的遞回程式如下： 677 678 679 #include "LinkList.cpp" //包含單鏈表的基本運算演算法 680 void Delfirstx(LinkNode *&L,int x) //洗掉單鏈表 L 中第一個值為 x 的結點 681 { if (L==NULL) return; 682 if (L->data=https://www.cnblogs.com/JUSTDOINS/p/=x) 683 { LinkNode *p=L; 684 L=L->next; 685 free(p); 686 } 687 else 688 Delfirstx(L->next,x); 689 } 690 void main() 691 { int a[]={1,2,5,2,3,2}; 692 int n=sizeof(a)/sizeof(a[0]); 693 LinkNode *L; 694 CreateList(L,a,n); 695 printf("洗掉前L: "); DispList(L); 696 int x=2; 697 printf("洗掉第一個值為%d的結點\n",x); 698 Delfirstx(L,x); 699 printf("洗掉后L: "); DispList(L); 700 Release(L); 701 } 702 上述程式的執行結果如圖 1.17 所示， 703 圖 1.17 程式執行結果 704 16. 解：設 f(bt)回傳二叉樹 bt 中所有葉子結點值之和，其遞回模型如下： 705 706 f(bt)=0 當 bt=NULL 707 f(bt)=bt->data 當 bt≠NULL 且 bt 結點為葉子結點 708 f(bt)=f(bt->lchild)+f(bt->rchild) 其他情況 709 對應的遞回程式如下： 710 #include "Btree.cpp" //包含二叉樹的基本運算演算法 711 int LeafSum(BTNode *bt) //二叉樹 bt 中所有葉子結點值之和 712 { if (bt==NULL) return 0; 713 if (bt->lchild==NULL && bt->rchild==NULL) 714 return bt->data; 715 int lsum=LeafSum(bt->lchild); 716 int rsum=LeafSum(bt->rchild); 717 return lsum+rsum; 718 } 719 void main() 720 721 722 { BTNode *bt; 723 Int a[]={5,2,3,4,1,6}; //先序序列 724 Int b[]={2,3,5,1,4,6}; //中序序列 725 int n=sizeof(a)/sizeof(a[0]); 726 bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt 727 printf("二叉樹bt:"); DispBTree(bt); printf("\n"); 728 printf("所有葉子結點值之和: %d\n",LeafSum(bt)); 729 DestroyBTree(bt); //銷毀樹bt 730 } 731 上述程式的執行結果如圖 1.18 所示， 732 圖 1.18 程式執行結果 733 17. 解：設 f(bt，k)回傳二叉樹 bt 中所有結點值大于等于 k 的結點個數，其遞回模型如下： 734 f(bt，k)=0 當 bt=NULL 735 f(bt，k)=f(bt->lchild，k)+f(bt->rchild，k)+1 當 bt≠NULL 且 bt->data≥k f(bt，k)=f(bt->lchild，k)+f(bt->rchild，k) 其他情況 736 對應的遞回程式如下： 737 #include "Btree.cpp" //包含二叉樹的基本運算演算法 738 int Nodenum(BTNode *bt,int k) //大于等于 k 的結點個數 739 { if (bt==NULL) return 0; 740 int lnum=Nodenum(bt->lchild,k); 741 int rnum=Nodenum(bt->rchild,k); 742 if (bt->data>=k) 743 return lnum+rnum+1; 744 else 745 return lnum+rnum; 746 } 747 void main() 748 { BTNode *bt; 749 Int a[]={5,2,3,4,1,6}; 750 Int b[]={2,3,5,1,4,6}; 751 int n=sizeof(a)/sizeof(a[0]); 752 bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt 753 printf("二叉樹bt:"); DispBTree(bt); printf("\n"); 754 int k=3; 755 printf("大于等于%d的結點個數: %d\n",k,Nodenum(bt,k)); 756 DestroyBTree(bt); //銷毀樹bt 757 } 758 上述程式的執行結果如圖 1.19 所示， 759 760 761 762 763 圖 1.19 程式執行結果 764 18. 解：設 f(bt，x，h)回傳二叉樹 bt 中 x 結點的層次，其中 h 表示 bt 所指結點的層次，初始呼叫時，bt 指向根結點，h 置為 1，其遞回模型如下： 765 f(bt，x，h)=0 當 bt=NULL 766 f(bt，x，h)=h 當 bt≠NULL 且 bt->data=https://www.cnblogs.com/JUSTDOINS/p/x 767 f(bt，x，h) =l 當 l=f(bt->lchild，x，h+1)≠0 f(bt，x，h) =f(bt->rchild，x，h+1) 其他情況 768 對應的遞回程式如下： 769 #include "Btree.cpp" //包含二叉樹的基本運算演算法 770 int Level(BTNode *bt,int x,int h) //求二叉樹 bt 中 x 結點的層次 771 { //初始呼叫時：bt 為根，h 為 1 772 if (bt==NULL) return 0; 773 if (bt->data=https://www.cnblogs.com/JUSTDOINS/p/=x) //找到 x 結點，回傳 h 774 return h; 775 else 776 { int l=Level(bt->lchild,x,h+1); //在左子樹中查找 777 if (l!=0) //在左子樹中找到，回傳其層次 l 778 return l; 779 else 780 return Level(bt->rchild,x,h+1);//回傳在右子樹的查找結果 781 } 782 } 783 void main() 784 { BTNode *bt; 785 Int a[]={5,2,3,4,1,6}; 786 Int b[]={2,3,5,1,4,6}; 787 int n=sizeof(a)/sizeof(a[0]); 788 bt=CreateBTree(a,b,n); //由 a 和 b 構造二叉鏈 bt 789 printf("二叉樹 bt:"); DispBTree(bt); printf("\n"); 790 int x=1; 791 printf("%d 結點的層次: %d\n",x,Level(bt,x,1)); 792 DestroyBTree(bt); //銷毀樹 bt 793 } 794 上述程式的執行結果如圖 1.20 所示， 795 圖 1.20 程式執行結果 796 797 1.3 第 3 章─分治法 798 1.3.1 練習題 799 1. 分治法的設計思想是將一個難以直接解決的大問題分割成規模較小的子問題，分別解決子問題，最后將子問題的解組合起來形成原問題的解，這要求原問題和子問題 800 （ ）， 801 A.問題規模相同，問題性質相同B.問題規模相同，問題性質不同C.問題規模不同，問題性質相同D.問題規模不同，問題性質不同 802 2. 在尋找 n 個元素中第 k 小元素問題中，如快速排序演算法思想，運用分治演算法對 n 803 個元素進行劃分，如何選擇劃分基準？下面（ ）答案解釋最合理， 804 A. 隨機選擇一個元素作為劃分基準 805 B. 取子序列的第一個元素作為劃分基準C.用中位數的中位數方法尋找劃分基準 806 D.以上皆可行，但不同方法，演算法復雜度上界可能不同 807 3. 對于下列二分查找演算法，以下正確的是（ ）， 808 A. 809 int binarySearch(int a[], int n, int x) 810 { int low=0, high=n-1; 811 while(low<=high) 812 { int mid=(low+high)/2; 813 if(x==a[mid]) return mid; 814 if(x>a[mid]) low=mid; 815 else high=mid; 816 } 817 return –1; 818 } 819 B. 820 int binarySearch(int a[], int n, int x) 821 { int low=0, high=n-1; 822 while(low+1!=high) 823 { int mid=(low+high)/2; 824 if(x>=a[mid]) low=mid; 825 else high=mid; 826 } 827 if(x==a[low]) return low; 828 else return –1; 829 } 830 C. 831 int binarySearch (int a[], int n, int x) 832 { int low=0, high=n-1; 833 while(low<high-1) 834 { int mid=(low+high)/2; 835 836 837 if(x<a[mid]) 838 high=mid; 839 840 841 } else low=mid; 842 if(x==a[low]) return low; 843 else return –1; 844 } 845 D. 846 int binarySearch(int a[], int n, int x) 847 { if(n > 0 && x >= a[0]) 848 { int low = 0, high = n-1; 849 while(low < high) 850 { int mid=(low+high+1)/2; 851 if(x < a[mid]) 852 high=mid-1; 853 else low=mid; 854 } 855 if(x==a[low]) return low; 856 } 857 return –1; 858 } 859 4. 快速排序演算法是根據分治策略來設計的，簡述其基本思想， 860 5. 假設含有 n 個元素的待排序的資料 a 恰好是遞減排列的，說明呼叫 QuickSort(a， 0，n-1)遞增排序的時間復雜度為 O(n2)， 861 6. 以下哪些演算法采用分治策略： 862 （1） 堆排序演算法 863 （2） 二路歸并排序演算法 864 （3） 折半查找演算法 865 （4） 順序查找演算法 866 7. 適合并行計算的問題通常表現出哪些特征？ 867 8. 設有兩個復數 x=a+bi 和 y=c+di，復數乘積 xy 可以使用 4 次乘法來完成，即 868 xy=(ac-bd)+(ad+bc)i，設計一個僅用 3 次乘法來計算乘積 xy 的方法， 869 9. 有 4 個陣列 a、b、c 和 d，都已經排好序，說明找出這 4 個陣列的交集的方法， 870 10. 設計一個演算法，采用分治法求一個整數序列中的最大最小元素， 871 11. 設計一個演算法，采用分治法求 xn， 872 12. 假設二叉樹采用二叉鏈存盤結構進行存盤，設計一個演算法采用分治法求一棵二叉樹 bt 的高度， 873 13. 假設二叉樹采用二叉鏈存盤結構進行存盤，設計一個演算法采用分治法求一棵二叉樹 bt 中度為 2 的結點個數， 874 14. 有一種二叉排序樹，其定義是空樹是一棵二叉排序樹，若不空，左子樹中所有結點值小于根結點值，右子樹中所有結點值大于根結點值，并且左右子樹都是二叉排序樹，現在該二叉排序樹采用二叉鏈存盤，采用分治法設計查找值為 x 的結點地址，并分析演算法的最好的平均時間復雜度， 875 876 15. 設有 n 個互不相同的整數，按遞增順序存放在陣列 a[0..n-1]中，若存在一個下標i（0≤i<n），使得 a[i]=i，設計一個演算法以 O(log2n)時間找到這個下標 i， 877 16. 請你模仿二分查找程序設計一個三分查找演算法，分析其時間復雜度， 878 17. 對于大于 1 的正整數 n，可以分解為 n=x1*x2*…*xm，其中 xi≥2，例如，n=12 時有 8 種 不 同 的 分 解 式 ：12=12，12=6*2，12=4*3，12=3*4，12=3*2*2，12=2*6， 12=2*3*2，12=2*2*3，設計一個演算法求 n 的不同分解式個數， 879 18. 設計一個基于 BSP 模型的并行演算法，假設有 p 臺處理器，計算整數陣列 a[0..n-1] 880 的所有元素之和，并分析演算法的時間復雜度， 881 1.3.2 練習題參考答案 882 1. 答：C， 883 2. 答：D， 884 3. 答：以 a[]={1，2，3，4，5}為例說明，選項 A 中在查找 5 時出現死回圈，選項 B 885 中在查找 5 時回傳-1，選項 C 中在查找 5 時回傳-1，選項 D 正確， 886 4. 答：對于無序序列 a[low..high]進行快速排序，整個排序為“大問題”，選擇其中的一個基準 base=a[i]（通常以序列中第一個元素為基準），將所有小于等于 base 的元素移動到它的前面，所有大于等于 base 的元素移動到它的后面，即將基準歸位到 a[i]，這樣產生a[low..i-1]和 a[i+1..high]兩個無序序列，它們的排序為“小問題”，當 a[low..high]序列只有一個元素或者為空時對應遞回出口， 887 所以快速排序演算法就是采用分治策略，將一個“大問題”分解為兩個“小問題”來求解，由于元素都是在 a 陣列中，其合并程序是自然產生的，不需要特別設計， 888 5. 答：此時快速排序對應的遞回樹高度為 O(n)，每一次劃分對應的時間為 O(n)，所以整個排序時間為 O(n2)， 889 6. 答：其中二路歸并排序和折半查找演算法采用分治策略， 890 7. 答：適合并行計算的問題通常表現出以下特征： 891 （1） 將作業分離成離散部分，有助于同時解決，例如，對于分治法設計的串行演算法，可以將各個獨立的子問題并行求解，最后合并成整個問題的解，從而轉化為并行演算法， 892 （2） 隨時并及時地執行多個程式指令， 893 （3） 多計算資源下解決問題的耗時要少于單個計算資源下的耗時， 894 8. 答：xy=(ac-bd)+((a+b)(c+d)-ac-bd)i，由此可見，這樣計算 xy 只需要 3 次乘法（即 895 ac、bd 和(a+b)(c+d)乘法運算）， 896 9. 答：采用基本的二路歸并思路，先求出 a、b 的交集 ab，再求出 c、d 的交集 cd， 最后求出 ab 和 cd 的交集，即為最后的結果，也可以直接采用 4 路歸并方法求解， 897 10. 解：采用類似求求一個整數序列中的最大次大元素的分治法思路，對應的程式如下： 898 #include <stdio.h> 899 #define max(x,y) ((x)>(y)?(x):(y)) 900 #define min(x,y) ((x)<(y)?(x):(y)) 901 902 903 void MaxMin(int a[],int low,int high,int &maxe,int &mine) //求a中最大最小元素 904 { if (low==high) //只有一個元素 905 { maxe=a[low]; 906 mine=a[low]; 907 } 908 else if (low==high-1) //只有兩個元素 909 { maxe=max(a[low],a[high]); 910 mine=min(a[low],a[high]); 911 } 912 else //有兩個以上元素 913 { int mid=(low+high)/2; 914 int lmaxe,lmine; 915 MaxMin(a,low,mid,lmaxe,lmine); 916 int rmaxe,rmine; 917 MaxMin(a,mid+1,high,rmaxe,rmine); 918 maxe=max(lmaxe,rmaxe); 919 mine=min(lmine,rmine); 920 } 921 } 922 void main() 923 { int a[]={4,3,1,2,5}; 924 int n=sizeof(a)/sizeof(a[0]); 925 int maxe,mine; 926 MaxMin(a,0,n-1,maxe,mine); 927 printf("Max=%d, Min=%d\n",maxe,mine); 928 } 929 上述程式的執行結果如圖 1.21 所示， 930 圖 1.21 程式執行結果 931 11. 解：設 f(x，n)=xn，采用分治法求解對應的遞回模型如下： 932 933 f(x，n)=x 當 n=1 934 f(x，n)=f(x，n/2)*f(x，n/2) 當 n 為偶數時 935 f(x，n)=f(x，(n-1)/2)*f(x，(n-1)/2)*x 當 n 為奇數時 936 對應的遞回程式如下： 937 #include <stdio.h> 938 double solve(double x,int n) 939 940 //求x^n 941 { double fv; 942 if (n==1) return x; 943 if (n%2==0) 944 { fv=solve(x,n/2); 945 return fv*fv; 946 } 947 948 else 949 { fv=solve(x,(n-1)/2); 950 return fv*fv*x; 951 } 952 } 953 void main() 954 { double x=2.0; 955 printf("求解結果:\n"); 956 for (int i=1;i<=10;i++) 957 printf(" %g^%d=%g\n",x,i,solve(x,i)); 958 } 959 上述程式的執行結果如圖 1.22 所示， 960 圖 1.22 程式執行結果 961 12. 解：設 f(bt)回傳二叉樹 bt 的高度，對應的遞回模型如下： 962 963 f(bt)=0 964 f(bt)=MAX{f(bt->lchild)，f(bt->rchild)}+1 965 對應的程式如下： 966 #include "Btree.cpp" 967 968 當 bt=NULL 969 其他情況 970 971 //包含二叉樹的基本運算演算法 972 int Height(BTNode *bt) 973 { if (bt==NULL) return 0; 974 int lh=Height(bt->lchild); 975 //求二叉樹bt的高度 976 //子問題1 977 int rh=Height(bt->rchild); //子問題2 978 if (lh>rh) return lh+1; 979 else return rh+1; 980 } 981 void main() //合并 982 { 983 984 985 986 BTNode *bt; 987 Int a[]={5,2,3,4,1,6}; 988 Int b[]={2,3,5,1,4,6}; 989 int n=sizeof(a)/sizeof(a[0]); 990 bt=CreateBTree(a,b,n); 991 992 993 994 //由a和b構造二叉鏈bt 995 printf("二叉樹bt:"); DispBTree(bt); printf("\n"); 996 printf("bt的高度: %d\n",Height(bt)); 997 998 } DestroyBTree(bt); //銷毀樹bt 999 1000 1001 上述程式的執行結果如圖 1.23 所示， 1002 圖 1.23 程式執行結果 1003 13. 解：設 f(bt)回傳二叉樹 bt 中度為 2 的結點個數，對應的遞回模型如下： 1004 1005 f(bt)=0 當 bt=NULL 1006 f(bt)=f(bt->lchild)+f(bt->rchild)+1 若 bt≠NULL 且 bt 為雙分支結點 1007 f(bt)=f(bt->lchild)+f(bt->rchild) 其他情況 1008 對應的演算法如下： 1009 #include "Btree.cpp" //包含二叉樹的基本運算演算法 1010 int Nodes(BTNode *bt) //求 bt 中度為 2 的結點個數 1011 { int n=0; 1012 if (bt==NULL) return 0; 1013 if (bt->lchild!=NULL && bt->rchild!=NULL) 1014 n=1; 1015 return Nodes(bt->lchild)+Nodes(bt->rchild)+n; 1016 } 1017 void main() 1018 { BTNode *bt; 1019 Int a[]={5,2,3,4,1,6}; 1020 Int b[]={2,3,5,1,4,6}; 1021 int n=sizeof(a)/sizeof(a[0]); 1022 bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt 1023 printf("二叉樹bt:"); DispBTree(bt); printf("\n"); 1024 printf("bt中度為2的結點個數: %d\n",Nodes(bt)); 1025 DestroyBTree(bt); //銷毀樹bt 1026 } 1027 上述程式的執行結果如圖 1.24 所示， 1028 圖 1.24 程式執行結果 1029 14. 解：設 f(bt，x)回傳在二叉排序樹 bt 得到的值為 x 結點的地址，若沒有找到回傳空，對應的遞回模型如下： 1030 f(bt，x)=NULL 當 bt=NULL 1031 f(bt，x)=bt 當 bt≠NULL 且 x=bt->data f(bt，x)=f(bt->lchild，x) 當 x>bt->data 1032 1033 f(bt，x)=f(bt->rchild，x) 當 x<bt->data 1034 對應的程式如下： 1035 #include "Btree.cpp" //包含二叉樹的基本運算演算法 1036 BTNode *Search(BTNode *bt,Int x) //在二叉排序樹 bt 查找的值為 x 結點 1037 { if (bt==NULL) return NULL; 1038 if (x==bt->data) return bt; 1039 if (x<bt->data) return Search(bt->lchild,x); 1040 else return Search(bt->rchild,x); 1041 } 1042 void main() 1043 { BTNode *bt; 1044 Int a[]={4,3,2,8,6,7,9}; 1045 Int b[]={2,3,4,6,7,8,9}; 1046 int n=sizeof(a)/sizeof(a[0]); 1047 bt=CreateBTree(a,b,n); //構造一棵二叉排序樹 bt 1048 printf("二叉排序樹 bt:"); DispBTree(bt); printf("\n"); 1049 int x=6; 1050 BTNode *p=Search(bt,x); 1051 if (p!=NULL) 1052 printf("找到結點: %d\n",p->data); 1053 else 1054 printf("沒有找到結點\n",x); 1055 DestroyBTree(bt); //銷毀樹 bt 1056 } 1057 上述程式的執行結果如圖 1.25 所示， 1058 圖 1.25 程式執行結果 1059 Search(bt，x)演算法采用的是減治法，最好的情況是某個結點左右子樹高度大致相同， 其平均執行時間 T(n)如下： 1060 T(n)=1 當 n=1 T(n)=T(n/2)+1 當 n>1 1061 可以推出 T(n)=O(log2n)，其中 n 為二叉排序樹的結點個數， 1062 15. 解：采用二分查找方法，a[i]=i 時表示該元素在有序非重復序列 a 中恰好第 i 大，對于序列 a[low..high]，mid=(low+high)/2，若 a[mid]=mid 表示找到該元素；若 a[mid]>mid 說明右區間的所有元素都大于其位置，只能在左區間中查找；若 a[mid]<mid 說明左區間的所有元素都小于其位置，只能在右區間中查找，對應的程式如下： 1063 #include <stdio.h> 1064 int Search(int a[],int n) //查找使得 a[i]=i 1065 { int low=0,high=n-1,mid; 1066 1067 1068 while (low<=high) 1069 { mid=(low+high)/2; 1070 if (a[mid]==mid) //查找到這樣的元素 1071 return mid; 1072 else if (a[mid]<mid) //這樣的元素只能在右區間中出現 1073 low=mid+1; 1074 else //這樣的元素只能在左區間中出現 1075 high=mid-1; 1076 } 1077 return -1; 1078 } 1079 void main() 1080 { int a[]={-2,-1,2,4,6,8,9}; 1081 int n=sizeof(a)/sizeof(a[0]); 1082 int i=Search(a,n); 1083 printf("求解結果\n"); 1084 if (i!=-1) 1085 printf(" 存在a[%d]=%d\n",i,i); 1086 else 1087 printf(" 不存在\n"); 1088 } 1089 上述程式的執行結果如圖 1.26 所示， 1090 圖 1.26 程式執行結果 1091 16. 解：對于有序序列 a[low..high]，若元素個數少于 3 個，直接查找，若含有更多的元素，將其分為 a[low..mid1-1]、a[mid1+1..mid2-1]、a[mid2+1..high]子序列，對每個子序列遞回查找，演算法的時間復雜度為 O(log3n)，屬于 O(log2n)級別，對應的演算法如下： 1092 #include <stdio.h> 1093 int Search(int a[],int low,int high,int x) //三分查找 1094 1095 return -1; 1096 } 1097 int length=(high-low+1)/3; //每個子序列的長度 1098 int mid1=low+length; 1099 int mid2=high-length; 1100 if (x==a[mid1]) 1101 return mid1; 1102 else if (x<a[mid1]) 1103 return Search(a,low,mid1-1,x); 1104 else if (x==a[mid2]) 1105 return mid2; 1106 else if (x<a[mid2]) 1107 return Search(a,mid1+1,mid2-1,x); 1108 else 1109 return Search(a,mid2+1,high,x); 1110 } 1111 void main() 1112 { int a[]={1,3,5,7,9,11,13,15}; 1113 int n=sizeof(a)/sizeof(a[0]); 1114 printf("求解結果\n"); 1115 int x=13; 1116 int i=Search(a,0,n-1,x); 1117 if (i!=-1) 1118 printf(" a[%d]=%d\n",i,x); 1119 else 1120 printf(" 不存在%d\n",x); 1121 int y=10; 1122 int j=Search(a,0,n-1,y); 1123 if (j!=-1) 1124 printf(" a[%d]=%d\n",j,y); 1125 else 1126 printf(" 不存在%d\n",y); 1127 } 1128 上述程式的執行結果如圖 1.27 所示， 1129 圖 1.27 程式執行結果 1130 17. 解：設 f(n)表示 n 的不同分解式個數，有： f(1)=1，作為遞回出口 1131 f(2)=1，分解式為：2=2 1132 f(3)=1， 分 解 式 為 ：3=3 f(4)=2，分解式為：4=4，4=2*2 1133 1134 1135 f(6)=3，分解式為：6=6，6=2*3，6=3*2，即 f(6)=f(1)+f(2)+f(3) 1136 以此類推，可以看出 f(n)為 n 的所有因數的不同分解式個數之和，即 f(n)= 1137 ∑ ??(??/??)，對應的程式如下： 1138 #include <stdio.h> #define MAX 101 1139 int solve(int n) //求 n 的不同分解式個數 1140 { if (n==1) return 1; 1141 else 1142 { int sum=0; 1143 for (int i=2;i<=n;i++) 1144 if (n%i==0) 1145 sum+=solve(n/i); 1146 return sum; 1147 } 1148 } 1149 void main() 1150 { int n=12; 1151 int ans=solve(n); 1152 printf("結果: %d\n",ans); 1153 } 1154 上述程式的執行結果如圖 1.28 所示， 1155 圖 1.28 程式執行結果 1156 18. 解：對應的并行演算法如下： 1157 int Sum(int a[],int s,int t,int p,int i) //處理器i執行求和 1158 { int j,s=0; 1159 for (j=s;j<=t;j++) 1160 s+=a[j]; 1161 return s; 1162 } 1163 int ParaSum(int a[],int s,int t,int p,int i) 1164 { int sum=0,j,k=0,sj; 1165 for (j=0;j<p;j++) //for回圈的各個子問題并行執行 1166 { sj=Sum(a,k,k+n/p-1,p,j); 1167 k+=n/p; 1168 } 1169 sum+=sj; 1170 return sum; 1171 } 1172 每個處理器的執行時間為O(n/p)，同步開銷為O(p)，所以該演算法的時間復雜度為 1173 O(n/p+p)， 1174 1175 1.4 第 4 章─蠻力法 1176 1.4.1 練習題 1177 1. 簡要比較蠻力法和分治法， 1178 2. 在采用蠻力法求解時什么情況下使用遞回？ 1179 3. 考慮下面這個演算法，它求的是陣列 a 中大小相差最小的兩個元素的差，請對這個演算法做盡可能多的改進， 1180 #define INF 99999 1181 #define abs(x) (x)<0?-(x):(x) //求絕對值宏 1182 int Mindif(int a[],int n) 1183 { int dmin=INF; 1184 for (int i=0;i<=n-2;i++) 1185 for (int j=i+1;j<=n-1;j++) 1186 { int temp=abs(a[i]-a[j]); 1187 if (temp<dmin) 1188 dmin=temp; 1189 } 1190 return dmin; 1191 } 1192 4. 給定一個整數陣列 A=(a0，a1，…an-1)，若 i<j 且 ai>aj，則<ai，aj>就為一個逆序對，例如陣列（3，1，4，5，2）的逆序對有<3，1>，<3，2>，<4，2>，<5，2>，設計一個演算法采用蠻力法求 A 中逆序對的個數即逆序數， 1193 5. 對于給定的正整數 n（n>1）, 采用蠻力法求 1!+2!+…+n!，并改進該演算法提高效率， 1194 6. 有一群雞和一群兔，它們的只數相同，它們的腳數都是三位數，且這兩個三位數的各位數字只能是 0、1、2、3、4、5，設計一個演算法用蠻力法求雞和兔的只數各是多 1195 少？它們的腳數各是多少？ 1196 7. 有一個三位數，個位數字比百位數字大，而百位數字又比十位數字大，并且各位數字之和等于各位數字相乘之積，設計一個演算法用窮舉法求此三位數， 1197 8. 某年級的同學集體去公園劃船，如果每只船坐 10 人，那么多出 2 個座位；如果每只船多坐 2 人，那么可少租 1 只船，設計一個演算法用蠻力法求該年級的最多人數？ 1198 9. 已知：若一個合數的質因數分解式逐位相加之和等于其本身逐位相加之和，則稱這 個 數 為 Smith 數 ， 如 4937775=3*5*5*65837， 而 3+5+5+6+5+8+3+7=42， 4+9+3+7+7+7+5=42，所以 4937775 是 Smith 數，求給定一個正整數 N，求大于 N 的最小Smith 數， 1199 輸入：若干個 case，每個 case 一行代表正整數 N，輸入 0 表示結束輸出：大于 N 的最小 Smith 數 1200 輸入樣例： 1201 4937774 1202 0 1203 樣例輸出： 1204 1205 1206 4937775 1207 10. 求解涂棋盤問題，小易有一塊 n*n 的棋盤，棋盤的每一個格子都為黑色或者白色，小易現在要用他喜歡的紅色去涂畫棋盤，小易會找出棋盤中某一列中擁有相同顏色的最大的區域去涂畫，幫助小易算算他會涂畫多少個棋格， 1208 輸入描述：輸入資料包括 n+1 行：第一行為一個整數 n（1≤ n≤50），即棋盤的大小，接下來的 n 行每行一個字串表示第 i 行棋盤的顏色，'W'表示白色，'B'表示黑色， 1209 輸出描述：輸出小易會涂畫的區域大小，輸入例子： 1210 3 1211 BWW BBB BWB 1212 輸出例子： 1213 3 1214 11. 給定一個含 n（n>1）個整數元素的 a，所有元素不相同，采用蠻力法求出 a 中所有元素的全排列， 1215 1.4.2 練習題參考答案 1216 1. 答：蠻力法是一種簡單直接地解決問題的方法，適用范圍廣，是能解決幾乎所有問題的一般性方法，常用于一些非常基本、但又十分重要的演算法（排序、查找、矩陣乘法和字串匹配等），蠻力法主要解決一些規模小或價值低的問題，可以作為同樣問題的更高效演算法的一個標準，而分治法采用分而治之思路，把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題直到問題解決，分治法在求解問題 時，通常性能比蠻力法好， 1217 2. 答：如果用蠻力法求解的問題可以分解為若干個規模較小的相似子問題，此時可以采用遞回來實作演算法， 1218 3. 解：上述演算法的時間復雜度為 O(n2)，采用的是最基本的蠻力法，可以先對 a 中元素遞增排序，然后依次比較相鄰元素的差，求出最小差，改進后的演算法如下： 1219 #include <stdio.h> #include <algorithm> using namespace std; 1220 int Mindif1(int a[],int n) 1221 { sort(a,a+n); //遞增排序 1222 int dmin=a[1]-a[0]; 1223 for (int i=2;i<n;i++) 1224 { int temp=a[i]-a[i-1]; 1225 if (temp<dmin) 1226 dmin=temp; 1227 } 1228 return dmin; 1229 } 1230 1231 上述演算法的主要時間花費在排序上，演算法的時間復雜度為 O(nlog2n)， 1232 4. 解：采用兩重回圈直接判斷是否為逆序對，演算法的時間復雜度為 O(n2)，比第 3 章實驗 3 演算法的性能差，對應的演算法如下： 1233 int solve(int a[],int n) //求逆序數 1234 { int ans=0; 1235 for (int i=0;i<n-1;i++) 1236 for (int j=i+1;j<n;j++) 1237 if (a[i]>a[j]) 1238 ans++; 1239 return ans; 1240 } 1241 5. 解：直接采用蠻力法求解演算法如下： 1242 long f(int n) //求n! 1243 { long fn=1; 1244 for (int i=2;i<=n;i++) 1245 fn=fn*i; 1246 return fn; 1247 } 1248 long solve(int n) //求1!+2!+…+n! 1249 { long ans=0; 1250 for (int i=1;i<=n;i++) 1251 ans+=f(i); 1252 return ans; 1253 } 1254 實際上，f(n)=f(n-1)*n，f(1)=1，在求 f(n)時可以利用 f(n-1)的結果，改進后的演算法如 1255 下： 1256 long solve1(int n) //求1!+2!+…+n! 1257 { long ans=0; 1258 long fn=1; 1259 for (int i=1;i<=n;i++) 1260 { fn=fn*i; 1261 ans+=fn; 1262 } 1263 return ans; 1264 } 1265 6. 解：設雞腳數為 y=abc，兔腳數為 z=def，有 1≤a，d≤5，0≤b，c，e，f≤5，采 1266 用 6 重回圈，求出雞只數 x1=y/2（y 是 2 的倍數），兔只數 x2=z/4（z 是 4 的倍數），當 1267 x1=x2 時輸出結果，對應的程式如下： 1268 #include <stdio.h> 1269 void solve() 1270 { int a,b,c,d,e,f; 1271 int x1,x2,y,z; 1272 for (a=1;a<=5;a++) 1273 for (b=0;b<=5;b++) 1274 for (c=0;c<=5;c++) 1275 1276 1277 for (d=1;d<=5;d++) 1278 for (e=0;e<=5;e++) 1279 for (f=0;f<=5;f++) 1280 { y=a*100+b*10+c; //雞腳數 1281 z=d*100+e*10+f; //兔腳數 1282 if (y%2!=0 || z%4!=0) 1283 continue; 1284 x1=y/2; //雞只數 1285 x2=z/4; //兔只數 1286 if (x1==x2) 1287 printf(" 雞只數:%d,兔只數:%d,雞腳數:%d, 1288 兔腳數:%d\n",x1,x2,y,z); 1289 } 1290 } 1291 void main() 1292 { printf("求解結果\n"); 1293 solve(); 1294 } 1295 上述程式的執行結果如圖 1.29 所示， 1296 圖 1.29 程式執行結果 1297 7. 解：設該三位數為 x=abc，有 1≤a≤9，0≤b，c≤9，滿足 c>a，a>b， a+b+c=a*b*c，對應的程式如下： 1298 #include <stdio.h> 1299 void solve() 1300 { int a,b,c; 1301 for (a=1;a<=9;a++) 1302 for (b=0;b<=9;b++) 1303 for (c=0;c<=9;c++) 1304 { if (c>a && a>b && a+b+c==a*b*c) 1305 printf(" %d%d%d\n",a,b,c); 1306 } 1307 } 1308 void main() 1309 1310 { printf("求解結果\n"); 1311 solve(); 1312 } 1313 上述程式的執行結果如圖 1.30 所示， 1314 圖 1.30 程式執行結果 1315 8. 解：設該年級的人數為 x，租船數為 y，因為每只船坐 10 人正好多出 2 個座位，則x=10*y-2；因為每只船多坐 2 人即 12 人時可少租 1 只船（沒有說恰好全部座位占滿），有 x+z=12*(y-1)，z 表示此時空出的座位，顯然 z<12，讓 y 從 1 到 100（實際上 y 取更大范圍的結果是相同的）、z 從 0 到 11 列舉，求出最大的 x 即可，對應的程式如下： 1316 #include <stdio.h> 1317 int solve() 1318 { int x,y,z; 1319 for (y=1;y<=100;y++) 1320 for (z=0;z<12;z++) 1321 if (10*y-2==12*(y-1)-z) 1322 x=10*y-2; 1323 return x; 1324 } 1325 void main() 1326 { printf("求解結果\n"); 1327 printf(" 最多人數:%d\n",solve()); 1328 } 1329 上述程式的執行結果如圖 1.31 所示， 1330 圖 1.31 程式執行結果 1331 9. 解：采用蠻力法求出一個正整數 n 的各位數字和 sum1，以及 n 的所有質因數的數字和 sum2，若 sum1=sum2，即為 Smitch 數，從用戶輸入的 n 開始列舉，若是 Smitch 1332 數，輸出，本次結束，否則 n++繼續查找大于 n 的最小 Smitch 數，對應的完整程式如下： 1333 #include <stdio.h> 1334 int Sum(int n) //求n的各位數字和 1335 { int sum=0; 1336 while (n>0) 1337 1338 1339 { sum+=n%10; 1340 n=n/10; 1341 } 1342 return sum; 1343 } 1344 bool solve(int n) //判斷n是否為Smitch數 1345 { int m=2; 1346 int sum1=Sum(n); 1347 int sum2=0; 1348 while (n>=m) 1349 { if (n%m==0) //找到一個質因數m 1350 { n=n/m; 1351 sum2+=Sum(m); 1352 } 1353 else 1354 m++; 1355 } 1356 if (sum1==sum2) 1357 return true; 1358 else 1359 return false; 1360 } 1361 void main() 1362 { int n; 1363 while (true) 1364 { scanf("%d",&n); 1365 if (n==0) break; 1366 while (!solve(n)) 1367 n++; 1368 printf("%d\n",n); 1369 } 1370 } 1371 10. 解：采用蠻力法，統計每一列相鄰相同顏色的棋格個數 countj，在 countj 中求最大值，對應的程式如下： 1372 #include <stdio.h> #define MAXN 51 1373 //問題表示int n; 1374 char board[MAXN][MAXN]; 1375 int getMaxArea() //蠻力法求解演算法 1376 { int maxArea=0; 1377 for (int j=0; j<n; j++) 1378 { int countj=1; 1379 for (int i=1; i<n; i++) //統計第j列中相同顏色相鄰棋格個數 1380 { if (board[i][j]==board[i-1][j]) 1381 countj++; 1382 else 1383 countj=1; 1384 } 1385 1386 if (countj>maxArea) 1387 maxArea=countj; 1388 } 1389 return maxArea; 1390 } 1391 int main() 1392 { scanf("%d",&n); 1393 for (int i=0;i<n;i++) 1394 scanf("%s",board[i]); 1395 printf("%d\n",getMaxArea()); 1396 return 0; 1397 } 1398 11. 解：與《教程》中求全排列類似，但需要將求 1～n 的全排列改為按下標 0～n-1 1399 求 a 的全排列（下標從 0 開始），采用非遞回的程式如下： 1400 #include <stdio.h> #include <vector> using namespace std; 1401 vector<vector<int> > ps; //存放全排列 1402 void Insert(vector<int> s,int a[],int i,vector<vector<int> > &ps1) 1403 //在每個集合元素中間插入i得到ps1 1404 { vector<int> s1; 1405 vector<int>::iterator it; 1406 for (int j=0;j<=i;j++) //在s(含i個整數)的每個位置插入a[i] 1407 { s1=s; 1408 it=s1.begin()+j; //求出插入位置 1409 s1.insert(it,a[i]); //插入整數a[i] 1410 ps1.push_back(s1); //添加到ps1中 1411 } 1412 } 1413 void Perm(int a[],int n) //求a[0..n-1]的所有全排列 1414 { vector<vector<int> > ps1; //臨時存放子排列 1415 vector<vector<int> >::iterator it; //全排列迭代器 1416 vector<int> s,s1; 1417 s.push_back(a[0]); 1418 ps.push_back(s); //添加{a[0]}集合元素 1419 for (int i=1;i<n;i++) //回圈添加a[1]～a[n-1] 1420 { ps1.clear(); //ps1存放插入a[i]的結果 1421 for (it=ps.begin();it!=ps.end();++it) 1422 Insert(*it,a,i,ps1); //在每個集合元素中間插入a[i]得到ps1 1423 ps=ps1; 1424 } 1425 } 1426 void dispps() //輸出全排列 ps 1427 { vector<vector<int> >::reverse_iterator it; //全排列的反向迭代器 1428 vector<int>::iterator sit; //排列集合元素迭代器 1429 for (it=ps.rbegin();it!=ps.rend();++it) 1430 { for (sit=(*it).begin();sit!=(*it).end();++sit) 1431 printf("%d",*sit); 1432 printf(" "); 1433 1434 1435 } 1436 printf("\n"); 1437 } 1438 void main() 1439 { int a[]={2,5,8}; 1440 int n=sizeof(a)/sizeof(a[0]); 1441 printf("a[0～%d]的全排序如下:\n ",n-1); 1442 Perm(a,n); 1443 dispps(); 1444 } 1445 上述程式的執行結果如圖 1.32 所示， 1446 圖 1.32 程式執行結果 1447 1.5 第 5 章─回溯法 1448 1.5.1 練習題 1449 1. 回溯法在問題的解空間樹中，按（ ）策略，從根結點出發搜索解空間樹， 1450 A. 廣度優先 B.活結點優先 C.擴展結點優先 D.深度優先 1451 2. 關于回溯法以下敘述中不正確的是（ ）， 1452 A.回溯法有“通用解題法”之稱，它可以系統地搜索一個問題的所有解或任意解 B.回溯法是一種既帶系統性又帶有跳躍性的搜索演算法 1453 C.回溯演算法需要借助佇列這種結構來保存從根結點到當前擴展結點的路徑 1454 D.回溯演算法在生成解空間的任一結點時，先判斷該結點是否可能包含問題的解，如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向祖先結點回溯 1455 3. 回溯法的效率不依賴于下列哪些因素（ ）， 1456 A. 確定解空間的時間 B.滿足顯約束的值的個數 1457 C.計算約束函式的時間 D.計算限界函式的時間 1458 4. 下面（ ）函式是回溯法中為避免無效搜索采取的策略， 1459 A.遞回函式 B.剪枝函式 C.亂數函式 D.搜索函式5.回溯法的搜索特點是什么？ 1460 6. 用回溯法解 0/1 背包問題時，該問題的解空間是何種結構？用回溯法解流水作業調度問題時，該問題的解空間是何種結構？ 1461 7. 對于遞增序列 a[]={1，2，3，4，5}，采用例 5.4 的回溯法求全排列，以 1、2 開頭的排列一定最先出現嗎？為什么？ 1462 8. 考慮 n 皇后問題，其解空間樹為由 1、2、…、n 構成的 n!種排列所組成，現用回 1463 1464 溯法求解，要求： 1465 （1） 通過解搜索空間說明 n=3 時是無解的， 1466 （2） 給出剪枝操作， 1467 （3） 最壞情況下在解空間樹上會生成多少個結點？分析演算法的時間復雜度， 1468 9. 設計一個演算法求解簡單裝載問題，設有一批集裝箱要裝上一艘載重量為 W 的輪船，其中編號為 i（0≤i≤n-1）的集裝箱的重量為 wi，現要從 n 個集裝箱中選出若干裝上輪船，使它們的重量之和正好為 W，如果找到任一種解回傳 true，否則回傳 false， 1469 10. 給定若干個正整數a0、a0 、…、an-1 ，從中選出若干數，使它們的和恰好為k， 要求找選擇元素個數最少的解， 1470 11. 設計求解有重復元素的排列問題的演算法，設有 n 個元素 a[]={a0，a1，…，an-1)， 其中可能含有重復的元素，求這些元素的所有不同排列，如 a[]={1，1，2}，輸出結果是 1471 （1，1，2)，（1，2，1），（2，1，1）， 1472 12. 采用遞回回溯法設計一個演算法求1～n的n個整數中取出m個元素的排列，要求每個元素最多只能取一次，例如，n=3，m=2的輸出結果是（1，2），（1，3），（2，1）， 1473 （2，3），（3，1），（3，2）， 1474 13. 對于n皇后問題，有人認為當n為偶數時，其解具有對稱性，即n皇后問題的解個數恰好為n/2皇后問題的解個數的2倍，這個結論正確嗎？請撰寫回溯法程式對n=4、6、 1475 8、10的情況進行驗證， 1476 14. 給定一個無向圖，由指定的起點前往指定的終點，途中經過所有其他頂點且只經過一次，稱為哈密頓路徑，閉合的哈密頓路徑稱作哈密頓回路（Hamiltonian cycle），設計一個回溯演算法求無向圖的所有哈密頓回路， 1477 1.5.2 練習題參考答案 1478 1. 答：D， 1479 2. 答：回溯演算法是采用深度優先遍歷的，需要借助系統堆疊結構來保存從根結點到當前擴展結點的路徑，答案為 C， 1480 3. 答：回溯法解空間是虛擬的，不必確定整個解空間，答案為 A， 1481 4. 答：B， 1482 5. 答：回溯法在解空間樹中采用深度優先遍歷方式進行解搜索，即用約束條件和限界函式考察解向量元素 x[i]的取值，如果 x[i]是合理的就搜索 x[i]為根結點的子樹，如果x[i]取完了所有的值，便回溯到 x[i-1]， 1483 6. 答：用回溯法解 0/1 背包問題時，該問題的解空間是子集樹結構，用回溯法解流水作業調度問題時，該問題的解空間是排列樹結構， 1484 7. 答：是的，對應的解空間是一棵排列樹，如圖 1.33 所示給出前面 3 層部分，顯然最先產生的排列是從 G 結點擴展出來的葉子結點，它們就是以 1、2 開頭的排列， 1485 1486 1487 1488 1489 圖 1.33 部分解空間樹 1490 8. 答：（1）n=3 時的解搜索空間如圖 1.34 所示，不能得到任何葉子結點，所有無解， 1491 （2） 剪枝操作是任何兩個皇后不能同行、同列和同兩條對角線， 1492 （3） 最壞情況下每個結點擴展 n 個結點，共有 nn 個結點，演算法的時間復雜度為 1493 O(nn)， 1494 1495 1496 1497 圖 1.34 3 皇后問題的解搜索空間 1498 9. 解：用陣列 w[0..n-1]存放 n 個集裝箱的重量，采用類似判斷子集和是否存在解的方法求解，對應完整的求解程式如下： 1499 #include <stdio.h> 1500 #define MAXN 20 //最多集裝箱個數 1501 //問題表示 1502 int n=5,W; 1503 int w[]={2,9,5,6,3}; 1504 int count; //全域變數，累計解個數 1505 void dfs(int tw,int rw,int i) //求解簡單裝載問題 1506 { if (i>=n) //找到一個葉子結點 1507 1508 1509 1510 1511 1512 1513 1514 bool solve() //判斷簡單裝載問題是否存在解 1515 1516 1517 { 1518 1519 1520 count=0; 1521 int rw=0; 1522 for (int j=0;j<n;j++) 1523 rw+=w[j]; 1524 1525 //求所有集裝箱重量和rw 1526 dfs(0,rw,0); //i從0開始 1527 if (count>0) 1528 return true; 1529 else 1530 return false; 1531 } 1532 void main() 1533 { printf("求解結果\n"); 1534 W=4; 1535 printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); 1536 W=10; 1537 printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); 1538 W=12; 1539 printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); 1540 W=21; 1541 printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); 1542 } 1543 本程式執行結果如圖 1.35 所示， 1544 圖 1.35 程式執行結果 1545 10. 解：這是一個典型的解空間為子集樹的問題，采用子集樹的回溯演算法框架，當找到一個解后通過選取的元素個數進行比較求最優解 minpath，對應的完整程式如下： 1546 #include <stdio.h> #include <vector> using namespace std; 1547 //問題表示 1548 int a[]={1,2,3,4,5}; //設定為全域變數 1549 int n=5,k=9; 1550 vector<int> minpath; //存放最優解 1551 //求解結果表示 1552 int minn=n; //最多選擇n個元素 1553 void disppath() //輸出一個解 1554 { printf(" 選擇的元素:"); 1555 for (int j=0;j<minpath.size();j++) 1556 printf("%d ",minpath[j]); 1557 printf("元素個數=%d\n",minn); 1558 } 1559 1560 1561 void dfs(vector<int> path,int sum,int start) //求解演算法 1562 { if (sum==k) //如果找到一個解，不一定到葉子結點 1563 { if (path.size()<minn) 1564 { minn=path.size(); 1565 minpath=path; 1566 } 1567 return; 1568 } 1569 if (start>=n) return; //全部元素找完，回傳 1570 dfs(path,sum,start+1); //不選擇a[start] 1571 path.push_back(a[start]); //選擇a[start] 1572 dfs(path,sum+a[start],start+1); 1573 } 1574 void main() 1575 { vector<int> path; //path存放一個子集 1576 dfs(path,0,0); 1577 printf("最優解:\n"); 1578 disppath(); 1579 } 1580 上述程式的執行結果如圖 1.36 所示， 1581 圖 1.36 程式執行結果 1582 11. 解：在回溯法求全排列的基礎上，增加元素的重復性判斷，例如，對于 a[]={1， 1583 1，2}，不判斷重復性時輸出（1，1，2），（1，2，1），（1，1，2），（1，2，1）， 1584 （2，1，1），（2，1，1），共 6 個，有 3 個是重復的，重復性判斷是這樣的，對于在擴展 a[i]時，僅僅將與 a[i..j-1]沒有出現的元素 a[j]交換到 a[i]的位置，如果出現，對應的排列已經在前面求出了，對應的完整程式如下： 1585 #include <stdio.h> 1586 bool ok(int a[],int i,int j) //ok用于判別重復元素 1587 { if (j>i) 1588 { for(int k=i;k<j;k++) 1589 if (a[k]==a[j]) 1590 return false; 1591 } 1592 return true; 1593 } 1594 void swap(int &x,int &y) //交換兩個元素 1595 { int tmp=x; 1596 x=y; y=tmp; 1597 } 1598 void dfs(int a[],int n,int i) //求有重復元素的排列問題 1599 { if (i==n) 1600 1601 1602 1603 1604 1605 { 1606 1607 1608 } for(int j=0;j<n;j++) 1609 printf("%3d",a[j]); printf("\n"); 1610 else 1611 { for (int j=i;j<n;j++) 1612 if (ok(a,i,j)) //選取與a[i..j-1]不重復的元素a[j] 1613 { swap(a[i],a[j]); 1614 dfs(a,n,i+1); 1615 swap(a[i],a[j]); 1616 } 1617 } 1618 } 1619 void main() 1620 { int a[]={1,2,1,2}; 1621 int n=sizeof(a)/sizeof(a[0]); 1622 printf("序列("); 1623 for (int i=0;i<n-1;i++) 1624 printf("%d ",a[i]); 1625 printf("%d)的所有不同排列:\n",a[n-1]); 1626 dfs(a,n,0); 1627 } 1628 上述程式的執行結果如圖 1.37 所示， 1629 圖 1.37 程式執行結果 1630 12. 解：采用求全排列的遞回框架，選取的元素個數用 i 表示（i 從 1 開始），當 i>m時達到一個葉子結點，輸出一個排列，為了避免重復，用 used 陣列實作，used[i]=0 表示沒有選擇整數 i，used[i]=1 表示已經選擇整數 i，對應的完整程式如下： 1631 #include <stdio.h> #include <string.h> #define MAXN 20 #define MAXM 10 1632 int m,n; 1633 1634 1635 1636 1637 } 1638 else 1639 { 1640 for (int j=1;j<=n;j++) 1641 1642 1643 { if (!used[j]) 1644 { used[j]=true; //修改used[i] 1645 x[i]=j; //x[i]選擇j 1646 dfs(i+1); //繼續搜索排列的下一個元素 1647 1648 1649 1650 1651 } 1652 1653 1654 } 1655 1656 } 1657 } used[j]=false; //回溯：恢復used[i] 1658 voi 1659 { 1660 d main() 1661 n=4,m=2; 1662 memset(used,0,sizeof(used)); 1663 1664 //初始化為0 1665 printf("n=%d,m=%d的求解結果\n",n,m); 1666 dfs(1); //i從1開始 1667 } 1668 上述程式的執行結果如圖 1.38 所示， 1669 圖 1.38 程式執行結果 1670 13. 解：這個結論不正確，驗證程式如下： 1671 #include <stdio.h> #include <stdlib.h> #define MAXN 10 1672 int q[MAXN]; 1673 bool place(int i) //測驗第i行的q[i]列上能否擺放皇后 1674 { int j=1; 1675 if (i==1) return true; 1676 while (j<i) //j=1～i-1是已放置了皇后的行 1677 { if ((q[j]==q[i]) || (abs(q[j]-q[i])==abs(j-i))) 1678 //該皇后是否與以前皇后同列，位置(j,q[j])與(i,q[i])是否同對角線 1679 return false; 1680 j++; 1681 } 1682 return true; 1683 } 1684 1685 1686 int Queens(int n) //求n皇后問題的解個數 1687 { int count=0,k; //計數器初始化 1688 int i=1; //i為當前行 1689 q[1]=0; //q[i]為皇后i的列號 1690 while (i>0) 1691 { q[i]++; //移到下一列 1692 1693 1694 1695 while (q[i]<=n && !place(i)) 1696 q[i]++; 1697 if (q[i]<=n) 1698 { if (i==n) 1699 count++; //找到一個解計數器count加1 1700 else 1701 { 1702 i++;; q[i]=0; 1703 } 1704 } 1705 else i--; //回溯 1706 } 1707 return count; 1708 } 1709 void main() 1710 { printf("驗證結果如下:\n"); 1711 for (int n=4;n<=10;n+=2) 1712 if (Queens(n)==2*Queens(n/2)) 1713 printf(" n=%d: 正確\n",n); 1714 else 1715 printf(" n=%d: 錯誤\n",n); 1716 } 1717 上述程式的執行結果如圖1.39所示，從執行結果看出結論是不正確的， 1718 圖 1.39 程式執行結果 1719 14. 解：假設給定的無向圖有 n 個頂點（頂點編號從 0 到 n-1），采用鄰接矩陣陣列 a 1720 （0/1 矩陣）存放，求從頂點 v 出發回到頂點 v 的哈密頓回路，采用回溯法，解向量為x[0..n]，x[i]表示第 i 步找到的頂點編號（i=n-1 時表示除了起點 v 外其他頂點都查找了），初始時將起點 v 存放到 x[0]，i 從 1 開始查找，i>0 時回圈：為 x[i]找到一個合適的頂點， 當 i=n-1 時，若頂點 x[i]到頂點 v 有邊對應一個解；否則繼續查找下一個頂點，如果不能為 x[i]找到一個合適的頂點，則回溯，采用非遞回回溯框架（與《教程》中求解 n 皇后問題的非遞回回溯框架類似）的完整程式如下： 1721 #include <stdio.h> #define MAXV 10 1722 1723 1724 //求解問題表示 1725 int n=5; //圖中頂點個數 1726 int a[MAXV][MAXV]={{0,1,1,1,0},{1,0,0,1,1},{1,0,0,0,1},{1,1,0,0,1},{0,1,1,1,0}}; 1727 //鄰接矩陣陣列 1728 //求解結果表示int x[MAXV]; int count; 1729 void dispasolution() //輸出一個解路徑 1730 { for (int i=0;i<=n-1;i++) 1731 printf("(%d,%d) ",x[i],x[i+1]); 1732 printf("\n"); 1733 } 1734 bool valid(int i) //判斷頂點第i個頂點x[i]的有效性 1735 { if (a[x[i-1]][x[i]]!=1) //x[i-1]到x[i]沒有邊，回傳false 1736 return false; 1737 for (int j=0;j<=i-1;j++) 1738 if (x[i]==x[j]) //頂點i重復出現，回傳false 1739 return false; 1740 return true; 1741 } 1742 void Hamiltonian(int v) //求從頂點v出發的哈密頓回路 1743 { x[0]=v; //存放起點 1744 int i=1; 1745 x[i]=-1; //從頂點-1+1=0開始試探 1746 while (i>0) //尚未回溯到頭，回圈 1747 1748 { x[i]++; 1749 while (!valid(i) && x[i]<n) 1750 x[i]++; //試探一個頂點x[i] 1751 if (x[i]<n) //找到一個有效的頂點x[i] 1752 { if (i==n-1) //達到葉子結點 1753 { if (a[x[i]][v]==1) 1754 { x[n]=v; //找到一個解 1755 printf(" 第%d個解: ",count++); 1756 dispasolution(); 1757 } 1758 } 1759 else 1760 { 1761 i++; x[i]=-1; 1762 } 1763 } 1764 else 1765 i--; //回溯 1766 } 1767 } 1768 void main() 1769 { printf("求解結果\n"); 1770 for (int v=0;v<n;v++) 1771 { printf(" 從頂點%d出發的哈密頓回路:\n",v); 1772 count=1; 1773 1774 Hamiltonian(v); //從頂點v出發 1775 } 1776 } 1777 上述程式對如圖 1.40 所示的無向圖求從每個頂點出發的哈密頓回路，程式執行結果如圖 1.41 所示， 1778 1779 圖 1.40 一個無向圖 1780 圖 1.41 程式執行結果 1781 1.6 第 6 章─分枝限界法 1782 1.6.1 練習題 1783 1. 分枝限界法在問題的解空間樹中，按（ ）策略，從根結點出發搜索解空間樹， 1784 A. 廣度優先 B.活結點優先 C.擴展結點優先 D. 深度優先 1785 2. 常見的兩種分枝限界法為（ ）， 1786 A. 廣度優先分枝限界法與深度優先分枝限界法 1787 1788 1789 B. 佇列式（FIFO）分枝限界法與堆疊式分枝限界法C.排列樹法與子集樹法 1790 D.佇列式（FIFO）分枝限界法與優先佇列式分枝限界法 1791 3. 分枝限界法求解 0/1 背包問題時，活結點表的組織形式是（ ），A.小根堆 B.大根堆 C.堆疊 D.陣列 1792 4. 采用最大效益優先搜索方式的演算法是（ ）， 1793 A. 分支界限法 B.動態規劃法 C.貪心法 D.回溯法 1794 5. 優先佇列式分枝限界法選取擴展結點的原則是（ ）， 1795 A. 先進先出 B.后進先出 C.結點的優先級 D.隨機 1796 6. 簡述分枝限界法的搜索策略， 1797 7. 有一個 0/1 背包問題，其中 n=4，物品重量為（4，7，5，3），物品價值為（40， 1798 42，25，12），背包最大載重量 W=10，給出采用優先佇列式分枝限界法求最優解的程序， 1799 8. 有一個流水作業調度問題，n=4，a[]={5，10，9，7}，b[]={7，5，9，8}，給出采用優先佇列式分枝限界法求一個解的程序， 1800 9. 有一個含 n 個頂點（頂點編號為 0～n-1）的帶權圖，采用鄰接矩陣陣列 A 表示， 采用分枝限界法求從起點 s 到目標點 t 的最短路徑長度，以及具有最短路徑長度的路徑條數， 1801 10. 采用優先佇列式分枝限界法求解最優裝載問題，給出以下裝載問題的求解程序和結果：n=5，集裝箱重量為 w=（5，2，6，4，3），限重為 W=10，在裝載重量相同時，最優裝載方案是集裝箱個數最少的方案， 1802 1.6.2 練習題參考答案 1803 1. 答：A， 1804 2. 答：D， 1805 3. 答：B， 1806 4. 答：A， 1807 5. 答：C， 1808 6. 答：分枝限界法的搜索策略是廣度優先遍歷，通過限界函式可以快速找到一個解或者最優解， 1809 7. 答：求解程序如下： 1810 （1）根結點 1 進隊，對應結點值：e.i=0，e.w=0，e.v=0，e.ub=76，x:[0，0，0，0]， 1811 （2） 出隊結點 1：左孩子結點 2 進隊，對應結點值：e.no=2，e.i=1，e.w=4， e.v=40，e.ub=76，x:[1，0，0，0]；右孩子結點 3 進隊，對應結點值：e.no=3，e.i=1， e.w=0，e.v=0，e.ub=57，x:[0，0，0，0]， 1812 （3） 出隊結點 2：左孩子超重；右孩子結點 4 進隊，對應結點值：e.no=4，e.i=2， e.w=4，e.v=40，e.ub=69，x:[1，0，0，0]， 1813 （4） 出隊結點 4：左孩子結點 5 進隊，對應結點值：e.no=5，e.i=3，e.w=9， e.v=65，e.ub=69，x:[1，0，1，0]；右孩子結點 6 進隊，對應結點值：e.no=6，e.i=3， e.w=4，e.v=40，e.ub=52，x:[1，0，0，0]， 1814 1815 （5） 出隊結點 5：產生一個解，maxv= 65，bestx:[1，0，1，0]， 1816 （6） 出隊結點 3：左孩子結點 8 進隊，對應結點值：e.no=8，e.i=2，e.w=7， e.v=42，e.ub=57，x:[0，1，0，0]；右孩子結點 9 被剪枝， 1817 （7） 出隊結點 8：左孩子超重；右孩子結點 10 被剪枝， 1818 （8） 出隊結點 6：左孩子結點 11 超重；右孩子結點 12 被剪枝， 1819 （9） 佇列空，演算法結束，產生的最優解：maxv= 65，bestx:[1，0，1，0]， 1820 8. 答：求解程序如下： 1821 （1）根結點 1 進隊，對應結點值：e.i=0，e.f1=0，e.f2=0，e.lb=29， x：[0，0，0， 1822 1823 0]， 1824 1825 （2） 出隊結點 1：擴展結點如下： 1826 進隊（j=1）：結點 2，e.i=1，e.f1=5，e.f2=12，e.lb=27，x：[1，0，0，0]，進隊（j=2）：結點 3，e.i=1，e.f1=10，e.f2=15，e.lb=34，x：[2，0，0，0]，進隊（j=3）：結點 4，e.i=1，e.f1=9，e.f2=18，e.lb=29，x：[3，0，0，0]，進隊（j=4）：結點 5，e.i=1，e.f1=7，e.f2=15，e.lb=28，x：[4，0，0，0]， 1827 （3） 出隊結點 2：擴展結點如下： 1828 進隊（j=2）：結點 6，e.i=2，e.f1=15，e.f2=20，e.lb=32，x：[1，2，0，0]，進隊（j=3）：結點 7，e.i=2，e.f1=14，e.f2=23，e.lb=27，x：[1，3，0，0]，進隊（j=4）：結點 8，e.i=2，e.f1=12，e.f2=20，e.lb=26，x：[1，4，0，0]， 1829 （4） 出隊結點 8：擴展結點如下： 1830 進隊（j=2）：結點 9，e.i=3，e.f1=22，e.f2=27，e.lb=31，x：[1，4，2，0]，進隊（j=3）：結點 10，e.i=3，e.f1=21，e.f2=30，e.lb=26，x：[1，4，3，0]， 1831 （5） 出隊結點 10，擴展一個 j=2 的子結點，有 e.i=4，到達葉子結點，產生的一個解 1832 1833 是 e.f1=31，e.f2=36，e.lb=31，x=[1，4，3，2]， 1834 該解對應的調度方案是：第 1 步執行作業 1，第 2 步執行作業 4，第 3 步執行作業3，第 4 步執行作業 2，總時間=36， 1835 9. 解：采用優先佇列式分枝限界法求解，佇列中結點的型別如下： 1836 struct NodeType 1837 { int vno; //頂點的編號 1838 int length; //當前結點的路徑長度 1839 bool operator<(const NodeType &s) const //多載<關系函式 1840 { return length>s.length; } //length越小越優先 1841 }; 1842 從頂點 s 開始廣度優先搜索，找到目標點 t 后比較求最短路徑長度及其路徑條數，對應的完整程式如下： 1843 #include <stdio.h> #include <queue> using namespace std; #define MAX 11 1844 #define INF 0x3f3f3f3f 1845 //問題表示 1846 int A[MAX][MAX]={ //一個帶權有向圖 1847 1848 1849 {0，1，4，INF，INF}， 1850 {INF，0，INF，1，5}， 1851 {INF，INF，0，INF，1}， 1852 {INF，INF，2，0，3}， 1853 {INF，INF，INF，INF，INF} }; 1854 1855 int n=5; 1856 //求解結果表示 1857 int bestlen=INF; //最優路徑的路徑長度 1858 int bestcount=0; //最優路徑的條數 1859 struct NodeType 1860 { int vno; //頂點的編號 1861 int length; //當前結點的路徑長度 1862 bool operator<(const NodeType &s) const //多載>關系函式 1863 { return length>s.length; } //length越小越優先 1864 }; 1865 void solve(int s，int t) //求最短路徑問題 1866 { NodeType e，e1; //定義2個結點 1867 priority_queue<NodeType> qu; //定義一個優先佇列qu 1868 e.vno=s; //構造根結點 1869 e.length=0; 1870 qu.push(e); //根結點進隊 1871 while (!qu.empty()) //隊不慷訓圈 1872 { e=qu.top(); qu.pop(); //出隊結點e作為當前結點 1873 if (e.vno==t) //e是一個葉子結點 1874 { if (e.length<bestlen) //比較找最優解 1875 { bestcount=1; 1876 bestlen=e.length; //保存最短路徑長度 1877 } 1878 else if (e.length==bestlen) 1879 bestcount++; 1880 } 1881 else //e不是葉子結點 1882 { for (int j=0; j<n; j++) //檢查e的所有相鄰頂點 1883 if (A[e.vno][j]!=INF && A[e.vno][j]!=0) //頂點e.vno到頂點j有邊 1884 { if (e.length+A[e.vno][j]<bestlen) //剪枝 1885 { e1.vno=j; 1886 e1.length=e.length+A[e.vno][j]; 1887 qu.push(e1); //有效子結點e1進隊 1888 } 1889 } 1890 } 1891 } 1892 } 1893 void main() 1894 { int s=0，t=4; 1895 solve(s，t); 1896 if (bestcount==0) 1897 printf("頂點%d到%d沒有路徑\n"，s，t); 1898 else 1899 { printf("頂點%d到%d存在路徑\n"，s，t); 1900 1901 printf(" 最短路徑長度=%d，條數=%d\n"， bestlen，bestcount); 1902 //輸出：5 3 1903 } 1904 } 1905 上述程式的執行結果如圖 1.39 所示， 1906 圖 1.39 程式執行結果 1907 10. 解：采用優先佇列式分枝限界法求解，設計優先佇列priority_queue<NodeType>，并設計優先佇列的關系比較函式 Cmp，指定按結點的 ub 值進行比較，即 ub 值越大的結點越先出隊，對應的完整程式如下： 1908 #include <stdio.h> #include <queue> using namespace std; 1909 #define MAXN 21 //最多的集裝箱數 1910 //問題表示 1911 int n=5; 1912 int W=10; 1913 int w[]={0,5,2,6,4,3}; //集裝箱重量,不計下標0的元素 1914 //求解結果表示 1915 int bestw=0; //存放最大重量,全域變數 1916 int bestx[MAXN]; //存放最優解,全域變數 1917 int Count=1; //搜索空間中結點數累計,全域變數 1918 typedef struct 1919 { int no; //結點編號 1920 int i; //當前結點在解空間中的層次 1921 int w; //當前結點的總重量 1922 int x[MAXN]; //當前結點包含的解向量 1923 int ub; //上界 1924 } NodeType; 1925 struct Cmp //佇列中關系比較函式 1926 { bool operator()(const NodeType &s,const NodeType &t) 1927 { return (s.ub<t.ub) || (s.ub==t.ub && s.x[0]>t.x[0]); 1928 //ub越大越優先,當ub相同時x[0]越小越優先 1929 } 1930 }; 1931 1932 1933 } 1934 void Loading() //求裝載問題的最優解 1935 { NodeType e,e1,e2; //定義3個結點 1936 priority_queue<NodeType,vector<NodeType>,Cmp > qu; //定義一個優先佇列qu 1937 e.no=Count++; //設定結點編號 1938 e.i=0; //根結點置初值,其層次計為0 1939 e.w=0; 1940 for (int j=0; j<=n; j++) //初始化根結點的解向量 1941 e.x[j]=0; 1942 bound(e); //求根結點的上界 1943 qu.push(e); //根結點進隊 1944 while (!qu.empty()) //隊不慷訓圈 1945 { e=qu.top(); qu.pop(); //出隊結點e作為當前結點 1946 if (e.i==n) //e是一個葉子結點 1947 { if ((e.w>bestw) || (e.w==bestw && e.x[0]<bestx[0])) //比較找最優解 1948 { bestw=e.w; //更新bestw 1949 1950 1951 1952 1953 1954 1955 1956 1957 } for (int j=0;j<=e.i;j++) 1958 bestx[j]=e.x[j]; //復制解向量e.x->bestx 1959 } 1960 else //e不是葉子結點 1961 { if (e.w+w[e.i+1]<=W) //檢查左孩子結點 1962 { e1.no=Count++; //設定結點編號 1963 e1.i=e.i+1; //建立左孩子結點 1964 e1.w=e.w+w[e1.i]; 1965 for (int j=0; j<=e.i; j++) 1966 e1.x[j]=e.x[j]; //復制解向量e.x->e1.x 1967 e1.x[e1.i]=1; //選擇集裝箱i 1968 e1.x[0]++; //裝入集裝箱數增1 1969 bound(e1); //求左孩子結點的上界 1970 qu.push(e1); //左孩子結點進隊 1971 } 1972 e2.no=Count++; //設定結點編號 1973 e2.i=e.i+1; //建立右孩子結點 1974 e2.w=e.w; 1975 for (int j=0; j<=e.i; j++) //復制解向量e.x->e2.x 1976 e2.x[j]=e.x[j]; 1977 e2.x[e2.i]=0; //不選擇集裝箱i 1978 bound(e2); //求右孩子結點的上界 1979 if (e2.ub>bestw) //若右孩子結點可行,則進隊,否則被剪枝 1980 qu.push(e2); 1981 } 1982 } 1983 } 1984 void disparr(int x[],int len) //輸出一個解向量 1985 { for (int i=1;i<=len;i++) 1986 printf("%2d",x[i]); 1987 } 1988 void dispLoading() //輸出最優解 1989 { printf(" X=["); 1990 1991 disparr(bestx,n); 1992 printf("],裝入總價值為%d\n",bestw); 1993 } 1994 void main() 1995 { Loading(); 1996 printf("求解結果:\n"); 1997 dispLoading(); //輸出最優解 1998 } 1999 上述程式的執行結果如圖 1.40 所示， 2000 圖 1.40 程式執行結果 2001 1.7 第 7 章─貪心法 2002 1.7.1 練習題 2003 1. 下面是貪心演算法的基本要素的是（ ）， 2004 A. 重疊子問題 B.構造最優解 C.貪心選擇性質 D.定義最優解 2005 2. 下面問題（ ）不能使用貪心法解決， 2006 A. 單源最短路徑問題 B.n 皇后問題 C.最小花費生成樹問題 D.背包問題 2007 3. 采用貪心演算法的最優裝載問題的主要計算量在于將集裝箱依其重量從小到大排序，故演算法的時間復雜度為（ ）， 2008 A.O(n) B.O(n2) C.O(n3) D.O(nlog2n) 2009 4. 關于 0/ 1 背包問題以下描述正確的是（ ），A.可以使用貪心演算法找到最優解 2010 B. 能找到多項式時間的有效演算法 2011 C. 使用教材介紹的動態規劃方法可求解任意 0－1 背包問題 2012 D. 對于同一背包與相同的物品，做背包問題取得的總價值一定大于等于做 0/1 背包問 2013 題 2014 5. 一棵哈夫曼樹共有 215 個結點，對其進行哈夫曼編碼，共能得到（ ）個不同的碼 2015 字， 2016 A.107 B.108 C.214 D.215 2017 6. 求解哈夫曼編碼中如何體現貪心思路？ 2018 7. 舉反例證明 0/1 背包問題若使用的演算法是按照 vi/wi 的非遞減次序考慮選擇的物品，即只要正在被考慮的物品裝得進就裝入背包，則此方法不一定能得到最優解（此題說明 0/1 背包問題與背包問題的不同）， 2019 2020 2021 8. 求解硬幣問題，有 1 分、2 分、5 分、10 分、50 分和 100 分的硬幣各若干枚，現在要用這些硬幣來支付 W 元，最少需要多少枚硬幣， 2022 9. 求解正整數的最大乘積分解問題，將正整數 n 分解為若干個互不相同的自然數之和，使這些自然數的乘積最大， 2023 10. 求解乘船問題，有 n 個人，第 i 個人體重為 wi（0≤i<n），每艘船的最大載重量均為 C，且最多只能乘兩個人，用最少的船裝載所有人， 2024 11. 求解會議安排問題，有一組會議 A 和一組會議室 B，A[i]表示第 i 個會議的參加人數，B[j]表示第 j 個會議室最多可以容納的人數，當且僅當 A[i]≤B[j]時，第 j 個會議室可以用于舉辦第 i 個會議，給定陣列 A 和陣列 B，試問最多可以同時舉辦多少個會議，例如，A[]={1，2，3}，B[]={3，2，4}，結果為 3；若 A[]={3，4，3，1}，B[]={1，2，2， 6}，結果為 2. 2025 12. 假設要在足夠多的會場里安排一批活動，n 個活動編號為 1～n，每個活動有開始時間 bi 和結束時間 ei（1≤i≤n），設計一個有效的貪心演算法求出最少的會場個數， 2026 13. 給定一個 m×n 的數字矩陣，計算從左到右走過該矩陣且經過的方格中整數最小的路徑，一條路徑可以從第 1 列的任意位置出發，到達第 n 列的任意位置，每一步為從第 i 列走到第 i+1 列相鄰行（水平移動或沿 45 度斜線移動），如圖 1.41 所示，第 1 行和最后一行看作是相鄰的，即應當把這個矩陣看成是一個卷起來的圓筒， 2027 2028 2029 圖 1.41 每一步的走向 2030 兩個略有不同的 5×6 的數字矩陣的最小路徑如圖 1.42 所示，只有最下面一行的數不同，右邊矩陣的路徑利用了第一行與最后一行相鄰的性質， 2031 輸入：包含多個矩陣，每個矩陣的第一行為兩個數 m 和 n，分別表示矩陣的行數和列數，接下來的 m×n 個整數按行優先的順序排列，即前 n 個陣列成第一行，接下的 n 個陣列成第 2 行，依此類推，相鄰整數間用一個或多個空格分隔，注意這些數不一定是正數，輸入中可能有一個或多個矩陣描述，直到輸入結束，每個矩陣的行數在 1 到 10 之間，列數在 1 到 100 之間， 2032 輸出：對每個矩陣輸出兩行，第一行為最小整數之和的路徑，路徑由 n 個整陣列成， 表示路徑經過的行號，如果這樣的路徑不止一條，輸出字典序最小一條， 2033 2034 3 4 1 2 8 6 2035 圖 1.42 兩個數字矩陣的最小路徑 2036 6 1 8 2 7 4 2037 5 9 3 9 9 5 2038 8 4 1 3 2 6 2039 3 7 2 1 2 3 2040 2041 2042 6 1 8 2 7 4 2043 5 9 3 9 9 5 2044 8 4 1 3 2 6 2045 3 7 2 8 6 4 2046 輸出結果： 2047 1 2 3 4 4 5 2048 16 2049 1.7.2 練習題參考答案 2050 1. 答：C， 2051 2. 答：n 皇后問題的解不滿足貪心選擇性質，答案為 B， 2052 3. 答：D， 2053 4. 答：由于背包問題可以取物品的一部分，所以總價值一定大于等于做 0/1 背包問題，答案為 D， 2054 5. 答：這里 n=215，哈夫曼樹中 n1=0，而 n0=n2+1，n=n0+n1+n2=2n0-1， n0=(n+1)/2=108，答案為 B， 2055 6. 答：在構造哈夫曼樹時每次都是將兩棵根結點最小的樹合并，從而體現貪心的思路， 2056 7. 證明：例如，n=3，w={3，2，2}，v={7，4，4}，W=4 時，由于 7/3 最大，若按題目要求的方法，只能取第一個，收益是 7，而此實體的最大的收益應該是 8，取第 2、3 2057 個物品， 2058 8. 解：用結構體陣列 A 存放硬幣資料，A[i].v 存放硬幣 i 的面額，A[i].c 存放硬幣 i 的枚數，采用貪心思路，首先將陣列 A 按面額遞減排序，再兌換硬幣，每次盡可能兌換面額大的硬幣，對應的完整程式如下： 2059 #include <stdio.h> #include <algorithm> using namespace std; 2060 #define min(x,y) ((x)<(y)?(x):(y)) #define MAX 21 2061 //問題表示int n=7; 2062 struct NodeType 2063 { int v; //面額 2064 int c; //枚數 2065 bool operator<(const NodeType &s) 2066 { //用于按面額遞減排序 2067 return s.v<v; 2068 } 2069 }; 2070 NodeType A[]={{1,12},{2,8},{5,6},{50,10},{10,8},{200,1},{100,4}}; 2071 int W; 2072 //求解結果表示 2073 2074 2075 { sort(A,A+n); //按面額遞減排序 2076 for (int i=0;i<n;i++) 2077 { int t=min(W/A[i].v,A[i].c); //使用硬幣i的枚數 2078 if (t!=0) 2079 printf(" 支付%3d面額: %3d枚\n",A[i].v,t); 2080 W-=t*A[i].v; //剩余的金額 2081 ans+=t; 2082 if (W==0) break; 2083 } 2084 } 2085 void main() 2086 { W=325; //支付的金額 2087 printf("支付%d分:\n",W); 2088 solve(); 2089 printf("最少硬幣的個數: %d枚\n",ans); 2090 } 2091 上述程式的執行結果如圖 1.43 所示， 2092 圖 1.43 程式執行結果 2093 9. 解：采用貪心方法求解，用 a[0..k]存放 n 的分解結果： 2094 （1） n≤4 時可以驗證其分解成幾個正整數的和的乘積均小于 n，沒有解， 2095 （2） n>4 時，把 n 分拆成若干個互不相等的自然數的和，分解數的個數越多乘積越大，為此讓 n 的分解數個數盡可能多（體現貪心的思路），把 n 分解成從 2 開始的連續的自然數之和，例如，分解 n 為 a[0]=2，a[1]=3，a[2]=4，…，a[k]=k+2（共有 k+1 個分解數），用 m 表示剩下數，這樣的分解直到 m≤a[k]為止，即 m≤k+2，對剩下數 m 的處理分為如下兩種情況： 2096 ① m<k+2：將 m 平均分解到 a[k..i]（對應的分解數個數為 m）中，即從 a[k]開始往前的分解數增加 1（也是貪心的思路，分解數越大加 1 和乘積也越大）， 2097 ② m=k+2：將 a[0..k-1] （對應的分解數個數為 k）的每個分解數增加 1，剩下的 2 增加到 a[k]中，即 a[k]增加 2， 2098 對應的完整程式如下： 2099 #include <stdio.h> #include <string.h> #define MAX 20 2100 //問題表示int n; 2101 //求解結果表示 2102 2103 2104 int a[MAX]; 2105 int k=0; 2106 void solve() 2107 2108 //存放被分解的數 2109 //a[0..k]存放被分解的數 2110 //求解n的最大乘積分解問題 2111 { int i; 2112 int sum=1; 2113 if (n<4) //不存在最優方案,直接回傳 2114 return; 2115 else 2116 { int m=n; //m表示剩下數 2117 a[0]=2; //第一個數從2開始 2118 m-=a[0]; //減去已經分解的數 2119 k=0; 2120 while (m>a[k]) //若剩下數大于最后一個分解數,則繼續分解 2121 { k++; //a陣列下標+1 2122 a[k]=a[k-1]+1; //按2、3、4遞增順序分解 2123 m-=a[k]; //減去最新分解的數 2124 } 2125 if (m<a[k]) //若剩下數小于a[k],從a[k]開始往前的數+1 2126 { for (i=0; i<m; i++) 2127 a[k-i]+=1; 2128 } 2129 if (m==a[k]) //若剩下數等于a[k],則a[k]的值+2,之前的數+1 2130 { a[k]+=2; 2131 for (i=0; i<k; i++) 2132 a[i]+=1; 2133 } 2134 } 2135 } 2136 void main() 2137 { n=23; 2138 memset(a,0,sizeof(a)); 2139 solve(); 2140 printf("%d的最優分解方案\n",n); 2141 int mul=1; 2142 printf(" 分解的數: "); 2143 for (int i=0;i<=k;i++) 2144 if (a[i]!=0) 2145 { printf("%d ",a[i]); 2146 mul*=a[i]; 2147 } 2148 printf("\n 乘積最大值: %d\n",mul); 2149 } 2150 上述程式的執行結果如圖 1.44 所示， 2151 2152 2153 圖 1.44 程式執行結果 2154 10. 解：采用貪心思路，首先按體重遞增排序；再考慮前后的兩個人（最輕者和最重者），分別用 i、j 指向：若 w[i]+w[j]≤C，說明這兩個人可以同乘（執行 i++，j--），否則 w[j]單乘（執行 j--），若最后只剩余一個人，該人只能單乘， 2155 對應的完整程式如下： 2156 #include <stdio.h> #include <algorithm> using namespace std; #define MAXN 101 2157 //問題表示int n=7; 2158 int w[]={50,65,58,72,78,53,82}; 2159 int C=150; 2160 //求解結果表示int bests=0; 2161 void Boat() 2162 { sort(w,w+n); 2163 int i=0; 2164 //求解乘船問題 2165 //遞增排序 2166 int j=n - 1; 2167 while (i<=j) 2168 { if(i==j) //剩下最后一個人 2169 { printf(" 一艘船: %d\n",w[i]); 2170 bests++; 2171 break; 2172 } 2173 if (w[i]+w[j]<=C) //前后兩個人同乘 2174 { printf(" 一艘船: %d %d\n",w[i],w[j]); 2175 bests++; 2176 i++; 2177 j--; 2178 } 2179 else //w[j]單乘 2180 { printf(" 一艘船: %d\n",w[j]); 2181 bests++; 2182 j--; 2183 } 2184 } 2185 } 2186 void main() 2187 { printf("求解結果:\n"); 2188 Boat(); 2189 printf("最少的船數=%d\n",bests); 2190 } 2191 上述程式的執行結果如圖 1.45 所示， 2192 2193 2194 2195 2196 圖 1.45 程式執行結果 2197 11. 解：采用貪心思路，每次都在還未安排的容量最大的會議室安排盡可能多的參會人數，即對于每個會議室，都安排當前還未安排的會議中，參會人數最多的會議，若能容納下，則選擇該會議，否則找參會人數次多的會議來安排，直到找到能容納下的會議， 2198 對應的完整程式如下： 2199 #include <stdio.h> #include <algorithm> using namespace std; 2200 //問題表示 2201 int n=4; //會議個數 2202 int m=4; //會議室個數 2203 int A[]={3,4,3,1}; 2204 int B[]={1,2,2,6}; 2205 //求解結果表示int ans=0; 2206 void solve() //求解演算法 2207 { sort(A,A+n); //遞增排序 2208 sort(B,B+m); //遞增排序 2209 int i=n-1,j=m-1; //從最多人數會議和最多容納人數會議室開始 2210 for(i;i>=0;i--) 2211 { if(A[i]<=B[j] && j>=0) 2212 { ans++; //轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114583.html
標籤：其他