1 .1 第 1 章─概論 1.1.1 練習題 1 . 下列關于演算法的說法中正確的有（ ）， Ⅰ Ⅱ Ⅲ Ⅳ .求解某一類問題的演算法是唯一的 .演算法必須在有限步操作之后停止 .演算法的每一步操作必須是明確的，不能有歧義或含義模糊 .演算法執行后一定產生確定的結果 A. 1 個 B.2 個 C.3 個 D.4 個 2 . T(n)表示當輸入規模為 n 時的演算法效率，以下演算法效率最優的是（ ）， A.T(n)= T(n-1)+1，T(1)=1 C.T(n)= T(n/2)+1，T(1)=1 B.T(n)= 2n2 D.T(n)=3nlog2n 3 4 . 什么是演算法？演算法有哪些特征？ . 判斷一個大于 2 的正整數 n 是否為素數的方法有多種，給出兩種演算法，說明其中 一種演算法更好的理由， 5 . 證明以下關系成立： （ （ 1）10n2-2n=?(n2) 2）2n+1=?(2n) 6 7 . 證明 O(f(n))+O(g(n))=O(max{f(n)，g(n)}) ， . 有一個含 n（n>2）個整數的陣列 a，判斷其中是否存在出現次數超過所有元素一 半的元素， 8 9 . 一個字串采用 string 物件存盤，設計一個演算法判斷該字串是否為回文， . 有一個整數序列，設計一個演算法判斷其中是否存在兩個元素和恰好等于給定的整 數 k， 0. 有兩個整數序列，每個整數序列中所有元素均不相同，設計一個演算法求它們的公 共元素，要求不使用 STL 的集合演算法， 1. 正整數 n（n>1）可以寫成質數的乘積形式，稱為整數的質因數分解，例如， 2=2*2*3，18=2*3*3，11=11，設計一個演算法求 n 這樣分解后各個質因數出現的次數，采 用 vector 向量存放結果， 2. 有一個整數序列，所有元素均不相同，設計一個演算法求相差最小的元素對的個 數，如序列 4、1、2、3 的相差最小的元素對的個數是 3，其元素對是（1，2），（2，3）， 3，4）， 3. 有一個 map<string，int>容器，其中已經存放了較多元素，設計一個演算法求出其 中重復的 value 并且回傳重復 value 的個數， 1 1 1 1 （ 1 1 1 4. 重新做第 10 題，采用 map 容器存放最終結果， 5. 假設有一個含 n（n>1）個元素的 stack<int>堆疊容器 st，設計一個演算法出堆疊從堆疊頂 到堆疊底的第 k（1≤k≤n）個元素，其他堆疊元素不變， 演算法設計 1 .1.2 練習題參考答案 答：由于演算法具有有窮性、確定性和輸出性，因而Ⅱ、Ⅲ、Ⅳ正確，而解決某一 類問題的演算法不一定是唯一的，答案為 C， 答：選項 A 的時間復雜度為 O(n)，選項 B 的時間復雜度為 O(n2)，選項 C 的時間 復雜度為 O(log2n)，選項 D 的時間復雜度為 O(nlog2n)，答案為 C， 答：演算法是求解問題的一系列計算步驟，演算法具有有限性、確定性、可行性、輸 入性和輸出性 5 個重要特征， . 答：兩種演算法如下： 1 . 2 . 3 . 4 # # include <stdio.h> include <math.h> bool isPrime1(int n) //方法 1 { for (int i=2;i<n;i++) if (n%i==0) return false; return true; } bool isPrime2(int n) //方法 2 { for (int i=2;i<=(int)sqrt(n);i++) if (n%i==0) return false; return true; } void main() { int n=5; printf("%d,%d\n",isPrime1(n),isPrime2(n)); } 方法 1 的時間復雜度為 O(n)，方法 2 的時間復雜度為 n，所以方法 2 更好， . 答：（1）當 n 足夠大時，(10n2-2n)/( n2)=10，所以 10n2-2n=?(n2)， 2）2n+1=2*2n=?(2n)， . 證明：對于任意 f1(n)∈O(f(n)) ，存在正常數 c1 和正常數 n1，使得對所有 n≥n1， 有 f1(n)≤c1f(n) ， 類似地，對于任意 g1(n)∈O(g(n)) ，存在正常數 c2 和自然數 n2，使得對所有 n≥n2， 5 （ 6 有 g1(n)≤c2g(n) ， 令 c3=max{c1，c2}，n3=max{n1，n2}，h(n)= max{f(n)，g(n)} ， 則對所有的 n≥n3，有： f1(n) +g1(n)≤c1f(n) + c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n)) ≤ c32max{f(n)，g(n)}=2c3h(n)=O(max{f(n)，g(n)})， . 解：先將 a 中元素遞增排序，再求出現次數最多的次數 maxnum，最后判斷是否滿 足條件，對應的程式如下： 7 # # include <stdio.h> include <algorithm> using namespace std; 2 第 1 章 概論 bool solve(int a[],int n,int &x) { sort(a,a+n); //遞增排序 //出現次數最多的次數 int maxnum=0; int num=1; int e=a[0]; for (int i=1;i<n;i++) { if (a[i]==e) { num++; if (num>maxnum) { maxnum=num; x=e; } } else { e=a[i]; num=1; } } if (maxnum>n/2) return true; else return false; } void main() { int a[]={2,2,2,4,5,6,2}; int n=sizeof(a)/sizeof(a[0]); int x; if (solve(a,n,x)) printf("出現次數超過所有元素一半的元素為%d\n",x); else printf("不存在出現次數超過所有元素一半的元素\n"); } 上述程式的執行結果如圖 1.1 所示， 圖 1.1 程式執行結果 8 . 解：采用前后字符判斷方法，對應的程式如下： # # include <iostream> include <string> using namespace std; bool solve(string str) //判斷字串 str是否為回文 { int i=0,j=str.length()-1; while (i<j) if (str[i]!=str[j]) return false; { 3 演算法設計 i++; j--; return true; void main() } } { cout << "求解結果" << endl; string str="abcd"; cout << " " << str << (solve(str)?"是回文":"不是回文") << endl; string str1="abba"; cout << " " << str1 << (solve(str1)?"是回文":"不是回文") << endl; } 上述程式的執行結果如圖 1.2 所示， 圖 1.2 程式執行結果 9 . 解：先將 a 中元素遞增排序，然后從兩端開始進行判斷，對應的程式如下： # # include <stdio.h> include <algorithm> using namespace std; bool solve(int a[],int n,int k) { sort(a,a+n); int i=0, j=n-1; while (i<j) //遞增排序 //區間中存在兩個或者以上元素 { if (a[i]+a[j]==k) return true; else if (a[i]+a[j]<k) i++; else j--; } return false; } void main() int a[]={1,2,4,5,3}; { int n=sizeof(a)/sizeof(a[0]); printf("求解結果\n"); int k=9,i,j; if (solve(a,n,k,i,j)) printf(" 存在: %d+%d=%d\n",a[i],a[j],k); else printf(" 不存在兩個元素和為%d\n",k); int k1=10; if (solve(a,n,k1,i,j)) printf(" 存在: %d+%d=%d\n",a[i],a[j],k1); 4 第 1 章 概論 else printf(" 不存在兩個元素和為%d\n",k1); } 上述程式的執行結果如圖 1.3 所示， 圖 1.3 程式執行結果 1 0. 解：采用集合 set<int>存盤整數序列，集合中元素默認是遞增排序的，再采用二 路歸并演算法求它們的交集，對應的程式如下： # # include <stdio.h> include <set> using namespace std; void solve(set<int> s1,set<int> s2,set<int> &s3) //求交集 s3 { set<int>::iterator it1,it2; it1=s1.begin(); it2=s2.begin(); while (it1!=s1.end() && it2!=s2.end()) { if (*it1==*it2) { s3.insert(*it1); + +it1; ++it2; } else if (*it1<*it2) + +it1; else + +it2; } } void dispset(set<int> s) //輸出集合的元素 { set<int>::iterator it; for (it=s.begin();it!=s.end();++it) printf("%d ",*it); printf("\n"); } void main() { int a[]={3,2,4,8}; int n=sizeof(a)/sizeof(a[0]); set<int> s1(a,a+n); int b[]={1,2,4,5,3}; int m=sizeof(b)/sizeof(b[0]); set<int> s2(b,b+m); set<int> s3; solve(s1,s2,s3); printf("求解結果\n"); printf(" s1: "); dispset(s1); 5 演算法設計 printf(" s2: "); dispset(s2); printf(" s3: "); dispset(s3); } 上述程式的執行結果如圖 1.4 所示， 圖 1.4 程式執行結果 1 1. 解：對于正整數 n，從 i=2 開始查找其質因數，ic 記錄質因數 i 出現的次數，當找 到這樣質因數后，將（i，ic）作為一個元素插入到 vector 容器 v 中，最后輸出 v，對應的 演算法如下： # # include <stdio.h> include <vector> using namespace std; struct NodeType //vector向量元素型別 //質因數 { int p; int pc; //質因數出現次數 } ; void solve(int n,vector<NodeType> &v)//求 n的質因數分解 { int i=2; int ic=0; NodeType e; do { if (n%i==0) { ic++; n=n/i; } else { if (ic>0) { e.p=i; e.pc=ic; v.push_back(e); } ic=0; i++; } } while (n>1 || ic!=0); } void disp(vector<NodeType> &v) //輸出 v { vector<NodeType>::iterator it; for (it=v.begin();it!=v.end();++it) printf(" 質因數%d出現%d次\n",it->p,it->pc); } 6 第 1 章 概論 void main() { vector<NodeType> v; int n=100; printf("n=%d\n",n); solve(n,v); disp(v); } 上述程式的執行結果如圖 1.5 所示， 圖 1.5 程式執行結果 1 2. 解：先遞增排序，再求相鄰元素差，比較求最小元素差，累計最小元素差的個 數，對應的程式如下： # # # include <iostream> include <algorithm> include <vector> using namespace std; int solve(vector<int> &myv) //求 myv中相差最小的元素對的個數 //遞增排序 { sort(myv.begin(),myv.end()); int ans=1; int mindif=myv[1]-myv[0]; for (int i=2;i<myv.size();i++) { if (myv[i]-myv[i-1]<mindif) { ans=1; mindif=myv[i]-myv[i-1]; } else if (myv[i]-myv[i-1]==mindif) ans++; } return ans; } void main() { int a[]={4,1,2,3}; int n=sizeof(a)/sizeof(a[0]); vector<int> myv(a,a+n); cout << "相差最小的元素對的個數: " << solve(myv) << endl; } 上述程式的執行結果如圖 1.6 所示， 7 演算法設計 圖 1.6 程式執行結果 1 3. 解：對于 map<string，int>容器 mymap，設計另外一個 map<int，int>容器 tmap， 將前者的 value 作為后者的關鍵字，遍歷 mymap，累計 tmap 中相同關鍵字的次數，一個 參考程式及其輸出結果如下： # # # include <iostream> include <map> include <string> using namespace std; void main() { map<string,int> mymap; mymap.insert(pair<string,int>("Mary",80)); mymap.insert(pair<string,int>("Smith",82)); mymap.insert(pair<string,int>("John",80)); mymap.insert(pair<string,int>("Lippman",95)); mymap.insert(pair<string,int>("Detial",82)); map<string,int>::iterator it; map<int,int> tmap; for (it=mymap.begin();it!=mymap.end();it++) tmap[(*it).second]++; map<int，int>::iterator it1; cout << "求解結果" << endl; for (it1=tmap.begin();it1!=tmap.end();it1++) cout << " " << (*it1).first << ": " << (*it1).second << "次\n"; } 上述程式的執行結果如圖 1.7 所示， 圖 1.7 程式執行結果 1 4. 解：采用 map<int，int>容器 mymap 存放求解結果，第一個分量存放質因數，第 二個分量存放質因數出現次數，對應的程式如下： # # include <stdio.h> include <map> using namespace std; void solve(int n,map<int,int> &mymap) //求 n的質因數分解 { int i=2; int ic=0; do { if (n%i==0) { ic++; n=n/i; } 8 第 1 章 概論 else { if (ic>0) mymap[i]=ic; ic=0; i++; } } while (n>1 || ic!=0); } void disp(map<int,int> &mymap) //輸出 mymap { map<int,int>::iterator it; for (it=mymap.begin();it!=mymap.end();++it) printf(" 質因數%d出現%d次\n",it->first,it->second); } void main() { map<int,int> mymap; int n=12345; printf("n=%d\n",n); solve(n,mymap); disp(mymap); } 上述程式的執行結果如圖 1.8 所示， 圖 1.8 程式執行結果 1 5. 解：堆疊容器不能順序遍歷，為此創建一個臨時 tmpst 堆疊，將 st 的 k 個元素出堆疊并 進堆疊到 tmpst 中，再出堆疊 tmpst 一次得到第 k 個元素，最后將堆疊 tmpst 的所有元素出堆疊并進 堆疊到 st 中，對應的程式如下： # # include <stdio.h> include <stack> using namespace std; int solve(stack<int> &st,int k) //出堆疊第 k個元素 { stack<int> tmpst; int e; for (int i=0;i<k;i++) //出堆疊 st的 k個元素并進 tmpst堆疊 { e=st.top(); st.pop(); tmpst.push(e); } e=tmpst.top(); //求第 k個元素 tmpst.pop(); while (!tmpst.empty()) //將 tmpst的所有元素出堆疊并進堆疊 st { st.push(tmpst.top()); tmpst.pop(); 9 演算法設計 } return e; } void disp(stack<int> &st) //出堆疊 st的所有元素 { while (!st.empty()) { printf("%d ",st.top()); st.pop(); } printf("\n"); } void main() { stack<int> st; printf("進堆疊元素 1,2,3,4\n"); st.push(1); st.push(2); st.push(3); st.push(4); int k=3; int e=solve(st,k); printf("出堆疊第%d個元素是: %d\n",k,e); printf("st中元素出堆疊順序: "); disp(st); } 上述程式的執行結果如圖 1.9 所示， 圖 1.9 程式執行結果 1 .2 第 2 章─遞回演算法設計技術 1.2.1 練習題 1 2 . 什么是直接遞回和間接遞回？消除遞回一般要用到什么資料結構？ . 分析以下程式的執行結果： # include <stdio.h> void f(int n,int &m) { if (n<1) return; else { printf("呼叫f(%d,%d)前,n=%d,m=%d\n",n-1,m-1,n,m); n--; m--; f(n-1,m); printf("呼叫f(%d,%d)后:n=%d,m=%d\n",n-1,m-1,n,m); } 1 0 第 1 章 概論 } void main() { int n=4,m=4; f(n,m); } 3 . 采用直接推導方法求解以下遞回方程： T(1)=1 T(n)=T(n-1)+n 當 n>1 4 . 采用特征方程方法求解以下遞回方程： H(0)=0 H(1)=1 H(2)=2 H(n)=H(n-1)+9H(n-2)-9H(n-3) 當 n>2 5 . 采用遞回樹方法求解以下遞回方程： T(1)=1 T(n)=4T(n/2)+n 當 n>1 6 . 采用主方法求解以下題的遞回方程， T(n)=1 T(n)=4T(n/2)+n2 當 n=1 當 n>1 7 8 . 分析求斐波那契 f(n)的時間復雜度， . 數列的首項 a1=0，后續奇數項和偶數項的計算公式分別為 a2n=a2n-1+2，a2n+1=a2n- 1+ a2n-1，寫出計算數列第 n 項的遞回演算法， 9 . 對于一個采用字符陣列存放的字串 str，設計一個遞回演算法求其字符個數（長 度）， 1 0. 對于一個采用字符陣列存放的字串 str，設計一個遞回演算法判斷 str 是否為回 文， 1 1 1 1. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法正序輸出所有結點值， 2. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法逆序輸出所有結點值， 3. 對于不帶頭結點的非空單鏈表 L，設計一個遞回演算法回傳最大值結點的地址（假 設這樣的結點唯一）， 4. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法回傳第一個值為 x 的結點的地 址，沒有這樣的結點時回傳 NULL， 1 1 1 5. 對于不帶頭結點的單鏈表 L，設計一個遞回演算法洗掉第一個值為 x 的結點， 6. 假設二叉樹采用二叉鏈存盤結構存放，結點值為 int 型別，設計一個遞回演算法求 二叉樹 bt 中所有葉子結點值之和， 7. 假設二叉樹采用二叉鏈存盤結構存放，結點值為 int 型別，設計一個遞回演算法求 二叉樹 bt 中所有結點值大于等于 k 的結點個數， 8. 假設二叉樹采用二叉鏈存盤結構存放，所有結點值均不相同，設計一個遞回演算法 求值為 x 的結點的層次（根結點的層次為 1），沒有找到這樣的結點時回傳 0， 1 1 1 1 演算法設計 1 .2.2 練習題參考答案 答：一個 f 函式定義中直接呼叫 f 函式自己，稱為直接遞回，一個 f 函式定義中調 用 g 函式，而 g 函式的定義中呼叫 f 函式，稱為間接遞回，消除遞回一般要用堆疊實作， 答：遞回函式f(n，m)中，n是非參考引數，m是參考引數，所以遞回函式的狀態為 1 . 2 . （ n），程式執行結果如下： 呼叫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 3 . 解：求 T(n)的程序如下： T(n)=T(n-1)+n=[T(n-2)+n-1)]+n=T(n-2)+n+(n-1) = = = = T(n-3)+n+(n-1)+(n-2) … T(1)+n+(n-1)+…+2 n+(n-1)+ +…+2+1=n(n+1)/2=O(n2)， 4 . 解：整數一個常系數的線性齊次遞推式，用 xn 代替 H(n)，有：xn=xn-1+9xn-2-9xn-3， 兩邊同時除以 xn-3，得到：x3=x2+9x-9，即 x3-x2-9x+9=0， 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 則遞回方程的通解為：H(n)=c1+c2(-3)n+c33n 代入 H(0)=0，有 c1+c2+c3=0 代入 H(1)=1，有 c1-3c2+3c3=1 代入 H(2)=2，有 c1+9c2+9c3=2 ( ? 1)n ? 1 1 ? 4， n ? 1 求出：c1=-1/4，c2=-1/12，c3=1/3，H(n)=c1+c2(-3)n+c33n=( + 1)3 4 5 . 解：構造的遞回樹如圖 1.10 所示，第 1 層的問題規模為 n，第 2 的層的子問題的 問題規模為 n/2，依此類推，當展開到第 k+1 層，其規模為 n/2k=1，所以遞回樹的高度為 log2n+1， 第1層有1個結點，其時間為n，第2層有4個結點，其時間為4(n/2)=2n，依次類推，第k 層有4k-1個結點，每個子問題規模為n/2k-1，其時間為4k-1(n/2k-1)=2k-1n，葉子結點的個數為n 個，其時間為n，將遞回樹每一層的時間加起來，可得： log2n T(n)=n+2n+…+ 2k-1n+…+n≈? ? 2 =O(n2)， 1 2 第 1 章 概論 n n (n/2) (n/2) (n/2) (n/2) 2 n 2 高度 h 為 log n+1 n/22) (n/22) (n/22) (n/22) ( 2 2 n … … … … 1 1 1 1 n 圖 1.10 一棵遞回樹 6 . 解：采用主方法求解，這里 a=4，b=2，f(n)=n2， log a log 4 b 2 =? logba因此，? =n2，它與 f(n)一樣大，滿足主定理中的情況（2），所以 T(n)=O( ? log2n)=O(n2log2n)， 7 . 解：設求斐波那契 f(n)的時間為 T(n)，有以下遞推式： T(1)=T(2) T(n)=T(n-1)+T(n-2)+1 當 n>2 其中，T(n)式中加 1 表示一次加法運算的時間， 不妨先求 T1(1)=T1(2)=1，T1(n)=T1(n-1)+T1(n-2)，按《教程》例 2.14 的方法可以求 出： n n n ? 1? 5 ?? ? ? ? ? ? 1? 5 ?? ? ? ? ? ? ? ? ? T1(n)= 1 ?? ? 1 ≈ 1 ? ? 1? 5 2 = ? 5 2 5 2 5 ? n ? ? ? ? ? 所以 T(n)=T1(n)+1≈ 1 1? 5 2 +1=O(φn)，其中 φ= 1? 5 2 ， ? ? ? 5 8 . 解：設 f(m)計算數列第 m 項值， 當 m 為偶數時，不妨設 m=2n，則 2n-1=m-1，所以有 f(m)=f(m-1)+2， 當 m 為奇數時，不妨設 m=2n+1，則 2n-1=m-2，2n=m-1，所以有 f(m)=f(m-2)+f(m- 1 )-1， 對應的遞回演算法如下： int f(int m) { if (m==1) return 0; if (m%2==0) return f(m-1)+2; else return f(m-2)+f(m-1)-1; } 9 . 解：設 f(str)回傳字串 str 的長度，其遞回模型如下： f(str)=0 當*str='\0'時 f(str)=f(str+1)+1 其他情況 對應的遞回程式如下： 1 3 演算法設計 # include <iostream> using namespace std; int Length(char *str) //求str的字符個數 { if (*str=='\0') return 0; else return Length(str+1)+1; } void main() { char str[]="abcd"; cout << str << "的長度: " << Length(str) << endl; } 上述程式的執行結果如圖 1.11 所示， 圖 1.11 程式執行結果 1 0. 解：設 f(str，n)回傳含 n 個字符的字串 str 是否為回文，其遞回模型如下： f(str，n)=true 當 n=0 或者 n=1 時 當 str[0]≠str[n-1]時 其他情況 f(str，n)=flase f(str，n)=f(str+1，n-2) 對應的遞回演算法如下： # # include <stdio.h> include <string.h> bool isPal(char *str,int n) //str回文判斷演算法 { if (n==0 || n==1) return true; if (str[0]!=str[n-1]) return false; return isPal(str+1,n-2); } void disp(char *str) { int n=strlen(str); if (isPal(str,n)) printf(" %s是回文\n",str); else printf(" %s不是回文\n",str); } void main() { printf("求解結果\n"); disp("abcba"); disp("a"); disp("abc"); } 1 4 第 1 章 概論 上述程式的執行結果如圖 1.12 所示， 圖 1.12 程式執行結果 1 1. 解：設 f(L)正序輸出單鏈表 L 的所有結點值，其遞回模型如下： f(L) ≡ 不做任何事情 當 L=NULL f(L) ≡ 輸出 L->data; f(L->next); 當 L≠NULL 時 對應的遞回程式如下： # include "LinkList.cpp" //包含單鏈表的基本運算演算法 //正序輸出所有結點值 void dispLink(LinkNode *L) { if (L==NULL) return; else { printf("%d ",L->data); dispLink(L->next); } } void main() { int a[]={1,2,5,2,3,2}; int n=sizeof(a)/sizeof(a[0]); LinkNode *L; CreateList(L,a,n); printf("正向L: "); dispLink(L); printf("\n"); Release(L); //由a[0..n-1]創建不帶頭結點的單鏈表 //銷毀單鏈表 } 上述程式的執行結果如圖 1.13 所示， 圖 1.13 程式執行結果 1 2. 解：設 f(L)逆序輸出單鏈表 L 的所有結點值，其遞回模型如下： f(L) ≡ 不做任何事情 當 L=NULL f(L) ≡ f(L->next); 輸出 L->data 當 L≠NULL 時 對應的遞回程式如下： # include "LinkList.cpp" void Revdisp(LinkNode *L) if (L==NULL) return; //包含單鏈表的基本運算演算法 //逆序輸出所有結點值 { 1 5 演算法設計 else { Revdisp(L->next); printf("%d ",L->data); } } void main() { int a[]={1,2,5,2,3,2}; int n=sizeof(a)/sizeof(a[0]); LinkNode *L; CreateList(L,a,n); printf("反向L: "); Revdisp(L); printf("\n"); Release(L); } 上述程式的執行結果如圖 1.14 所示， 圖 1.14 程式執行結果 1 3. 解：設 f(L)回傳單鏈表 L 中值最大結點的地址，其遞回模型如下： f(L) = L 當 L 只有一個結點時 f(L) = MAX{f(L->next)，L->data} 其他情況 對應的遞回程式如下： # include "LinkList.cpp" //包含單鏈表的基本運算演算法 LinkNode *Maxnode(LinkNode *L) //回傳最大值結點的地址 { if (L->next==NULL) return L; //只有一個結點時 else { } LinkNode *maxp; maxp=Maxnode(L->next); if (L->data>maxp->data) return L; else return maxp; } void main() int a[]={1,2,5,2,3,2}; int n=sizeof(a)/sizeof(a[0]); { LinkNode *L,*p; CreateList(L,a,n); p=Maxnode(L); printf("最大結點值: %d\n",p->data); Release(L); 1 6 第 1 章 概論 } 上述程式的執行結果如圖 1.15 所示， 圖 1.15 程式執行結果 1 4. 解：設 f(L，x)回傳單鏈表 L 中第一個值為 x 的結點的地址，其遞回模型如下： f(L，x) = NULL f(L，x) = L 當 L=NULL 時 當 L≠NULL 且 L->data=https://www.cnblogs.com/JUSTDOINS/p/x 時 其他情況 f(L，x) = f(L->next，x) 對應的遞回程式如下： # include "LinkList.cpp" //包含單鏈表的基本運算演算法 LinkNode *Firstxnode(LinkNode *L,int x) //回傳第一個值為 x的結點的地址 { if (L==NULL) return NULL; if (L->data=https://www.cnblogs.com/JUSTDOINS/p/=x) return L; else return Firstxnode(L->next,x); } void main() { int a[]={1,2,5,2,3,2}; int n=sizeof(a)/sizeof(a[0]); LinkNode *L,*p; CreateList(L,a,n); int x=2; p=Firstxnode(L,x); printf("結點值: %d\n",p->data); Release(L); } 上述程式的執行結果如圖 1.16 所示， 圖 1.16 程式執行結果 1 5. 解：設 f(L，x)洗掉單鏈表 L 中第一個值為 x 的結點，其遞回模型如下： f(L，x) ≡ 不做任何事情 當 L=NULL f(L，x) ≡ 洗掉 L 結點，L=L->next f(L，x) ≡ f(L->next，x) 當 L≠NULL 且 L->data=https://www.cnblogs.com/JUSTDOINS/p/x 其他情況 對應的遞回程式如下： 1 7 演算法設計 # include "LinkList.cpp" //包含單鏈表的基本運算演算法 void Delfirstx(LinkNode *&L,int x) //洗掉單鏈表 L中第一個值為 x的結點 { if (L==NULL) return; if (L->data=https://www.cnblogs.com/JUSTDOINS/p/=x) { LinkNode *p=L; L=L->next; free(p); } else Delfirstx(L->next,x); } void main() { int a[]={1,2,5,2,3,2}; int n=sizeof(a)/sizeof(a[0]); LinkNode *L; CreateList(L,a,n); printf("洗掉前L: "); DispList(L); int x=2; printf("洗掉第一個值為%d的結點\n",x); Delfirstx(L,x); printf("洗掉后L: "); DispList(L); Release(L); } 上述程式的執行結果如圖 1.17 所示， 圖 1.17 程式執行結果 1 6. 解：設 f(bt)回傳二叉樹 bt 中所有葉子結點值之和，其遞回模型如下： f(bt)=0 當 bt=NULL f(bt)=bt->data 當 bt≠NULL 且 bt 結點為葉子結點 其他情況 f(bt)=f(bt->lchild)+f(bt->rchild) 對應的遞回程式如下： # include "Btree.cpp" //包含二叉樹的基本運算演算法 int LeafSum(BTNode *bt) //二叉樹 bt中所有葉子結點值之和 { if (bt==NULL) return 0; if (bt->lchild==NULL && bt->rchild==NULL) return bt->data; int lsum=LeafSum(bt->lchild); int rsum=LeafSum(bt->rchild); return lsum+rsum; } void main() 1 8 第 1 章 概論 { BTNode *bt; Int a[]={5,2,3,4,1,6}; Int b[]={2,3,5,1,4,6}; //先序序列 //中序序列 int n=sizeof(a)/sizeof(a[0]); bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt printf("二叉樹bt:"); DispBTree(bt); printf("\n"); printf("所有葉子結點值之和: %d\n",LeafSum(bt)); DestroyBTree(bt); //銷毀樹bt } 上述程式的執行結果如圖 1.18 所示， 圖 1.18 程式執行結果 1 7. 解：設 f(bt，k)回傳二叉樹 bt 中所有結點值大于等于 k 的結點個數，其遞回模型 如下： f(bt，k)=0 當 bt=NULL f(bt，k)=f(bt->lchild，k)+f(bt->rchild，k)+1 f(bt，k)=f(bt->lchild，k)+f(bt->rchild，k) 當 bt≠NULL 且 bt->data≥k 其他情況 對應的遞回程式如下： # include "Btree.cpp" //包含二叉樹的基本運算演算法 //大于等于 k的結點個數 int Nodenum(BTNode *bt,int k) { if (bt==NULL) return 0; int lnum=Nodenum(bt->lchild,k); int rnum=Nodenum(bt->rchild,k); if (bt->data>=k) return lnum+rnum+1; else return lnum+rnum; } void main() { BTNode *bt; Int a[]={5,2,3,4,1,6}; Int b[]={2,3,5,1,4,6}; int n=sizeof(a)/sizeof(a[0]); bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt printf("二叉樹bt:"); DispBTree(bt); printf("\n"); int k=3; printf("大于等于%d的結點個數: %d\n",k,Nodenum(bt,k)); DestroyBTree(bt); //銷毀樹bt } 上述程式的執行結果如圖 1.19 所示， 1 9 演算法設計 圖 1.19 程式執行結果 1 8. 解：設 f(bt，x，h)回傳二叉樹 bt 中 x 結點的層次，其中 h 表示 bt 所指結點的層 次，初始呼叫時，bt 指向根結點，h 置為 1，其遞回模型如下： f(bt，x，h)=0 當 bt=NULL f(bt，x，h)=h 當 bt≠NULL 且 bt->data=https://www.cnblogs.com/JUSTDOINS/p/x 當 l=f(bt->lchild，x，h+1)≠0 其他情況 f(bt，x，h) =l f(bt，x，h) =f(bt->rchild，x，h+1) 對應的遞回程式如下： # include "Btree.cpp" //包含二叉樹的基本運算演算法 int Level(BTNode *bt,int x,int h) //求二叉樹 bt中 x結點的層次 { //初始呼叫時：bt為根，h為 1 if (bt==NULL) return 0; if (bt->data=https://www.cnblogs.com/JUSTDOINS/p/=x) return h; //找到 x結點，回傳 h else { int l=Level(bt->lchild,x,h+1); //在左子樹中查找 if (l!=0) return l; //在左子樹中找到，回傳其層次 l else return Level(bt->rchild,x,h+1);//回傳在右子樹的查找結果 } } void main() { BTNode *bt; Int a[]={5,2,3,4,1,6}; Int b[]={2,3,5,1,4,6}; int n=sizeof(a)/sizeof(a[0]); bt=CreateBTree(a,b,n); //由 a和 b構造二叉鏈 bt printf("二叉樹 bt:"); DispBTree(bt); printf("\n"); int x=1; printf("%d結點的層次: %d\n",x,Level(bt,x,1)); DestroyBTree(bt); //銷毀樹 bt } 上述程式的執行結果如圖 1.20 所示， 圖 1.20 程式執行結果 2 0 第 1 章 概論 1 .3 第 3 章─分治法 1 .3.1 練習題 分治法的設計思想是將一個難以直接解決的大問題分割成規模較小的子問題，分 別解決子問題，最后將子問題的解組合起來形成原問題的解，這要求原問題和子問題 ）， A.問題規模相同，問題性質相同 1 . （ B.問題規模相同，問題性質不同 C.問題規模不同，問題性質相同 D.問題規模不同，問題性質不同 2 . 在尋找 n 個元素中第 k 小元素問題中，如快速排序演算法思想，運用分治演算法對 n 個元素進行劃分，如何選擇劃分基準？下面（ ）答案解釋最合理， A.隨機選擇一個元素作為劃分基準 B.取子序列的第一個元素作為劃分基準 C.用中位數的中位數方法尋找劃分基準 D.以上皆可行，但不同方法，演算法復雜度上界可能不同 3 . 對于下列二分查找演算法，以下正確的是（ ）， A. int binarySearch(int a[], int n, int x) { int low=0, high=n-1; while(low<=high) { int mid=(low+high)/2; if(x==a[mid]) return mid; if(x>a[mid]) low=mid; else high=mid; } return –1; } B. int binarySearch(int a[], int n, int x) { int low=0, high=n-1; while(low+1!=high) { int mid=(low+high)/2; if(x>=a[mid]) low=mid; else high=mid; } if(x==a[low]) return low; else return –1; } C. int binarySearch (int a[], int n, int x) { int low=0, high=n-1; while(low<high-1) { int mid=(low+high)/2; 2 1 演算法設計 if(x<a[mid]) high=mid; else low=mid; } if(x==a[low]) return low; else return –1; } D. int binarySearch(int a[], int n, int x) { if(n > 0 && x >= a[0]) { int low = 0, high = n-1; while(low < high) { int mid=(low+high+1)/2; if(x < a[mid]) high=mid-1; else low=mid; } if(x==a[low]) return low; } return –1; } 4 5 . 快速排序演算法是根據分治策略來設計的，簡述其基本思想， . 假設含有 n 個元素的待排序的資料 a 恰好是遞減排列的，說明呼叫 QuickSort(a， 0 ，n-1)遞增排序的時間復雜度為 O(n2)， 6 . 以下哪些演算法采用分治策略： （ （ （ （ 1）堆排序演算法 2）二路歸并排序演算法 3）折半查找演算法 4）順序查找演算法 7 8 . 適合并行計算的問題通常表現出哪些特征？ . 設有兩個復數 x=a+bi 和 y=c+di，復數乘積 xy 可以使用 4 次乘法來完成，即 xy=(ac-bd)+(ad+bc)i，設計一個僅用 3 次乘法來計算乘積 xy 的方法， 9 1 1 1 . 有 4 個陣列 a、b、c 和 d，都已經排好序，說明找出這 4 個陣列的交集的方法， 0. 設計一個演算法，采用分治法求一個整數序列中的最大最小元素， 1. 設計一個演算法，采用分治法求 xn， 2. 假設二叉樹采用二叉鏈存盤結構進行存盤，設計一個演算法采用分治法求一棵二叉 樹 bt 的高度， 1 3. 假設二叉樹采用二叉鏈存盤結構進行存盤，設計一個演算法采用分治法求一棵二叉 樹 bt 中度為 2 的結點個數， 1 4. 有一種二叉排序樹，其定義是空樹是一棵二叉排序樹，若不空，左子樹中所有結 點值小于根結點值，右子樹中所有結點值大于根結點值，并且左右子樹都是二叉排序樹， 現在該二叉排序樹采用二叉鏈存盤，采用分治法設計查找值為 x 的結點地址，并分析演算法 的最好的平均時間復雜度， 2 2 第 1 章 概論 1 5. 設有 n 個互不相同的整數，按遞增順序存放在陣列 a[0..n-1]中，若存在一個下標 i（0≤i<n），使得 a[i]=i，設計一個演算法以 O(log2n)時間找到這個下標 i， 1 6. 請你模仿二分查找程序設計一個三分查找演算法，分析其時間復雜度， 1 7. 對于大于 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， 2=2*3*2，12=2*2*3，設計一個演算法求 n 的不同分解式個數， 8. 設計一個基于 BSP 模型的并行演算法，假設有 p 臺處理器，計算整數陣列 a[0..n-1] 的所有元素之和，并分析演算法的時間復雜度， 1 1 1.3.2 練習題參考答案 1 2 3 . 答：C， . 答：D， . 答：以 a[]={1，2，3，4，5}為例說明，選項 A 中在查找 5 時出現死回圈，選項 B 中在查找 5 時回傳-1，選項 C 中在查找 5 時回傳-1，選項 D 正確， 4. 答：對于無序序列 a[low..high]進行快速排序，整個排序為“大問題”，選擇其中的 一個基準 base=a[i]（通常以序列中第一個元素為基準），將所有小于等于 base 的元素移動 到它的前面，所有大于等于 base 的元素移動到它的后面，即將基準歸位到 a[i]，這樣產生 a[low..i-1]和 a[i+1..high]兩個無序序列，它們的排序為“小問題”，當 a[low..high]序列只 有一個元素或者為空時對應遞回出口， 所以快速排序演算法就是采用分治策略，將一個“大問題”分解為兩個“小問題”來求 解，由于元素都是在 a 陣列中，其合并程序是自然產生的，不需要特別設計， 5 . 答：此時快速排序對應的遞回樹高度為 O(n)，每一次劃分對應的時間為 O(n)，所 以整個排序時間為 O(n2)， 6 7 . 答：其中二路歸并排序和折半查找演算法采用分治策略， . 答：適合并行計算的問題通常表現出以下特征： （ 1）將作業分離成離散部分，有助于同時解決，例如，對于分治法設計的串行算 法，可以將各個獨立的子問題并行求解，最后合并成整個問題的解，從而轉化為并行算 法， （ （ 2）隨時并及時地執行多個程式指令， 3）多計算資源下解決問題的耗時要少于單個計算資源下的耗時， 8 . 答：xy=(ac-bd)+((a+b)(c+d)-ac-bd)i，由此可見，這樣計算 xy 只需要 3 次乘法（即 ac、bd 和(a+b)(c+d)乘法運算）， 答：采用基本的二路歸并思路，先求出 a、b 的交集 ab，再求出 c、d 的交集 cd， 最后求出 ab 和 cd 的交集，即為最后的結果，也可以直接采用 4 路歸并方法求解， 0. 解：采用類似求求一個整數序列中的最大次大元素的分治法思路，對應的程式如 9 . 1 下： # # # include <stdio.h> define max(x,y) ((x)>(y)?(x):(y)) define min(x,y) ((x)<(y)?(x):(y)) 2 3 演算法設計 void MaxMin(int a[],int low,int high,int &maxe,int &mine) //求a中最大最小元素 { if (low==high) //只有一個元素 //只有兩個元素 //有兩個以上元素 { maxe=a[low]; mine=a[low]; } else if (low==high-1) { maxe=max(a[low],a[high]); mine=min(a[low],a[high]); } else { int mid=(low+high)/2; int lmaxe,lmine; MaxMin(a,low,mid,lmaxe,lmine); int rmaxe,rmine; MaxMin(a,mid+1,high,rmaxe,rmine); maxe=max(lmaxe,rmaxe); mine=min(lmine,rmine); } } void main() { int a[]={4,3,1,2,5}; int n=sizeof(a)/sizeof(a[0]); int maxe,mine; MaxMin(a,0,n-1,maxe,mine); printf("Max=%d, Min=%d\n",maxe,mine); } 上述程式的執行結果如圖 1.21 所示， 圖 1.21 程式執行結果 1 1. 解：設 f(x，n)=xn，采用分治法求解對應的遞回模型如下： f(x，n)=x 當 n=1 f(x，n)=f(x，n/2)*f(x，n/2) f(x，n)=f(x，(n-1)/2)*f(x，(n-1)/2)*x 當 n 為偶數時 當 n 為奇數時 對應的遞回程式如下： # include <stdio.h> double solve(double x,int n) //求x^n { double fv; if (n==1) return x; if (n%2==0) { fv=solve(x,n/2); return fv*fv; } 2 4 第 1 章 概論 else { fv=solve(x,(n-1)/2); return fv*fv*x; } } void main() { double x=2.0; printf("求解結果:\n"); for (int i=1;i<=10;i++) printf(" %g^%d=%g\n",x,i,solve(x,i)); } 上述程式的執行結果如圖 1.22 所示， 圖 1.22 程式執行結果 1 2. 解：設 f(bt)回傳二叉樹 bt 的高度，對應的遞回模型如下： f(bt)=0 當 bt=NULL f(bt)=MAX{f(bt->lchild)，f(bt->rchild)}+1 其他情況 對應的程式如下： # include "Btree.cpp" //包含二叉樹的基本運算演算法 //求二叉樹bt的高度 int Height(BTNode *bt) { if (bt==NULL) return 0; int lh=Height(bt->lchild); int rh=Height(bt->rchild); if (lh>rh) return lh+1; else return rh+1; //子問題1 //子問題2 //合并 } void main() { BTNode *bt; Int a[]={5,2,3,4,1,6}; Int b[]={2,3,5,1,4,6}; int n=sizeof(a)/sizeof(a[0]); bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt printf("二叉樹bt:"); DispBTree(bt); printf("\n"); printf("bt的高度: %d\n",Height(bt)); DestroyBTree(bt); //銷毀樹bt } 2 5 演算法設計 上述程式的執行結果如圖 1.23 所示， 圖 1.23 程式執行結果 1 3. 解：設 f(bt)回傳二叉樹 bt 中度為 2 的結點個數，對應的遞回模型如下： f(bt)=0 當 bt=NULL f(bt)=f(bt->lchild)+f(bt->rchild)+1 f(bt)=f(bt->lchild)+f(bt->rchild) 若 bt≠NULL 且 bt 為雙分支結點 其他情況 對應的演算法如下： # include "Btree.cpp" //包含二叉樹的基本運算演算法 //求 bt中度為 2的結點個數 int Nodes(BTNode *bt) { int n=0; if (bt==NULL) return 0; if (bt->lchild!=NULL && bt->rchild!=NULL) n=1; return Nodes(bt->lchild)+Nodes(bt->rchild)+n; } void main() { BTNode *bt; Int a[]={5,2,3,4,1,6}; Int b[]={2,3,5,1,4,6}; int n=sizeof(a)/sizeof(a[0]); bt=CreateBTree(a,b,n); //由a和b構造二叉鏈bt printf("二叉樹bt:"); DispBTree(bt); printf("\n"); printf("bt中度為2的結點個數: %d\n",Nodes(bt)); DestroyBTree(bt); //銷毀樹bt } 上述程式的執行結果如圖 1.24 所示， 圖 1.24 程式執行結果 1 4. 解：設 f(bt，x)回傳在二叉排序樹 bt 得到的值為 x 結點的地址，若沒有找到回傳 空，對應的遞回模型如下： f(bt，x)=NULL 當 bt=NULL f(bt，x)=bt 當 bt≠NULL 且 x=bt->data 當 x>bt->data f(bt，x)=f(bt->lchild，x) 2 6 第 1 章 概論 f(bt，x)=f(bt->rchild，x) 當 x<bt->data 對應的程式如下： # include "Btree.cpp" //包含二叉樹的基本運算演算法 BTNode *Search(BTNode *bt,Int x) //在二叉排序樹 bt查找的值為 x結點 { if (bt==NULL) return NULL; if (x==bt->data) return bt; if (x<bt->data) return Search(bt->lchild,x); else return Search(bt->rchild,x); } void main() { BTNode *bt; Int a[]={4,3,2,8,6,7,9}; Int b[]={2,3,4,6,7,8,9}; int n=sizeof(a)/sizeof(a[0]); bt=CreateBTree(a,b,n); //構造一棵二叉排序樹 bt printf("二叉排序樹 bt:"); DispBTree(bt); printf("\n"); int x=6; BTNode *p=Search(bt,x); if (p!=NULL) printf("找到結點: %d\n",p->data); else printf("沒有找到結點\n",x); DestroyBTree(bt); //銷毀樹 bt } 上述程式的執行結果如圖 1.25 所示， 圖 1.25 程式執行結果 Search(bt，x)演算法采用的是減治法，最好的情況是某個結點左右子樹高度大致相同， 其平均執行時間 T(n)如下： T(n)=1 當 n=1 當 n>1 T(n)=T(n/2)+1 可以推出 T(n)=O(log2n)，其中 n 為二叉排序樹的結點個數， 15. 解：采用二分查找方法，a[i]=i 時表示該元素在有序非重復序列 a 中恰好第 i 大， 對于序列 a[low..high]，mid=(low+high)/2，若 a[mid]=mid 表示找到該元素；若 a[mid]>mid 說明右區間的所有元素都大于其位置，只能在左區間中查找；若 a[mid]<mid 說明左區間 的所有元素都小于其位置，只能在右區間中查找，對應的程式如下： # include <stdio.h> int Search(int a[],int n) int low=0,high=n-1,mid; //查找使得 a[i]=i { 2 7 演算法設計 while (low<=high) { mid=(low+high)/2; if (a[mid]==mid) return mid; else if (a[mid]<mid) low=mid+1; //查找到這樣的元素 //這樣的元素只能在右區間中出現 //這樣的元素只能在左區間中出現 else high=mid-1; } return -1; } void main() { int a[]={-2,-1,2,4,6,8,9}; int n=sizeof(a)/sizeof(a[0]); int i=Search(a,n); printf("求解結果\n"); if (i!=-1) printf(" 存在a[%d]=%d\n",i,i); else printf(" 不存在\n"); } 上述程式的執行結果如圖 1.26 所示， 圖 1.26 程式執行結果 1 6. 解：對于有序序列 a[low..high]，若元素個數少于 3 個，直接查找，若含有更多的 元素，將其分為 a[low..mid1-1]、a[mid1+1..mid2-1]、a[mid2+1..high]子序列，對每個子序 列遞回查找，演算法的時間復雜度為 O(log3n)，屬于 O(log2n)級別，對應的演算法如下： # include <stdio.h> int Search(int a[],int low,int high,int x) //三分查找 { if (high<low) return -1; //序列中沒有元素 else if (high==low) //序列中只有1個元素 { if (x==a[low]) return low; else return -1; } if (high-low<2) { if (x==a[low]) //序列中只有2個元素 return low; else if (x==a[low+1]) return low+1; else 2 8 第 1 章 概論 return -1; } int length=(high-low+1)/3; int mid1=low+length; int mid2=high-length; if (x==a[mid1]) //每個子序列的長度 return mid1; else if (x<a[mid1]) return Search(a,low,mid1-1,x); else if (x==a[mid2]) return mid2; else if (x<a[mid2]) return Search(a,mid1+1,mid2-1,x); else return Search(a,mid2+1,high,x); } void main() { int a[]={1,3,5,7,9,11,13,15}; int n=sizeof(a)/sizeof(a[0]); printf("求解結果\n"); int x=13; int i=Search(a,0,n-1,x); if (i!=-1) printf(" a[%d]=%d\n",i,x); else printf(" 不存在%d\n",x); int y=10; int j=Search(a,0,n-1,y); if (j!=-1) printf(" a[%d]=%d\n",j,y); else printf(" 不存在%d\n",y); } 上述程式的執行結果如圖 1.27 所示， 圖 1.27 程式執行結果 1 7. 解：設 f(n)表示 n 的不同分解式個數，有： f(1)=1，作為遞回出口 f(2)=1，分解式為：2=2 f(3)=1，分解式為：3=3 f(4)=2，分解式為：4=4，4=2*2 2 9 演算法設計 f(6)=3，分解式為：6=6，6=2*3，6=3*2，即 f(6)=f(1)+f(2)+f(3) 以此類推，可以看出 f(n)為 n 的所有因數的不同分解式個數之和，即 f(n)= ∑??? = 0?(???)，對應的程式如下： # # include <stdio.h> define MAX 101 int solve(int n) { if (n==1) return 1; //求 n的不同分解式個數 else { int sum=0; for (int i=2;i<=n;i++) if (n%i==0) sum+=solve(n/i); return sum; } } void main() { int n=12; int ans=solve(n); printf("結果: %d\n",ans); } 上述程式的執行結果如圖 1.28 所示， 圖 1.28 程式執行結果 1 8. 解：對應的并行演算法如下： int Sum(int a[],int s,int t,int p,int i) //處理器i執行求和 { int j,s=0; for (j=s;j<=t;j++) s+=a[j]; return s; } int ParaSum(int a[],int s,int t,int p,int i) { int sum=0,j,k=0,sj; for (j=0;j<p;j++) //for回圈的各個子問題并行執行 { sj=Sum(a,k,k+n/p-1,p,j); k+=n/p; } sum+=sj; return sum; } 每個處理器的執行時間為O(n/p)，同步開銷為O(p)，所以該演算法的時間復雜度為 O(n/p+p)， 3 0 第 1 章 概論 1 .4 第 4 章─蠻力法 1.4.1 練習題 1 2 3 . 簡要比較蠻力法和分治法， . 在采用蠻力法求解時什么情況下使用遞回？ . 考慮下面這個演算法，它求的是陣列 a 中大小相差最小的兩個元素的差，請對這個 演算法做盡可能多的改進， # # define INF 99999 define abs(x) (x)<0?-(x):(x) //求絕對值宏 int Mindif(int a[],int n) { int dmin=INF; for (int i=0;i<=n-2;i++) for (int j=i+1;j<=n-1;j++) { int temp=abs(a[i]-a[j]); if (temp<dmin) dmin=temp; } return dmin; } 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 中逆序對的個數即逆序數， 5 . 對于給定的正整數 n（n>1）, 采用蠻力法求 1!+2!+…+n!，并改進該演算法提高效 率， 6 . 有一群雞和一群兔，它們的只數相同，它們的腳數都是三位數，且這兩個三位數 的各位數字只能是 0、1、2、3、4、5，設計一個演算法用蠻力法求雞和兔的只數各是多 少？它們的腳數各是多少？ 7 . 有一個三位數，個位數字比百位數字大，而百位數字又比十位數字大，并且各位 數字之和等于各位數字相乘之積，設計一個演算法用窮舉法求此三位數， . 某年級的同學集體去公園劃船，如果每只船坐 10 人，那么多出 2 個座位；如果每 只船多坐 2 人，那么可少租 1 只船，設計一個演算法用蠻力法求該年級的最多人數？ 已知：若一個合數的質因數分解式逐位相加之和等于其本身逐位相加之和，則稱 這個數為 Smith 數，如 4937775=3*5*5*65837，而 3+5+5+6+5+8+3+7=42， +9+3+7+7+7+5=42，所以 4937775 是 Smith 數，求給定一個正整數 N，求大于 N 的最小 Smith 數， 輸入：若干個 case，每個 case 一行代表正整數 N，輸入 0 表示結束 8 9 . 4 輸出：大于 N 的最小 Smith 數 輸入樣例： 4 0 937774 樣例輸出： 3 1 演算法設計 4 937775 1 0. 求解涂棋盤問題，小易有一塊 n*n 的棋盤，棋盤的每一個格子都為黑色或者白 色，小易現在要用他喜歡的紅色去涂畫棋盤，小易會找出棋盤中某一列中擁有相同顏色的 最大的區域去涂畫，幫助小易算算他會涂畫多少個棋格， 輸入描述：輸入資料包括 n+1 行：第一行為一個整數 n（1≤ n≤50），即棋盤的大 小，接下來的 n 行每行一個字串表示第 i 行棋盤的顏色，'W'表示白色，'B'表示黑色， 輸出描述：輸出小易會涂畫的區域大小， 輸入例子： 3 BWW BBB BWB 輸出例子： 3 1 1. 給定一個含 n（n>1）個整數元素的 a，所有元素不相同，采用蠻力法求出 a 中所 有元素的全排列， 1.4.2 練習題參考答案 1 . 答：蠻力法是一種簡單直接地解決問題的方法，適用范圍廣，是能解決幾乎所有 問題的一般性方法，常用于一些非常基本、但又十分重要的演算法（排序、查找、矩陣乘法 和字串匹配等），蠻力法主要解決一些規模小或價值低的問題，可以作為同樣問題的更 高效演算法的一個標準，而分治法采用分而治之思路，把一個復雜的問題分成兩個或更多的 相同或相似的子問題，再把子問題分成更小的子問題直到問題解決，分治法在求解問題 時，通常性能比蠻力法好， 2 . 答：如果用蠻力法求解的問題可以分解為若干個規模較小的相似子問題，此時可 以采用遞回來實作演算法， . 解：上述演算法的時間復雜度為 O(n2)，采用的是最基本的蠻力法，可以先對 a 中元 素遞增排序，然后依次比較相鄰元素的差，求出最小差，改進后的演算法如下： 3 # # include <stdio.h> include <algorithm> using namespace std; int Mindif1(int a[],int n) { sort(a,a+n); //遞增排序 int dmin=a[1]-a[0]; for (int i=2;i<n;i++) { int temp=a[i]-a[i-1]; if (temp<dmin) dmin=temp; } return dmin; } 3 2 第 1 章 概論 上述演算法的主要時間花費在排序上，演算法的時間復雜度為 O(nlog2n)， 4 . 解：采用兩重回圈直接判斷是否為逆序對，演算法的時間復雜度為 O(n2)，比第 3 章 實驗 3 演算法的性能差，對應的演算法如下： int solve(int a[],int n) //求逆序數 { int ans=0; for (int i=0;i<n-1;i++) for (int j=i+1;j<n;j++) if (a[i]>a[j]) ans++; return ans; } 5 . 解：直接采用蠻力法求解演算法如下： long f(int n) //求n! { long fn=1; for (int i=2;i<=n;i++) fn=fn*i; return fn; } long solve(int n) //求1!+2!+…+n! { long ans=0; for (int i=1;i<=n;i++) ans+=f(i); return ans; } 實際上，f(n)=f(n-1)*n，f(1)=1，在求 f(n)時可以利用 f(n-1)的結果，改進后的演算法如 下： long solve1(int n) //求1!+2!+…+n! { long ans=0; long fn=1; for (int i=1;i<=n;i++) { fn=fn*i; ans+=fn; } return ans; } 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 時輸出結果，對應的程式如下： # include <stdio.h> void solve() int a,b,c,d,e,f; { int x1,x2,y,z; for (a=1;a<=5;a++) for (b=0;b<=5;b++) for (c=0;c<=5;c++) 3 3 演算法設計 for (d=1;d<=5;d++) for (e=0;e<=5;e++) for (f=0;f<=5;f++) { y=a*100+b*10+c; z=d*100+e*10+f; if (y%2!=0 || z%4!=0) continue; //雞腳數 //兔腳數 x1=y/2; //雞只數 //兔只數 x2=z/4; if (x1==x2) printf(" 雞只數:%d,兔只數:%d,雞腳數:%d, 兔腳數:%d\n",x1,x2,y,z); } } void main() { printf("求解結果\n"); solve(); } 上述程式的執行結果如圖 1.29 所示， 圖 1.29 程式執行結果 7 . 解：設該三位數為 x=abc，有 1≤a≤9，0≤b，c≤9，滿足 c>a，a>b， a+b+c=a*b*c，對應的程式如下： # include <stdio.h> void solve() { int a,b,c; for (a=1;a<=9;a++) for (b=0;b<=9;b++) for (c=0;c<=9;c++) { if (c>a && a>b && a+b+c==a*b*c) printf(" %d%d%d\n",a,b,c); } } void main() 3 4 第 1 章 概論 { } printf("求解結果\n"); solve(); 上述程式的執行結果如圖 1.30 所示， 圖 1.30 程式執行結果 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 即可，對應的程式如下： # include <stdio.h> int solve() { int x,y,z; for (y=1;y<=100;y++) for (z=0;z<12;z++) if (10*y-2==12*(y-1)-z) x=10*y-2; return x; } void main() { printf("求解結果\n"); printf(" 最多人數:%d\n",solve()); } 上述程式的執行結果如圖 1.31 所示， 圖 1.31 程式執行結果 9 . 解：采用蠻力法求出一個正整數 n 的各位數字和 sum1，以及 n 的所有質因數的數 字和 sum2，若 sum1=sum2，即為 Smitch 數，從用戶輸入的 n 開始列舉，若是 Smitch 數，輸出，本次結束，否則 n++繼續查找大于 n 的最小 Smitch 數，對應的完整程式如 下： # include <stdio.h> int Sum(int n) //求n的各位數字和 { int sum=0; while (n>0) 3 5 演算法設計 { } sum+=n%10; n=n/10; return sum; } bool solve(int n) //判斷n是否為Smitch數 { int m=2; int sum1=Sum(n); int sum2=0; while (n>=m) { if (n%m==0) //找到一個質因數m { n=n/m; sum2+=Sum(m); } else m++; } if (sum1==sum2) return true; else return false; } void main() { int n; while (true) { scanf("%d",&n); if (n==0) break; while (!solve(n)) n++; printf("%d\n",n); } } 1 0. 解：采用蠻力法，統計每一列相鄰相同顏色的棋格個數 countj，在 countj 中求最 大值，對應的程式如下： # # / include <stdio.h> define MAXN 51 /問題表示 int n; char board[MAXN][MAXN]; int getMaxArea() //蠻力法求解演算法 { int maxArea=0; for (int j=0; j<n; j++) { int countj=1; for (int i=1; i<n; i++) //統計第j列中相同顏色相鄰棋格個數 { } if (board[i][j]==board[i-1][j]) countj++; countj=1; else 3 6 第 1 章 概論 if (countj>maxArea) maxArea=countj; } return maxArea; } int main() { scanf("%d",&n); for (int i=0;i<n;i++) scanf("%s",board[i]); printf("%d\n",getMaxArea()); return 0; } 1 1. 解：與《教程》中求全排列類似，但需要將求 1～n 的全排列改為按下標 0～n-1 求 a 的全排列（下標從 0 開始），采用非遞回的程式如下： # # include <stdio.h> include <vector> using namespace std; vector<vector<int> > ps; //存放全排列 void Insert(vector<int> s,int a[],int i,vector<vector<int> > &ps1) / /在每個集合元素中間插入i得到ps1 vector<int> s1; { vector<int>::iterator it; for (int j=0;j<=i;j++) //在s(含i個整數)的每個位置插入a[i] { s1=s; it=s1.begin()+j; s1.insert(it,a[i]); ps1.push_back(s1); //求出插入位置 //插入整數a[i] //添加到ps1中 } } void Perm(int a[],int n) //求a[0..n-1]的所有全排列 //臨時存放子排列 { vector<vector<int> > ps1; vector<vector<int> >::iterator it; vector<int> s,s1; //全排列迭代器 s.push_back(a[0]); ps.push_back(s); //添加{a[0]}集合元素 //回圈添加a[1]～a[n-1] //ps1存放插入a[i]的結果 for (int i=1;i<n;i++) { ps1.clear(); for (it=ps.begin();it!=ps.end();++it) Insert(*it,a,i,ps1); ps=ps1; //在每個集合元素中間插入a[i]得到ps1 } } void dispps() vector<vector<int> >::reverse_iterator it; //輸出全排列 ps { //全排列的反向迭代器 //排列集合元素迭代器 vector<int>::iterator sit; for (it=ps.rbegin();it!=ps.rend();++it) { for (sit=(*it).begin();sit!=(*it).end();++sit) printf("%d",*sit); printf(" "); 3 7 演算法設計 } printf("\n"); } void main() { int a[]={2,5,8}; int n=sizeof(a)/sizeof(a[0]); printf("a[0～%d]的全排序如下:\n ",n-1); Perm(a,n); dispps(); } 上述程式的執行結果如圖 1.32 所示， 圖 1.32 程式執行結果 1 .5 第 5 章─回溯法 1 .5.1 練習題 . 回溯法在問題的解空間樹中，按（ ）策略，從根結點出發搜索解空間樹， A.廣度優先 B.活結點優先 C.擴展結點優先 D.深度優先 . 關于回溯法以下敘述中不正確的是（ ）， 1 2 A.回溯法有“通用解題法”之稱，它可以系統地搜索一個問題的所有解或任意解 B.回溯法是一種既帶系統性又帶有跳躍性的搜索演算法 C.回溯演算法需要借助佇列這種結構來保存從根結點到當前擴展結點的路徑 D.回溯演算法在生成解空間的任一結點時，先判斷該結點是否可能包含問題的解，如果 肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向祖先結點回溯 3. 回溯法的效率不依賴于下列哪些因素（ ）， A.確定解空間的時間 B.滿足顯約束的值的個數 D.計算限界函式的時間 C.計算約束函式的時間 4 . 下面（ ）函式是回溯法中為避免無效搜索采取的策略， A.遞回函式 B.剪枝函式 C.亂數函式 D.搜索函式 5 6 .回溯法的搜索特點是什么？ . 用回溯法解 0/1 背包問題時，該問題的解空間是何種結構？用回溯法解流水作業調 度問題時，該問題的解空間是何種結構？ . 對于遞增序列 a[]={1，2，3，4，5}，采用例 5.4 的回溯法求全排列，以 1、2 開頭 的排列一定最先出現嗎？為什么？ 考慮 n 皇后問題，其解空間樹為由 1、2、…、n 構成的 n!種排列所組成，現用回 7 8 . 3 8 第 1 章 概論 溯法求解，要求： （ （ （ 1）通過解搜索空間說明 n=3 時是無解的， 2）給出剪枝操作， 3）最壞情況下在解空間樹上會生成多少個結點？分析演算法的時間復雜度， 設計一個演算法求解簡單裝載問題，設有一批集裝箱要裝上一艘載重量為 W 的輪 9 . 船，其中編號為 i（0≤i≤n-1）的集裝箱的重量為 wi，現要從 n 個集裝箱中選出若干裝上 輪船，使它們的重量之和正好為 W，如果找到任一種解回傳 true，否則回傳 false， 1 0. 給定若干個正整數a0、a0 、…、an-1 ，從中選出若干數，使它們的和恰好為k， 要求找選擇元素個數最少的解， 1. 設計求解有重復元素的排列問題的演算法，設有 n 個元素 a[]={a0，a1，…，an-1)， 其中可能含有重復的元素，求這些元素的所有不同排列，如 a[]={1，1，2}，輸出結果是 1，1，2)，（1，2，1），（2，1，1）， 2. 采用遞回回溯法設計一個演算法求1～n的n個整數中取出m個元素的排列，要求每個 元素最多只能取一次，例如，n=3，m=2的輸出結果是（1，2），（1，3），（2，1）， 2，3），（3，1），（3，2）， 3. 對于n皇后問題，有人認為當n為偶數時，其解具有對稱性，即n皇后問題的解個 數恰好為n/2皇后問題的解個數的2倍，這個結論正確嗎？請撰寫回溯法程式對n=4、6、 、10的情況進行驗證， 4. 給定一個無向圖，由指定的起點前往指定的終點，途中經過所有其他頂點且只經 1 （ 1 （ 1 8 1 過一次，稱為哈密頓路徑，閉合的哈密頓路徑稱作哈密頓回路（Hamiltonian cycle），設計 一個回溯演算法求無向圖的所有哈密頓回路， 1.5.2 練習題參考答案 1 2 . 答：D， . 答：回溯演算法是采用深度優先遍歷的，需要借助系統堆疊結構來保存從根結點到當 前擴展結點的路徑，答案為 C， 3 4 5 . 答：回溯法解空間是虛擬的，不必確定整個解空間，答案為 A， . 答：B， . 答：回溯法在解空間樹中采用深度優先遍歷方式進行解搜索，即用約束條件和限 界函式考察解向量元素 x[i]的取值，如果 x[i]是合理的就搜索 x[i]為根結點的子樹，如果 x[i]取完了所有的值，便回溯到 x[i-1]， 6 . 答：用回溯法解 0/1 背包問題時，該問題的解空間是子集樹結構，用回溯法解流水 作業調度問題時，該問題的解空間是排列樹結構， 答：是的，對應的解空間是一棵排列樹，如圖 1.33 所示給出前面 3 層部分，顯然 最先產生的排列是從 G 結點擴展出來的葉子結點，它們就是以 1、2 開頭的排列， 7 . 3 9 演算法設計 A 5 1 3 2 4 B C D E F 2 5 3 4 G H I J 圖 1.33 部分解空間樹 8 . 答：（1）n=3 時的解搜索空間如圖 1.34 所示，不能得到任何葉子結點，所有無 解， （ （ 2）剪枝操作是任何兩個皇后不能同行、同列和同兩條對角線， 3）最壞情況下每個結點擴展 n 個結點，共有 nn 個結點，演算法的時間復雜度為 O(nn)， (*,*,*) ( 1,*,*) 1,3,*) (2,*,*) (3,*,*) (3,1,*) ( 圖 1.34 3 皇后問題的解搜索空間 9 . 解：用陣列 w[0..n-1]存放 n 個集裝箱的重量，采用類似判斷子集和是否存在解的 方法求解，對應完整的求解程式如下： # # / include <stdio.h> define MAXN 20 /問題表示 //最多集裝箱個數 int n=5,W; int w[]={2,9,5,6,3}; int count; //全域變數，累計解個數 //求解簡單裝載問題 void dfs(int tw,int rw,int i) { if (i>=n) //找到一個葉子結點 { if (tw==W) count++; //找到一個滿足條件的解,輸出它 } else { //尚未找完 rw-=w[i]; if (tw+w[i]<=W) dfs(tw+w[i],rw,i+1); if (tw+rw>=W) dfs(tw,rw,i+1); //求剩余的集裝箱重量和 //左孩子結點剪枝：選取滿足條件的集裝箱w[i] //選取第i個集裝箱 //右孩子結點剪枝：剪除不可能存在解的結點 //不選取第i個集裝箱,回溯 } } bool solve() //判斷簡單裝載問題是否存在解 4 0 第 1 章 概論 { count=0; int rw=0; for (int j=0;j<n;j++) rw+=w[j]; //求所有集裝箱重量和rw //i從0開始 dfs(0,rw,0); if (count>0) return true; else return false; } void main() { printf("求解結果\n"); W=4; printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); W=10; printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); W=12; printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); W=21; printf(" W=%d時%s\n",W,(solve()?"存在解":"沒有解")); } 本程式執行結果如圖 1.35 所示， 圖 1.35 程式執行結果 1 0. 解：這是一個典型的解空間為子集樹的問題，采用子集樹的回溯演算法框架，當找 到一個解后通過選取的元素個數進行比較求最優解 minpath，對應的完整程式如下： # # include <stdio.h> include <vector> using namespace std; / /問題表示 int a[]={1,2,3,4,5}; int n=5,k=9; //設定為全域變數 //存放最優解 vector<int> minpath; / /求解結果表示 int minn=n; //最多選擇n個元素 //輸出一個解 void disppath() { } printf(" 選擇的元素:"); for (int j=0;j<minpath.size();j++) printf("%d ",minpath[j]); printf("元素個數=%d\n",minn); 4 1 演算法設計 void dfs(vector<int> path,int sum,int start) //求解演算法 { if (sum==k) //如果找到一個解，不一定到葉子結點 { if (path.size()<minn) { minn=path.size(); minpath=path; } return; } if (start>=n) return; //全部元素找完，回傳 //不選擇a[start] //選擇a[start] dfs(path,sum,start+1); path.push_back(a[start]); dfs(path,sum+a[start],start+1); } void main() { vector<int> path; //path存放一個子集 dfs(path,0,0); printf("最優解:\n"); disppath(); } 上述程式的執行結果如圖 1.36 所示， 圖 1.36 程式執行結果 1 1. 解：在回溯法求全排列的基礎上，增加元素的重復性判斷，例如，對于 a[]={1， 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]的位置，如果出現，對應的排 列已經在前面求出了，對應的完整程式如下： # include <stdio.h> bool ok(int a[],int i,int j) //ok用于判別重復元素 { if (j>i) { for(int k=i;k<j;k++) if (a[k]==a[j]) return false; } return true; } void swap(int &x,int &y) //交換兩個元素 { int tmp=x; x=y; y=tmp; } void dfs(int a[],int n,int i) { if (i==n) //求有重復元素的排列問題 4 2 第 1 章 概論 { for(int j=0;j<n;j++) printf("%3d",a[j]); printf("\n"); } else { for (int j=i;j<n;j++) if (ok(a,i,j)) //選取與a[i..j-1]不重復的元素a[j] { swap(a[i],a[j]); dfs(a,n,i+1); swap(a[i],a[j]); } } } void main() { int a[]={1,2,1,2}; int n=sizeof(a)/sizeof(a[0]); printf("序列("); for (int i=0;i<n-1;i++) printf("%d ",a[i]); printf("%d)的所有不同排列:\n",a[n-1]); dfs(a,n,0); } 上述程式的執行結果如圖 1.37 所示， 圖 1.37 程式執行結果 1 2. 解：采用求全排列的遞回框架，選取的元素個數用 i 表示（i 從 1 開始），當 i>m 時達到一個葉子結點，輸出一個排列，為了避免重復，用 used 陣列實作，used[i]=0 表示 沒有選擇整數 i，used[i]=1 表示已經選擇整數 i，對應的完整程式如下： # # # # include <stdio.h> include <string.h> define MAXN 20 define MAXM 10 int m,n; int x[MAXM]; bool used[MAXN]; void dfs(int i) //x[1..m]存放一個排列 //求n個元素中m個元素的全排列 { if (i>m) for (int j=1;j<=m;j++) printf(" %d",x[j]); printf("\n"); { //輸出一個排列 4 3 演算法設計 } else { for (int j=1;j<=n;j++) { if (!used[j]) { used[j]=true; //修改used[i] x[i]=j; //x[i]選擇j dfs(i+1); //繼續搜索排列的下一個元素 //回溯：恢復used[i] used[j]=false; } } } } void main() { n=4,m=2; memset(used,0,sizeof(used)); printf("n=%d,m=%d的求解結果\n",n,m); dfs(1); //初始化為0 //i從1開始 } 上述程式的執行結果如圖 1.38 所示， 圖 1.38 程式執行結果 1 3. 解：這個結論不正確，驗證程式如下： # # # include <stdio.h> include <stdlib.h> define MAXN 10 int q[MAXN]; bool place(int i) //測驗第i行的q[i]列上能否擺放皇后 //j=1～i-1是已放置了皇后的行 { int j=1; if (i==1) return true; while (j<i) { if ((q[j]==q[i]) || (abs(q[j]-q[i])==abs(j-i))) /該皇后是否與以前皇后同列，位置(j,q[j])與(i,q[i])是否同對角線 return false; / j++; } return true; } 4 4 第 1 章 概論 int Queens(int n) //求n皇后問題的解個數 { int count=0,k; int i=1; //計數器初始化 //i為當前行 q[1]=0; //q[i]為皇后i的列號 while (i>0) { q[i]++; //移到下一列 while (q[i]<=n && !place(i)) q[i]++; if (q[i]<=n) { if (i==n) count++; //找到一個解計數器count加1 else { i++;; q[i]=0; } } else i--; //回溯 } return count; } void main() { printf("驗證結果如下:\n"); for (int n=4;n<=10;n+=2) if (Queens(n)==2*Queens(n/2)) printf(" n=%d: 正確\n",n); else printf(" n=%d: 錯誤\n",n); } 上述程式的執行結果如圖1.39所示，從執行結果看出結論是不正確的， 圖 1.39 程式執行結果 1 4. 解：假設給定的無向圖有 n 個頂點（頂點編號從 0 到 n-1），采用鄰接矩陣陣列 a （ 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 皇后問 題的非遞回回溯框架類似）的完整程式如下： # # include <stdio.h> define MAXV 10 4 5 演算法設計 / /求解問題表示 int n=5; //圖中頂點個數 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}}; //鄰接矩陣陣列 / /求解結果表示 int x[MAXV]; int count; void dispasolution() //輸出一個解路徑 { for (int i=0;i<=n-1;i++) printf("(%d,%d) ",x[i],x[i+1]); printf("\n"); } bool valid(int i) //判斷頂點第i個頂點x[i]的有效性 //x[i-1]到x[i]沒有邊，回傳false { if (a[x[i-1]][x[i]]!=1) return false; for (int j=0;j<=i-1;j++) if (x[i]==x[j]) return false; //頂點i重復出現，回傳false return true; } void Hamiltonian(int v) //求從頂點v出發的哈密頓回路 //存放起點 { x[0]=v; int i=1; x[i]=-1; while (i>0) //從頂點-1+1=0開始試探 //尚未回溯到頭，回圈 { x[i]++; while (!valid(i) && x[i]<n) x[i]++; //試探一個頂點x[i] if (x[i]<n) //找到一個有效的頂點x[i] //達到葉子結點 { if (i==n-1) { if (a[x[i]][v]==1) { x[n]=v; //找到一個解 printf(" 第%d個解: ",count++); dispasolution(); } } else { i++; x[i]=-1; } } else i--; //回溯 } } void main() { printf("求解結果\n"); for (int v=0;v<n;v++) { printf(" 從頂點%d出發的哈密頓回路:\n",v); count=1; 4 6 第 1 章 概論 Hamiltonian(v); //從頂點v出發 } } 上述程式對如圖 1.40 所示的無向圖求從每個頂點出發的哈密頓回路，程式執行結果 如圖 1.41 所示， 1 3 2 0 4 圖 1.40 一個無向圖 圖 1.41 程式執行結果 1 .6 第 6 章─分枝限界法 1 .6.1 練習題 . 分枝限界法在問題的解空間樹中，按（ ）策略，從根結點出發搜索解空間樹， A.廣度優先 B.活結點優先 C.擴展結點優先 D. 深度優先 . 常見的兩種分枝限界法為（ ）， A.廣度優先分枝限界法與深度優先分枝限界法 1 2 4 7 演算法設計 B.佇列式（FIFO）分枝限界法與堆疊式分枝限界法 C.排列樹法與子集樹法 D.佇列式（FIFO）分枝限界法與優先佇列式分枝限界法 3 . 分枝限界法求解 0/1 背包問題時，活結點表的組織形式是（ ）， A.小根堆 B.大根堆 C.堆疊 D.陣列 4 . 采用最大效益優先搜索方式的演算法是（ ）， A.分支界限法 B.動態規劃法 C.貪心法 D.回溯法 D.隨機 5 . 優先佇列式分枝限界法選取擴展結點的原則是（ ）， A.先進先出 B.后進先出 C.結點的優先級 . 簡述分枝限界法的搜索策略， 有一個 0/1 背包問題，其中 n=4，物品重量為（4，7，5，3），物品價值為（40， 6 7 . 4 2，25，12），背包最大載重量 W=10，給出采用優先佇列式分枝限界法求最優解的程序， . 有一個流水作業調度問題，n=4，a[]={5，10，9，7}，b[]={7，5，9，8}，給出采 用優先佇列式分枝限界法求一個解的程序， 有一個含 n 個頂點（頂點編號為 0～n-1）的帶權圖，采用鄰接矩陣陣列 A 表示， 8 9 . 采用分枝限界法求從起點 s 到目標點 t 的最短路徑長度，以及具有最短路徑長度的路徑條 數， 1 0. 采用優先佇列式分枝限界法求解最優裝載問題，給出以下裝載問題的求解程序和 結果：n=5，集裝箱重量為 w=（5，2，6，4，3），限重為 W=10，在裝載重量相同時，最 優裝載方案是集裝箱個數最少的方案， 1.6.2 練習題參考答案 1 2 3 4 5 6 . 答：A， . 答：D， . 答：B， . 答：A， . 答：C， . 答：分枝限界法的搜索策略是廣度優先遍歷，通過限界函式可以快速找到一個解 或者最優解， 7 . 答：求解程序如下： （ （ 1）根結點 1 進隊，對應結點值：e.i=0，e.w=0，e.v=0，e.ub=76，x:[0，0，0，0]， 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]， （ 3）出隊結點 2：左孩子超重；右孩子結點 4 進隊，對應結點值：e.no=4，e.i=2， e.w=4，e.v=40，e.ub=69，x:[1，0，0，0]， 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]， 4 8 第 1 章 概論 （ （ 5）出隊結點 5：產生一個解，maxv= 65，bestx:[1，0，1，0]， 6）出隊結點 3：左孩子結點 8 進隊，對應結點值：e.no=8，e.i=2，e.w=7， e.v=42，e.ub=57，x:[0，1，0，0]；右孩子結點 9 被剪枝， （ （ （ 7）出隊結點 8：左孩子超重；右孩子結點 10 被剪枝， 8）出隊結點 6：左孩子結點 11 超重；右孩子結點 12 被剪枝， 9）佇列空，演算法結束，產生的最優解：maxv= 65，bestx:[1，0，1，0]， 8 . 答：求解程序如下： （ 1）根結點 1 進隊，對應結點值：e.i=0，e.f1=0，e.f2=0，e.lb=29， x：[0，0，0， 0 ]， （ 2）出隊結點 1：擴展結點如下： 進隊（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]， （ 3）出隊結點 2：擴展結點如下： 進隊（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]， （ 4）出隊結點 8：擴展結點如下： 進隊（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]， （ 5）出隊結點 10，擴展一個 j=2 的子結點，有 e.i=4，到達葉子結點，產生的一個解 是 e.f1=31，e.f2=36，e.lb=31，x=[1，4，3，2]， 該解對應的調度方案是：第 1 步執行作業 1，第 2 步執行作業 4，第 3 步執行作業 3 ，第 4 步執行作業 2，總時間=36， 解：采用優先佇列式分枝限界法求解，佇列中結點的型別如下： 9 . struct NodeType { int vno; //頂點的編號 int length; //當前結點的路徑長度 bool operator<(const NodeType &s) const //多載<關系函式 { return length>s.length; } //length越小越優先 } ; 從頂點 s 開始廣度優先搜索，找到目標點 t 后比較求最短路徑長度及其路徑條數，對 應的完整程式如下： # # include <stdio.h> include <queue> using namespace std; # # / define MAX 11 define INF 0x3f3f3f3f /問題表示 int A[MAX][MAX]={ //一個帶權有向圖 4 9 演算法設計 { { { { { 0，1，4，INF，INF}， INF，0，INF，1，5}， INF，INF，0，INF，1}， INF，INF，2，0，3}， INF，INF，INF，INF，INF} }; int n=5; / /求解結果表示 int bestlen=INF; int bestcount=0; struct NodeType //最優路徑的路徑長度 //最優路徑的條數 { int vno; //頂點的編號 int length; //當前結點的路徑長度 bool operator<(const NodeType &s) const //多載>關系函式 { return length>s.length; } //length越小越優先 } ; void solve(int s，int t) //求最短路徑問題 //定義2個結點 { NodeType e，e1; priority_queue<NodeType> qu; e.vno=s; //定義一個優先佇列qu //構造根結點 e.length=0; qu.push(e); //根結點進隊 while (!qu.empty()) //隊不慷訓圈 { e=qu.top(); qu.pop(); if (e.vno==t) //出隊結點e作為當前結點 //e是一個葉子結點 //比較找最優解 { if (e.length<bestlen) { bestcount=1; bestlen=e.length; //保存最短路徑長度 } else if (e.length==bestlen) bestcount++; } else { //e不是葉子結點 for (int j=0; j<n; j++) //檢查e的所有相鄰頂點 if (A[e.vno][j]!=INF && A[e.vno][j]!=0) //頂點e.vno到頂點j有邊 { if (e.length+A[e.vno][j]<bestlen) //剪枝 { e1.vno=j; e1.length=e.length+A[e.vno][j]; qu.push(e1); //有效子結點e1進隊 } } } } } void main() int s=0，t=4; solve(s，t); if (bestcount==0) { printf("頂點%d到%d沒有路徑\n"，s，t); else { printf("頂點%d到%d存在路徑\n"，s，t); 5 0 第 1 章 概論 printf(" 最短路徑長度=%d，條數=%d\n"， bestlen，bestcount); / /輸出：5 3 } } 上述程式的執行結果如圖 1.39 所示， 圖 1.39 程式執行結果 1 0. 解：采用優先佇列式分枝限界法求解，設計優先佇列 priority_queue<NodeType>，并設計優先佇列的關系比較函式 Cmp，指定按結點的 ub 值進 行比較，即 ub 值越大的結點越先出隊，對應的完整程式如下： # # include <stdio.h> include <queue> using namespace std; # / define MAXN 21 //最多的集裝箱數 /問題表示 int n=5; int W=10; int w[]={0,5,2,6,4,3}; //集裝箱重量,不計下標0的元素 / /求解結果表示 int bestw=0; //存放最大重量,全域變數 //存放最優解,全域變數 int bestx[MAXN]; int Count=1; //搜索空間中結點數累計,全域變數 typedef struct { int no; int i; //結點編號 //當前結點在解空間中的層次 //當前結點的總重量 //當前結點包含的解向量 //上界 int w; int x[MAXN]; int ub; } NodeType; struct Cmp //佇列中關系比較函式 { bool operator()(const NodeType &s,const NodeType &t) { return (s.ub<t.ub) || (s.ub==t.ub && s.x[0]>t.x[0]); / /ub越大越優先,當ub相同時x[0]越小越優先 } } ; void bound(NodeType &e) //計算分枝結點e的上界 //r為剩余集裝箱的重量 { int i=e.i+1; int r=0; while (i<=n) { r+=w[i]; i++; } e.ub=e.w+r; 5 1 演算法設計 } void Loading() //求裝載問題的最優解 { NodeType e,e1,e2; //定義3個結點 priority_queue<NodeType,vector<NodeType>,Cmp > qu; //定義一個優先佇列qu e.no=Count++; e.i=0; //設定結點編號 //根結點置初值,其層次計為0 e.w=0; for (int j=0; j<=n; j++) e.x[j]=0; //初始化根結點的解向量 bound(e); //求根結點的上界 //根結點進隊 qu.push(e); while (!qu.empty()) //隊不慷訓圈 { e=qu.top(); qu.pop(); if (e.i==n) //出隊結點e作為當前結點 //e是一個葉子結點 { if ((e.w>bestw) || (e.w==bestw && e.x[0]<bestx[0]))//比較找最優解 { bestw=e.w; //更新bestw for (int j=0;j<=e.i;j++) bestx[j]=e.x[j]; //復制解向量e.x->bestx } } else { //e不是葉子結點 if (e.w+w[e.i+1]<=W) //檢查左孩子結點 //設定結點編號 //建立左孩子結點 { e1.no=Count++; e1.i=e.i+1; e1.w=e.w+w[e1.i]; for (int j=0; j<=e.i; j++) e1.x[j]=e.x[j]; //復制解向量e.x->e1.x e1.x[e1.i]=1; //選擇集裝箱i e1.x[0]++; bound(e1); qu.push(e1); //裝入集裝箱數增1 //求左孩子結點的上界 //左孩子結點進隊 } e2.no=Count++; e2.i=e.i+1; e2.w=e.w; //設定結點編號 //建立右孩子結點 for (int j=0; j<=e.i; j++) //復制解向量e.x->e2.x e2.x[j]=e.x[j]; e2.x[e2.i]=0; bound(e2); //不選擇集裝箱i //求右孩子結點的上界 if (e2.ub>bestw) qu.push(e2); //若右孩子結點可行,則進隊,否則被剪枝 } } } void disparr(int x[],int len) //輸出一個解向量 //輸出最優解 { for (int i=1;i<=len;i++) printf("%2d",x[i]); } void dispLoading() { printf(" X=["); 5 2 第 1 章 概論 disparr(bestx,n); printf("],裝入總價值為%d\n",bestw); } void main() { Loading(); printf("求解結果:\n"); dispLoading(); //輸出最優解 } 上述程式的執行結果如圖 1.40 所示， 圖 1.40 程式執行結果 1 .7 第 7 章─貪心法 1 .7.1 練習題 . 下面是貪心演算法的基本要素的是（ ）， A.重疊子問題 B.構造最優解 C.貪心選擇性質 . 下面問題（ ）不能使用貪心法解決， A.單源最短路徑問題 B.n 皇后問題 采用貪心演算法的最優裝載問題的主要計算量在于將集裝箱依其重量從小到大排 序，故演算法的時間復雜度為（ ）， A.O(n) B.O(n2) . 關于 0/ 1 背包問題以下描述正確的是（ ）， 1 D.定義最優解 2 C.最小花費生成樹問題 D.背包問題 3 . C.O(n3) D.O(nlog2n) 4 A.可以使用貪心演算法找到最優解 B.能找到多項式時間的有效演算法 C.使用教材介紹的動態規劃方法可求解任意 0－1 背包問題 D.對于同一背包與相同的物品，做背包問題取得的總價值一定大于等于做 0/1 背包問 題 5 . 一棵哈夫曼樹共有 215 個結點，對其進行哈夫曼編碼，共能得到（ ）個不同的碼 字，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/114585.html
標籤：其他