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