----------------------------------------------------- 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%10;
- 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 个 字 阵 最
来源: http://www.bubuko.com/infodetail-3203140.html