算法設計與分析作業

姓名：學號：專業：

習題一

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);