算法分析与设计作业题

算法分析与设计作业题

第2章:

22.分别对如下函数完成练习21：

9)SequentialSearch(见程序2-28),分析最坏情况下的执行步数。

程序2-28另一个顺序搜索函数

template<classT>

intSequentialSearch(Ta[],constT&x,intn)

{//在未排序的数组a[0:n-1]中查找x

//如果找到，则返回相应位置，否则返回-1

a[n]=x;//假定该位置有效

inti;

for(i=0;a[i]!=x;i++);

if(i==n)return-1;

returni;

)

答案：

1)

template<classT>

intSequentialSearch(Ta[],constT&x,intn)

{//在未排序的数组a[0:n-1]中查找x

//如果找到，则返回相应位置，否则返回-1

a[n]=x;//假定该位置有效

count++;//对应于a[n]=x;

inti;

count++;//对应于intI;

for(i=0;a[i]!=x;i++)

count++;〃对应于for语句

count++;//对应于最后一条for语句

count++;//对应于if语句

if(i==n)

(

count++;//对应于return-1;

return-1;

}

count++;〃对应于returni;

returni;

)

2)

template<classT>

intSequentialSearch(Ta[],constT&x,intn)

{//在未排序的数组a[0:n-1]中查找x

//如果找到，则返回相应位置，否则返回-1

a[n]=x;//假定该位置有效

inti;

for(i=0;a[i]!=x;i++)

count++;

if(i==n)

(

count=count+5;

return-1;

)

count=count+5;

returni;

}

3)在最坏的情况下，count的值为n+5;

4)

语句s/e频率总步数

intSequentialSearch(Ta[],constT&x,intn)000

(000

a[n]=x;//假定该位置有效111

inti;111

for(i=0;a[i]!=x;i++);1n+1n+1

if(i==n)return-1;111

returni;111

)000

总计n+5

表12-28程序在最坏的情况的执行步数

10)SelectionSort(见程序2-7),分析最好和最坏情况下的执行步

数。

程序2-7选择排序

template<classT>

voidSelectionSort(Ta[],intn)

(〃对数组a[0:n-1]中的n个元素进行排序

for(intsize=n;size>l;size—)

(

intj=Max(a,size);

Swap(a[j],a[size-1]);

)

)

答案：

1)template<classT>

voidSelectionSort(Ta[],intn)

(〃对数组a[0:n-1]中的n个元素进行排序

for(intsize=n;size>l;size―)

(

count++;〃对应for语句

intj=Max(a,size);

count++;//对应intj=Max(a,size);

Swap(a[j],a[size-1]);

count++;//对应Swap(a[j],a[size-1]);

}

count++;//对应最后一条for语句

)

2)template<classT>

voidSelectionSort(Ta[],intn)

(〃对数组a[0:n-1]中的n个元素进行排序

for(intsize=n;size>l;size―)

(

intj=Max(a,size);

Swap(a[j],a[size-1]);

count=count+3;

)

count++;//对应最后一条for语句

)

3)在最好的情况和最坏的情况下程序结束时的count值均为3n-2;

4)

语句s/e频率总步数

voidSelectionSort(Ta[],intn)000

(000

for(intsize=n;size>l;size—)Inn

(000

intj=Max(a,size);1n-1n-1

Swap(a[j],a[size-1]);1n-1n-1

)000

)000

总计3n-2

表22-7程序在最好和最坏的情况下的执行步数

11)SelectionSort(见程序2-12),分析最好和最坏情况下的执行

步数。

程序2-12及时终止的选择排序

template<classT>

voidSelectionSort(Ta[],intn)

{//及时终止的选择排序

boolsorted=false;

for(intsize=n;!sorted&&(size>l);size―)

(

intpos=0;

sorted=true;

//找最大元素

for(inti=l;i<size;i++)

if(a[pos]<=a[i])pos=i;

elsesorted=false;//未按序排列

)

Swap(a[pos],a[size-1]);

)

)

答案：

1)template<classT>

voidSelectionSort(Ta[],intn)

{//及时终止的选择排序

boolsorted=false;

count++;〃对应于boolsorted=false;

for(intsize=n;!sorted&&(size>l);size—)

(

count++;〃对应于for语句

intpos=0;

count++;//对应于intpos=0;

sorted=true;

count++;//对应于sorted=true;

for(inti=l;i<size;i++)

count++;//对应于嵌套的for语句

count++;〃对应于if语句

if(a[pos]<=a[i])

(

pos=i;

count++;//对应于pos=i;

)

else

(

sorted=false;

count++;//对应于sorted=false;

)

)

count++;//对应于嵌套for语句的最后一条

count++;〃对应于Swap(a[pos],a[size-1]);

Swap(a[pos],a[size-1]);

)

count++;//对应于for语句的最后一条

)

2)template<classT>

voidSelectionSort(Ta[],intn)

{//及时终止的选择排序

boolsorted=false;

for(intsize=n;!sorted&&(size>l);size一)

intpos=0;

sorted=true;

for(inti=l;i<size;i++)

(

if(a[pos]<=a[i])

(

pos=i;

count=count+3;

)

else

(

sorted=false;

count=count+3;

)

)

Swap(a[pos],a[size-1]);

count=count+5;

count=count+2;

3)在最好的情况下count的值为3n+4,在最坏的情况下count的值为

n(3n-l)/2+4n-2

4)

语句s/e频率总步数

voidSelectionSort(Ta[],intn)000

{//及时终止的选择排序000

boolsorted=false;111

for(intsize=n;!sorted&&(size>l);size—)122

(000

intpos=0;111

sorted=true;111

for(inti=l;i<size;i++)1nn

(000

if(a[pos]<=a[i])1n-1n-1

pos=i;1n-1n-1

elsesorted=false;000

)000

Swap(a[pos],a[size-1]);111

)000

)000

总计3n+4

表32-12程序在最好的情况下的执行步数

语句s/e频率总步数

voidSelectionSort(Ta[],intn)000

{//及时终止的选择排序000

boolsorted=false;111

for(intsize=n;!sorted&&(size>l);size—)1nn

{000

intpos=0;1n-1n-1

sorted=true;1n-1n-1

for(inti=l;i<size;i++)1n(n+1)/2n(n+l)/2

(000

if(a[pos]<=a[i])1n(n-1)/2n(n-1)/2

pos=i;000

elsesorted=false;0n(n-1)/2n(n-1)/2

)000

Swap(a[pos],a[size-1]);1n-1n-1

)000

)000

总计n(3n-l)/2+4n-2

表42-12程序在最坏的情况下的执行步数

12）InsertionSort（见程序2-14）,分析最坏情况下的执行步数。

程序2-14插入排序

template<classT>

voidInsert(Ta[],intn,constT&x)

{//向有序数组a[0:n-1]中插入元素x

inti;

for(i=n-l;i>=0&&x<a[i];i-)

a[i+1]=a[i];

a[i+1]=x;

)

template<classT>

voidInsertionSort(Ta[],intn)

{//对a[0:n-1]进行排序

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

(

Tt=a[i];

Insert(a,i,t);

)

)

答案：

1)template<classT>

voidInsert(Ta[],intn,constT&x)

{//向有序数组a[0:n-1]中插入元素x

inti;

count++;

for(i=n-l;i>=0&&x<a[i];i一)

(

count++;

a[i+1]=a[i];

count++;

)

count++;

count++;

a[i+1]=x;

)

template<classT>

voidInsertionSort(Ta[],intn)

{//对a[0:n-1]进行排序

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

(

count++;

count++;

Tt=a[i];

Insert(a,i,t);

count++;

)

2)template<classT>

voidInsert(Ta[],intn,constT&x)

{//向有序数组a[0:n-1]中插入元素

inti;

for(i=n-l;i>=0&&x<a[i];i--)

(

a[i+1]=a[i];

count=count+2;

)

a[i+1]=x;

count=count+3;

)

template<classT>

voidInsertionSort(Ta[],intn)

{//对a[0:n-1]进行排序

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

Tt=a[i];

count=count+2;

Insert(a,i,t);

)

count++;

)

3)在最坏的情况下程序结束时的count值为(n+5)(n-l)+l;

4)

语句s/e频率总步数

voidInsertionSort(Ta[],intn)000

{//对a[0:n-1]进行排序000

for(inti=l;i<n;i++)1nn

(000

Tt=a[i];1n-1n-1

Insert(a,i,t);n+3(n+3)(n-1)(n+3)(n-1)

)000

)000

总计(n+5)(n-l)+l

36.下面哪些规则是正确的？为什么？

(6){f(n)=Q(F(n)),g(n)=Q(G(n))}-f(n)/g(n)=0(F(n)/G(n))

(7){f(n)=0(F(n)),g(n)=0(G(n))}-*f(n)/g(n)=0(F(n)/G(n))

(8){f(n)=0(F(n)),g(n)=0(G(n))}一f(n)/g(n)=Q(F(n)/G(n))

(9){f(n)=0(F(n)),g(n)=0(G(n))}-f(n)/g(n)=0(F(n)/G(n))

答案：

⑹是错误的，⑺⑻⑼是正确的.

53.对于n=10,20,30,...,100,确定函数Transpose(见程序2-22

的运行时间。用表格和图的形式给出测量结果。

程序2-22矩阵转置

template<classT>

voidTranspose(T**a,introws)

{//对矩阵a[0:rows-1][0:rows-1]进行转置

for(inti=0;i<rows;i++)

for(intj=i+l;j<rows;j++)

Swap(a[i][j],a[j][i]);

)

第13章：

2.考虑例13-4的找零钱问题，假设售货员只有有限的25美分，10美

分，5美分和1美分的硬币，给出一种找零钱的贪婪算法。这种方法总

能找出具有最少硬币数的零钱吗？证明结论。

(例13-4[找零钱]一个小孩买了价值少于1美元的糖，并将1美

元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提

供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。售

货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采

用的贪婪准则如下：每一次选择应使零钱数尽量增大。为保证解法的

可行性(即：所给的零钱等于要找的零钱数)，所选择的硬币不应使

零钱总数超过最终所需的数目。

假设需要找给小孩67美分，首先入选的是两枚25美分的硬币，第

三枚入选的不能是25美分的硬币，否则硬币的选择将不可行(零钱总

数超过67美分)，第三枚应选择10美分的硬币，然后是5美分的，最

后加入两个1美分的硬币。)

答:此时的一种贪婪算法是：

已知:现有的钞票面额和付款额：

intm[]={25,10,5,1);

intV;〃可由用户输入

输出：各种币值的钞票数intn[4];使得钞票总额为V并且钞票数最少

算法可描述为：

voidPay(intm[],intV)

(

inti,R,n[4];

for(i=0;i<4;i++)

n[i]=0;

R=V;

i=0;

while(R>0)

(

if(m[i]<=R)

(

R-=m[i];

n[i]++;

)

else

i++；

)

for(i=0;i<4;i++)

逐个输出n[i]个m[i]面值的钞票；

)

该算法的思路

*31.1)给出Prim算法(如图13-14所示)的一种正确性证明。

2)将图13-14细化为一个C++程序UNetwork::Prim,其复杂性应为

0(成)。

3)证明程序的复杂性确实是0(〃2)。

Prim最小生成树算法：

〃假设网络中至少具有一个顶点

设病所选择的边的集合，初始化后巾

设7师已在树中的顶点的集合，置7片｛1｝

令府网络中边的集合

（厌＞巾）&&（|7|0/7-1）

（

令（％。）为最小代价边，其中〃£7匕v^TV

if（没有这种边）break;

E=E-｛（u,力｝〃从肿删除此边

在外加入边（U,K）

｝

if（171==n-l）现一棵最小生成树

else网络是不连通的，没有最小生成树

第14章：

21.设计一个在最差情况下性能最好的排序算法。

1）比较插入排序、冒泡排序、选择排序、堆排序、归并排序和快速

排序在最坏情况下的运行时间。导致插入排序、冒泡排序、选择排序

和快速排序出现最坏复杂性的输入数据很容易产生。试编写一个程

序，用来产生导致归并排序出现最坏复杂性的输入数据。这个程序本

质上是将〃个排好序的元素“反归并”。对于堆排序，用随机产生的

输入序列来估算最坏情况下的时间复杂性。

2）利用1）中的结果设计一个混合排序函数，使其在最坏情况下具有

最佳性能。比如混合函数可以只包含归并排序和插入排序。

3)测试混合排序函数在最坏情况下的运行时间，并与原排序函数进

行比较。

4)用一个简单的图表来列出七种排序函数在最差情况下的运行时

间。

第15章：

2.修改程序15-1,使用一个表格来确定f(i,y)是否已被计算过。在

求