算法设计与分析(李春保)练习题答案v2

----------------------------------------------------- Page 1 -----------------------------------------------------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 )= 2 n D. T ( n )=3 n log 2 n 3. 什 么 是 算 法 ？ 算 法 有 哪 些 特 征 ？ 4. 判 断 一 个 大 于 2 的 正 整 数 n 是 否 为 素 数 的 方 法 有 多 种 ， 给 出 两 种 算 法 ， 说 明 其 中 一 种 算 法 更 好 的 理 由 。 5. 证 明 以 下 关 系 成 立 ： （ 1 ） 10 n - 2 n =  ( n ) （ 2 ） 2 =  (2 ) 6. 证 明 O( f ( n ))+O( g ( n ))=O(max{ f ( n ) ， g ( n )}) 。 7. 有 一 个 含 n （ n >2 ） 个 整 数 的 数 组 a ， 判 断 其 中 是 否 存 在 出 现 次 数 超 过 所 有 元 素 一 半 的 元 素 。 8. 一 个 字 符 串 采 用 string 对 象 存 储 ， 设 计 一 个 算 法 判 断 该 字 符 串 是 否 为 回 文 。 9. 有 一 个 整 数 序 列 ， 设 计 一 个 算 法 判 断 其 中 是 否 存 在 两 个 元 素 和 恰 好 等 于 给 定 的 整 数 k 。 10. 有 两 个 整 数 序 列 ， 每 个 整 数 序 列 中 所 有 元 素 均 不 相 同 。 设 计 一 个 算 法 求 它 们 的 公 共 元 素 ， 要 求 不 使 用 STL 的 集 合 算 法 。 11. 正 整 数 n （ n >1 ） 可 以 写 成 质 数 的 乘 积 形 式 ， 称 为 整 数 的 质 因 数 分 解 。 例 如 ， 12=2*2*3 ， 18=2*3*3 ， 11=11 。 设 计 一 个 算 法 求 n 这 样 分 解 后 各 个 质 因 数 出 现 的 次 数 ， 采 用 vector 向 量 存 放 结 果 。 12. 有 一 个 整 数 序 列 ， 所 有 元 素 均 不 相 同 ， 设 计 一 个 算 法 求 相 差 最 小 的 元 素 对 的 个 数 。 如 序 列 4 、 1 、 2 、 3 的 相 差 最 小 的 元 素 对 的 个 数 是 3 ， 其 元 素 对 是 （ 1 ， 2 ） ， （ 2 ， 3 ） ， （ 3 ， 4 ） 。 13. 有 一 个 map<string ， int> 容 器 ， 其 中 已 经 存 放 了 较 多 元 素 。 设 计 一 个 算 法 求 出 其 中 重 复 的 value 并 且 返 回 重 复 value 的 个 数 。 14. 重 新 做 第 10 题 ， 采 用 map 容 器 存 放 最 终 结 果 。 15. 假 设 有 一 个 含 n （ n >1 ） 个 元 素 的 stack<int> 栈 容 器 st ， 设 计 一 个 算 法 出 栈 从 栈 顶 到 栈 底 的 第 k （ 1 ≤ k ≤ n ） 个 元 素 ， 其 他 栈 元 素 不 变 。 2 2 2 n +1 n ----------------------------------------------------- Page 2 -----------------------------------------------------算 法 设 计 1.1.2 练 习 题 参 考 答 案 1. 答 ： 由 于 算 法 具 有 有 穷 性 、 确 定 性 和 输 出 性 ， 因 而 Ⅱ 、 Ⅲ 、 Ⅳ 正 确 ， 而 解 决 某 一 类 问 题 的 算 法 不 一 定 是 唯 一 的 。 答 案 为 C 。 2. 答 ： 选 项 A 的 时 间 复 杂 度 为 O( n ) 。 选 项 B 的 时 间 复 杂 度 为 O( n ) 。 选 项 C 的 时 间 复 杂 度 为 O(log 2 n ) 。 选 项 D 的 时 间 复 杂 度 为 O( n log 2 n ) 。 答 案 为 C 。 3. 答 ： 算 法 是 求 解 问 题 的 一 系 列 计 算 步 骤 。 算 法 具 有 有 限 性 、 确 定 性 、 可 行 性 、 输 入 性 和 输 出 性 5 个 重 要 特 征 。 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 更 好 。 5. 答 ： （ 1 ） 当 n 足 够 大 时 ， (10 n - 2 n )/( n )=10 ， 所 以 10 n - 2 n =  ( n ) 。 （ 2 ） 2 =2*2 =  (2 ) 。 6. 证 明 ： 对 于 任 意 f 1 (n) ∈ O( f ( n )) ， 存 在 正 常 数 c 1 和 正 常 数 n 1 ， 使 得 对 所 有 n ≥ n 1 ， 有 f 1 ( n ) ≤ c 1 f ( n ) 。 类 似 地 ， 对 于 任 意 g 1 ( n ) ∈ O( g ( n )) ， 存 在 正 常 数 c 2 和 自 然 数 n 2 ， 使 得 对 所 有 n ≥ n 2 ， 有 g 1 ( n ) ≤ c 2 g ( n ) 。 令 c 3 =max{ c 1 ， c 2 } ， n 3 =max{ n 1 ， n 2 } ， h ( n )= max{ f ( n ) ， g ( n )} 。 则 对 所 有 的 n ≥ n 3 ， 有 ： f 1 ( n ) + g 1 ( n ) ≤ c 1 f ( n ) + c 2 g ( n ) ≤ c 3 f ( n )+ c 3 g ( n )= c 3 ( f ( n )+ g ( n )) ≤ c 3 2max{ f ( n ) ， g ( n )}=2 c 3 h ( n )=O(max{ f ( n ) ， g ( n )}) 。 7. 解 ： 先 将 a 中 元 素 递 增 排 序 ， 再 求 出 现 次 数 最 多 的 次 数 maxnum ， 最 后 判 断 是 否 满 足 条 件 。 对 应 的 程 序 如 下 ： #include <stdio.h> #include <algorithm> using namespace std; 2 2 2 2 2 2 n +1 n n ----------------------------------------------------- Page 3 -----------------------------------------------------第 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 ----------------------------------------------------- Page 4 -----------------------------------------------------算 法 设 计 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 ----------------------------------------------------- Page 5 -----------------------------------------------------第 1 章 概 论 else printf(" 不 存 在 两 个 元 素 和 为 % d\n",k1); } 上 述 程 序 的 执 行 结 果 如 图 1.3 所 示 。 图 1.3 程 序 执 行 结 果 10. 解 ： 采 用 集 合 set<int> 存 储 整 数 序 列 ， 集 合 中 元 素 默 认 是 递 增 排 序 的 ， 再 采 用 二 路 归 并 算 法 求 它 们 的 交 集 。 对 应 的 程 序 如 下 ： #include <stdio.h> #include <set> using namespace std; void solve(set<int> s1,set<int> s2,set<int> &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; } } // 求 交 集 s3 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 ----------------------------------------------------- Page 6 -----------------------------------------------------算 法 设 计 printf(" printf(" s2: "); dispset(s2); s3: "); dispset(s3); } 上 述 程 序 的 执 行 结 果 如 图 1.4 所 示 。 图 1.4 程 序 执 行 结 果 11. 解 ： 对 于 正 整 数 n ， 从 i =2 开 始 查 找 其 质 因 数 ， ic 记 录 质 因 数 i 出 现 的 次 数 ， 当 找 到 这 样 质 因 数 后 ， 将 （ i ， ic ） 作 为 一 个 元 素 插 入 到 vector 容 器 v 中 。 最 后 输 出 v 。 对 应 的 算 法 如 下 ： #include <stdio.h> #include <vector> using namespace std; struct NodeType { int p; int pc; //vector 向 量 元 素 类 型 // 质 因 数 // 质 因 数 出 现 次 数 }; 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 ----------------------------------------------------- Page 7 -----------------------------------------------------第 1 章 概 论 void main() { vector<NodeType> v; int n=100; printf("n=%d\n",n); solve(n,v); disp(v); } 上 述 程 序 的 执 行 结 果 如 图 1.5 所 示 。 图 1.5 程 序 执 行 结 果 12. 解 ： 先 递 增 排 序 ， 再 求 相 邻 元 素 差 ， 比 较 求 最 小 元 素 差 ， 累 计 最 小 元 素 差 的 个 数 。 对 应 的 程 序 如 下 ： #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 ----------------------------------------------------- Page 8 -----------------------------------------------------图 1.6 算 法 设 计 程 序 执 行 结 果 13. 解 ： 对 于 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 程 序 执 行 结 果 14. 解 ： 采 用 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 ----------------------------------------------------- Page 9 -----------------------------------------------------第 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 程 序 执 行 结 果 15. 解 ： 栈 容 器 不 能 顺 序 遍 历 ， 为 此 创 建 一 个 临 时 tmpst 栈 ， 将 st 的 k 个 元 素 出 栈 并 进 栈 到 tmpst 中 ， 再 出 栈 tmpst 一 次 得 到 第 k 个 元 素 ， 最 后 将 栈 tmpst 的 所 有 元 素 出 栈 并 进 栈 到 st 中 。 对 应 的 程 序 如 下 ： #include <stdio.h> #include <stack> using namespace std; int solve(stack<int> &st,int k) { stack<int> tmpst; int e; for (int i=0;i<k;i++) { e=st.top(); st.pop(); tmpst.push(e); } e=tmpst.top(); tmpst.pop(); while (!tmpst.empty()) { st.push(tmpst.top()); tmpst.pop(); // 出 栈 第 k 个 元 素 // 出 栈 st 的 k 个 元 素 并 进 tmpst 栈 // 求 第 k 个 元 素 // 将 tmpst 的 所 有 元 素 出 栈 并 进 栈 st 9 ----------------------------------------------------- Page 10 -----------------------------------------------------} return e; } void disp(stack<int> &st) { while (!st.empty()) { printf("%d ",st.top()); st.pop(); } printf("\n"); } void main() { stack<int> st; 算 法 设 计 // 出 栈 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); 10 ----------------------------------------------------- Page 11 -----------------------------------------------------第 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)+9 H ( n - 2) - 9 H ( n - 3) 当 n >2 5. 采 用 递 归 树 方 法 求 解 以 下 递 归 方 程 ： T (1)=1 T ( n )=4 T ( n /2)+ n 当 n >1 6. 采 用 主 方 法 求 解 以 下 题 的 递 归 方 程 。 T ( n )=1 当 n =1 T ( n )=4 T ( n /2)+ n 当 n >1 7. 分 析 求 斐 波 那 契 f(n) 的 时 间 复 杂 度 。 8. 数 列 的 首 项 a 1 =0 ， 后 续 奇 数 项 和 偶 数 项 的 计 算 公 式 分 别 为 a 2 n =a 2 n -1 +2 ， a 2 n +1 =a 2 n - 1 +a 2 n - 1 ， 写 出 计 算 数 列 第 n 项 的 递 归 算 法 。 9. 对 于 一 个 采 用 字 符 数 组 存 放 的 字 符 串 str ， 设 计 一 个 递 归 算 法 求 其 字 符 个 数 （ 长 度 ） 。 10. 对 于 一 个 采 用 字 符 数 组 存 放 的 字 符 串 str ， 设 计 一 个 递 归 算 法 判 断 str 是 否 为 回 文 。 11. 对 于 不 带 头 结 点 的 单 链 表 L ， 设 计 一 个 递 归 算 法 正 序 输 出 所 有 结 点 值 。 12. 对 于 不 带 头 结 点 的 单 链 表 L ， 设 计 一 个 递 归 算 法 逆 序 输 出 所 有 结 点 值 。 13. 对 于 不 带 头 结 点 的 非 空 单 链 表 L ， 设 计 一 个 递 归 算 法 返 回 最 大 值 结 点 的 地 址 （ 假 设 这 样 的 结 点 唯 一 ） 。 14. 对 于 不 带 头 结 点 的 单 链 表 L ， 设 计 一 个 递 归 算 法 返 回 第 一 个 值 为 x 的 结 点 的 地 址 ， 没 有 这 样 的 结 点 时 返 回 NULL 。 15. 对 于 不 带 头 结 点 的 单 链 表 L ， 设 计 一 个 递 归 算 法 删 除 第 一 个 值 为 x 的 结 点 。 16. 假 设 二 叉 树 采 用 二 叉 链 存 储 结 构 存 放 ， 结 点 值 为 int 类 型 ， 设 计 一 个 递 归 算 法 求 二 叉 树 bt 中 所 有 叶 子 结 点 值 之 和 。 17. 假 设 二 叉 树 采 用 二 叉 链 存 储 结 构 存 放 ， 结 点 值 为 int 类 型 ， 设 计 一 个 递 归 算 法 求 二 叉 树 bt 中 所 有 结 点 值 大 于 等 于 k 的 结 点 个 数 。 18. 假 设 二 叉 树 采 用 二 叉 链 存 储 结 构 存 放 ， 所 有 结 点 值 均 不 相 同 ， 设 计 一 个 递 归 算 法 求 值 为 x 的 结 点 的 层 次 （ 根 结 点 的 层 次 为 1 ） ， 没 有 找 到 这 样 的 结 点 时 返 回 0 。 11 2 ----------------------------------------------------- Page 12 -----------------------------------------------------算 法 设 计 1.2.2 练 习 题 参 考 答 案 1. 答 ： 一 个 f 函 数 定 义 中 直 接 调 用 f 函 数 自 己 ， 称 为 直 接 递 归 。 一 个 f 函 数 定 义 中 调 用 g 函 数 ， 而 g 函 数 的 定 义 中 调 用 f 函 数 ， 称 为 间 接 递 归 。 消 除 递 归 一 般 要 用 栈 实 现 。 2. 答 ： 递 归 函 数 f ( n ， m ) 中 ， n 是 非 引 用 参 数 ， m 是 引 用 参 数 ， 所 以 递 归 函 数 的 状 态 为 （ 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( n ) 。 4. 解 ： 整 数 一 个 常 系 数 的 线 性 齐 次 递 推 式 ， 用 x n -3 3 2 3 2 代 替 H ( n ) ， 有 ： x = x +9 x - 9 x ， x - x - 9 x+ 9= x ( x - 9) - ( x - 9)=( x - 1)( x - 9)=( x - 1)( x +3)( x - 3)=0 。 得 到 r 1 =1 ， r 2 = - 3 ， r 3 =3 则 递 归 方 程 的 通 解 为 ： H ( n )= c 1 + c 2 ( - 3) + c 3 3 代 入 H (0)=0 ， 有 c 1 + c 2 + c 3 =0 代 入 H (1)=1 ， 有 c 1 - 3 c 2 +3 c 3 =1 代 入 H (2)=2 ， 有 c 1 +9 c 2 +9 c 3 =2 求 出 ： c 1 = - 1/4 ， c 2 = - 1/12 ， c 3 =1/3 ， H ( n )= c 1 + c 2 ( - 3) + c 3 3 = ( n ‒ 1 4 + 1 3 1 ‒ 。 5. 解 ： 构 造 的 递 归 树 如 图 1.10 所 示 ， 第 1 层 的 问 题 规 模 为 n ， 第 2 的 层 的 子 问 题 的 问 题 规 模 为 n /2 ， 依 此 类 推 ， 当 展 开 到 第 k +1 层 ， 其 规 模 为 n /2 =1 ， 所 以 递 归 树 的 高 度 为 log 2 n +1 。 第 1 层 有 1 个 结 点 ， 其 时 间 为 n ， 第 2 层 有 4 个 结 点 ， 其 时 间 为 4 ( n /2)=2 n ， 依 次 类 推 ， 第 k 层 有 4 个 结 点 ， 每 个 子 问 题 规 模 为 n /2 ， 其 时 间 为 4 ( n /2 )=2 n 。 叶 子 结 点 的 个 数 为 n 个 ， 其 时 间 为 n 。 将 递 归 树 每 一 层 的 时 间 加 起 来 ， 可 得 ： log n T ( n )= n +2 n + … + 2 n + … + n ≈ ? ∗ 2 =O( n ) 。 12 2 n n n -1 n -2 n -3 两 边 同 时 除 以 x ， 得 到 ： x = x +9 x - 9 ， 即 x - x - 9 x+ 9=0 。 3 2 2 2 2 n n ( n n ) ‒ 1 ) n ‒ 1 4 k k -1 k -1 k -1 k -1 k -1 2 k -1 2 ----------------------------------------------------- Page 13 -----------------------------------------------------第 1 章 概 论 n n ( n /2) ( n /2) ( n /2) ( n /2) 2 n 高 度 h 为 log 2 n +1 ( n /2 ) … 1 ( n /2 ) … 1 ( n /2 ) … 1 ( n /2 ) … 1 2 n n 图 1.10 一 棵 递 归 树 6. 解 ： 采 用 主 方 法 求 解 ， 这 里 a =4 ， b =2 ， f ( n )= n 。 log a log 4 因 此 ， ? = ? = n ， 它 与 f ( n ) 一 样 大 ， 满 足 主 定 理 中 的 情 况 （ 2 ） ， 所 以 T ( n )= O( log a ? log 2 n) =O( n log 2 n ) 。 7. 解 ： 设 求 斐 波 那 契 f ( n ) 的 时 间 为 T( n ) ， 有 以 下 递 推 式 ： T(1)=T(2) T(n)=T( n - 1)+T( n - 2)+1 当 n >2 其 中 ， T( n ) 式 中 加 1 表 示 一 次 加 法 运 算 的 时 间 。 不 妨 先 求 T 1 (1)=T 1 (2)=1 ， T 1 ( n )=T 1 ( n - 1)+T 1 ( n - 2) ， 按 《 教 程 》 例 2.14 的 方 法 可 以 求 出 ： T 1 ( n )= 1 5  1  5       1 5  1  5      1  1  5  ≈ =   所 以 T( n )=T 1 ( n )+1 ≈ 1 5  1  5      +1=O( φ ) ， 其 中 φ = 。 2 8. 解 ： 设 f ( m ) 计 算 数 列 第 m 项 值 。 当 m 为 偶 数 时 ， 不 妨 设 m =2 n ， 则 2 n - 1= m - 1 ， 所 以 有 f ( m )= f ( m - 1)+2 。 当 m 为 奇 数 时 ， 不 妨 设 m =2 n +1 ， 则 2 n - 1= m - 2 ， 2 n = 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 f (str)= f (str+1)+1 当 * str='\0' 时 其 他 情 况 对 应 的 递 归 程 序 如 下 ： 13 2 2 2 2 2 2 b 2 2 b 2 n   2 n   2 n     5 2 n   2 n 1  5 ----------------------------------------------------- Page 14 -----------------------------------------------------#include <iostream> using namespace std; int Length(char *str) { if (*str=='\0') return 0; else return Length(str+1)+1; } void main() { char str[]="abcd"; 算 法 设 计 // 求 s tr 的 字 符 个 数 cout << str << " 的 长 度 : " << Length(str) << endl; } 上 述 程 序 的 执 行 结 果 如 图 1.11 所 示 。 图 1.11 程 序 执 行 结 果 10. 解 ： 设 f (str ， n ) 返 回 含 n 个 字 符 的 字 符 串 str 是 否 为 回 文 ， 其 递 归 模 型 如 下 ： f (str ， n )=true f (str ， n )=flase f (str ， n )= f (str+1 ， n - 2) 当 n =0 或 者 n =1 时 当 str[0] ≠ str[ n - 1] 时 其 他 情 况 对 应 的 递 归 算 法 如 下 ： #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"); } 14 ----------------------------------------------------- Page 15 -----------------------------------------------------第 1 章 概 论 上 述 程 序 的 执 行 结 果 如 图 1.12 所 示 。 图 1.12 程 序 执 行 结 果 11. 解 ： 设 f (L) 正 序 输 出 单 链 表 L 的 所 有 结 点 值 ， 其 递 归 模 型 如 下 ： f (L) ≡ 不 做 任 何 事 情 f (L) ≡ 输 出 L - >data; f (L - >next); 对 应 的 递 归 程 序 如 下 ： #include "LinkList.cpp" 当 L=NULL 当 L ≠ NULL 时 // 包 含 单 链 表 的 基 本 运 算 算 法 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 程 序 执 行 结 果 12. 解 ： 设 f (L) 逆 序 输 出 单 链 表 L 的 所 有 结 点 值 ， 其 递 归 模 型 如 下 ： f (L) ≡ 不 做 任 何 事 情 f (L) ≡ f (L - >next); 输 出 L - >data 对 应 的 递 归 程 序 如 下 ： #include "LinkList.cpp" void Revdisp(LinkNode *L) { if (L==NULL) return; 当 L=NULL 当 L ≠ NULL 时 // 包 含 单 链 表 的 基 本 运 算 算 法 // 逆 序 输 出 所 有 结 点 值 15 ----------------------------------------------------- Page 16 -----------------------------------------------------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 算 法 设 计 程 序 执 行 结 果 13. 解 ： 设 f (L) 返 回 单 链 表 L 中 值 最 大 结 点 的 地 址 ， 其 递 归 模 型 如 下 ： f (L) = L f (L) = MAX{ f (L - >next) ， L->data} 对 应 的 递 归 程 序 如 下 ： #include "LinkList.cpp" 当 L 只 有 一 个 结 点 时 其 他 情 况 // 包 含 单 链 表 的 基 本 运 算 算 法 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); 16 ----------------------------------------------------- Page 17 -----------------------------------------------------第 1 章 概 论 } 上 述 程 序 的 执 行 结 果 如 图 1.15 所 示 。 图 1.15 程 序 执 行 结 果 14. 解 ： 设 f (L ， x ) 返 回 单 链 表 L 中 第 一 个 值 为 x 的 结 点 的 地 址 ， 其 递 归 模 型 如 下 ： f (L ， x ) = NULL f (L ， x ) = L f (L ， x ) = f (L - >next ， x ) 对 应 的 递 归 程 序 如 下 ： 当 L=NULL 时 当 L ≠ NULL 且 L - >data= x 时 其 他 情 况 #include "LinkList.cpp" LinkNode *Firstxnode(LinkNode *L,int x) { if (L==NULL) return NULL; if (L->data==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 所 示 。 // 包 含 单 链 表 的 基 本 运 算 算 法 // 返 回 第 一 个 值 为 x 的 结 点 的 地 址 图 1.16 程 序 执 行 结 果 15. 解 ： 设 f (L ， x ) 删 除 单 链 表 L 中 第 一 个 值 为 x 的 结 点 ， 其 递 归 模 型 如 下 ： f (L ， x ) ≡ 不 做 任 何 事 情 f (L ， x ) ≡ 删 除 L 结 点 ， L=L - >next f (L ， x ) ≡ f (L - >next ， x ) 对 应 的 递 归 程 序 如 下 ： 当 L=NULL 当 L ≠ NULL 且 L - >data= x 其 他 情 况 17 ----------------------------------------------------- Page 18 -----------------------------------------------------#include "LinkList.cpp" 算 法 设 计 // 包 含 单 链 表 的 基 本 运 算 算 法 void Delfirstx(LinkNode *&L,int x) // 删 除 单 链 表 L 中 第 一 个 值 为 x 的 结 点 { if (L==NULL) return; if (L->data==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 程 序 执 行 结 果 16. 解 ： 设 f (bt) 返 回 二 叉 树 bt 中 所 有 叶 子 结 点 值 之 和 ， 其 递 归 模 型 如 下 ： f (bt)=0 f (bt)=bt - >data f (bt)= f (bt - >lchild)+ f (bt - >rchild) 对 应 的 递 归 程 序 如 下 ： #include "Btree.cpp" int LeafSum(BTNode *bt) { if (bt==NULL) return 0; 当 bt=NULL 当 bt ≠ NULL 且 bt 结 点 为 叶 子 结 点 其 他 情 况 // 包 含 二 叉 树 的 基 本 运 算 算 法 // 二 叉 树 bt 中 所 有 叶 子 结 点 值 之 和 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() 18 ----------------------------------------------------- Page 19 -----------------------------------------------------第 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 构 造 二 叉 链 b t printf(" 二 叉 树 b t:"); DispBTree(bt); printf("\n"); printf(" 所 有 叶 子 结 点 值 之 和 : %d\n",LeafSum(bt)); DestroyBTree(bt); // 销 毁 树 b t } 上 述 程 序 的 执 行 结 果 如 图 1.18 所 示 。 图 1.18 程 序 执 行 结 果 17. 解 ： 设 f (bt ， k ) 返 回 二 叉 树 bt 中 所 有 结 点 值 大 于 等 于 k 的 结 点 个 数 ， 其 递 归 模 型 如 下 ： f (bt ， k )=0 f (bt ， k )= f (bt - >lchild ， k )+ f (bt - >rchild ， k )+1 f (bt ， k )= f (bt - >lchild ， k )+ f (bt - >rchild ， k ) 对 应 的 递 归 程 序 如 下 ： #include "Btree.cpp" 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); 当 bt=NULL 当 bt ≠ NULL 且 bt - >data ≥ k 其 他 情 况 // 包 含 二 叉 树 的 基 本 运 算 算 法 // 大 于 等 于 k 的 结 点 个 数 // 由 a 和 b 构 造 二 叉 链 b t printf(" 二 叉 树 b t:"); DispBTree(bt); printf("\n"); int k=3; printf(" 大 于 等 于 % d 的 结 点 个 数 : %d\n",k,Nodenum(bt,k)); DestroyBTree(bt); // 销 毁 树 b t } 上 述 程 序 的 执 行 结 果 如 图 1.19 所 示 。 19 ----------------------------------------------------- Page 20 -----------------------------------------------------算 法 设 计 图 1.19 程 序 执 行 结 果 18. 解 ： 设 f (bt ， x ， h ) 返 回 二 叉 树 bt 中 x 结 点 的 层 次 ， 其 中 h 表 示 bt 所 指 结 点 的 层 次 ， 初 始 调 用 时 ， bt 指 向 根 结 点 ， h 置 为 1 。 其 递 归 模 型 如 下 ： f (bt ， x ， h )=0 f (bt ， x ， h )= h f (bt ， x ， h ) = l f (bt ， x ， h ) = f (bt - >rchild ， x ， h +1) 对 应 的 递 归 程 序 如 下 ： 当 bt=NULL 当 bt ≠ NULL 且 bt - >data=x 当 l = f (bt - >lchild ， x ， h +1) ≠ 0 其 他 情 况 #include "Btree.cpp" int Level(BTNode *bt,int x,int h) { // 初 始 调 用 时 ： bt 为 根 ， h 为 1 if (bt==NULL) return 0; if (bt->data==x) return h; // 包 含 二 叉 树 的 基 本 运 算 算 法 // 求 二 叉 树 bt 中 x 结 点 的 层 次 // 找 到 x 结 点 ， 返 回 h else { int l=Level(bt->lchild,x,h+1); // 在 左 子 树 中 查 找 if (l!=0) return l; else // 在 左 子 树 中 找 到 ， 返 回 其 层 次 l 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); } 上 述 程 序 的 执 行 结 果 如 图 1.20 所 示 。 // 销 毁 树 bt 图 1.20 程 序 执 行 结 果 20 ----------------------------------------------------- Page 21 -----------------------------------------------------第 1 章 概 论 1.3 第 3 章 ─ 分 治 法 1.3.1 练 习 题 1. 分 治 法 的 设 计 思 想 是 将 一 个 难 以 直 接 解 决 的 大 问 题 分 割 成 规 模 较 小 的 子 问 题 ， 分 别 解 决 子 问 题 ， 最 后 将 子 问 题 的 解 组 合 起 来 形 成 原 问 题 的 解 。 这 要 求 原 问 题 和 子 问 题 （ ） 。 A. 问 题 规 模 相 同 ， 问 题 性 质 相 同 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; 21 ----------------------------------------------------- Page 22 -----------------------------------------------------算 法 设 计 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( n ) 。 6. 以 下 哪 些 算 法 采 用 分 治 策 略 ： （ 1 ） 堆 排 序 算 法 （ 2 ） 二 路 归 并 排 序 算 法 （ 3 ） 折 半 查 找 算 法 （ 4 ） 顺 序 查 找 算 法 7. 适 合 并 行 计 算 的 问 题 通 常 表 现 出 哪 些 特 征 ？ 8. 设 有 两 个 复 数 x = a + bi 和 y = c + di 。 复 数 乘 积 xy 可 以 使 用 4 次 乘 法 来 完 成 ， 即 xy =( ac - bd )+( ad + bc ) i 。 设 计 一 个 仅 用 3 次 乘 法 来 计 算 乘 积 xy 的 方 法 。 9. 有 4 个 数 组 a 、 b 、 c 和 d ， 都 已 经 排 好 序 ， 说 明 找 出 这 4 个 数 组 的 交 集 的 方 法 。 10. 设 计 一 个 算 法 ， 采 用 分 治 法 求 一 个 整 数 序 列 中 的 最 大 最 小 元 素 。 11. 设 计 一 个 算 法 ， 采 用 分 治 法 求 x 。 12. 假 设 二 叉 树 采 用 二 叉 链 存 储 结 构 进 行 存 储 。 设 计 一 个 算 法 采 用 分 治 法 求 一 棵 二 叉 树 bt 的 高 度 。 13. 假 设 二 叉 树 采 用 二 叉 链 存 储 结 构 进 行 存 储 。 设 计 一 个 算 法 采 用 分 治 法 求 一 棵 二 叉 树 bt 中 度 为 2 的 结 点 个 数 。 14. 有 一 种 二 叉 排 序 树 ， 其 定 义 是 空 树 是 一 棵 二 叉 排 序 树 ， 若 不 空 ， 左 子 树 中 所 有 结 点 值 小 于 根 结 点 值 ， 右 子 树 中 所 有 结 点 值 大 于 根 结 点 值 ， 并 且 左 右 子 树 都 是 二 叉 排 序 树 。 现 在 该 二 叉 排 序 树 采 用 二 叉 链 存 储 ， 采 用 分 治 法 设 计 查 找 值 为 x 的 结 点 地 址 ， 并 分 析 算 法 的 最 好 的 平 均 时 间 复 杂 度 。 22 2 n ----------------------------------------------------- Page 23 -----------------------------------------------------第 1 章 概 论 15. 设 有 n 个 互 不 相 同 的 整 数 ， 按 递 增 顺 序 存 放 在 数 组 a [0.. n - 1] 中 ， 若 存 在 一 个 下 标 i （ 0 ≤ i < n ） ， 使 得 a [ i ]= i 。 设 计 一 个 算 法 以 O(log 2 n ) 时 间 找 到 这 个 下 标 i 。 16. 请 你 模 仿 二 分 查 找 过 程 设 计 一 个 三 分 查 找 算 法 。 分 析 其 时 间 复 杂 度 。 17. 对 于 大 于 1 的 正 整 数 n ， 可 以 分 解 为 n = x 1 * x 2 * … * x m ， 其 中 x i ≥ 2 。 例 如 ， n =12 时 有 8 种 不 同 的 分 解 式 ： 12=12 ， 12=6*2 ， 12=4*3 ， 12=3*4 ， 12=3*2*2 ， 12=2*6 ， 12=2*3*2 ， 12=2*2*3 ， 设 计 一 个 算 法 求 n 的 不 同 分 解 式 个 数 。 18. 设 计 一 个 基 于 BSP 模 型 的 并 行 算 法 ， 假 设 有 p 台 处 理 器 ， 计 算 整 数 数 组 a [0.. n - 1] 的 所 有 元 素 之 和 。 并 分 析 算 法 的 时 间 复 杂 度 。 1.3.2 练 习 题 参 考 答 案 1. 答 ： C 。 2. 答 ： D 。 3. 答 ： 以 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( n ) 。 6. 答 ： 其 中 二 路 归 并 排 序 和 折 半 查 找 算 法 采 用 分 治 策 略 。 7. 答 ： 适 合 并 行 计 算 的 问 题 通 常 表 现 出 以 下 特 征 ： （ 1 ） 将 工 作 分 离 成 离 散 部 分 ， 有 助 于 同 时 解 决 。 例 如 ， 对 于 分 治 法 设 计 的 串 行 算 法 ， 可 以 将 各 个 独 立 的 子 问 题 并 行 求 解 ， 最 后 合 并 成 整 个 问 题 的 解 ， 从 而 转 化 为 并 行 算 法 。 （ 2 ） 随 时 并 及 时 地 执 行 多 个 程 序 指 令 。 （ 3 ） 多 计 算 资 源 下 解 决 问 题 的 耗 时 要 少 于 单 个 计 算 资 源 下 的 耗 时 。 8. 答 ： xy =( ac - bd )+(( a + b )( c + d ) - ac - bd ) i 。 由 此 可 见 ， 这 样 计 算 xy 只 需 要 3 次 乘 法 （ 即 ac 、 bd 和 ( a + b )( c + d ) 乘 法 运 算 ） 。 9. 答 ： 采 用 基 本 的 二 路 归 并 思 路 ， 先 求 出 a 、 b 的 交 集 ab ， 再 求 出 c 、 d 的 交 集 cd ， 最 后 求 出 ab 和 cd 的 交 集 ， 即 为 最 后 的 结 果 。 也 可 以 直 接 采 用 4 路 归 并 方 法 求 解 。 10. 解 ： 采 用 类 似 求 求 一 个 整 数 序 列 中 的 最 大 次 大 元 素 的 分 治 法 思 路 。 对 应 的 程 序 如 下 ： #include <stdio.h> #define max(x,y) ((x)>(y)?(x):(y)) #define min(x,y) ((x)<(y)?(x):(y)) 23 2 ----------------------------------------------------- Page 24 -----------------------------------------------------算 法 设 计 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 程 序 执 行 结 果 11. 解 ： 设 f ( x ， n )= x ， 采 用 分 治 法 求 解 对 应 的 递 归 模 型 如 下 ： f ( x ， n )= x 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 对 应 的 递 归 程 序 如 下 ： #include <stdio.h> double solve(double x,int n) { double fv; if (n==1) return x; if (n%2==0) { fv=solve(x,n/2); return fv*fv; } 当 n =1 当 n 为 偶 数 时 当 n 为 奇 数 时 // 求 x ^n 24 n ----------------------------------------------------- Page 25 -----------------------------------------------------第 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 程 序 执 行 结 果 12. 解 ： 设 f (bt) 返 回 二 叉 树 bt 的 高 度 ， 对 应 的 递 归 模 型 如 下 ： f (bt)=0 f (bt)=MAX{ f (bt - >lchild) ， f (bt - >rchild)}+1 对 应 的 程 序 如 下 ： #include "Btree.cpp" 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; } 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); 当 bt=NULL 其 他 情 况 // 包 含 二 叉 树 的 基 本 运 算 算 法 // 求 二 叉 树 b t 的 高 度 // 子 问 题 1 // 子 问 题 2 // 合 并 // 由 a 和 b 构 造 二 叉 链 b t printf(" 二 叉 树 b t:"); DispBTree(bt); printf("\n"); printf("bt 的 高 度 : %d\n",Height(bt)); DestroyBTree(bt); // 销 毁 树 b t } 25 ----------------------------------------------------- Page 26 -----------------------------------------------------算 法 设 计 上 述 程 序 的 执 行 结 果 如 图 1.23 所 示 。 图 1.23 程 序 执 行 结 果 13. 解 ： 设 f (bt) 返 回 二 叉 树 bt 中 度 为 2 的 结 点 个 数 ， 对 应 的 递 归 模 型 如 下 ： f (bt)=0 f (bt)= f (bt - >lchild)+ f (bt - >rchild)+1 f (bt)= f (bt - >lchild)+ f (bt - >rchild) 对 应 的 算 法 如 下 ： #include "Btree.cpp" int Nodes(BTNode *bt) { int n=0; 当 bt=NULL 若 bt ≠ NULL 且 bt 为 双 分 支 结 点 其 他 情 况 // 包 含 二 叉 树 的 基 本 运 算 算 法 // 求 bt 中 度 为 2 的 结 点 个 数 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 构 造 二 叉 链 b t printf(" 二 叉 树 b t:"); DispBTree(bt); printf("\n"); printf("bt 中 度 为 2 的 结 点 个 数 : %d\n",Nodes(bt)); DestroyBTree(bt); // 销 毁 树 b t } 上 述 程 序 的 执 行 结 果 如 图 1.24 所 示 。 图 1.24 程 序 执 行 结 果 14. 解 ： 设 f (bt ， x ) 返 回 在 二 叉 排 序 树 bt 得 到 的 值 为 x 结 点 的 地 址 ， 若 没 有 找 到 返 回 空 ， 对 应 的 递 归 模 型 如 下 ： f (bt ， x )=NULL f (bt ， x )=bt f (bt ， x )= f (bt - >lchild ， x ) 当 bt=NULL 当 bt ≠ NULL 且 x =bt - >data 当 x >bt - >data 26 ----------------------------------------------------- Page 27 -----------------------------------------------------第 1 章 概 论 f (bt ， x )= f (bt - >rchild ， x ) 对 应 的 程 序 如 下 ： #include "Btree.cpp" 当 x <bt - >data // 包 含 二 叉 树 的 基 本 运 算 算 法 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 T ( n )= T ( n /2)+1 当 n =1 当 n >1 可 以 推 出 T ( n )=O(log 2 n ) ， 其 中 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 27 ----------------------------------------------------- Page 28 -----------------------------------------------------算 法 设 计 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 程 序 执 行 结 果 16. 解 ： 对 于 有 序 序 列 a [low..high] ， 若 元 素 个 数 少 于 3 个 ， 直 接 查 找 。 若 含 有 更 多 的 元 素 ， 将 其 分 为 a [low..mid1 - 1] 、 a [mid1+1..mid2 - 1] 、 a [mid2+1..high] 子 序 列 ， 对 每 个 子 序 列 递 归 查 找 ， 算 法 的 时 间 复 杂 度 为 O(log 3 n ) ， 属 于 O(log 2 n ) 级 别 。 对 应 的 算 法 如 下 ： #include <stdio.h> int Search(int a[],int low,int high,int x) { if (high<low) return -1; else if (high==low) { if (x==a[low]) return low; else return -1; } if (high-low<2) { if (x==a[low]) return low; else if (x==a[low+1]) return low+1; else // 三 分 查 找 // 序 列 中 没 有 元 素 // 序 列 中 只 有 1 个 元 素 // 序 列 中 只 有 2 个 元 素 28 ----------------------------------------------------- Page 29 -----------------------------------------------------第 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 程 序 执 行 结 果 17. 解 ： 设 f ( n ) 表 示 n 的 不 同 分 解 式 个 数 。 有 ： f (1)=1 ， 作 为 递 归 出 口 f (2)=1 ， 分 解 式 为 ： 2=2 f (3)=1 ， 分 解 式 为 ： 3=3 f (4)=2 ， 分 解 式 为 ： 4=4 ， 4=2*2 29 ----------------------------------------------------- Page 30 -----------------------------------------------------算 法 设 计 f (6)=3 ， 分 解 式 为 ： 6=6 ， 6=2*3 ， 6=3*2 ， 即 f (6)= f (1)+ f (2)+ f (3) 以 此 类 推 ， 可 以 看 出 f ( n ) 为 n 的 所 有 因 数 的 不 同 分 解 式 个 数 之 和 ， 即 f ( n )= ∑ ? ( ?/ ? ) 。 对 应 的 程 序 如 下 ： #include <stdio.h> #define MAX 101 int solve(int n) { if (n==1) return 1; else { int sum=0; // 求 n 的 不 同 分 解 式 个 数 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 程 序 执 行 结 果 18. 解 ： 对 应 的 并 行 算 法 如 下 ： 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++) { sj=Sum(a,k,k+n/p-1,p,j); k+=n/p; } sum+=sj; return sum; //for 循 环 的 各 个 子 问 题 并 行 执 行 } 每 个 处 理 器 的 执 行 时 间 为 O ( n / p ) ， 同 步 开 销 为 O ( p ) ， 所 以 该 算 法 的 时 间 复 杂 度 为 O( n / p + p ) 。 30 ?% ? = 0 ----------------------------------------------------- Page 31 -----------------------------------------------------第 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 =( a 0 ， a 1 ， … a n -1 ) ， 若 i < j 且 a i > a j ， 则 < a i ， a j > 就 为 一 个 逆 序 对 。 例 如 数 组 （ 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. 有 一 个 三 位 数 ， 个 位 数 字 比 百 位 数 字 大 ， 而 百 位 数 字 又 比 十 位 数 字 大 ， 并 且 各 位 数 字 之 和 等 于 各 位 数 字 相 乘 之 积 ， 设 计 一 个 算 法 用 穷 举 法 求 此 三 位 数 。 8. 某 年 级 的 同 学 集 体 去 公 园 划 船 ， 如 果 每 只 船 坐 10 人 ， 那 么 多 出 2 个 座 位 ； 如 果 每 只 船 多 坐 2 人 ， 那 么 可 少 租 1 只 船 ， 设 计 一 个 算 法 用 蛮 力 法 求 该 年 级 的 最 多 人 数 ？ 9. 已 知 ： 若 一 个 合 数 的 质 因 数 分 解 式 逐 位 相 加 之 和 等 于 其 本 身 逐 位 相 加 之 和 ， 则 称 这 个 数 为 Smith 数 。 如 4937775=3*5*5*65837 ， 而 3+5+5+6+5+8+3+7=42 ， 4+9+3+7+7+7+5=42 ， 所 以 4937775 是 Smith 数 。 求 给 定 一 个 正 整 数 N ， 求 大 于 N 的 最 小 Smith 数 。 输 入 ： 若 干 个 case ， 每 个 case 一 行 代 表 正 整 数 N ， 输 入 0 表 示 结 束 输 出 ： 大 于 N 的 最 小 Smith 数 输 入 样 例 ： 4937774 0 样 例 输 出 ： 31 ----------------------------------------------------- Page 32 -----------------------------------------------------算 法 设 计 4937775 10. 求 解 涂 棋 盘 问 题 。 小 易 有 一 块 n * n 的 棋 盘 ， 棋 盘 的 每 一 个 格 子 都 为 黑 色 或 者 白 色 ， 小 易 现 在 要 用 他 喜 欢 的 红 色 去 涂 画 棋 盘 。 小 易 会 找 出 棋 盘 中 某 一 列 中 拥 有 相 同 颜 色 的 最 大 的 区 域 去 涂 画 ， 帮 助 小 易 算 算 他 会 涂 画 多 少 个 棋 格 。 输 入 描 述 ： 输 入 数 据 包 括 n +1 行 ： 第 一 行 为 一 个 整 数 n （ 1 ≤ n ≤ 50 ） ， 即 棋 盘 的 大 小 ， 接 下 来 的 n 行 每 行 一 个 字 符 串 表 示 第 i 行 棋 盘 的 颜 色 ， 'W' 表 示 白 色 ， 'B' 表 示 黑 色 。 输 出 描 述 ： 输 出 小 易 会 涂 画 的 区 域 大 小 。 输 入 例 子 ： 3 BWW BBB BWB 输 出 例 子 ： 3 11. 给 定 一 个 含 n （ n >1 ） 个 整 数 元 素 的 a ， 所 有 元 素 不 相 同 ， 采 用 蛮 力 法 求 出 a 中 所 有 元 素 的 全 排 列 。 1.4.2 练 习 题 参 考 答 案 1. 答 ： 蛮 力 法 是 一 种 简 单 直 接 地 解 决 问 题 的 方 法 ， 适 用 范 围 广 ， 是 能 解 决 几 乎 所 有 问 题 的 一 般 性 方 法 ， 常 用 于 一 些 非 常 基 本 、 但 又 十 分 重 要 的 算 法 （ 排 序 、 查 找 、 矩 阵 乘 法 和 字 符 串 匹 配 等 ） ， 蛮 力 法 主 要 解 决 一 些 规 模 小 或 价 值 低 的 问 题 ， 可 以 作 为 同 样 问 题 的 更 高 效 算 法 的 一 个 标 准 。 而 分 治 法 采 用 分 而 治 之 思 路 ， 把 一 个 复 杂 的 问 题 分 成 两 个 或 更 多 的 相 同 或 相 似 的 子 问 题 ， 再 把 子 问 题 分 成 更 小 的 子 问 题 直 到 问 题 解 决 。 分 治 法 在 求 解 问 题 时 ， 通 常 性 能 比 蛮 力 法 好 。 2. 答 ： 如 果 用 蛮 力 法 求 解 的 问 题 可 以 分 解 为 若 干 个 规 模 较 小 的 相 似 子 问 题 ， 此 时 可 以 采 用 递 归 来 实 现 算 法 。 3. 解 ： 上 述 算 法 的 时 间 复 杂 度 为 O( n ) ， 采 用 的 是 最 基 本 的 蛮 力 法 。 可 以 先 对 a 中 元 素 递 增 排 序 ， 然 后 依 次 比 较 相 邻 元 素 的 差 ， 求 出 最 小 差 ， 改 进 后 的 算 法 如 下 ： #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; } // 递 增 排 序 32 2 ----------------------------------------------------- Page 33 -----------------------------------------------------第 1 章 概 论 上 述 算 法 的 主 要 时 间 花 费 在 排 序 上 ， 算 法 的 时 间 复 杂 度 为 O( n log 2 n ) 。 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) { long fn=1; for (int i=2;i<=n;i++) fn=fn*i; return fn; } long solve(int n) { long ans=0; for (int i=1;i<=n;i++) ans+=f(i); return ans; // 求 n ! // 求 1 !+2!+ …+n! } 实 际 上 ， f ( n )= f ( n - 1)* n ， f (1)=1 ， 在 求 f ( n ) 时 可 以 利 用 f ( n - 1) 的 结 果 。 改 进 后 的 算 法 如 下 ： long solve1(int n) { long ans=0; long fn=1; for (int i=1;i<=n;i++) { fn=fn*i; ans+=fn; } return ans; // 求 1 !+2!+ …+n! } 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++) 33 ----------------------------------------------------- Page 34 -----------------------------------------------------算 法 设 计 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() 34 ----------------------------------------------------- Page 35 -----------------------------------------------------第 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) { int sum=0; while (n>0) // 求 n 的 各 位 数 字 和 35 ----------------------------------------------------- Page 36 -----------------------------------------------------算 法 设 计 { sum+=n; n=n/10; } return sum; } bool solve(int n) // 判 断 n 是 否 为 S mitch 数 { 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); } } 10. 解 ： 采 用 蛮 力 法 ， 统 计 每 一 列 相 邻 相 同 颜 色 的 棋 格 个 数 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++; else countj=1; } 36 ----------------------------------------------------- Page 37 -----------------------------------------------------第 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; } 11. 解 ： 与 《 教 程 》 中 求 全 排 列 类 似 ， 但 需 要 将 求 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 得 到 p s1 { vector<int> s1; vector<int>::iterator it; for (int j=0;j<=i;j++) { s1=s; it=s1.begin()+j; s1.insert(it,a[i]); ps1.push_back(s1); } } void Perm(int a[],int n) { vector<vector<int> > ps1; vector<vector<int> >::iterator it; vector<int> s,s1; s.push_back(a[0]); ps.push_back(s); for (int i=1;i<n;i++) { ps1.clear(); for (it=ps.begin();it!=ps.end();++it) Insert(*it,a,i,ps1); ps=ps1; } } void dispps() // 在 s ( 含 i 个 整 数 ) 的 每 个 位 置 插 入 a [i] // 求 出 插 入 位 置 // 插 入 整 数 a [i] // 添 加 到 p s1 中 // 求 a [0..n-1] 的 所 有 全 排 列 // 临 时 存 放 子 排 列 // 全 排 列 迭 代 器 // 添 加 { a[0]} 集 合 元 素 // 循 环 添 加 a [1] ～ a[n-1] //ps1 存 放 插 入 a [i] 的 结 果 // 在 每 个 集 合 元 素 中 间 插 入 a [i] 得 到 p s1 // 输 出 全 排 列 ps { vector<vector<int> >::reverse_iterator it; // 全 排 列 的 反 向 迭 代 器 vector<int>::iterator sit; // 排 列 集 合 元 素 迭 代 器 for (it=ps.rbegin();it!=ps.rend();++it) { for (sit=(*it).begin();sit!=(*it).end();++sit) printf("%d",*sit); printf(" "); 37 ----------------------------------------------------- Page 38 -----------------------------------------------------} printf("\n"); } void main() { int a[]={2,5,8}; int n=sizeof(a)/sizeof(a[0]); printf("a[0 ～ %d] 的 全 排 序 如 下 : \n Perm(a,n); dispps(); 算 法 设 计 ",n-1); } 上 述 程 序 的 执 行 结 果 如 图 1.32 所 示 。 图 1.32 程 序 执 行 结 果 1.5 第 5 章 ─ 回 溯 法 1.5.1 练 习 题 1. 回 溯 法 在 问 题 的 解 空 间 树 中 ， 按 （ ） 策 略 ， 从 根 结 点 出 发 搜 索 解 空 间 树 。 A. 广 度 优 先 B. 活 结 点 优 先 C. 扩 展 结 点 优 先 D. 深 度 优 先 2. 关 于 回 溯 法 以 下 叙 述 中 不 正 确 的 是 （ ） 。 A. 回 溯 法 有 “ 通 用 解 题 法 ” 之 称 ， 它 可 以 系 统 地 搜 索 一 个 问 题 的 所 有 解 或 任 意 解 B. 回 溯 法 是 一 种 既 带 系 统 性 又 带 有 跳 跃 性 的 搜 索 算 法 C. 回 溯 算 法 需 要 借 助 队 列 这 种 结 构 来 保 存 从 根 结 点 到 当 前 扩 展 结 点 的 路 径 D. 回 溯 算 法 在 生 成 解 空 间 的 任 一 结 点 时 ， 先 判 断 该 结 点 是 否 可 能 包 含 问 题 的 解 ， 如 果 肯 定 不 包 含 ， 则 跳 过 对 该 结 点 为 根 的 子 树 的 搜 索 ， 逐 层 向 祖 先 结 点 回 溯 3. 回 溯 法 的 效 率 不 依 赖 于 下 列 哪 些 因 素 （ ） 。 A. 确 定 解 空 间 的 时 间 C. 计 算 约 束 函 数 的 时 间 B. 满 足 显 约 束 的 值 的 个 数 D. 计 算 限 界 函 数 的 时 间 4. 下 面 （ ） 函 数 是 回 溯 法 中 为 避 免 无 效 搜 索 采 取 的 策 略 。 A. 递 归 函 数 B. 剪 枝 函 数 C. 随 机 数 函 数 D. 搜 索 函 数 5. 回 溯 法 的 搜 索 特 点 是 什 么 ？ 6. 用 回 溯 法 解 0/1 背 包 问 题 时 ， 该 问 题 的 解 空 间 是 何 种 结 构 ？ 用 回 溯 法 解 流 水 作 业 调 度 问 题 时 ， 该 问 题 的 解 空 间 是 何 种 结 构 ？ 7. 对 于 递 增 序 列 a []={1 ， 2 ， 3 ， 4 ， 5} ， 采 用 例 5.4 的 回 溯 法 求 全 排 列 ， 以 1 、 2 开 头 的 排 列 一 定 最 先 出 现 吗 ？ 为 什 么 ？ 8. 考 虑 n 皇 后 问 题 ， 其 解 空 间 树 为 由 1 、 2 、 … 、 n 构 成 的 n ! 种 排 列 所 组 成 。 现 用 回 38 ----------------------------------------------------- Page 39 -----------------------------------------------------第 1 章 概 论 溯 法 求 解 ， 要 求 ： （ 1 ） 通 过 解 搜 索 空 间 说 明 n =3 时 是 无 解 的 。 （ 2 ） 给 出 剪 枝 操 作 。 （ 3 ） 最 坏 情 况 下 在 解 空 间 树 上 会 生 成 多 少 个 结 点 ？ 分 析 算 法 的 时 间 复 杂 度 。 9. 设 计 一 个 算 法 求 解 简 单 装 载 问 题 ， 设 有 一 批 集 装 箱 要 装 上 一 艘 载 重 量 为 W 的 轮 船 ， 其 中 编 号 为 i （ 0 ≤ i ≤ n - 1 ） 的 集 装 箱 的 重 量 为 w i 。 现 要 从 n 个 集 装 箱 中 选 出 若 干 装 上 轮 船 ， 使 它 们 的 重 量 之 和 正 好 为 W 。 如 果 找 到 任 一 种 解 返 回 true ， 否 则 返 回 false 。 10. 给 定 若 干 个 正 整 数 a 0 、 a 0 要 求 找 选 择 元 素 个 数 最 少 的 解 。 、 … 、 a n -1 ， 从 中 选 出 若 干 数 ， 使 它 们 的 和 恰 好 为 k ， 11. 设 计 求 解 有 重 复 元 素 的 排 列 问 题 的 算 法 ， 设 有 n 个 元 素 a []={ a 0 ， a 1 ， … ， a n -1 ) ， 其 中 可 能 含 有 重 复 的 元 素 ， 求 这 些 元 素 的 所 有 不 同 排 列 。 如 a []={1 ， 1 ， 2} ， 输 出 结 果 是 （ 1 ， 1 ， 2) ， （ 1 ， 2 ， 1 ） ， （ 2 ， 1 ， 1 ） 。 12. 采 用 递 归 回 溯 法 设 计 一 个 算 法 求 1 ～ n 的 n 个 整 数 中 取 出 m 个 元 素 的 排 列 ， 要 求 每 个 元 素 最 多 只 能 取 一 次 。 例 如 ， n =3 ， m =2 的 输 出 结 果 是 （ 1 ， 2 ） ， （ 1 ， 3 ） ， （ 2 ， 1 ） ， （ 2 ， 3 ） ， （ 3 ， 1 ） ， （ 3 ， 2 ） 。 13. 对 于 n 皇 后 问 题 ， 有 人 认 为 当 n 为 偶 数 时 ， 其 解 具 有 对 称 性 ， 即 n 皇 后 问 题 的 解 个 数 恰 好 为 n /2 皇 后 问 题 的 解 个 数 的 2 倍 ， 这 个 结 论 正 确 吗 ？ 请 编 写 回 溯 法 程 序 对 n =4 、 6 、 8 、 10 的 情 况 进 行 验 证 。 14. 给 定 一 个 无 向 图 ， 由 指 定 的 起 点 前 往 指 定 的 终 点 ， 途 中 经 过 所 有 其 他 顶 点 且 只 经 过 一 次 ， 称 为 哈 密 顿 路 径 ， 闭 合 的 哈 密 顿 路 径 称 作 哈 密 顿 回 路 （ Hamiltonian cycle ） 。 设 计 一 个 回 溯 算 法 求 无 向 图 的 所 有 哈 密 顿 回 路 。 1.5.2 练 习 题 参 考 答 案 1. 答 ： D 。 2. 答 ： 回 溯 算 法 是 采 用 深 度 优 先 遍 历 的 ， 需 要 借 助 系 统 栈 结 构 来 保 存 从 根 结 点 到 当 前 扩 展 结 点 的 路 径 。 答 案 为 C 。 3. 答 ： 回 溯 法 解 空 间 是 虚 拟 的 ， 不 必 确 定 整 个 解 空 间 。 答 案 为 A 。 4. 答 ： B 。 5. 答 ： 回 溯 法 在 解 空 间 树 中 采 用 深 度 优 先 遍 历 方 式 进 行 解 搜 索 ， 即 用 约 束 条 件 和 限 界 函 数 考 察 解 向 量 元 素 x [ i ] 的 取 值 ， 如 果 x [ i ] 是 合 理 的 就 搜 索 x [ i ] 为 根 结 点 的 子 树 ， 如 果 x [ i ] 取 完 了 所 有 的 值 ， 便 回 溯 到 x [ i - 1] 。 6. 答 ： 用 回 溯 法 解 0/1 背 包 问 题 时 ， 该 问 题 的 解 空 间 是 子 集 树 结 构 。 用 回 溯 法 解 流 水 作 业 调 度 问 题 时 ， 该 问 题 的 解 空 间 是 排 列 树 结 构 。 7. 答 ： 是 的 。 对 应 的 解 空 间 是 一 棵 排 列 树 ， 如 图 1.33 所 示 给 出 前 面 3 层 部 分 ， 显 然 最 先 产 生 的 排 列 是 从 G 结 点 扩 展 出 来 的 叶 子 结 点 ， 它 们 就 是 以 1 、 2 开 头 的 排 列 。 39 ----------------------------------------------------- Page 40 -----------------------------------------------------算 法 设 计 A 1 2 3 4 5 B C D E F 2 3 4 5 G H I 图 1.33 J 部 分 解 空 间 树 8. 答 ： （ 1 ） n =3 时 的 解 搜 索 空 间 如 图 1.34 所 示 ， 不 能 得 到 任 何 叶 子 结 点 ， 所 有 无 解 。 （ 2 ） 剪 枝 操 作 是 任 何 两 个 皇 后 不 能 同 行 、 同 列 和 同 两 条 对 角 线 。 （ 3 ） 最 坏 情 况 下 每 个 结 点 扩 展 n 个 结 点 ， 共 有 n 个 结 点 ， 算 法 的 时 间 复 杂 度 为 O( n ) 。 (*,*,*) (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() // 判 断 简 单 装 载 问 题 是 否 存 在 解 40 n n ----------------------------------------------------- Page 41 -----------------------------------------------------第 1 章 概 论 { count=0; int rw=0; for (int j=0;j<n;j++) rw+=w[j]; dfs(0,rw,0); if (count>0) return true; else return false; } void main() { printf(" 求 解 结 果 \ n"); // 求 所 有 集 装 箱 重 量 和 r w //i 从 0 开 始 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 程 序 执 行 结 果 10. 解 ： 这 是 一 个 典 型 的 解 空 间 为 子 集 树 的 问 题 ， 采 用 子 集 树 的 回 溯 算 法 框 架 。 当 找 到 一 个 解 后 通 过 选 取 的 元 素 个 数 进 行 比 较 求 最 优 解 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; void disppath() { printf(" 选 择 的 元 素 : "); // 设 置 为 全 局 变 量 // 存 放 最 优 解 // 最 多 选 择 n 个 元 素 // 输 出 一 个 解 for (int j=0;j<minpath.size();j++) printf("%d ",minpath[j]); printf(" 元 素 个 数 = %d\n",minn); } 41 ----------------------------------------------------- Page 42 -----------------------------------------------------算 法 设 计 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; dfs(path,sum,start+1); // 如 果 找 到 一 个 解 ， 不 一 定 到 叶 子 结 点 // 全 部 元 素 找 完 ， 返 回 // 不 选 择 a [start] path.push_back(a[start]); // 选 择 a [start] dfs(path,sum+a[start],start+1); } void main() { vector<int> path; dfs(path,0,0); printf(" 最 优 解 : \n"); disppath(); //path 存 放 一 个 子 集 } 上 述 程 序 的 执 行 结 果 如 图 1.36 所 示 。 图 1.36 程 序 执 行 结 果 11. 解 ： 在 回 溯 法 求 全 排 列 的 基 础 上 ， 增 加 元 素 的 重 复 性 判 断 。 例 如 ， 对 于 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) 42 ----------------------------------------------------- Page 43 -----------------------------------------------------第 1 章 概 论 { for(int j=0;j<n;j++) printf("=",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 程 序 执 行 结 果 12. 解 ： 采 用 求 全 排 列 的 递 归 框 架 。 选 取 的 元 素 个 数 用 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) { if (i>m) { for (int j=1;j<=m;j++) printf(" %d",x[j]); printf("\n"); //x[1..m] 存 放 一 个 排 列 // 求 n 个 元 素 中 m 个 元 素 的 全 排 列 // 输 出 一 个 排 列 43 ----------------------------------------------------- Page 44 -----------------------------------------------------算 法 设 计 } else { for (int j=1;j<=n;j++) { if (!used[j]) { used[j]=true; x[i]=j; dfs(i+1); used[j]=false; } } } } void main() { n=4,m=2; memset(used,0,sizeof(used)); printf("n=%d,m=%d 的 求 解 结 果 \ n",n,m); dfs(1); } 上 述 程 序 的 执 行 结 果 如 图 1.38 所 示 。 // 修 改 u sed[i] //x[i] 选 择 j // 继 续 搜 索 排 列 的 下 一 个 元 素 // 回 溯 ： 恢 复 u sed[i] // 初 始 化 为 0 //i 从 1 开 始 图 1.38 程 序 执 行 结 果 13. 解 ： 这 个 结 论 不 正 确 。 验 证 程 序 如 下 ： #include <stdio.h> #include <stdlib.h> #define MAXN 10 int q[MAXN]; bool place(int i) { int j=1; if (i==1) return true; while (j<i) // 测 试 第 i 行 的 q [i] 列 上 能 否 摆 放 皇 后 //j=1 ～ i-1 是 已 放 置 了 皇 后 的 行 { if ((q[j]==q[i]) || (abs(q[j]-q[i])==abs(j-i))) // 该 皇 后 是 否 与 以 前 皇 后 同 列 ， 位 置 ( j,q[j]) 与 ( i,q[i]) 是 否 同 对 角 线 return false; j++; } return true; } 44 ----------------------------------------------------- Page 45 -----------------------------------------------------第 1 章 概 论 int Queens(int n) { int count=0,k; int i=1; q[1]=0; while (i>0) { q[i]++; // 求 n 皇 后 问 题 的 解 个 数 // 计 数 器 初 始 化 //i 为 当 前 行 //q[i] 为 皇 后 i 的 列 号 // 移 到 下 一 列 while (q[i]<=n && !place(i)) q[i]++; if (q[i]<=n) { if (i==n) count++; // 找 到 一 个 解 计 数 器 c ount 加 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 程 序 执 行 结 果 14. 解 ： 假 设 给 定 的 无 向 图 有 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 45 ----------------------------------------------------- Page 46 -----------------------------------------------------// 求 解 问 题 表 示 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] 的 有 效 性 { if (a[x[i-1]][x[i]]!=1) //x[i-1] 到 x [i] 没 有 边 ， 返 回 f alse return false; for (int j=0;j<=i-1;j++) if (x[i]==x[j]) // 顶 点 i 重 复 出 现 ， 返 回 f alse return false; return true; } void Hamiltonian(int v) { x[0]=v; int i=1; x[i]=-1; while (i>0) { x[i]++; // 求 从 顶 点 v 出 发 的 哈 密 顿 回 路 // 存 放 起 点 // 从 顶 点 - 1+1=0 开 始 试 探 // 尚 未 回 溯 到 头 ， 循 环 while (!valid(i) && x[i]<n) x[i]++; if (x[i]<n) // 试 探 一 个 顶 点 x [i] // 找 到 一 个 有 效 的 顶 点 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; 46 ----------------------------------------------------- Page 47 -----------------------------------------------------第 1 章 概 论 Hamiltonian(v); // 从 顶 点 v 出 发 } } 上 述 程 序 对 如 图 1.40 所 示 的 无 向 图 求 从 每 个 顶 点 出 发 的 哈 密 顿 回 路 ， 程 序 执 行 结 果 如 图 1.41 所 示 。 1 0 3 2 4 图 1.40 一 个 无 向 图 图 1.41 程 序 执 行 结 果 1.6 第 6 章 ─ 分 枝 限 界 法 1.6.1 练 习 题 1. 分 枝 限 界 法 在 问 题 的 解 空 间 树 中 ， 按 （ ） 策 略 ， 从 根 结 点 出 发 搜 索 解 空 间 树 。 A. 广 度 优 先 B. 活 结 点 优 先 C. 扩 展 结 点 优 先 D. 深 度 优 先 2. 常 见 的 两 种 分 枝 限 界 法 为 （ ） 。 A. 广 度 优 先 分 枝 限 界 法 与 深 度 优 先 分 枝 限 界 法 47 ----------------------------------------------------- Page 48 -----------------------------------------------------算 法 设 计 B. 队 列 式 （ FIFO ） 分 枝 限 界 法 与 堆 栈 式 分 枝 限 界 法 C. 排 列 树 法 与 子 集 树 法 D. 队 列 式 （ FIFO ） 分 枝 限 界 法 与 优 先 队 列 式 分 枝 限 界 法 3. 分 枝 限 界 法 求 解 0/1 背 包 问 题 时 ， 活 结 点 表 的 组 织 形 式 是 （ ） 。 A. 小 根 堆 B. 大 根 堆 C. 栈 4. 采 用 最 大 效 益 优 先 搜 索 方 式 的 算 法 是 （ ） 。 A. 分 支 界 限 法 B. 动 态 规 划 法 C. 贪 心 法 D. 数 组 D. 回 溯 法 5. 优 先 队 列 式 分 枝 限 界 法 选 取 扩 展 结 点 的 原 则 是 （ ） 。 A. 先 进 先 出 B. 后 进 先 出 C. 结 点 的 优 先 级 D. 随 机 6. 简 述 分 枝 限 界 法 的 搜 索 策 略 。 7. 有 一 个 0/1 背 包 问 题 ， 其 中 n =4 ， 物 品 重 量 为 （ 4 ， 7 ， 5 ， 3 ） ， 物 品 价 值 为 （ 40 ， 42 ， 25 ， 12 ） ， 背 包 最 大 载 重 量 W =10 ， 给 出 采 用 优 先 队 列 式 分 枝 限 界 法 求 最 优 解 的 过 程 。 8. 有 一 个 流 水 作 业 调 度 问 题 ， n =4 ， a []={5 ， 10 ， 9 ， 7} ， b []={7 ， 5 ， 9 ， 8} ， 给 出 采 用 优 先 队 列 式 分 枝 限 界 法 求 一 个 解 的 过 程 。 9. 有 一 个 含 n 个 顶 点 （ 顶 点 编 号 为 0 ～ n - 1 ） 的 带 权 图 ， 采 用 邻 接 矩 阵 数 组 A 表 示 ， 采 用 分 枝 限 界 法 求 从 起 点 s 到 目 标 点 t 的 最 短 路 径 长 度 ， 以 及 具 有 最 短 路 径 长 度 的 路 径 条 数 。 10. 采 用 优 先 队 列 式 分 枝 限 界 法 求 解 最 优 装 载 问 题 。 给 出 以 下 装 载 问 题 的 求 解 过 程 和 结 果 ： n =5 ， 集 装 箱 重 量 为 w = （ 5 ， 2 ， 6 ， 4 ， 3 ） ， 限 重 为 W =10 。 在 装 载 重 量 相 同 时 ， 最 优 装 载 方 案 是 集 装 箱 个 数 最 少 的 方 案 。 1.6.2 练 习 题 参 考 答 案 1. 答 ： A 。 2. 答 ： D 。 3. 答 ： B 。 4. 答 ： A 。 5. 答 ： C 。 6. 答 ： 分 枝 限 界 法 的 搜 索 策 略 是 广 度 优 先 遍 历 ， 通 过 限 界 函 数 可 以 快 速 找 到 一 个 解 或 者 最 优 解 。 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] 。 48 ----------------------------------------------------- Page 49 -----------------------------------------------------第 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]={ // 一 个 带 权 有 向 图 49 ----------------------------------------------------- Page 50 -----------------------------------------------------{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; } }; void solve(int s ， int t) { NodeType e ， e1; priority_queue<NodeType> qu; e.vno=s; e.length=0; qu.push(e); while (!qu.empty()) { e=qu.top(); qu.pop(); if (e.vno==t) { if (e.length<bestlen) { bestcount=1; bestlen=e.length; } else if (e.length==bestlen) bestcount++; } else { for (int j=0; j<n; j++) //length 越 小 越 优 先 // 求 最 短 路 径 问 题 // 定 义 2 个 结 点 // 定 义 一 个 优 先 队 列 q u // 构 造 根 结 点 // 根 结 点 进 队 // 队 不 空 循 环 // 出 队 结 点 e 作 为 当 前 结 点 //e 是 一 个 叶 子 结 点 // 比 较 找 最 优 解 // 保 存 最 短 路 径 长 度 //e 不 是 叶 子 结 点 // 检 查 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); } } } } } 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); 50 // 有 效 子 结 点 e 1 进 队 ----------------------------------------------------- Page 51 -----------------------------------------------------第 1 章 概 论 printf(" 最 短 路 径 长 度 = %d ， 条 数 = %d\n" ， bestlen ， bestcount); // 输 出 ： 5 3 } } 上 述 程 序 的 执 行 结 果 如 图 1.39 所 示 。 图 1.39 程 序 执 行 结 果 10. 解 ： 采 用 优 先 队 列 式 分 枝 限 界 法 求 解 。 设 计 优 先 队 列 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}; // 求 解 结 果 表 示 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 // 最 多 的 集 装 箱 数 // 集 装 箱 重 量 , 不 计 下 标 0 的 元 素 // 存 放 最 大 重 量 , 全 局 变 量 // 存 放 最 优 解 , 全 局 变 量 // 搜 索 空 间 中 结 点 数 累 计 , 全 局 变 量 // 结 点 编 号 // 当 前 结 点 在 解 空 间 中 的 层 次 // 当 前 结 点 的 总 重 量 // 当 前 结 点 包 含 的 解 向 量 // 上 界 // 队 列 中 关 系 比 较 函 数 { bool operator()(const NodeType &s,const NodeType &t) { return (s.ub<t.ub) || (s.ub==t.ub && s.x[0]>t.x[0]); //ub 越 大 越 优 先 , 当 u b 相 同 时 x [0] 越 小 越 优 先 } }; void bound(NodeType &e) { int i=e.i+1; int r=0; while (i<=n) { r+=w[i]; i++; } e.ub=e.w+r; // 计 算 分 枝 结 点 e 的 上 界 //r 为 剩 余 集 装 箱 的 重 量 51 ----------------------------------------------------- Page 52 -----------------------------------------------------} void Loading() { NodeType e,e1,e2; 算 法 设 计 // 求 装 载 问 题 的 最 优 解 // 定 义 3 个 结 点 priority_queue<NodeType,vector<NodeType>,Cmp > qu; // 定 义 一 个 优 先 队 列 q u e.no=Count++; e.i=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) // 设 置 结 点 编 号 // 根 结 点 置 初 值 , 其 层 次 计 为 0 // 初 始 化 根 结 点 的 解 向 量 // 求 根 结 点 的 上 界 // 根 结 点 进 队 // 队 不 空 循 环 // 出 队 结 点 e 作 为 当 前 结 点 //e 是 一 个 叶 子 结 点 { if ((e.w>bestw) || (e.w==bestw && e.x[0]<bestx[0])) // 比 较 找 最 优 解 { bestw=e.w; // 更 新 b estw for (int j=0;j<=e.i;j++) bestx[j]=e.x[j]; // 复 制 解 向 量 e .x->bestx } } else { if (e.w+w[e.i+1]<=W) { e1.no=Count++; e1.i=e.i+1; //e 不 是 叶 子 结 点 // 检 查 左 孩 子 结 点 // 设 置 结 点 编 号 // 建 立 左 孩 子 结 点 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; e1.x[0]++; bound(e1); qu.push(e1); } e2.no=Count++; e2.i=e.i+1; // 选 择 集 装 箱 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); if (e2.ub>bestw) qu.push(e2); } } } void disparr(int x[],int len) { for (int i=1;i<=len;i++) printf("-",x[i]); } void dispLoading() { printf(" X=["); // 不 选 择 集 装 箱 i // 求 右 孩 子 结 点 的 上 界 // 若 右 孩 子 结 点 可 行 , 则 进 队 , 否 则 被 剪 枝 // 输 出 一 个 解 向 量 // 输 出 最 优 解 52 ----------------------------------------------------- Page 53 -----------------------------------------------------第 1 章 概 论 disparr(bestx,n); printf("], 装 入 总 价 值 为 % d\n",bestw); } void main() { Loading(); printf(" 求 解 结 果 : \n"); dispLoading(); } 上 述 程 序 的 执 行 结 果 如 图 1.40 所 示 。 // 输 出 最 优 解 图 1.40 程 序 执 行 结 果 1.7 第 7 章 ─ 贪 心 法 1.7.1 练 习 题 1. 下 面 是 贪 心 算 法 的 基 本 要 素 的 是 （ ） 。 A. 重 叠 子 问 题 B. 构 造 最 优 解 C. 贪 心 选 择 性 质 D. 定 义 最 优 解 2. 下 面 问 题 （ ） 不 能 使 用 贪 心 法 解 决 。 A. 单 源 最 短 路 径 问 题 B. n 皇 后 问 题 C. 最 小 花 费 生 成 树 问 题 D. 背 包 问 题 3. 采 用 贪 心 算 法 的 最 优 装 载 问 题 的 主 要 计 算 量 在 于 将 集 装 箱 依 其 重 量 从 小 到 大 排 序 ， 故 算 法 的 时 间 复 杂 度 为 （ ） 。 A.O( n ) B.O( n ) C.O( n ) D.O( n log 2 n ) 4. 关 于 0/ 1 背 包 问 题 以 下 描 述 正 确 的 是 （ ） 。 A. 可 以 使 用 贪 心 算 法 找 到 最 优 解 B. 能 找 到 多 项 式 时 间 的 有 效 算 法 C. 使 用 教 材 介 绍 的 动 态 规 划 方 法 可 求 解 任 意 0 － 1 背 包 问 题 D. 对 于 同 一 背 包 与 相 同 的 物 品 ， 做 背 包 问 题 取 得 的 总 价 值 一 定 大 于 等 于 做 0/1 背 包 问 题 5. 一 棵 哈 夫 曼 树 共 有 215 个 结 点 ， 对 其 进 行 哈 夫 曼 编 码 ， 共 能 得 到 （ ） 个 不 同 的 码 字 。 A.107 B.108 C.214 D.215 6. 求 解 哈 夫 曼 编 码 中 如 何 体 现 贪 心 思 路 ？ 7. 举 反 例 证 明 0/1 背 包 问 题 若 使 用 的 算 法 是 按 照 v i / w i 的 非 递 减 次 序 考 虑 选 择 的 物 品 ， 即 只 要 正 在 被 考 虑 的 物 品 装 得 进 就 装 入 背 包 ， 则 此 方 法 不 一 定 能 得 到 最 优 解 （ 此 题 说 明 0/1 背 包 问 题 与 背 包 问 题 的 不 同 ） 。 53 2 3 ----------------------------------------------------- Page 54 -----------------------------------------------------算 法 设 计 8. 求 解 硬 币 问 题 。 有 1 分 、 2 分 、 5 分 、 10 分 、 50 分 和 100 分 的 硬 币 各 若 干 枚 ， 现 在 要 用 这 些 硬 币 来 支 付 W 元 ， 最 少 需 要 多 少 枚 硬 币 。 9. 求 解 正 整 数 的 最 大 乘 积 分 解 问 题 。 将 正 整 数 n 分 解 为 若 干 个 互 不 相 同 的 自 然 数 之 和 ， 使 这 些 自 然 数 的 乘 积 最 大 。 10. 求 解 乘 船 问 题 。 有 n 个 人 ， 第 i 个 人 体 重 为 w i （ 0 ≤ i < n ） 。 每 艘 船 的 最 大 载 重 量 均 为 C ， 且 最 多 只 能 乘 两 个 人 。 用 最 少 的 船 装 载 所 有 人 。 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. 12. 假 设 要 在 足 够 多 的 会 场 里 安 排 一 批 活 动 ， n 个 活 动 编 号 为 1 ～ n ， 每 个 活 动 有 开 始 时 间 b i 和 结 束 时 间 e i （ 1 ≤ i ≤ n ） 。 设 计 一 个 有 效 的 贪 心 算 法 求 出 最 少 的 会 场 个 数 。 13. 给 定 一 个 m × n 的 数 字 矩 阵 ， 计 算 从 左 到 右 走 过 该 矩 阵 且 经 过 的 方 格 中 整 数 最 小 的 路 径 。 一 条 路 径 可 以 从 第 1 列 的 任 意 位 置 出 发 ， 到 达 第 n 列 的 任 意 位 置 ， 每 一 步 为 从 第 i 列 走 到 第 i +1 列 相 邻 行 （ 水 平 移 动 或 沿 45 度 斜 线 移 动 ） ， 如 图 1.41 所 示 。 第 1 行 和 最 后 一 行 看 作 是 相 邻 的 ， 即 应 当 把 这 个 矩 阵 看 成 是 一 个 卷 起 来 的 圆 筒 。 图 1.41 每 一 步 的 走 向 两 个 略 有 不 同 的 5×6 的 数 字 矩 阵 的 最 小 路 径 如 图 1.42 所 示 ， 只 有 最 下 面 一 行 的 数 不 同 。 右 边 矩 阵 的 路 径 利 用 了 第 一 行 与 最 后 一 行 相 邻 的 性 质 。 输 入 ： 包 含 多 个 矩 阵 ， 每 个 矩 阵 的 第 一 行 为 两 个 数 m 和 n ， 分 别 表 示 矩 阵 的 行 数 和 列 数 ， 接 下 来 的 m × n 个 整 数 按 行 优 先 的 顺 序 排 列 ， 即 前 n 个 数 组 成 第 一 行 ， 接 下 的 n 个 数 组 成 第 2 行 ， 依 此 类 推 。 相 邻 整 数 间 用 一 个 或 多 个 空 格 分 隔 。 注 意 这 些 数 不 一 定 是 正 数 。 输 入 中 可 能 有 一 个 或 多 个 矩 阵 描 述 ， 直 到 输 入 结 束 。 每 个 矩 阵 的 行 数 在 1 到 10 之 间 ， 列 数 在 1 到 100 之 间 。 输 出 ： 对 每 个 矩 阵 输 出 两 行 ， 第 一 行 为 最 小 整 数 之 和 的 路 径 ， 路 径 由 n 个 整 数 组 成 ， 表 示 路 径 经 过 的 行 号 ， 如 果 这 样 的 路 径 不 止 一 条 ， 输 出 字 典 序 最 小 一 条 。 54 输 入 样 本 ： 图 1.42 个 字 阵 最

2 ----------------------------------------------------- Page 55 -----------------------------------------------------第 1 章 概 论 6 18 2 7 4 5 9 3 9 9 5 8 4 1 326 37 2 8 64 输 出 结 果 ： 1 2 3 4 4 5 16 1.7.2 练 习 题 参 考 答 案 1. 答 ： C 。 2. 答 ： n 皇 后 问 题 的 解 不 满 足 贪 心 选 择 性 质 。 答 案 为 B 。 3. 答 ： D 。 4. 答 ： 由 于 背 包 问 题 可 以 取 物 品 的 一 部 分 ， 所 以 总 价 值 一 定 大 于 等 于 做 0/1 背 包 问 题 。 答 案 为 D 。 5. 答 ： 这 里 n =215 ， 哈 夫 曼 树 中 n 1 =0 ， 而 n 0 = n 2 +1 ， n = n 0 + n 1 + n 2 =2n 0 - 1 ， n 0 =( n +1)/2=108 。 答 案 为 B 。 6. 答 ： 在 构 造 哈 夫 曼 树 时 每 次 都 是 将 两 棵 根 结 点 最 小 的 树 合 并 ， 从 而 体 现 贪 心 的 思 路 。 7. 证 明 ： 例 如 ， n =3 ， w ={3 ， 2 ， 2} ， v ={7 ， 4 ， 4} ， W =4 时 ， 由 于 7/3 最 大 ， 若 按 题 目 要 求 的 方 法 ， 只 能 取 第 一 个 ， 收 益 是 7 。 而 此 实 例 的 最 大 的 收 益 应 该 是 8 ， 取 第 2 、 3 个 物 品 。 8. 解 ： 用 结 构 体 数 组 A 存 放 硬 币 数 据 ， A [ i ]. v 存 放 硬 币 i 的 面 额 ， A [ i ]. c 存 放 硬 币 i 的 枚 数 。 采 用 贪 心 思 路 ， 首 先 将 数 组 A 按 面 额 递 减 排 序 ， 再 兑 换 硬 币 ， 每 次 尽 可 能 兑 换 面 额 大 的 硬 币 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <algorithm> using namespace std; #define min(x,y) ((x)<(y)?(x):(y)) #define MAX 21 // 问 题 表 示 int n=7; struct NodeType { int v; int c; // 面 额 // 枚 数 bool operator<(const NodeType &s) { // 用 于 按 面 额 递 减 排 序 return s.v<v; } }; NodeType A[]={{1,12},{2,8},{5,6},{50,10},{10,8},{200,1},{100,4}}; int W; // 求 解 结 果 表 示 int ans=0; void solve() // 兑 换 的 硬 币 枚 数 // 兑 换 硬 币 55 ----------------------------------------------------- Page 56 -----------------------------------------------------{ sort(A,A+n); 算 法 设 计 // 按 面 额 递 减 排 序 for (int i=0;i<n;i++) { int t=min(W/A[i].v,A[i].c); // 使 用 硬 币 i 的 枚 数 if (t!=0) printf(" 支 付 = 面 额 : = 枚 \ n",A[i].v,t); W-=t*A[i].v; ans+=t; if (W==0) break; } } void main() { W=325; // 剩 余 的 金 额 // 支 付 的 金 额 printf(" 支 付 % d 分 : \n",W); solve(); printf(" 最 少 硬 币 的 个 数 : %d 枚 \ n",ans); } 上 述 程 序 的 执 行 结 果 如 图 1.43 所 示 。 图 1.43 程 序 执 行 结 果 9. 解 ： 采 用 贪 心 方 法 求 解 。 用 a [0.. k ] 存 放 n 的 分 解 结 果 ： （ 1 ） n ≤ 4 时 可 以 验 证 其 分 解 成 几 个 正 整 数 的 和 的 乘 积 均 小 于 n ， 没 有 解 。 （ 2 ） n >4 时 ， 把 n 分 拆 成 若 干 个 互 不 相 等 的 自 然 数 的 和 ， 分 解 数 的 个 数 越 多 乘 积 越 大 。 为 此 让 n 的 分 解 数 个 数 尽 可 能 多 （ 体 现 贪 心 的 思 路 ） ， 把 n 分 解 成 从 2 开 始 的 连 续 的 自 然 数 之 和 。 例 如 ， 分 解 n 为 a [0]=2 ， a [1]=3 ， a [2]=4 ， … ， a [ k ]= k +2 （ 共 有 k +1 个 分 解 数 ） ， 用 m 表 示 剩 下 数 ， 这 样 的 分 解 直 到 m ≤ a [ k ] 为 止 ， 即 m ≤ k +2 。 对 剩 下 数 m 的 处 理 分 为 如 下 两 种 情 况 ： ① m < k +2 ： 将 m 平 均 分 解 到 a [ k .. i ] （ 对 应 的 分 解 数 个 数 为 m ） 中 ， 即 从 a [ k ] 开 始 往 前 的 分 解 数 增 加 1 （ 也 是 贪 心 的 思 路 ， 分 解 数 越 大 加 1 和 乘 积 也 越 大 ） 。 ② m = k +2 ： 将 a [0.. k - 1] （ 对 应 的 分 解 数 个 数 为 k ） 的 每 个 分 解 数 增 加 1 ， 剩 下 的 2 增 加 到 a [ k ] 中 ， 即 a [ k ] 增 加 2 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <string.h> #define MAX 20 // 问 题 表 示 int n; // 求 解 结 果 表 示 56 ----------------------------------------------------- Page 57 -----------------------------------------------------第 1 章 概 论 int a[MAX]; int k=0; void solve() { int i; int sum=1; if (n<4) return; else { int m=n; a[0]=2; m-=a[0]; k=0; while (m>a[k]) { k++; // 存 放 被 分 解 的 数 //a[0..k] 存 放 被 分 解 的 数 // 求 解 n 的 最 大 乘 积 分 解 问 题 // 不 存 在 最 优 方 案 , 直 接 返 回 //m 表 示 剩 下 数 // 第 一 个 数 从 2 开 始 // 减 去 已 经 分 解 的 数 // 若 剩 下 数 大 于 最 后 一 个 分 解 数 , 则 继 续 分 解 //a 数 组 下 标 + 1 a[k]=a[k-1]+1; // 按 2 、 3 、 4 递 增 顺 序 分 解 m-=a[k]; } if (m<a[k]) // 减 去 最 新 分 解 的 数 // 若 剩 下 数 小 于 a [k], 从 a [k] 开 始 往 前 的 数 + 1 { for (i=0; i<m; i++) a[k-i]+=1; } if (m==a[k]) { a[k]+=2; // 若 剩 下 数 等 于 a [k], 则 a [k] 的 值 + 2, 之 前 的 数 + 1 for (i=0; i<k; i++) a[i]+=1; } } } void main() { n=23; memset(a,0,sizeof(a)); solve(); printf("%d 的 最 优 分 解 方 案 \ n",n); int mul=1; printf(" 分 解 的 数 : "); for (int i=0;i<=k;i++) if (a[i]!=0) { printf("%d ",a[i]); mul*=a[i]; } printf("\n 乘 积 最 大 值 : %d\n",mul); } 上 述 程 序 的 执 行 结 果 如 图 1.44 所 示 。 57 ----------------------------------------------------- Page 58 -----------------------------------------------------图 1.44 算 法 设 计 程 序 执 行 结 果 10. 解 ： 采 用 贪 心 思 路 ， 首 先 按 体 重 递 增 排 序 ； 再 考 虑 前 后 的 两 个 人 （ 最 轻 者 和 最 重 者 ） ， 分 别 用 i 、 j 指 向 ： 若 w [ i ]+ w [ j ] ≤ C ， 说 明 这 两 个 人 可 以 同 乘 （ 执 行 i ++ ， j -- ） ， 否 则 w [ j ] 单 乘 （ 执 行 j -- ） ， 若 最 后 只 剩 余 一 个 人 ， 该 人 只 能 单 乘 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <algorithm> using namespace std; #define MAXN 101 // 问 题 表 示 int n=7; int w[]={50,65,58,72,78,53,82}; int C=150; // 求 解 结 果 表 示 int bests=0; void Boat() { sort(w,w+n); int i=0; int j=n - 1; while (i<=j) { if(i==j) // 求 解 乘 船 问 题 // 递 增 排 序 // 剩 下 最 后 一 个 人 { printf(" 一 艘 船 : %d\n",w[i]); bests++; break; } if (w[i]+w[j]<=C) // 前 后 两 个 人 同 乘 { printf(" 一 艘 船 : %d %d\n",w[i],w[j]); bests++; i++; j--; } else //w[j] 单 乘 { printf(" 一 艘 船 : %d\n",w[j]); bests++; j--; } } } void main() { printf(" 求 解 结 果 : \n"); Boat(); printf(" 最 少 的 船 数 = %d\n",bests); } 上 述 程 序 的 执 行 结 果 如 图 1.45 所 示 。 58 ----------------------------------------------------- Page 59 -----------------------------------------------------第 1 章 概 论 图 1.45 程 序 执 行 结 果 11. 解 ： 采 用 贪 心 思 路 。 每 次 都 在 还 未 安 排 的 容 量 最 大 的 会 议 室 安 排 尽 可 能 多 的 参 会 人 数 ， 即 对 于 每 个 会 议 室 ， 都 安 排 当 前 还 未 安 排 的 会 议 中 ， 参 会 人 数 最 多 的 会 议 。 若 能 容 纳 下 ， 则 选 择 该 会 议 ， 否 则 找 参 会 人 数 次 多 的 会 议 来 安 排 ， 直 到 找 到 能 容 纳 下 的 会 议 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <algorithm> using namespace std; // 问 题 表 示 int n=4; int m=4; int A[]={3,4,3,1}; int B[]={1,2,2,6}; // 求 解 结 果 表 示 int ans=0; void solve() { sort(A,A+n); sort(B,B+m); // 会 议 个 数 // 会 议 室 个 数 // 求 解 算 法 // 递 增 排 序 // 递 增 排 序 int i=n-1,j=m-1; // 从 最 多 人 数 会 议 和 最 多 容 纳 人 数 会 议 室 开 始 for(i;i>=0;i--) { if(A[i]<=B[j] && j>=0) { ans++; // 不 满 足 条 件 ， 增 加 一 个 会 议 室 j--; } } } void main() { solve(); printf("%d\n",ans); // 输 出 2 } 12. 解 ： 与 《 教 程 》 例 7.2 类 似 ， 会 场 对 应 蓄 栏 ， 只 是 这 里 仅 仅 求 会 场 个 数 ， 即 最 大 兼 容 活 动 子 集 的 个 数 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define MAX 51 // 问 题 表 示 struct Action // 活 动 的 类 型 声 明 59 ----------------------------------------------------- Page 60 -----------------------------------------------------{ int b; int e; 算 法 设 计 // 活 动 起 始 时 间 // 活 动 结 束 时 间 bool operator<(const Action &s) const // 重 载 < 关 系 函 数 { if (e==s.e) return b<=s.b; else return e<=s.e; } // 结 束 时 间 相 同 按 开 始 时 间 递 增 排 序 // 否 则 按 结 束 时 间 递 增 排 序 }; int n=5; Action A[]={{0},{1,10},{2,4},{3,6},{5,8},{4,7}}; // 下 标 0 不 用 // 求 解 结 果 表 示 int ans; void solve() { bool flag[MAX]; memset(flag,0,sizeof(flag)); sort(A+1,A+n+1); ans=0; for (int j=1;j<=n;j++) { if (!flag[j]) { flag[j]=true; int preend=j; // 最 少 会 场 个 数 // 求 解 最 大 兼 容 活 动 子 集 // 活 动 标 志 //A[1..n] 按 指 定 方 式 排 序 // 会 场 个 数 // 前 一 个 兼 容 活 动 的 下 标 for (int i=preend+1;i<=n;i++) { if (A[i].b>=A[preend].e && !flag[i]) { preend=i; flag[i]=true; } } ans++; // 增 加 一 个 最 大 兼 容 活 动 子 集 } } } void main() { solve(); printf(" 求 解 结 果 \ n"); printf(" 最 少 会 场 个 数 : %d\n",ans); // 输 出 4 } 13. 解 ： 采 用 贪 心 思 路 。 从 第 1 列 开 始 每 次 查 找 a [ i ][ j ] 元 素 上 、 中 、 下 3 个 对 应 数 中 的 最 小 数 。 对 应 的 程 序 如 下 ： #include <stdio.h> #define M 12 #define N 110 int m=5, n=6; int a[M][N]={{3,4,1,2,8,6},{6,1,8,2,7,4},{5,9,3,9,9,5},{8,4,1,3,2,6},{3,7,2,8,6,4}}; int minRow,minCol; int minValue(int i, int j) // 求 a [i][j] 有 方 上 、 中 、 下 3 个 数 的 最 小 数 , 同 时 要 把 行 标 记 录 下 来 { int s = (i == 0) ? m - 1 : i - 1; int x = (i == m - 1) ? 0 : i + 1; 60 ----------------------------------------------------- Page 61 -----------------------------------------------------第 1 章 概 论 minRow = s; minRow = a[i][j+1] < a[minRow][j+1] ? i : minRow; minRow = a[x][j+1] < a[minRow][j+1] ? x : minRow; minRow = a[minRow][j+1] == a[s][j+1] && minRow > s ? s : minRow; minRow = a[minRow][j+1] == a[i][j+1] && minRow > i ? i : minRow; minRow = a[minRow][j+1] == a[x][j+1] && minRow > x ? x : minRow; return a[minRow][j+1]; } void solve() { int i,j,min; for (j=n-2; j>=0; j--) for (i=0; i<m; i++) a[i][j]+= minValue(i,j); min=a[0][0]; minRow=0; for (i=1; i<m; i++) if (a[i][0]<min) { min=a[i][0]; minRow=i; } for (j=0; j<n; j++) { printf("%d",minRow+1); if (j<n-1) printf(" "); minValue(minRow, j); } printf("\n%d\n",min); } void main() { solve(); } // 在 第 一 列 查 找 最 小 代 价 的 行 1.8 第 8 章 ─ 动 态 规 划 1.8.1 练 习 题 1. 下 列 算 法 中 通 常 以 自 底 向 上 的 方 式 求 解 最 优 解 的 是 （ ） 。 A. 备 忘 录 法 B. 动 态 规 划 法 C. 贪 心 法 D. 回 溯 法 2. 备 忘 录 方 法 是 （ ） 算 法 的 变 形 。 A. 分 治 法 B. 回 溯 法 C. 贪 心 法 D. 动 态 规 划 法 3. 下 列 是 动 态 规 划 算 法 基 本 要 素 的 是 （ ） 。 A. 定 义 最 优 解 B. 构 造 最 优 解 C. 算 出 最 优 解 D. 子 问 题 重 叠 性 质 4. 一 个 问 题 可 用 动 态 规 划 算 法 或 贪 心 算 法 求 解 的 关 键 特 征 是 问 题 的 （ ） 。 A. 贪 心 选 择 性 质 B. 重 叠 子 问 题 C. 最 优 子 结 构 性 质 D. 定 义 最 优 解 5. 简 述 动 态 规 划 法 的 基 本 思 路 。 6. 简 述 动 态 规 划 法 与 贪 心 法 的 异 同 。 61 ----------------------------------------------------- Page 62 -----------------------------------------------------算 法 设 计 7. 简 述 动 态 规 划 法 与 分 治 法 的 异 同 。 8. 下 列 算 法 中 哪 些 属 于 动 态 规 划 算 法 ？ （ 1 ） 顺 序 查 找 算 法 （ 2 ） 直 接 插 入 排 序 算 法 （ 3 ） 简 单 选 择 排 序 算 法 （ 4 ） 二 路 归 并 排 序 算 法 9. 某 个 问 题 对 应 的 递 归 模 型 如 下 ： f (1)=1 f (2)=2 f ( n )= f ( n - 1)+ f ( n - 2)+ … + f (1)+1 可 以 采 用 如 下 递 归 算 法 求 解 ： long f(int n) { if (n==1) return 1; if (n==2) return 2; long sum=1; for (int i=1;i<=n-1;i++) sum+=f(i); return sum; 当 n >2 时 } 但 其 中 存 在 大 量 的 重 复 计 算 ， 请 采 用 备 忘 录 方 法 求 解 。 10. 第 3 章 中 的 实 验 4 采 用 分 治 法 求 解 半 数 集 问 题 ， 如 果 直 接 递 归 求 解 会 存 在 大 量 重 复 计 算 ， 请 改 进 该 算 法 。 11. 设 计 一 个 时 间 复 杂 度 为 O( n ) 的 算 法 来 计 算 二 项 式 系 数 C n （ k ≤ n ） 。 二 项 式 系 数 C n 的 求 值 过 程 如 下 ： ? = 1 ? = 1 ? ? ‒ 1 ? ? ? ‒ 1 ? ‒ 1 当 i ≥ j 12. 一 个 机 器 人 只 能 向 下 和 向 右 移 动 ， 每 次 只 能 移 动 一 步 ， 设 计 一 个 算 法 求 它 从 （ 0 ， 0 ） 移 动 到 （ m ， n ） 有 多 少 条 路 径 。 13. 两 种 水 果 杂 交 出 一 种 新 水 果 ， 现 在 给 新 水 果 取 名 ， 要 求 这 个 名 字 中 包 含 了 以 前 两 种 水 果 名 字 的 字 母 ， 并 且 这 个 名 字 要 尽 量 短 。 也 就 是 说 以 前 的 一 种 水 果 名 字 arr1 是 新 水 果 名 字 arr 的 子 序 列 ， 另 一 种 水 果 名 字 arr2 也 是 新 水 果 名 字 arr 的 子 序 列 。 设 计 一 个 算 法 求 arr 。 例 如 ： 输 入 以 下 3 组 水 果 名 称 ： apple peach ananas banana pear peach 输 出 的 新 水 果 名 称 如 下 ： 62 2 k n k 0 ? ? ? ? = ? + ? ----------------------------------------------------- Page 63 -----------------------------------------------------第 1 章 概 论 appleach bananas pearch 1.8.2 练 习 题 参 考 答 案 1. 答 ： B 。 2. 答 ： D 。 3. 答 ： D 。 4. 答 ： C 。 5. 答 ： 动 态 规 划 法 的 基 本 思 路 是 将 待 求 解 问 题 分 解 成 若 干 个 子 问 题 ， 先 求 子 问 题 的 解 ， 然 后 从 这 些 子 问 题 的 解 得 到 原 问 题 的 解 。 6. 答 ： 动 态 规 划 法 的 3 个 基 本 要 素 是 最 优 子 结 构 性 质 、 无 后 效 性 和 重 叠 子 问 题 性 质 ， 而 贪 心 法 的 两 个 基 本 要 素 是 贪 心 选 择 性 质 和 最 优 子 结 构 性 质 。 所 以 两 者 的 共 同 点 是 都 要 求 问 题 具 有 最 优 子 结 构 性 质 。 两 者 的 不 同 点 如 下 ： （ 1 ） 求 解 方 式 不 同 ， 动 态 规 划 法 是 自 底 向 上 的 ， 有 些 具 有 最 优 子 结 构 性 质 的 问 题 只 能 用 动 态 规 划 法 ， 有 些 可 用 贪 心 法 。 而 贪 心 法 是 自 顶 向 下 的 。 （ 2 ） 对 子 问 题 的 依 赖 不 同 ， 动 态 规 划 法 依 赖 于 各 子 问 题 的 解 ， 所 以 应 使 各 子 问 题 最 优 ， 才 能 保 证 整 体 最 优 ； 而 贪 心 法 依 赖 于 过 去 所 作 过 的 选 择 ， 但 决 不 依 赖 于 将 来 的 选 择 ， 也 不 依 赖 于 子 问 题 的 解 。 7. 答 ： 两 者 的 共 同 点 是 将 待 求 解 的 问 题 分 解 成 若 干 子 问 题 ， 先 求 解 子 问 题 ， 然 后 再 从 这 些 子 问 题 的 解 得 到 原 问 题 的 解 。 两 者 的 不 同 点 是 ： 适 合 于 用 动 态 规 划 法 求 解 的 问 题 ， 分 解 得 到 的 各 子 问 题 往 往 不 是 相 互 独 立 的 （ 重 叠 子 问 题 性 质 ） ， 而 分 治 法 中 子 问 题 相 互 独 立 ； 另 外 动 态 规 划 法 用 表 保 存 已 求 解 过 的 子 问 题 的 解 ， 再 次 碰 到 同 样 的 子 问 题 时 不 必 重 新 求 解 ， 而 只 需 查 询 答 案 ， 故 可 获 得 多 项 式 级 时 间 复 杂 度 ， 效 率 较 高 ， 而 分 治 法 中 对 于 每 次 出 现 的 子 问 题 均 求 解 ， 导 致 同 样 的 子 问 题 被 反 复 求 解 ， 故 产 生 指 数 增 长 的 时 间 复 杂 度 ， 效 率 较 低 。 8. 答 ： 判 断 算 法 是 否 具 有 最 优 子 结 构 性 质 、 无 后 效 性 和 重 叠 子 问 题 性 质 。 （ 2 ） 、 （ 3 ） 和 （ 4 ） 均 属 于 动 态 规 划 算 法 。 9. 解 ： 设 计 一 个 dp 数 组 ， dp[ i ] 对 应 f ( i ) 的 值 ， 首 先 dp 的 所 有 元 素 初 始 化 为 0 ， 在 计 算 f ( i ) 时 ， 若 dp[0]>0 表 示 f ( i ) 已 经 求 出 ， 直 接 返 回 dp[ i ] 即 可 ， 这 样 避 免 了 重 复 计 算 。 对 应 的 算 法 如 下 ： long dp[MAX]; //dp[n] 保 存 f (n) 的 计 算 结 果 long f1(int n) { if (n==1) { dp[n]=1; return dp[n]; } if (n==2) { dp[n]=2; return dp[n]; 63 ----------------------------------------------------- Page 64 -----------------------------------------------------算 法 设 计 } if (dp[n]>0) return dp[n]; long sum=1; for (int i=1;i<=n-1;i++) sum+=f1(i); dp[n]=sum; return dp[n]; } 10. 解 ： 设 计 一 个 数 组 a ， 其 中 a [ i ]= f ( i ) ， 首 先 将 a 的 所 有 元 素 初 始 化 为 0 ， 当 a [ i ]>0 时 表 示 对 应 的 f ( i ) 已 经 求 出 ， 直 接 返 回 就 可 以 了 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <string.h> #define MAXN 201 // 问 题 表 示 int n; int a[MAXN]; int fa(int i) { int ans=1; if (a[i]>0) return a[i]; for(int j=1;j<=i/2;j++) ans+=fa(j); a[i]=ans; return ans; } int solve(int n) { memset(a,0,sizeof(a)); a[1]=1; return fa(n); } void main() { n=6; // 求 a [i] // 求 s et(n) 的 元 素 个 数 printf(" 求 解 结 果 \ n"); printf(" n=%d 时 半 数 集 元 素 个 数 = %d\n",n,solve(n)); } 11. 解 ： 定 义 C ( i ， j )= C i ， i ≥ j 。 则 有 如 下 递 推 计 算 公 式 ： C ( i ， n j )= C ( i - 1 ， j - 1)+C( i - 1 ， j ) ， 初 始 条 件 为 C ( i ， 0)=1 ， C ( i ， i )=1 。 可 以 根 据 初 始 条 件 由 此 递 推 关 系 计 算 C ( n ， k ) ， n 即 C n 。 对 应 的 程 序 如 下 ： #include <stdio.h> #define MAXN 51 #define MAXK 31 // 问 题 表 示 int n,k; // 求 解 结 果 表 示 int C[MAXN][MAXK]; void solve() { int i,j; 64 j k ----------------------------------------------------- Page 65 -----------------------------------------------------第 1 章 概 论 for (i=0;i<=n;i++) { C[i][i]=1; C[i][0]=1; } for (i=1;i<=n;i++) for (j=1;j<=k;j++) C[i][j]=C[i-1][j-1]+C[i-1][j]; } void main() { n=5,k=3; solve(); printf("%d\n",C[n][k]); // 输 出 1 0 } 显 然 ， solve() 算 法 的 时 间 复 杂 度 为 O( n ) 。 12. 解 ： 设 从 （ 0 ， 0 ） 移 动 到 （ i ， j ） 的 路 径 条 数 为 dp[ i ][ j ] ， 由 于 机 器 人 只 能 向 下 和 向 右 移 动 ， 不 同 于 迷 宫 问 题 （ 迷 宫 问 题 由 于 存 在 后 退 ， 不 满 足 无 后 效 性 ， 不 适 合 用 动 态 规 划 法 求 解 ） 。 对 应 的 状 态 转 移 方 程 如 下 ： dp[0][ j ]=1 dp[ i ][0]=1 dp[ i ][ j ]=dp[ i ][ j - 1]+dp[ i - 1][ j ] i 、 j >0 最 后 结 果 是 dp[ m ][ n ] 。 对 应 的 程 序 如 下 ： #include <stdio.h> #include <string.h> #define MAXX 51 #define MAXY 51 // 问 题 表 示 int m,n; // 求 解 结 果 表 示 int dp[MAXX][MAXY]; void solve() { int i,j; dp[0][0]=0; memset(dp,0,sizeof(dp)); for (i=1;i<=m;i++) dp[i][0]=1; for (j=1;j<=n;j++) dp[0][j]=1; for (i=1;i<=m;i++) for (j=1;j<=n;j++) dp[i][j]=dp[i][j-1]+dp[i-1][j]; } void main() { m=5,n=3; solve(); printf("%d\n",dp[m][n]); } 13. 解 ： 本 题 目 的 思 路 是 求 arr1 和 arr2 字 符 串 的 最 长 公 共 子 序 列 ， 基 本 过 程 参 见 《 教 65 2 ----------------------------------------------------- Page 66 -----------------------------------------------------程 》 第 8 章 8.5 节 。 对 应 的 完 整 程 序 如 下 ： #include <iostream> #include <string.h> #include <vector> #include <string> using namespace std; #define max(x,y) ((x)>(y)?(x):(y)) #define MAX 51 // 问 题 表 示 int m,n; string arr1,arr2; // 求 解 结 果 表 示 int dp[MAX][MAX]; vector<char> subs; void LCSlength() { int i,j; for (i=0;i<=m;i++) dp[i][0]=0; for (j=0;j<=n;j++) dp[0][j]=0; for (i=1;i<=m;i++) for (j=1;j<=n;j++) 算 法 设 计 // 序 列 中 最 多 的 字 符 个 数 // 动 态 规 划 数 组 // 存 放 L CS // 求 d p // 将 d p[i][0] 置 为 0 , 边 界 条 件 // 将 d p[0][j] 置 为 0 , 边 界 条 件 // 两 重 f or 循 环 处 理 arr1 、 arr2 的 所 有 字 符 { if (arr1[i-1]==arr2[j-1]) // 比 较 的 字 符 相 同 dp[i][j]=dp[i-1][j-1]+1; else // 比 较 的 字 符 不 同 dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } void Buildsubs() { int k=dp[m][n]; int i=m; int j=n; while (k>0) // 由 d p 构 造 从 s ubs //k 为 a rr1 和 a rr2 的 最 长 公 共 子 序 列 长 度 // 在 s ubs 中 放 入 最 长 公 共 子 序 列 ( 反 向 ) if (dp[i][j]==dp[i-1][j]) i--; else if (dp[i][j]==dp[i][j-1]) j--; else { subs.push_back(arr1[i-1]); //subs 中 添 加 a rr1[i-1] i--; j--; k--; } } void main() { cin >> arr1 >> arr2; m=arr1.length(); n=arr2.length(); LCSlength(); Buildsubs(); cout << " 求 解 结 果 " << endl; cout << " arr: "; vector<char>::reverse_iterator rit; // 输 入 a rr1 和 a rr2 //m 为 a rr1 的 长 度 //n 为 a rr2 的 长 度 // 求 出 d p // 求 出 L CS 66 ----------------------------------------------------- Page 67 -----------------------------------------------------第 1 章 for (rit=subs.rbegin();rit!=subs.rend();++rit) cout << *rit; cout << endl; cout << " 长 度 : " << dp[m][n] << endl; 概 论 } 改 为 如 下 ： 13. 解 ： 本 题 目 的 思 路 是 先 求 arr1 和 arr2 字 符 串 的 最 长 公 共 子 序 列 ， 基 本 过 程 参 见 《 教 程 》 第 8 章 8.5 节 ， 再 利 用 递 归 输 出 新 水 果 取 名 。 算 法 中 设 置 二 维 动 态 规 划 数 组 dp ， dp[i][j] 表 示 arr1[0..i-1] （ i 个 字 母 ） 和 arr2[0..j-1] （ j 个 字 母 ） 中 最 长 公 共 子 序 列 的 长 度 。 另 外 设 置 二 维 数 组 b ， b[i][j] 表 示 arr1 和 arr2 比 较 的 3 种 情 况 ： b[i][j]=0 表 示 arr1[i-1]=arr2[j-1] ， b[i][j]=1 表 示 arr1[i-1] ≠ arr2[j-1] 并 且 dp[i- 1][j]>dp[i][j-1] ， b[i][j]=2 表 示 arr1[i-1] ≠ arr2[j-1] 并 且 dp[i-1][j] ≤ dp[i][j-1] 。 对 应 的 完 整 程 序 如 下 ： #include <stdio.h> #include <string.h> #define MAX 51 // 问 题 表 示 int m,n; char arr1[MAX],arr2[MAX]; // 求 解 结 果 表 示 int dp[MAX][MAX]; int b[MAX][MAX]; void Output(int i,int j) { if (i==0 && j==0) return; if(i==0) { Output(i,j-1); printf("%c",arr2[j-1]); return; } else if(j==0) { Output(i-1,j); printf("%c",arr1[i-1]); return; } if (b[i][j]==0) { Output(i-1,j-1); printf("%c",arr1[i-1]); return; } else if(b[i][j]==1) { Output(i-1,j); printf("%c",arr1[i-1]); return; } else { Output(i,j-1); // 序 列 中 最 多 的 字 符 个 数 // 动 态 规 划 数 组 // 存 放 a rr1 与 a rr2 比 较 的 3 种 情 况 // 利 用 递 归 输 出 新 水 果 取 名 // 输 出 完 毕 //arr1 完 毕 ， 输 出 arr2 的 剩 余 部 分 //arr2 完 毕 ， 输 出 a rr1 的 剩 余 部 分 //arr1[i-1]=arr2[j-1] 的 情 况 67 ----------------------------------------------------- Page 68 -----------------------------------------------------算 法 设 计 printf("%c",arr2[j-1]); return; } } void LCSlength() { int i,j; for (i=0;i<=m;i++) dp[i][0]=0; for (j=0;j<=n;j++) dp[0][j]=0; for (i=1;i<=m;i++) for (j=1;j<=n;j++) { if (arr1[i-1]==arr2[j-1]) { dp[i][j]=dp[i-1][j-1]+1; b[i][j]=0; } else if (dp[i-1][j]>dp[i][j-1]) { dp[i][j]=dp[i-1][j]; b[i][j]=1; } else { dp[i][j]=dp[i][j-1]; b[i][j]=2; } } } void main() { int t; printf(" 测 试 用 例 个 数 : "); scanf("%d",&t); while(t--) { scanf("%s",arr1); scanf("%s",arr2); memset(b,-1,sizeof(b)); m=strlen(arr1); n=strlen(arr2); LCSlength(); printf(" 结 果 : "); Output(m,n); printf("\n"); } } 上 述 程 序 的 一 次 执 行 结 果 如 图 1.46 所 示 。 // 求 d p // 将 d p[i][0] 置 为 0 , 边 界 条 件 // 将 d p[0][j] 置 为 0 , 边 界 条 件 // 两 重 f or 循 环 处 理 a rr1 、 arr2 的 所 有 字 符 // 比 较 的 字 符 相 同 ： 情 况 0 // 情 况 1 //dp[i-1][j]<=dp[i][j-1]: 情 况 2 // 输 入 测 试 用 例 个 数 //m 为 a rr1 的 长 度 //n 为 a rr2 的 长 度 // 求 出 d p // 输 出 新 水 果 取 名 68 ----------------------------------------------------- Page 69 -----------------------------------------------------第 1 章 概 论 图 1.46 程 序 的 一 次 执 行 结 果 13. 解 ： 本 题 目 的 思 路 是 求 arr1 和 arr2 字 符 串 的 最 长 公 共 子 序 列 ， 基 本 过 程 参 见 《 教 程 》 第 8 章 8.5 节 。 对 应 的 完 整 程 序 如 下 ： 然 后 再 用 递 归 思 想 ， 逐 一 输 出 ， 得 到 的 就 是 最 后 答 案 。 #include <iostream> #include <string.h> #include <vector> #include <string> using namespace std; #define max(x,y) ((x)>(y)?(x):(y)) #define MAX 51 // 问 题 表 示 int m,n; string arr1,arr2; // 求 解 结 果 表 示 int dp[MAX][MAX]; vector<char> subs; void LCSlength() { int i,j; for (i=0;i<=m;i++) dp[i][0]=0; for (j=0;j<=n;j++) dp[0][j]=0; for (i=1;i<=m;i++) for (j=1;j<=n;j++) // 序 列 中 最 多 的 字 符 个 数 // 动 态 规 划 数 组 // 存 放 L CS // 求 d p // 将 d p[i][0] 置 为 0 , 边 界 条 件 // 将 d p[0][j] 置 为 0 , 边 界 条 件 // 两 重 f or 循 环 处 理 a rr1 、 arr2 的 所 有 字 符 { if (arr1[i-1]==arr2[j-1]) // 比 较 的 字 符 相 同 dp[i][j]=dp[i-1][j-1]+1; else // 比 较 的 字 符 不 同 dp[i][j]=max(dp[i][j-1],dp[i-1][j]); } } void Buildsubs() { int k=dp[m][n]; int i=m; int j=n; while (k>0) // 由 d p 构 造 从 s ubs //k 为 a rr1 和 a rr2 的 最 长 公 共 子 序 列 长 度 // 在 s ubs 中 放 入 最 长 公 共 子 序 列 ( 反 向 ) if (dp[i][j]==dp[i-1][j]) i--; else if (dp[i][j]==dp[i][j-1]) j--; 69 ----------------------------------------------------- Page 70 -----------------------------------------------------算 法 设 计 else { subs.push_back(arr1[i-1]); //subs 中 添 加 a rr1[i-1] i--; j--; k--; } } void main() { cin >> arr1 >> arr2; m=arr1.length(); n=arr2.length(); LCSlength(); Buildsubs(); // 输 入 a rr1 和 arr2 //m 为 a rr1 的 长 度 //n 为 a rr2 的 长 度 // 求 出 d p // 求 出 L CS cout << " 求 解 结 果 " << endl; cout << " arr: "; vector<char>::reverse_iterator rit; for (rit=subs.rbegin();rit!=subs.rend();++rit) cout << *rit; cout << endl; cout << " 长 度 : " << dp[m][n] << endl; } 上 述 程 序 的 一 次 执 行 结 果 如 图 1.46 所 示 。 图 1.46 程 序 的 一 次 执 行 结 果 1.9 第 9 章 ─ 图 算 法 设 计 1.9.1 练 习 题 1. 以 下 不 属 于 贪 心 算 法 的 是 （ ） 。 A.Prim 算 法 B.Kruskal 算 法 C.Dijkstra 算 法 D. 深 度 优 先 遍 历 2. 一 个 有 n 个 顶 点 的 连 通 图 的 生 成 树 是 原 图 的 最 小 连 通 子 图 ， 且 包 含 原 图 中 所 有 n 个 顶 点 ， 并 且 有 保 持 图 联 通 的 最 少 的 边 。 最 大 生 成 树 就 是 权 和 最 大 生 成 树 ， 现 在 给 出 一 个 无 向 带 权 图 的 邻 接 矩 阵 为 { {0 ， 4 ， 5 ， 0 ， 3} ， {4 ， 0 ， 4 ， 2 ， 3} ， {5 ， 4 ， 0 ， 2 ， 0} ， {0 ， 2 ， 2 ， 0 ， 1} ， {3 ， 3 ， 0 ， 1 ， 0}} ， 其 中 权 为 0 表 示 没 有 边 。 一 个 图 为 求 这 个 图 的 最 大 生 成 树 的 权 和 是 （ ） 。 A.11 B.12 C.13 D.14 E.15 3. 某 个 带 权 连 通 图 有 4 个 以 上 的 顶 点 ， 其 中 恰 好 有 2 条 权 值 最 小 的 边 ， 尽 管 该 图 的 最 小 生 成 树 可 能 有 多 个 ， 而 这 2 条 权 值 最 小 的 边 一 定 包 含 在 所 有 的 最 小 生 成 树 中 吗 ？ 如 果 有 3 条 权 值 最 小 的 边 呢 ？ 70 ----------------------------------------------------- Page 71 -----------------------------------------------------第 1 章 概 论 4. 为 什 么 TSP 问 题 采 用 贪 心 算 法 求 解 不 一 定 得 到 最 优 解 ？ 5. 求 最 短 路 径 的 4 种 算 法 适 合 带 权 无 向 图 吗 ？ 6. 求 单 源 最 短 路 径 的 算 法 有 Dijkstra 算 法 、 Bellman - Ford 算 法 和 SPFA 算 法 ， 比 较 这 些 算 法 的 不 同 点 。 7. 有 人 这 样 修 改 Dijkstra 算 法 以 便 求 一 个 带 权 连 通 图 的 单 源 最 长 路 径 ， 将 每 次 选 择 dist 最 小 的 顶 点 u 改 为 选 择 最 大 的 顶 点 u ， 将 按 路 径 长 度 小 进 行 调 整 改 为 按 路 径 长 度 大 调 整 。 这 样 可 以 求 单 源 最 长 路 径 吗 ？ 8. 给 出 一 种 方 法 求 无 环 带 权 连 通 图 （ 所 有 权 值 非 负 ） 中 从 顶 点 s 到 顶 点 t 的 一 条 最 长 简 单 路 径 。 9. 一 个 运 输 网 络 如 图 1.47 所 示 ， 边 上 数 字 为 （ c ( i ， j ) ， b ( i ， j ) ） ， 其 中 c ( i ， j ) 表 示 容 量 ， b ( i ， j ) 表 示 单 位 运 输 费 用 。 给 出 从 1 、 2 、 3 位 置 运 输 货 物 到 位 置 6 的 最 小 费 用 最 大 流 的 过 程 。 10. 本 教 程 中 的 Dijkstra 算 法 采 用 邻 接 矩 阵 存 储 图 ， 算 法 时 间 复 杂 度 为 O( n ) 。 请 你 从 各 个 方 面 考 虑 优 化 该 算 法 ， 用 于 求 源 点 v 到 其 他 顶 点 的 最 短 路 径 长 度 。 11. 有 一 个 带 权 有 向 图 G （ 所 有 权 为 正 整 数 ） ， 采 用 邻 接 矩 阵 存 储 。 设 计 一 个 算 法 求 其 中 的 一 个 最 小 环 。 1 (4,2) (6,4) 4 (12,3) 2 (3,5) 6 (3,4) (1,6) 5 (9,12) 3 (2,3) 图 1.47 一 个 运 输 网 络 1.9.2 练 习 题 参 考 答 案 1. 答 ： D 。 2. 答 ： 采 用 类 似 Kurskal 算 法 来 求 最 大 生 成 树 ， 第 1 步 取 最 大 边 （ 0 ， 2 ） ， 第 2 步 取 边 （ 0 ， 1 ） ， 第 3 步 取 边 （ 0 ， 4 ） ， 第 4 步 取 最 大 边 （ 1 ， 3 ） ， 得 到 的 权 和 为 14 。 答 案 为 D 。 3. 答 ： 这 2 条 权 值 最 小 的 边 一 定 包 含 在 所 有 的 最 小 生 成 树 中 ， 因 为 按 Kurskal 算 法 一 定 首 先 选 中 这 2 条 权 值 最 小 的 边 。 如 果 有 3 条 权 值 最 小 的 边 ， 就 不 一 定 了 ， 因 为 首 先 选 中 这 3 条 权 值 最 小 的 边 有 可 能 出 现 回 路 。 4. 答 ： TSP 问 题 不 满 足 最 优 子 结 构 性 质 ， 如 （ 0 ， 1 ， 2 ， 3 ， 0 ） 是 整 个 问 题 的 最 优 解 ， 但 （ 0 ， 1 ， 2 ， 0 ） 不 一 定 是 子 问 题 的 最 优 解 。 5. 答 ： 都 适 合 带 权 无 向 图 求 最 短 路 径 。 6. 答 ： Dijkstra 算 法 不 适 合 存 在 负 权 边 的 图 求 单 源 最 短 路 径 ， 其 时 间 复 杂 度 为 O( n ) 。 Bellman - Ford 算 法 和 SPFA 算 法 适 合 存 在 负 权 边 的 图 求 单 源 最 短 路 径 ， 但 图 中 不 能 71 2 2 ----------------------------------------------------- Page 72 -----------------------------------------------------算 法 设 计 存 在 权 值 和 为 负 的 环 。 Bellman - Ford 算 法 的 时 间 复 杂 度 为 O( ne ) ， 而 SPFA 算 法 的 时 间 复 杂 度 为 O( e ) ， 所 以 SPFA 算 法 更 优 。 7. 答 ： 不 能 。 Dijkstra 算 法 本 质 上 是 一 种 贪 心 算 法 ， 而 求 单 源 最 长 路 径 不 满 足 贪 心 选 择 性 质 。 8. 答 ： Bellman - Ford 算 法 和 SPFA 算 法 适 合 存 在 负 权 边 的 图 求 单 源 最 短 路 径 。 可 以 将 图 中 所 有 边 权 值 改 为 负 权 值 ， 求 出 从 顶 点 s 到 顶 点 t 的 一 条 最 短 简 单 路 径 ， 它 就 是 原 来 图 中 从 顶 点 s 到 顶 点 t 的 一 条 最 长 简 单 路 径 。 9. 答 ： 为 该 运 输 网 络 添 加 一 个 虚 拟 起 点 0 ， 它 到 1 、 2 、 3 位 置 运 输 费 用 为 0 ， 容 量 分 别 为 到 1 、 2 、 3 位 置 运 输 容 量 和 ， 如 图 1.48 所 示 ， 起 点 s =0 ， 终 点 t =6 。 1 (4,2) (10,0) (6,4) 4 (12,3) 0 (6,0) 2 (3,5) 6 (3,0) (3,4) (1,6) 5 (9,12) 3 (2,3) 图 1.48 添 加 一 个 虚 拟 起 点 的 运 输 网 络 首 先 初 始 化 f 为 零 流 ， 最 大 流 量 maxf=0 ， 最 小 费 用 mincost=0 ， 采 用 最 小 费 用 最 大 流 算 法 求 解 过 程 如 下 ： （ 1 ） k =0 ， 求 出 w 如 下 ： 求 出 从 起 点 0 到 终 点 6 的 最 短 路 径 为 0→1 →4 →6 ， 求 出 最 小 调 整 量  =4 ， f [4][6] 调 整 为 4 ， f [1][4] 调 整 为 4 ， f [0][1] 调 整 为 4 ， mincost=20 ， maxf=4 。 （ 2 ） k =1 ， 求 出 w 如 下 ： 求 出 从 起 点 0 到 终 点 6 的 最 短 路 径 为 0 →2 →4 →6 ， 求 出 最 小 调 整 量  =3 ， f [4][6] 调 整 72 ----------------------------------------------------- Page 73 -----------------------------------------------------第 1 章 概 论 为 7 ， f [2][4] 调 整 为 3 ， f [0][2] 调 整 为 3 ， mincost=44 ， maxf=4+3=7 。 （ 3 ） k =2 ， 求 出 w 如 下 ： 求 出 从 起 点 0 到 终 点 6 的 最 短 路 径 为 0 →3 →4 →6 ， 求 出 最 小 调 整 量  =1 ， f [4][6] 调 整 为 8 ， f [3][4] 调 整 为 1 ， f [0][3] 调 整 为 1 ， mincost=53 ， maxf=7+1=8 。 （ 4 ） k =3 ， 求 出 w 如 下 ： 求 出 从 起 点 0 到 终 点 6 的 最 短 路 径 为 0 →3 →5 →6 ， 求 出 最 小 调 整 量  =2 ， f [5][6] 调 整 为 2 ， f [3][5] 调 整 为 2 ， f [0][3] 调 整 为 3 ， mincost=83 ， maxf=8+2=10 。 （ 5 ） k =4 ， 求 出 w 如 下 ： 求 出 从 起 点 0 到 终 点 6 的 最 短 路 径 为 0 →1→5 →6 ， 求 出 最 小 调 整 量  =6 ， f [5][6] 调 整 为 8 ， f [1][5] 调 整 为 6 ， f [0][1] 调 整 为 10 ， mincost=179 ， maxf=10+6=16 。 （ 6 ） k =5 ， 求 出 w 如 下 ： 求 出 从 起 点 0 到 终 点 6 的 最 短 路 径 为 0 →1 →5→6 ， 求 出 最 小 调 整 量  =1 ， f [5][6] 调 整 73 ----------------------------------------------------- Page 74 -----------------------------------------------------算 法 设 计 为 9 ， f [2][5] 调 整 为 1 ， f [0][2] 调 整 为 4 ， mincost=195 ， maxf=16+1=17 。 （ 7 ） k =6 ， 求 出 的 w 中 没 有 增 广 路 径 ， 调 整 结 束 。 对 应 的 最 大 流 如 下 ： 最 终 结 果 ， maxf=17 ， mincost=195 。 即 运 输 的 最 大 货 物 量 为 17 ， 对 应 的 最 小 总 运 输 费 用 为 195 。 10. 解 ： 从 两 个 方 面 考 虑 优 化 ： （ 1 ） 在 Dijkstra 算 法 中 ， 当 求 出 源 点 v 到 顶 点 u 的 最 短 路 径 长 度 后 ， 仅 仅 调 整 从 顶 点 u 出 发 的 邻 接 点 的 最 短 路 径 长 度 ， 而 教 程 中 的 Dijkstra 算 法 由 于 采 用 邻 接 矩 阵 存 储 图 ， 需 要 花 费 O( n ) 的 时 间 来 调 整 顶 点 u 出 发 的 邻 接 点 的 最 短 路 径 长 度 ， 如 果 采 用 邻 接 表 存 储 图 ， 可 以 很 快 查 找 到 顶 点 u 的 所 有 邻 接 点 并 进 行 调 整 ， 时 间 为 O(MAX( 图 中 顶 点 的 出 度 ) ) 。 （ 2 ） 求 目 前 一 个 最 短 路 径 长 度 的 顶 点 u 时 ， 教 科 书 上 的 Dijkstra 算 法 采 用 简 单 比 较 方 法 ， 可 以 改 为 采 用 优 先 队 列 （ 小 根 堆 ） 求 解 。 由 于 最 多 e 条 边 对 应 的 顶 点 进 队 ， 对 应 的 时 间 为 O(log 2 e ) 。 对 应 的 完 整 程 序 和 测 试 数 据 算 法 如 下 ： #include "Graph.cpp" #include <queue> #include <string.h> using namespace std; ALGraph *G; struct Node { int i; int v; // 包 含 图 的 基 本 运 算 算 法 // 图 的 邻 接 表 存 储 结 构 ， 作 为 全 局 变 量 // 声 明 堆 中 结 点 类 型 // 顶 点 编 号 //dist[i] 值 friend bool operator<(const Node &a ， const Node &b) // 定 义 比 较 运 算 符 { return a.v > b.v; } }; void Dijkstra(int v ， int dist[]) // 改 进 的 D ijkstra 算 法 { ArcNode *p; priority_queue<Node> qu; Node e; int S[MAXV]; // 创 建 小 根 堆 //S[i]=1 表 示 顶 点 i 在 S 中 ， S[i]=0 表 示 顶 点 i 在 U 中 int i ， j ， u ， w; memset(S ， 0 ， sizeof(S)); p=G->adjlist[v].firstarc; for (i=0;i<G->n;i++) dist[i]=INF; while (p!=NULL) { w=p->adjvex; 74 ----------------------------------------------------- Page 75 -----------------------------------------------------第 1 章 概 论 dist[w]=p->weight; e.i=w; e.v=dist[w]; qu.push(e); p=p->nextarc; } S[v]=1; for (i=0;i<G->n-1;i++) // 距 离 初 始 化 // 将 v 的 出 边 顶 点 进 队 q u // 源 点 编 号 v 放 入 S 中 // 循 环 直 到 所 有 顶 点 的 最 短 路 径 都 求 出 { e=qu.top(); qu.pop(); // 出 队 e u=e.i; S[u]=1; p=G->adjlist[u].firstarc; while (p!=NULL) { w=p->adjvex; if (S[w]==0) // 选 取 具 有 最 小 最 短 路 径 长 度 的 顶 点 u // 顶 点 u 加 入 S 中 // 考 察 从 顶 点 u 出 发 的 所 有 相 邻 点 // 考 虑 修 改 不 在 S 中 的 顶 点 w 的 最 短 路 径 长 度 if (dist[u]+p->weight<dist[w]) { dist[w]=dist[u]+p->weight; // 修 改 最 短 路 径 长 度 e.i=w; e.v=dist[w]; qu.push(e); // 修 改 最 短 路 径 长 度 的 顶 点 进 队 } p=p->nextarc; } } } void Disppathlength(int v ， int dist[]) // 输 出 最 短 路 径 长 度 { printf(" 从 % d 顶 点 出 发 的 最 短 路 径 长 度 如 下 : \n" ， v); for (int i=0;i<G->n;++i) if (i!=v) printf(" 到 顶 点 % d: %d\n" ， i ， dist[i]); } void main() { int A[MAXV][MAXV]={ {0 ， 4 ， 6 ， 6 ， INF ， INF ， INF} ， {INF ， 0 ， 1 ， INF ， 7 ， INF ， INF} ， {INF ， INF ， 0 ， INF ， 6 ， 4 ， INF} ， {INF ， INF ， 2 ， 0 ， INF ， 5 ， INF} ， {INF ， INF ， INF ， INF ， 0 ， INF ， 6} ， {INF ， INF ， INF ， INF ， 1 ， 0 ， 8} ， {INF ， INF ， INF ， INF ， INF ， INF ， 0}}; int n=7 ， e=12; CreateAdj(G ， A ， n ， e); printf(" 图 G 的 邻 接 表 : \n"); DispAdj(G); int v=0; int dist[MAXV]; Dijkstra(v ， dist); Disppathlength(v ， dist); DestroyAdj(G); // 建 立 图 的 邻 接 表 // 输 出 邻 接 表 // 调 用 Dijkstra 算 法 // 输 出 结 果 // 销 毁 图 的 邻 接 表 } 上 述 程 序 的 执 行 结 果 如 图 1.49 所 示 。 75 ----------------------------------------------------- Page 76 -----------------------------------------------------算 法 设 计 图 1.49 程 序 执 行 结 果 其 中 Dijkstra 算 法 的 时 间 复 杂 度 为 O( n (log 2 e +MAX( 顶 点 的 出 度 ) ) ， 一 般 图 中 最 大 顶 点 出 度 远 小 于 e ， 所 以 进 一 步 简 化 时 间 复 杂 度 为 O( n log 2 e ) 。 11. 有 一 个 带 权 有 向 图 G （ 所 有 权 为 正 整 数 ） ， 采 用 邻 接 矩 阵 存 储 。 设 计 一 个 算 法 求 其 中 的 一 个 最 小 环 。 解 ： 利 用 Floyd 算 法 求 出 所 有 顶 点 对 之 间 的 最 短 路 径 ， 若 顶 点 i 到 j 有 最 短 路 径 ， 而 图 中 又 存 在 顶 点 j 到 i 的 边 ， 则 构 成 一 个 环 ， 在 所 有 环 中 比 较 找 到 一 个 最 小 环 并 输 出 。 对 应 的 程 序 如 下 ： #include "Graph.cpp" // 包 含 图 的 基 本 运 算 算 法 #include <vector> using namespace std; void Dispapath(int path[][MAXV],int i,int j) // 输 出 顶 点 i 到 j 的 一 条 最 短 路 径 { vector<int> apath; int k=path[i][j]; apath.push_back(j); while (k!=-1 && k!=i) { apath.push_back(k); k=path[i][k]; } apath.push_back(i); // 存 放 一 条 最 短 路 径 中 间 顶 点 ( 反 向 ) // 路 径 上 添 加 终 点 // 路 径 上 添 加 中 间 点 // 路 径 上 添 加 起 点 for (int s=apath.size()-1;s>=0;s--) // 输 出 路 径 上 的 中 间 顶 点 printf("%d → ",apath[s]); } int Mincycle(MGraph g,int A[MAXV][MAXV],int &mini,int &minj) // 在 图 g 和 A 中 的 查 找 一 个 最 小 环 { int i,j,min=INF; for (i=0;i<g.n;i++) for (j=0;j<g.n;j++) if (i!=j && g.edges[j][i]<INF) { if (A[i][j]+g.edges[j][i]<min) { min=A[i][j]+g.edges[j][i]; mini=i; minj=j; 76 ----------------------------------------------------- Page 77 -----------------------------------------------------第 1 章 概 论 } } return min; } void Floyd(MGraph g) { int A[MAXV][MAXV],path[MAXV][MAXV]; int i,j,k,min,mini,minj; for (i=0;i<g.n;i++) for (j=0;j<g.n;j++) { A[i][j]=g.edges[i][j]; //Floyd 算 法 求 图 g 中 的 一 个 最 小 环 if (i!=j && g.edges[i][j]<INF) path[i][j]=i; else path[i][j]=-1; } for (k=0;k<g.n;k++) { for (i=0;i<g.n;i++) for (j=0;j<g.n;j++) // 顶 点 i 到 j 有 边 时 // 顶 点 i 到 j 没 有 边 时 // 依 次 考 察 所 有 顶 点 if (A[i][j]>A[i][k]+A[k][j]) { A[i][j]=A[i][k]+A[k][j]; // 修 改 最 短 路 径 长 度 path[i][j]=path[k][j]; // 修 改 最 短 路 径 } } min=Mincycle(g,A,mini,minj); if (min!=INF) { printf(" 图 中 最 小 环 ： "); Dispapath(path,mini,minj); printf("%d, 长 度 ： %d\n",mini,min); } else printf(" 图 中 没 有 任 何 环 \ n"); } void main() { MGraph g; // 输 出 一 条 最 短 路 径 int A[MAXV][MAXV]={ {0,5,INF,INF},{INF,0,1,INF}, {3,INF,0,2}, {INF,4,INF,0}}; int n=4, e=5; CreateMat(g,A,n,e); printf(" 图 G 的 邻 接 矩 阵 : \n"); DispMat(g); Floyd(g); // 建 立 图 的 邻 接 矩 阵 // 输 出 邻 接 矩 阵 } 上 述 程 序 的 执 行 结 果 如 图 1.50 所 示 。 77 ----------------------------------------------------- Page 78 -----------------------------------------------------算 法 设 计 图 1.50 程 序 执 行 结 果 1.10 第 10 章 ─ 计 算 几 何 1.10.1 练 习 题 1. 对 如 图 1.51 所 示 的 点 集 A ， 给 出 采 用 Graham 扫 描 算 法 求 凸 包 的 过 程 及 结 果 。 10 9 8 7 6 5 4 3 2 1 a 8 a 11 a 9 a 0 a 6 a 7 a 5 a 3 a 10 a 4 a 1 a 2 1 2 3 4 5 6 7 8 9 10 图 1.51 一 个 点 集 A 2. 对 如 图 1.51 所 示 的 点 集 A ， 给 出 采 用 分 治 法 求 最 近 点 对 的 过 程 及 结 果 。 3. 对 如 图 1.51 所 示 的 点 集 A ， 给 出 采 用 旋 转 卡 壳 法 求 最 远 点 对 的 结 果 。 4. 对 应 3 个 点 向 量 p 1 、 p 2 、 p 3 ， 采 用 S (p 1 ， p 2 ， p 3 )=(p 2 - p 1 )  (p 3 - p 1 )/2 求 它 们 构 成 的 三 角 形 面 积 ， 请 问 什 么 情 况 下 计 算 结 果 为 正 ？ 什 么 情 况 下 计 算 结 果 为 负 ？ 5. 已 知 坐 标 为 整 数 ， 给 出 判 断 平 面 上 一 点 p 是 否 在 一 个 逆 时 针 三 角 形 p 1 -p 2 -p 3 的 算 法 。 1.10.2 练 习 题 参 考 答 案 内 部 1. 答 ： 采 用 Graham 扫 描 算 法 求 凸 包 的 过 程 及 结 果 如 下 ： 求 出 起 点 a 0 (1 ， 1) 。 排 序 后 ： a 0 (1 ， 1) a 1 (8 ， 1) a 2 (9 ， 4) a 3 (5 ， 4) a 4 (8 ， 7) a 5 (5 ， 6) a 10 (7 ， 10) a 9 (3 ， 5) a 6 (3 ， 7) a 7 (4 ， 10) a 8 (1 ， 6) a 11 (0 ， 3) 。 先 将 a 0 (1 ， 1) 进 栈 ， a 1 (8 ， 1) 进 栈 ， a 2 (9 ， 4) 进 栈 。 处 理 点 a 3 (5 ， 4) ： a 3 (5 ， 4) 进 栈 。 处 理 点 a 4 (8 ， 7) ： a 3 (5 ， 4) 存 在 右 拐 关 系 ， 退 栈 ， a 4 (8 ， 7) 进 栈 。 78 ----------------------------------------------------- Page 79 -----------------------------------------------------第 1 章 概 论 处 理 点 a 5 (5 ， 6) ： a 5 (5 ， 6) 进 栈 。 处 理 点 a 10 (7 ， 10) ： a 5 (5 ， 6) 存 在 右 拐 关 系 ， 退 栈 ， a 10 (7 ， 10) 进 栈 。 处 理 点 a 9 (3 ， 5) ： a 9 (3 ， 5) 进 栈 。 处 理 点 a 6 (3 ， 7) ： a 9 (3 ， 5) 存 在 右 拐 关 系 ， 退 栈 ， a 6 (3 ， 7) 进 栈 。 处 理 点 a 7 (4 ， 10) ： a 6 (3 ， 7) 存 在 右 拐 关 系 ， 退 栈 ， a 7 (4 ， 10) 进 栈 。 处 理 点 a 8 (1 ， 6) ： a 8 (1 ， 6) 进 栈 。 处 理 点 a 11 (0 ， 3) ： a 11 (0 ， 3) 进 栈 。 结 果 ： n =8 ， 凸 包 的 顶 点 ： a 0 (1 ， 1) a 1 (8 ， 1) a 2 (9 ， 4) a 4 (8 ， 7) a 10 (7 ， 10) a 7 (4 ， 10) a 8 (1 ， 6) a 11 (0 ， 3) 。 2. 答 ： 求 解 过 程 如 下 ： 排 序 前 ： (1 ， 1) (8 ， 1) (9 ， 4) (5 ， 4) (8 ， 7) (5 ， 6) (3 ， 7) (4 ， 10) (1 ， 6) (3 ， 5) (7 ， 10) (0 ， 3) 。 按 x 坐 标 排 序 后 ： (0 ， 3) (1 ， 1) (1 ， 6) (3 ， 7) (3 ， 5) (4 ， 10) (5 ， 4) (5 ， 6) (7 ， 10) (8 ， 1) (8 ， 7) (9 ， 4) 。 按 y 坐 标 排 序 后 ： (1 ， 1) (8 ， 1) (0 ， 3) (5 ， 4) (9 ， 4) (3 ， 5) (1 ， 6) (5 ， 6) (3 ， 7) (8 ， 7) (4 ， 10) (7 ， 10) 。 （ 1 ） 中 间 位 置 midindex=5 ， 左 部 分 ： (0 ， 3) (1 ， 1) (1 ， 6) (3 ， 7) (3 ， 5) (4 ， 10) ； 右 部 分 ： (5 ， 4) (5 ， 6) (7 ， 10) (8 ， 1) (8 ， 7) (9 ， 4) ； 中 间 部 分 点 集 为 (0 ， 3) (3 ， 7) (4 ， 10) (5 ， 4) (5 ， 6) (7 ， 10) (8 ， 7) 。 （ 2 ） 求 解 左 部 分 ： (0 ， 3) (1 ， 1) (1 ， 6) (3 ， 7) (3 ， 5) (4 ， 10) 。 中 间 位 置 = 2 ， 划 分 为 左 部 分 1 ： (0 ， 3) (1 ， 1) (1 ， 6) ， 右 部 分 1 ： (3 ， 7) (3 ， 5) (4 ， 10) 处 理 左 部 分 1 ： 点 数 少 于 4 ： 求 出 最 近 距 离 = 2.23607 ， 即 ( 0 ， 3) 和 ( 1 ， 1) 之 间 的 距 离 。 处 理 右 部 分 1 ： 点 数 少 于 4 ： 求 出 最 近 距 离 =2 ， 即 ( 3 ， 7) 和 ( 3 ， 5) 之 间 的 距 离 。 再 考 虑 中 间 部 分 （ 中 间 部 分 最 近 距 离 = 2.23 ） 求 出 左 部 分 d1=2 。 （ 3 ） 求 解 右 部 分 ： (5 ， 4) (5 ， 6) (7 ， 10) (8 ， 1) (8 ， 7) (9 ， 4) 。 中 间 位 置 = 8 ， 划 分 为 左 部 分 2 ： (5 ， 4) (5 ， 6) (7 ， 10) ， 右 部 分 2 ： (8 ， 1) (8 ， 7) (9 ， 4) 。 处 理 左 部 分 2 ： 点 数 少 于 4 ， 求 出 最 近 距 离 = 2 ， 即 (5 ， 4) 和 ( 5 ， 6) 之 间 的 距 离 。 处 理 右 部 分 2 ： 点 数 少 于 4 ， 求 出 最 近 距 离 = 3.16228 ， 即 ( 8 ， 1) 和 ( 9 ， 4) 之 间 的 距 离 。 再 考 虑 中 间 部 分 （ 中 间 部 分 为 空 ） 求 出 右 部 分 d2=2 。 （ 4 ） 求 解 中 间 部 分 点 集 ： (0 ， 3) (3 ， 7) (4 ， 10) (5 ， 4) (5 ， 6) (7 ， 10) (8 ， 7) 。 求 出 最 近 距 离 d3=5 。 最 终 结 果 为 ： d=MIN{d1 ， d2 ， d3)=2 。 3. 答 ： 采 用 旋 转 卡 壳 法 求 出 两 个 最 远 点 对 是 （ 1 ， 1 ） 和 （ 7 ， 10 ） ， 最 远 距 离 为 10.82 。 4. 答 ： 当 三 角 形 p 1 - p 2 - p 3 逆 时 针 方 向 时 ， 如 图 1.52 所 示 ， p 2 - p 1 在 p 3 - p 1 的 顺 时 针 方 向 上 ， (p 2 - p 1 )  (p 3 - p 1 )>0 ， 对 应 的 面 积 ( p 2 - p 1 )  (p 3 - p 1 )/2 为 正 。 当 三 角 形 p 1 - p 2 - p 3 顺 时 针 方 向 时 ， 如 图 1.53 所 示 ， p 2 - p 1 在 p 3 - p 1 的 逆 时 针 方 向 上 ， (p 2 - p 1 )  (p 3 - p 1 )<0 ， 对 应 的 面 积 ( p 2 - p 1 )  (p 3 - p 1 )/2 为 负 。 79 ----------------------------------------------------- Page 80 -----------------------------------------------------算 法 设 计 p 1 p 3 - p 1 p 2 - p 1 p 1 p 2 - p 1 p 3 - p 1 图 1.52 p 1 - p 2 - p 3 逆 时 针 方 向 图 图 1.53 p 1 - p 2 - p 3 逆 时 针 方 向 5. 答 ： 用 S (p 1 ， p 2 ， p 3 )=(p 2 - p 1 )  (p 3 - p 1 )/2 求 三 角 形 p 1 、 p 2 、 p 3 带 符 号 的 的 面 积 。 如 图 1.54 所 示 ， 若 S (p ， p 2 ， p 3 ) 和 S (p ， p 3 ， p 1 ) 和 S (p ， p 1 ， p 2 ) （ 3 个 三 角 形 的 方 向 均 为 逆 时 针 方 向 ） 均 大 于 0 ， 表 示 p 在 该 三 角 形 内 部 。 p 3 p 1 p p 2 图 1.54 一 个 点 p 和 一 个 三 角 形 对 应 的 程 序 如 下 ： #include "Fundament.cpp" // 包 含 向 量 基 本 运 算 算 法 double getArea(Point p1,Point p2,Point p3) // 求 带 符 号 的 面 积 { return Det(p2-p1,p3-p1); } bool Intrig(Point p,Point p1,Point p2,Point p3) // 判 断 p 是 否 在 三 角 形 p1p2p3 的 内 部 { double area1=getArea(p,p2,p3); double area2=getArea(p,p3,p1); double area3=getArea(p,p1,p2); if (area1>0 && area2>0 && area3>0) return true; else return false; } void main() { printf(" 求 解 结 果 \ n"); Point p1(0,0); Point p2(5,-4); Point p3(4,3); Point p4(3,1); Point p5(-1,1); printf(" p1:"); p1.disp(); printf("\n"); printf(" p2:"); p2.disp(); printf("\n"); printf(" p3:"); p3.disp(); printf("\n"); printf(" p4:"); p4.disp(); printf("\n"); 80 ----------------------------------------------------- Page 81 -----------------------------------------------------第 1 章 概 论 printf(" printf(" printf(" printf(" p5:"); p5.disp(); printf("\n"); p1p2p3 三 角 形 面 积 : %g\n",getArea(p1,p2,p3)); p4 在 p 1p2p3 三 角 形 内 部 : %s\n",Intrig(p4,p1,p2,p3)?" 是 " :" 不 是 " ); p5 在 p 1p2p3 三 角 形 内 部 : %s\n",Intrig(p5,p1,p2,p3)?" 是 " :" 不 是 " ); } 上 述 程 序 的 执 行 结 果 如 图 1.55 所 示 。 图 1.55 程 序 执 行 结 果 1.11 第 11 章 ─ 计 算 复 杂 性 理 论 1.11.1 练 习 题 1. 旅 行 商 问 题 是 NP 问 题 吗 ？ A. 否 B. 是 C. 至 今 尚 无 定 论 2. 下 面 有 关 P 问 题 ， NP 问 题 和 NPC 问 题 ， 说 法 错 误 的 是 （ ） 。 A. 如 果 一 个 问 题 可 以 找 到 一 个 能 在 多 项 式 的 时 间 里 解 决 它 的 算 法 ， 那 么 这 个 问 题 就 属 于 P 问 题 B.NP 问 题 是 指 可 以 在 多 项 式 的 时 间 里 验 证 一 个 解 的 问 题 C. 所 有 的 P 类 问 题 都 是 NP 问 题 D.NPC 问 题 不 一 定 是 个 NP 问 题 ， 只 要 保 证 所 有 的 NP 问 题 都 可 以 约 化 到 它 即 可 3. 对 于 《 教 程 》 例 11.2 设 计 的 图 灵 机 ， 分 别 给 出 执 行 f (3 ， 2) 和 f (2 ， 3) 的 瞬 像 演 变 过 程 。 4. 什 么 是 P 类 问 题 ？ 什 么 是 NP 类 问 题 ？ 5. 证 明 求 两 个 m 行 n 列 的 二 维 矩 阵 相 加 的 问 题 属 于 P 类 问 题 。 6. 证 明 求 含 有 n 个 元 素 的 数 据 序 列 中 求 最 大 元 素 的 问 题 属 于 P 类 问 题 。 7. 设 计 一 个 确 定 性 图 灵 机 M ， 用 于 计 算 后 继 函 数 S ( n )= n +1 （ n 为 一 个 二 进 制 数 ） ， 并 给 出 求 1010001 的 后 继 函 数 值 的 瞬 像 演 变 过 程 。 1.11.2 练 习 题 参 考 答 案 1. 答 ： B 。 2. 答 ： D 。 3. 答 ： （ 1 ） 执 行 f (3 ， 2) 时 ， 输 入 带 上 的 初 始 信 息 为 000100B ， 其 瞬 像 演 变 过 程 如 81 ----------------------------------------------------- Page 82 -----------------------------------------------------算 法 设 计 下 ： q 0 000100B  B0 q 3 0110B  BB01 q 2 10B  B q 1 00100B  B q 3 00110B  BB011 q 2 0B  B0 q 1 0100B  q 3 B00110B  BB01 q 3 11B  B00 q 1 100B  B001 q 2 00B  B00 q 3 110B  B q 0 00110B  BB q 1 0110B  BB0 q 1 110B  BB0 q 3 111B  BB q 3 0111B  BB q 0 0111B  BBB1 q 2 11B  BBB11 q 2 1B  BBB111 q 2 B  BBB11 q 4 1B  BBB1 q 4 1BB  BBB q 4 1BBB  BBB q 4 BBBB  BBB0 q 6 BBB 最 终 带 上 有 一 个 0 ， 计 算 结 果 为 1 。 （ 2 ） 执 行 f (2 ， 3) 时 ， 输 入 带 上 的 初 始 信 息 为 001000B ， 其 瞬 像 演 变 过 程 如 下 ： q 0 001000B  B q 0 01000B  B0 q 1 1000B  B01 q 2 000B  B0 q 3 1100B  B q 3 01100B  q 3 B01100B  BB q 3 1100B  B q 0 01100B  B q 3 B1100B  BB q 1 1100B  BB q 0 1100B  BB1 q 2 100B  BBB q 5 100B  BB11 q 2 00B  BBBB q 5 00B  BB1 q 3 100B  BBBBB q 5 0B  BBBBBB q 5 B  BBBBBBB q 6 最 终 带 上 有 零 个 0 ， 计 算 结 果 为 0 。 4. 答 ： 用 确 定 性 图 灵 机 以 多 项 式 时 间 界 可 解 的 问 题 称 为 P 类 问 题 。 用 非 确 定 性 图 灵 机 以 多 项 式 时 间 界 可 解 的 问 题 称 为 NP 类 问 题 。 5. 答 ： 求 两 个 m 行 n 列 的 二 维 矩 阵 相 加 的 问 题 对 应 的 算 法 时 间 复 杂 度 为 O( mn ) ， 所 以 属 于 P 类 问 题 。 6. 答 ： 求 含 有 n 个 元 素 的 数 据 序 列 中 最 大 元 素 的 问 题 的 算 法 时 间 复 杂 度 为 O( n ) ， 所 以 属 于 P 类 问 题 。 7. 解 ： q 0 为 初 始 状 态 ， q 3 为 终 止 状 态 ， 读 写 头 初 始 时 注 视 最 右 边 的 格 。 δ 动 作 函 数 如 下 ： δ ( q 0 ， 0) → ( q 1 ， 1 ， L ) δ ( q 0 ， 1) → ( q 2 ， 0 ， L ) δ ( q 0 ， B ) → ( q 3 ， B ， R ) δ ( q 1 ， 0) → ( q 1 ， 0 ， L ) δ ( q 1 ， 1) → ( q 1 ， 1 ， L ) δ ( q 1 ， B ) → ( q 3 ， B ， L ) δ ( q 2 ， 0) → ( q 1 ， 1 ， L ) δ ( q 2 ， 1) → ( q 2 ， 0 ， L ) δ ( q 2 ， B ) → ( q 3 ， B ， L ) 求 10100010 的 后 继 函 数 值 的 瞬 像 演 变 过 程 如 下 ： B 1010001 q 0 0 B  B 101000 q 1 11 B  B 10100 q 1 011 B  B 1010 q 1 0011 B  B 101 q 1 00011 B  B 10 q 1 100011 B  B 1 q 1 0100011 B  Bq 1 10100011 B  q 1 B10100011 B  q 3 BB 10100011 B 其 结 果 为 10100011 。 82 ----------------------------------------------------- Page 83 -----------------------------------------------------第 1 章 概 论 1.12 第 12 章 ─ 概 率 算 法 和 近 似 算 法 1.12.1 练 习 题 1. 蒙 特 卡 罗 算 法 是 （ ） 的 一 种 。 A. 分 枝 限 界 算 法 B. 贪 心 算 法 C. 概 率 算 法 D. 回 溯 算 法 2. 在 下 列 算 法 中 有 时 找 不 到 问 题 解 的 是 （ ） 。 A. 蒙 特 卡 罗 算 法 B. 拉 斯 维 加 斯 算 法 C. 舍 伍 德 算 法 D. 数 值 概 率 算 法 3. 在 下 列 算 法 中 得 到 的 解 未 必 正 确 的 是 （ ） 。 A. 蒙 特 卡 罗 算 法 B. 拉 斯 维 加 斯 算 法 C. 舍 伍 德 算 法 D. 数 值 概 率 算 法 4. 总 能 求 得 非 数 值 问 题 的 一 个 解 ， 且 所 求 得 的 解 总 是 正 确 的 是 （ ） 。 A. 蒙 特 卡 罗 算 法 B. 拉 斯 维 加 斯 算 法 C. 数 值 概 率 算 法 D. 舍 伍 德 算 法 5. 目 前 可 以 采 用 （ ） 在 多 项 式 级 时 间 内 求 出 旅 行 商 问 题 的 一 个 近 似 最 优 解 。 A. 回 溯 法 B. 蛮 力 法 C. 近 似 算 法 D. 都 不 可 能 6. 下 列 叙 述 错 误 的 是 （ ） 。 A. 概 率 算 法 的 期 望 执 行 时 间 是 指 反 复 解 同 一 个 输 入 实 例 所 花 的 平 均 执 行 时 间 B. 概 率 算 法 的 平 均 期 望 时 间 是 指 所 有 输 入 实 例 上 的 平 均 期 望 执 行 时 间 C. 概 率 算 法 的 最 坏 期 望 事 件 是 指 最 坏 输 入 实 例 上 的 期 望 执 行 时 间 D. 概 率 算 法 的 期 望 执 行 时 间 是 指 所 有 输 入 实 例 上 的 所 花 的 平 均 执 行 时 间 7. 下 列 叙 述 错 误 的 是 （ ） 。 A. 数 值 概 率 算 法 一 般 是 求 数 值 计 算 问 题 的 近 似 解 B.Monte Carlo 总 能 求 得 问 题 的 一 个 解 ， 但 该 解 未 必 正 确 C.Las Vegas 算 法 的 一 定 能 求 出 问 题 的 正 确 解 D.Sherwood 算 法 的 主 要 作 用 是 减 少 或 是 消 除 好 的 和 坏 的 实 例 之 间 的 差 别 8. 近 似 算 法 和 贪 心 法 有 什 么 不 同 ？ 9. 给 定 能 随 机 生 成 整 数 1 到 5 的 函 数 rand5() ， 写 出 能 随 机 生 成 整 数 1 到 7 的 函 数 rand7() 。 1.12.2 练 习 题 参 考 答 案 1. 答 ： C 。 2. 答 ： B 。 3. 答 ： A 。 4. 答 ： D 。 5. 答 ： C 。 6. 答 ： 对 概 率 算 法 通 常 讨 论 平 均 的 期 望 时 间 和 最 坏 的 期 望 时 间 ， 前 者 指 所 有 输 入 实 例 上 平 均 的 期 望 执 行 时 间 ， 后 者 指 最 坏 的 输 入 实 例 上 的 期 望 执 行 时 间 。 答 案 为 D 。 7. 答 ： 一 旦 用 拉 斯 维 加 斯 算 法 找 到 一 个 解 ， 那 么 这 个 解 肯 定 是 正 确 的 ， 但 有 时 用 拉 斯 维 加 斯 算 法 可 能 找 不 到 解 。 答 案 为 C 。 8. 答 ： 近 似 算 法 不 能 保 证 得 到 最 优 解 。 贪 心 算 法 不 一 定 是 近 似 算 法 ， 如 果 可 以 证 明 83 ----------------------------------------------------- Page 84 -----------------------------------------------------算 法 设 计 决 策 既 不 受 之 前 决 策 的 影 响 ， 也 不 影 响 后 续 决 策 ， 则 贪 心 算 法 就 是 确 定 的 最 优 解 算 法 。 9. 解 ： 通 过 rand5()*5+rand5() 产 生 6 ， 7 ， 8 ， 9 ， … ， 26 ， 27 ， 28 ， 29 ， 30 这 25 个 整 数 ， 每 个 整 数 x 出 现 的 概 率 相 等 ， 取 前 面 3*7=21 个 整 数 ， 舍 弃 后 面 的 4 个 整 数 ， 将 { 6 ， 7 ， 8} 转 化 成 1 ， {9 ， 10 ， 11} 转 化 成 2 ， 以 此 类 推 ， 即 由 y = ( x - 3)/3 为 最 终 结 果 。 对 应 的 程 序 如 下 ： #include <stdio.h> #include <stdlib.h> #include <time.h> int rand5() { int a=1,b=5; return rand()%(b-a+1)+a; } int rand7() { int x; do { x=rand5()*5+rand5(); } while (x>26); int y=(x-3)/3; return y; } void main() { srand((unsigned)time(NULL)); for (int i=1;i<=20;i++) printf("%d ",rand7()); printf("\n"); // 包 含 产 生 随 机 数 的 库 函 数 // 产 生 一 个 [ 1,5] 的 随 机 数 // 产 生 一 个 [ 1,7] 的 随 机 数 // 随 机 种 子 // 输 出 20 个 [ 1,7] 的 随 机 数 } 上 述 程 序 的 一 次 执 行 结 果 如 图 1.56 所 示 。 图 1.56 程 序 执 行 结 果 84

转载于:https://www.cnblogs.com/JUSTDOINS/p/11543964.html

相关资源：李春葆 算法设计与分析（第2版）课件 、习题答案、书中全部源代码