算法设计与分析 - 李春葆 - 第二版 - pdf->word v1
2024-08-24 09:02:51
1.1 第 章─概论
1.1. 练习题
. 下列关于算法的说法中正确的有（ ）。Ⅰ.求解某一类问题的算法是唯一的
Ⅱ.算法必须在有限步操作之后停止
Ⅲ.算法的每一步操作必须是明确的，不能有歧义或含义模糊Ⅳ.算法执行后一定产生确定的结果
A. 个 B. 个 C. 个 D. 个
. T(n)表示当输入规模为 n 时的算法效率，以下算法效率最优的是（ ）。
A.T(n)= T(n-)+，T()= B.T(n)= 2n2
C.T(n)= T(n/)+，T()= D.T(n)=3nlog2n
. 什么是算法？算法有哪些特征？
. 判断一个大于 的正整数 n 是否为素数的方法有多种，给出两种算法，说明其中一种算法更好的理由。
. 证明以下关系成立：
（）10n2-2n=(n2)
（）2n+=(2n)
. 证明 O(f(n))+O(g(n))=O(max{f(n)，g(n)}) 。
. 有一个含 n（n>）个整数的数组 a，判断其中是否存在出现次数超过所有元素一半的元素。
. 一个字符串采用 string 对象存储，设计一个算法判断该字符串是否为回文。
. 有一个整数序列，设计一个算法判断其中是否存在两个元素和恰好等于给定的整数 k。
. 有两个整数序列，每个整数序列中所有元素均不相同。设计一个算法求它们的公共元素，要求不使用 STL 的集合算法。
. 正整数 n（n>）可以写成质数的乘积形式，称为整数的质因数分解。例如， =**，=**，=。设计一个算法求 n 这样分解后各个质因数出现的次数，采用 vector 向量存放结果。
. 有一个整数序列，所有元素均不相同，设计一个算法求相差最小的元素对的个数。如序列 、、、 的相差最小的元素对的个数是 ，其元素对是（，），（，），
（，）。
. 有一个 map<string，int>容器，其中已经存放了较多元素。设计一个算法求出其中重复的 value 并且返回重复 value 的个数。
. 重新做第 题，采用 map 容器存放最终结果。
. 假设有一个含 n（n>）个元素的 stack<int>栈容器 st，设计一个算法出栈从栈顶到栈底的第 k（≤k≤n）个元素，其他栈元素不变。 1.1. 练习题参考答案
. 答：由于算法具有有穷性、确定性和输出性，因而Ⅱ、Ⅲ、Ⅳ正确，而解决某一类问题的算法不一定是唯一的。答案为 C。
. 答：选项 A 的时间复杂度为 O(n)。选项 B 的时间复杂度为 O(n2)。选项 C 的时间复杂度为 O(log2n)。选项 D 的时间复杂度为 O(nlog2n)。答案为 C。
. 答：算法是求解问题的一系列计算步骤。算法具有有限性、确定性、可行性、输入性和输出性 个重要特征。
. 答：两种算法如下：
#include <stdio.h> #include <math.h>
bool isPrime1(int n) //方法 1
{ for (int i=;i<n;i++)
if (n%i==)
return false;
return true;
}
bool isPrime2(int n) //方法 2
{ for (int i=;i<=(int)sqrt(n);i++)
if (n%i==)
return false;
return true;
}
void main()
{ int n=;
printf("%d,%d\n",isPrime1(n),isPrime2(n));
}
方法 的时间复杂度为 O(n)，方法 的时间复杂度为 n，所以方法 更好。
. 答：（）当 n 足够大时，(10n2-2n)/( n2)=，所以 10n2-2n=(n2)。
（）2n+=*2n=(2n)。
. 证明：对于任意 f1(n)∈O(f(n)) ，存在正常数 c1 和正常数 n1，使得对所有 n≥n1， 有 f1(n)≤c1f(n) 。
类似地，对于任意 g1(n)∈O(g(n)) ，存在正常数 c2 和自然数 n2，使得对所有 n≥n2， 有 g1(n)≤c2g(n) 。
令 c3=max{c1，c2}，n3=max{n1，n2}，h(n)= max{f(n)，g(n)} 。则对所有的 n≥n3，有：
f1(n) +g1(n)≤c1f(n) + c2g(n)≤c3f(n)+c3g(n)=c3(f(n)+g(n))
≤c32max{f(n)，g(n)}=2c3h(n)=O(max{f(n)，g(n)})。
. 解：先将 a 中元素递增排序，再求出现次数最多的次数 maxnum，最后判断是否满足条件。对应的程序如下：
#include <stdio.h> #include <algorithm> using namespace std; bool solve(int a[],int n,int &x)
{
sort(a,a+n);
int maxnum=; //递增排序
//出现次数最多的次数
int num=;
int e=a[];
for (int i=;i<n;i++)
{ if (a[i]==e)
{ num++;
if (num>maxnum)
{ maxnum=num;
x=e;
}
}
else
{ e=a[i];
num=;
}
}
if (maxnum>n/)
return true;
else
return false;
}
void main()
{ int a[]={,,,,,,};
int n=sizeof(a)/sizeof(a[]);
int x;
if (solve(a,n,x))
printf("出现次数超过所有元素一半的元素为%d\n",x);
else
printf("不存在出现次数超过所有元素一半的元素\n");
}
上述程序的执行结果如图 1.1 所示。
图 1.1 程序执行结果
. 解：采用前后字符判断方法，对应的程序如下：
#include <iostream> #include <string> using namespace std;
bool solve(string str) //判断字符串 str 是否为回文
{ int i=,j=str.length()-;
while (i<j)
{ if (str[i]!=str[j])
return false; 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 程序执行结果
. 解：先将 a 中元素递增排序，然后从两端开始进行判断。对应的程序如下：
#include <stdio.h> #include <algorithm> using namespace std;
bool solve(int a[],int n,int k)
{ sort(a,a+n); //递增排序
int i=, j=n-;
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[]={,,,,};
int n=sizeof(a)/sizeof(a[]);
printf("求解结果\n");
int k=,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=;
if (solve(a,n,k1,i,j))
printf(" 存在: %d+%d=%d\n",a[i],a[j],k1); else
printf(" 不存在两个元素和为%d\n",k1);
}
上述程序的执行结果如图 1.3 所示。
图 1.3 程序执行结果
. 解：采用集合 set<int>存储整数序列，集合中元素默认是递增排序的，再采用二路归并算法求它们的交集。对应的程序如下：
#include <stdio.h> #include <set>
using namespace std;
void solve(set<int> s1,set<int> s2,set<int> &s3) //求交集 s3
{ set<int>::iterator it1,it2;
it1=s1.begin(); it2=s2.begin();
while (it1!=s1.end() && it2!=s2.end())
{ if (*it1==*it2)
{ s3.insert(*it1);
++it1; ++it2;
}
else if (*it1<*it2)
++it1;
else
++it2;
}
}
void dispset(set<int> s) //输出集合的元素
{ set<int>::iterator it;
for (it=s.begin();it!=s.end();++it)
printf("%d ",*it);
printf("\n");
}
void main()
{ int a[]={,,,};
int n=sizeof(a)/sizeof(a[]);
set<int> s1(a,a+n);
int b[]={,,,,};
int m=sizeof(b)/sizeof(b[]);
set<int> s2(b,b+m);
set<int> s3;
solve(s1,s2,s3);
printf("求解结果\n");
printf(" s1: "); dispset(s1); printf(" s2: "); dispset(s2);
printf(" s3: "); dispset(s3);
}
上述程序的执行结果如图 1.4 所示。
图 1.4 程序执行结果
. 解：对于正整数 n，从 i= 开始查找其质因数，ic 记录质因数 i 出现的次数，当找到这样质因数后，将（i，ic）作为一个元素插入到 vector 容器 v 中。最后输出 v。对应的算法如下：
#include <stdio.h> #include <vector> using namespace std;
struct NodeType //vector 向量元素类型
{ int p; //质因数
int pc; //质因数出现次数
};
void solve(int n,vector<NodeType> &v) //求 n 的质因数分解
{ int i=;
int ic=;
NodeType e;
do
{ if (n%i==)
{ ic++;
n=n/i;
}
else
{ if (ic>)
{ e.p=i;
e.pc=ic;
v.push_back(e);
}
ic=;
i++;
}
} while (n> || ic!=);
}
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);
} void main()
{ vector<NodeType> v;
int n=;
printf("n=%d\n",n);
solve(n,v);
disp(v);
}
上述程序的执行结果如图 1.5 所示。
图 1.5 程序执行结果
. 解：先递增排序，再求相邻元素差，比较求最小元素差，累计最小元素差的个数。对应的程序如下：
#include <iostream> #include <algorithm> #include <vector> using namespace std;
int solve(vector<int> &myv) //求 myv 中相差最小的元素对的个数
{ sort(myv.begin(),myv.end()); //递增排序
int ans=;
int mindif=myv[]-myv[];
for (int i=;i<myv.size();i++)
{ if (myv[i]-myv[i-]<mindif)
{ ans=;
mindif=myv[i]-myv[i-];
}
else if (myv[i]-myv[i-]==mindif)
ans++;
}
return ans;
}
void main()
{ int a[]={,,,};
int n=sizeof(a)/sizeof(a[]);
vector<int> myv(a,a+n);
cout << "相差最小的元素对的个数: " << solve(myv) << endl;
}
上述程序的执行结果如图 1.6 所示。 图 1.6 程序执行结果
. 解：对于 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",));
mymap.insert(pair<string,int>("Smith",));
mymap.insert(pair<string,int>("John",));
mymap.insert(pair<string,int>("Lippman",));
mymap.insert(pair<string,int>("Detial",));
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 程序执行结果
. 解：采用 map<int，int>容器 mymap 存放求解结果，第一个分量存放质因数，第二个分量存放质因数出现次数。对应的程序如下：
#include <stdio.h> #include <map>
using namespace std;
void solve(int n,map<int,int> &mymap) //求 n 的质因数分解 else
{ if (ic>)
mymap[i]=ic;
ic=;
i++;
}
} while (n> || ic!=);
}
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=;
printf("n=%d\n",n);
solve(n,mymap);
disp(mymap);
}
上述程序的执行结果如图 1.8 所示。
图 1.8 程序执行结果
. 解：栈容器不能顺序遍历，为此创建一个临时 tmpst 栈，将 st 的 k 个元素出栈并进栈到 tmpst 中，再出栈 tmpst 一次得到第 k 个元素，最后将栈 tmpst 的所有元素出栈并进栈到 st 中。对应的程序如下：
#include <stdio.h> #include <stack> using namespace std;
int solve(stack<int> &st,int k) //出栈第 k 个元素
{ stack<int> tmpst;
int e;
for (int i=;i<k;i++) //出栈 st 的 k 个元素并进 tmpst 栈
{ e=st.top();
st.pop();
tmpst.push(e);
}
e=tmpst.top(); //求第 k 个元素
tmpst.pop();
while (!tmpst.empty()) //将 tmpst 的所有元素出栈并进栈 st
{ st.push(tmpst.top());
tmpst.pop(); }
return e;
}
void disp(stack<int> &st) //出栈 st 的所有元素
{ while (!st.empty())
{ printf("%d ",st.top());
st.pop();
}
printf("\n");
}
void main()
{ stack<int> st;
printf("进栈元素 1,2,3,4\n");
st.push();
st.push();
st.push();
st.push();
int k=;
int e=solve(st,k);
printf("出栈第%d 个元素是: %d\n",k,e);
printf("st 中元素出栈顺序: ");
disp(st);
}
上述程序的执行结果如图 1.9 所示。
图 1.9 程序执行结果
1.2 第 章─递归算法设计技术
1.2. 练习题
. 什么是直接递归和间接递归？消除递归一般要用到什么数据结构？
. 分析以下程序的执行结果：
#include <stdio.h>
void f(int n,int &m)
{ if (n<) return;
else
{ printf("调用f(%d,%d)前,n=%d,m=%d\n",n-,m-,n,m);
n--; m--;
f(n-,m);
printf("调用f(%d,%d)后:n=%d,m=%d\n",n-,m-,n,m);
} }
void main()
{ int n=,m=;
f(n,m);
}
. 采用直接推导方法求解以下递归方程：
T()=
T(n)=T(n-)+n 当 n>
. 采用特征方程方法求解以下递归方程：
H()=
H()=
H()=
H(n)=H(n-)+9H(n-)-9H(n-) 当 n>
. 采用递归树方法求解以下递归方程：
T()=
T(n)=4T(n/)+n 当 n>
. 采用主方法求解以下题的递归方程。
T(n)= 当 n=
T(n)=4T(n/)+n2 当 n>
. 分析求斐波那契 f(n)的时间复杂度。
. 数列的首项 a1=，后续奇数项和偶数项的计算公式分别为 a2n=a2n-+，a2n+=a2n- +a2n-，写出计算数列第 n 项的递归算法。
. 对于一个采用字符数组存放的字符串 str，设计一个递归算法求其字符个数（长度）。
. 对于一个采用字符数组存放的字符串 str，设计一个递归算法判断 str 是否为回文。
. 对于不带头结点的单链表 L，设计一个递归算法正序输出所有结点值。
. 对于不带头结点的单链表 L，设计一个递归算法逆序输出所有结点值。
. 对于不带头结点的非空单链表 L，设计一个递归算法返回最大值结点的地址（假设这样的结点唯一）。
. 对于不带头结点的单链表 L，设计一个递归算法返回第一个值为 x 的结点的地址，没有这样的结点时返回 NULL。
. 对于不带头结点的单链表 L，设计一个递归算法删除第一个值为 x 的结点。
. 假设二叉树采用二叉链存储结构存放，结点值为 int 类型，设计一个递归算法求二叉树 bt 中所有叶子结点值之和。
. 假设二叉树采用二叉链存储结构存放，结点值为 int 类型，设计一个递归算法求二叉树 bt 中所有结点值大于等于 k 的结点个数。
. 假设二叉树采用二叉链存储结构存放，所有结点值均不相同，设计一个递归算法求值为 x 的结点的层次（根结点的层次为 ），没有找到这样的结点时返回 。 1.2. 练习题参考答案
. 答：一个 f 函数定义中直接调用 f 函数自己，称为直接递归。一个 f 函数定义中调用 g 函数，而 g 函数的定义中调用 f 函数，称为间接递归。消除递归一般要用栈实现。
. 答：递归函数f(n，m)中，n是非引用参数，m是引用参数，所以递归函数的状态为
（n）。程序执行结果如下：
调用f(,)前,n=,m= 调用f(,)前,n=,m= 调用f(,)后,n=,m= 调用f(,)后,n=,m=
. 解：求 T(n)的过程如下：
T(n)=T(n-)+n=[T(n-)+n-)]+n=T(n-)+n+(n-)
=T(n-)+n+(n-)+(n-)
=…
=T()+n+(n-)+…+
=n+(n-)+ +…++=n(n+)/=O(n2)。
. 解：整数一个常系数的线性齐次递推式，用 xn 代替 H(n)，有：xn=xn-+9xn--9xn-， 两边同时除以 xn-，得到：x3=x2+9x-，即 x3-x2-9x+=。
x3-x2-9x+=x(x2-)-(x2-)=(x-)(x2-)=(x-)(x+)(x-)=。得到 r1=，r2=-，r3=
则递归方程的通解为：H(n)=c1+c2(-)n+c33n 代入 H()=，有 c1+c2+c3=
代入 H()=，有 c1-3c2+3c3=
代入 H()=，有 c1+9c2+9c3= ( ‒ )n ‒ n ‒ 求出：c1=-/，c2=-/，c3=/，H(n)=c1+c2(-)n+c33n=( + ) ‒ 。 . 解：构造的递归树如图 1.10 所示，第 层的问题规模为 n，第 的层的子问题的问题规模为 n/，依此类推，当展开到第 k+ 层，其规模为 n/2k=，所以递归树的高度为log2n+。
第1层有1个结点，其时间为n，第2层有4个结点，其时间为4(n/)=2n，依次类推，第k 层有4k-1个结点，每个子问题规模为n/2k-，其时间为4k-(n/2k-)=2k-1n。叶子结点的个数为n 个，其时间为n。将递归树每一层的时间加起来，可得：
T(n)=n+2n+…+ 2k-1n+…+n≈最新文章
- IBatis分页显示
- 测试table数据 winfrom datagridview 点击标头数字排序的时候table 列类型要为数字类型
- NCPC 2013: Dance Reconstruction
- 单源最短路径——Floyd算法
- CDOJ 482 Charitable Exchange bfs
- ArcGis ：正尝试在 OS 加载程序锁内执行托管代码。不要尝试在 DllMain 或映像初始化函数内运行托管代码，这样做会导致应用程序挂起。
- 经典关于多态的demo
- IOS 消息
- Kindle电子阅读器收不到个人文档推送解决方案
- MyBatis框架概述
- 中国.NET：各地微软技术俱乐部汇总(持续更新中...)
- python 自定义模块的发布和安装
- 北大poj-1021
- BZOJ3876[Ahoi2014&Jsoi2014]支线剧情——有上下界的最小费用最大流
- Mosquitto --topic
- call、apply、bind的用法
- 【Java】Springboot-Quartz-分布式任务调度
- IIS Express并发数设置
- github不能访问，可能原因是host里有太多过期的对应
- window7安装MongoDB详细步骤
热门文章