算法设计和分析作业

算法设计与分析作业

姓名：学号：专业：

习题一

1-1函数的渐进表达式

3n2+10n=O(n2);

n2/10+2n=O(2n);

21+l/n=0(l);

logn3=O(logn);

10log3n=O(n)

1-2O⑴和0(2)的区别

分析与解答：根据符号0的定义可知。(1)=0(2)用。(1)和。(2)

表示同一个函数时，差别仅在于其中的常数因子。

1-3按渐进阶排列表达式

分析与解答：按渐进阶从低到高，函数排列顺序如下：

0(2)<0(logn)<0(n2/3)<0(20n)<0(4n2)<0(3n)<0(n!)

习题二

算法分析题

2-27个二分搜索算法

分析与解答：(1)与主教材中的算法Binarysearch相比，数组段左、右游

标left和right的调整不正确，导致陷入死循环。

(2)数组段左、右游标left和right的调整不正确，导致当x=a[n-l]时返回

错误。

(3)数组段左、右游标left和right的调整不正确，导致当x=a[n-l]时返回

错误。

(4)数组段左、右游标left和right的调整不正确，导致陷入死循环。

(5)算法正确,且当数组中有重复元素时，返回满足条件的最右元素。

(6)数组段左、右游标left和right的调整不正确，导致当x=a[n-l]时返回

错误。

(7)数组段左、右游标left和right的调整不正确，导致当x=a⑼时陷入死

循环。

2-26修改快速排序算法，使它在最坏情况下的计算时间为0(nlogn).

分析与解答：从一个无序的序列中随机取出一个值q做为支点，然后把大

于q的放到一边，小于q的放到q的另一边，然后再以q为分界点，分别对q的

两边进行排序(快排时直接再对q两边重新取支点，整理，再取支点，…直到支

点两旁都有序。也就是支点两旁只有一个数时)

#include<stdio.h>

#include<stdlib.h>

intQsort(intp[],intbegjntend)

if(beg+l>=end)return0;〃退出递归

intlow,hight,q;

low=beg;

hight=end;

q=p[low];〃q为支点，其实q可以为随机数。但相应以下程序就要改了

while(l){

while(low<hight&&p[hight]>q)hight-;

if(low>=hight)break;

p[low++]=p[hight];

while(low<hight&&p[low]<q)low++;

p[hight++]=p[low];

}

p[low]=q;

Qsort(p,beg,low-1);

Qsortfpjow+l^nd);

}

intmain()

(

inti,a[]={lz32,6,4,54,654,6,6,2,76,76,7,66,5,544,334,34,78};

Qsort(a,0,sizeof(a)/4-l);

for(i=0;i<sizeof(a)/4;i++)printf("%d",a[i]);

system(,,pause");

return0;

)

算法实现题

2-2众数问题

分析与解答：算法具体实现如下：

Voidmode(intl,intr)

{intllzrl;

Intmed=median(aj,r);

lf(largest<rl-ll+l)

Largest=rl-ll+l,element=med;

lf(largest<ll-l)

mode(IJl-l);

lf(largest<r-rl)

mode(rl+l,r);

)

其中，median用于找中位数，split用中位数将数组分割为2段。

习题三

算法分析题

3-5二维0-1背包问题

分析与解答：问题的形式化描述是：给定c>0,d>0.wi>0,bi>0,vi>0,l<=i<=n,

要求找出n7C0-1向量(xl,x2,......,xn),xi属于{0.1},1<=I<=n,使得fwixi<=c,

i=l

Z〃汉而且2心，达到最大。

z=li=l

因此，二维0-1背包问题也是一个特殊的整数规划问题。

Max^vm

i=l

ZWZXZ<=c

/=1

(>bixi<=d

i=\

xi属于{0.1},1<=i<=n

I

容易证明该问题具有最优子结构性质

设所给二维0.1背包问题的子问题

MaxZ心/

/=/

ZmX/<=j

t=i

xt属于{0.1},1<=t<=n

I

的最优质为m(l,j,k),即m(ljk)背包容量为j溶积为k,可选择物品为IJ+1，…,n

时二维0-1背包问题的最优值。由二维0-1背包问题的最优子结构性质，可以建

立计算m(l,j,k)的递归式如下：

“Max{m(i+Lj),m(i+ljwi,k-bi)+vi}j>=wiandk>=bi

m(ijk)二y

Im(i+l,j)0<=j<wior0<=k<bi

"vnj>=wnandk>=bn

m(nj,k)-

100<=j<wnor0<=k<bn

按此递归式计算出的m(n,c,d)为最优值。算法所需的计算时间为O(ncd).

算法实现题

3-2最少硬币问题

分析与解答：对于这个硬币问题，我们每次都是取硬币，或者不取硬币。

因此我们可以将这个硬币问题切割成若干个子问题(取不取这种硬币)，而且每

次决策都会用到这个子问题。而且所有的子问题中必定存在最优解。每次取硬币，

都仅仅是做出决策，判断是否取这三种硬币，每次决策之后，除了n块钱会改变

之外，其他都没有改变，都是判断是否取这三种硬币的一种，因此可以说硬币问

题无后效性。

#include<iostream>

usingnamespacestd;

intfind_dest(intmoney,int*coin,intn)

{int*minCoin=newint[money+1]();

int*valueCoin=newint[money+1]();

memset(minCoin,0,sizeof(int)*(money+1));

memset(valueCoin,0,sizeof(int)*(money+1));

for(inti=1;i<=money;i++)

{intmaxCoin=i;

intvalue=0;

for(intj=0;j<n;j++)

{if(i>=coinfj])

{if(minCoin[i-coin[j]]+1<=maxCoin&&(i==coin[j]||valueCoin[i-coin[j]]!=0)/*

检测上一个是否有效，无效则跳过*/)

(

maxCoin=minCoin[i-coin[j]]+1;

value=coin[j];

})

minCoin[i]=maxCoin;

valueCoin[i]=value;

}

if(valueCoin[money]!=0)

(

while(money)

(

cout«valueCoin[money]«

money-=valueCoin[money];}

cout«endl;

}

else

(

cout«"error!"«endl;

}

delete[]minCoin;

deletef]valueCoin;

return0;}

intmain()

(

intmoney=9;

intcoin[3]={2,3,5};

find_dest(money,coin,3);

system("pause");

return0;

}

习题4

算法实现题

4-6最优服务次序问题

分析与解答：贪心策略：最短服务时间优先。

doublegreedy(vector<int>x)

{intn=x.size();

Sort(x.begin(),x.end());

For(inti=l;i<n;i++)

x[i]+=x[i-l];

doublet=0;

For(i=l;i<n;i++)

t+=x[i];

t/=n;

returnt;

)

4-7多次最优服务次序问题

分析与解答：贪心策略：最短服务时间优先。

Doublegreedy(vector<int>x,ints)

{vector<int>st(s+l,O);

vector<int>su(s+l,0);

intn=x.size();

sort(x.begin(),x.end());

inti=0,j=0;

while(i<n){

st[j]+=x[i];

su[j]+=st[j];

i++；j++；

if(j==s)

j=0；}

doublet=0;

for(i=0;i<s;i++)t+=su[i];

t/=n

returnt;}

习题五

算法分析题

5-4最大团问题的迭代回溯法

分析与解答：与教材中装载问题的迭代回溯法相似，最大团问题的迭代回

溯法描述如下：

voidclique::iterclique()

{for(inti=0;i<=n;i++)x[i]=0;

i=l；

while(true){

while(i<=n&&ok(i)){x[i++]=l;cn++;}

if(i>=n){

for(intj=l;j<=n;j++)bestx[j]=x[j];

bestn=cn;

}

Elsex[i++]=0;

While(cn+n-i<=bestn){

i-；

while(i&&!x[i])i-;

if(i==0)return;

x[i++]=0;cn-;

}

)

}

其中，OK用于判断当前顶点是否可加入当前团。

boolClique::ok(inti)

{for(intj=l;j<l;j++)

lf(x[j]&&a[i][j]==NoEdge)returnfalse;

Returntrue;}

依「Clique用于初始化，并调用迭代回溯法求解。

IntClique::lterClique(intv[])

{x=newint[n+l];

cn=0;

bestn=O;

bestx=v;

lterClique();

delete[]x;

returnbetn;

)

算法实现题

5-4运动员最佳配对问题

分析与解答：磁体的解空间显然是一颗排列数，可以套用搜索排列数的回溯法框

架。

voidpref::Comppute(void)

{for(inti=l,temp=O;i<=n;i++)

Temp+=p[i][r[i]]*q[r[i]][i];

lf(temp>best){

Best=temp;

For(inti=l;i<=n;i++)bestr[i]=r[i];

)

}

习题六

算法分析题

6-9解旅行售货员问题的分支限界法中保存已产生的排列树。

分析与解答：排列树中结点类型定义为：

classbbnode{

public:

bbnode*parent;

ints,*x;

)；

保存已产生的排列树的旅行售货员问题的分支限界法如下。

template<classtype>

classTraveling(

friendintmain();

public:

typeBBTSP(intv[]);

private:

intn;

type**a,NoEdge,cc,bestc;

)；

Template<classtype>

ClassMinHeapNode{

Friendtraveling<type>;

Public:

Operatortype()const{returnIcost;}

Private:

TypeIcostccjcost;

Bbnode*ptr;};

Template<classtype>

Typetraveling<type>::BBTSP(intv[])

{〃解旅行售货员问题的优先队列式分支限界法

、、定义最小堆得容量为100000

MinHeap<MinHeapNode<Type»H(100000);

Type*MinOut=newType[n+1];

〃计算MinOut[i]二顶点i的最小出边费用

TypeMinSum=0;

For(inti=l;i<=n;i++)

{typeMin=NoEdge;

For(intj=l;j<=n;j++)

lf(a[i]U]!=NoEdge&&(a[i][j]<Min||Min==NoEdge))

Min=a[i][j];

lf(Min==NoEdge)returnNoEdge;

MinOut[i]=Min;

MinSum+=Min;

)

〃初始化

MinHeapNode<Type>E;

bbnode*bb=newbbnode;

bb->parent=O;

bb->x=newint[n];

bb->s=0;

for(intj=O;j<n;j++)bb->x[j]=j+l;

E.ptr=bb;=0;E.rcost=MinSum;

Typebestc=NoEdge;

〃搜索排列空间树

While(E.ptr->s<n-l){

lf(E.ptr->s==n-2){

lf(a[E.ptr->x[n-2]][E.ptr->x[n-l]]!=NoEdge&&a[E.ptr->x[n-l]][l]!=NoEdge&&{

+a.[E.ptr->x[n-2]][E.ptr->x[n-l]]+a[E.ptr->x[n-l]][l]<bestc||bestc==NoEdge)){

Bestc=+a.[E.ptr->x[n-2]][E.ptr->x[n-l]]+a[E.ptr->x[n-l]][l];

=bestc;

E.lcost=bestc;

E.ptr->s++;

H.lnsert(E);