算法分析与设计教程
习题解答
第1章  算法引论
1.  解：算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列计算方法。        频率计数是指计算机执行程序中的某一条语句的执行次数。
多项式时间算法是指可用多项式函数对某算法进行计算时间限界的算法。        指数时间算法是指某算法的计算时间只能使用指数函数限界的算法。
2. 解：算法分析的目的是使算法设计者知道为完成一项任务所设计的算法的优劣，进而促使人们想方设法地设计出一些效率更高效的算法，以便达到少花钱、多办事、办好事的经济效果。
3. 解：事前分析是指求出某个算法的一个时间限界函数（它是一些有关参数的函数）；事后测试指收集计算机对于某个算法的执行时间和占用空间的统计资料。
4. 解：评价一个算法应从事前分析和事后测试这两个阶段进行，事前分析主要应从时间复杂度和空间复杂度这两个维度进行分析；事后测试主要应对所评价的算法作时空性能分布图。
5. 解：①n=11； ②n=12； ③n=982； ④n=39。
第2章  递归算法与分治算法
1． 解：递归算法是将归纳法的思想应用于算法设计之中，递归算法充分地利用了计算机系统内部机能，自动实现调用过程中对于相关且必要的信息的保存与恢复；分治算法是把一个问题划分为一个或多个子问题，每个子问题与原问题具有完全相同的解决思路，进而可以按照递归的思路进行求解。
2． 解：通过分治算法的一般设计步骤进行说明。
3． 解：int fibonacci(int n)
{
if(n<=1)
return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
4. 解：void hanoi(int n,int a,int b,int c)
{
if(n>0)
{
hanoi(n-1,a,c,b);
move(a,b);
hanoi(n-1,c,b,a);
}
}
5.  解：①22*2)(−−=n n f n
②  )log *()(n n n f O =
6． 解：算法略。时间复杂度分析：设时间复杂度为T （n ），则
因此，T(n )≤2T(n-1)≤22T(n-2)≤···≤2n-1
T(1)=)2(n O 。 7． 解：后序遍历二叉树的非递归算法如下：
typedef struct{
BiTree link;
int flag;
}Stacktype;
void NRpostOrder(BiTree b){
Stacktype Stack[MAX_TREE_SIZE];
BiTree p;
int top,sign;
if(b==NULL) return;
top=-1;                          /*栈顶位置初始化*/
p=b;
while(!(p==NULL&&top==-1)){
if(p!=NULL){                  /*结点第一次进栈*/
Stack[++top].link=p;
Stack[top].flag=1;
p=p->lchild;                /*该结点的左孩子*/
}
else{
p=Stack[top].link;
sign=Stack[top--].flag;
if(sign==1){                  /*结点第二次进栈*/
Stack[++top].link=p;
Stack[top].flag=2;            /*标记第二次出栈*/
p=p->lchild;
}
else{
Visit(p->data)；            /*访问该结点数据域值*/
p=NULL;
}
}
}
}
8. 解：第一趟排序后数组中的元素排列为37、35、38、36、47、53、65、73；        第二趟排序后数组中的元素排列为36、35、37、38、47、53、65、73；        第三趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；        第四趟排序后数组中的元素排列为35、36、37、38、47、53、65、73； 00)2()1()(>≤⎪⎩⎪⎨⎧−+−=n n n T n T C n T
第五趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第六趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第七趟排序后数组中的元素排列为35、36、37、38、47、53、65、73；
第八趟排序后数组中的元素排列为35、36、37、38、47、53、65、73。9．解：①原数组是有序的；
②n*(n-1)/2。
10．解：（略）思路同第8题。
11．解：void maxmin(int A[],int &e_max,int low,int high)
{
int mid,x1,y1,x2,y2;
if((high-low)<=1){
if(A[high]>A[low]){
e_max=A[high];
e_min=A[low];
}
else{
e_max=A[low];
e_min=A[high];
}
}
else{
mid=(low+high)/2;
maxmin(A,x1,y1,low,mid);
maxmin(A,x2,y2,mid+1,high);
e_max=max(x1,x2);
e_min=min(x1,x2);
}
}
12. 解：void poly_product(float p[],float q[],float r0[],int n)
{
int k,i;
float *r1,*r2,*r3;
r1=new float[2*n-1];
r2=new float[2*n-1];
r3=new float[2*n-1];
for(i=0;i<2*n-1;i++)
r0[i]= r1[i]=r2[i]=r3[i]=0;
if(n==2)
product(p,q,c);
else{
k=n/2;
poly_product(p,q,r0,k);
poly_product(p+k,q+k,r1+2*k,k);
plus(p,p+k,r2+k,k);
plus(q,q+k,r3,k);
poly_product(r2+k,r3,r2+k,k);
mins(r2+k,r0,2*k-1);
mins(r2+k,r1+2*k,2*k-1);
plus(r0+k,r2+k,r0+k,2*k-1);
plus(r0+2*k,r1+2*k,r0+2*k,2*k-1);
}
delete r1;
delete r2;
delete r3;
}
void product(float p[],float q[],float c[])
{
c[0]=p[0]*q[0];
namespace是干嘛的c[2]=p[1]*q[1];
c[1]=(p[0]+p[1])*(q[0]+q[1])-c[0]-c[2];
}
void plus(float p[],float q[],float c[],int n)
{
int i;
for(i=0;i<n;i++)
c[i]=p[i]+q[i];
}
void mins(float p[],float q[],int n)
{
int i;
for(i=0;i<n;i++)
p[i]=p[i]-q[i];
}
第3章贪心算法
1．解：（1）最优解的序列为（1,2/3,1,0,1,1,1）；
FO（I）=10+2/3*5+15+6+18+3=166/3；
按Pi的非增次序输入时的序列为（1,0,1,4/7,0,1,0）；
FG（I）=10+15+4/7*7+18=47；
因此，FO（I）/FG（I）=166/141；
（2）按wi的非降次序列输入时的序列为（1,1,4/5,0,1,1,1）；
此时的背包问题解为FG*（I）=10+5+4/5*15+6+18+3=54；
因此，FO（I）/FG*（I）=83/81。
2．解：举一个反例如下：
设背包容量为13，有7件物品，它们的容量组成的向量为（1,2,4,5,3,3,7），它
们的效益值组成的向量为（6,10,18,14,8,7,7）。
按照贪心算法计算求解总效益值为6+10+18+14=48，此时物品的总容量为
1+2+4+5=12≤13；可是按照6+10+18+8+7=49，此时物品的总容量为1+2+4+3+3=13
亦没有超过背包容量13，由于总效益值48＜49，因此该策略在这种情况下得不到
最优解。
3．解：
#include<iostream>
using namespace std;
const int N=12;
void OutputResult(int Select[N])
{
cout<<”{0”;
for(int i=1;i<N;i++)
if(Select[i]==1)
cout<<”,”<<i;
cout<<’}’<<endl;
}
int main()
{
int Begin[N]={1,3,0,3,2,5,6,4,10,8,15,15};
int End[N]={3,4,7,8,9,10,12,14,15,18,19,20};
int Select[N]={0,0,0,0,0,0,0,0,0,0,0,0};
int i=0;
int TimeStart=0;
while(i<N)
{
if(Begin[i]>=TimeStart)
{
Select[i]=1;
TimeStart=End[i];
}
i++;
}
OutputResult(Select);
result 0;
}
4.解题思路提示如下：
连接法：将间距较小的相邻区间连接成一个大的新区间，然后将所得的几个新区间的距离相加继而求得最小长度。
5．解：
class JobNode{
friend void Greedy(JobNode *,int,int);
friend void main(void);
public:
operator int()const{return time;}
private:
int ID,time;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。