算法分析与设计(李清勇)课后习题答案.docx

算法分析与设计(李清勇)课后习题答案.docx

《算法分析与设计(李清勇)课后习题答案.docx》由会员分享，可在线阅读，更多相关《算法分析与设计(李清勇)课后习题答案.docx（16页珍藏版）》请在冰点文库上搜索。

5-1凸多边形最优三角剖分问题

//3d5凸多边形最优三角剖分

#include"stdafx.h"#includeusingnamespacestd;

constintN=7;//凸多边形边数+1

intweight[][N]={{0,2,2,3,1,4},{2,0,1,5,2,3},{2,1,0,2,1,4},{3,5,2,0,6,2},{1,2,1,6,0,1},{4,3,4,2,1,0}};//凸多边形的权

intMinWeightTriangulation（intn,int**t,int**s）;

voidTraceback（inti,intj,int**s）;//构造最优解

intWeight（inta,intb,intc）;//权函数

intmain（）{

int**s=newint*[N];

int**t=newint*[N];

for（inti=0;i

s[i]=newint[N];

t[i]=newint[N];

}

cout<<"此多边形的最优三角剖分值为：

"<

cout<<"最优三角剖分结构为：

"<

Traceback（1,5,s）;//s[i][j]记录了Vi-1和Vj构成三角形的第3个顶点的位置

return0;

}

intMinWeightTriangulation（intn,int**t,int**s）

{

for（inti=1;i<=n;i++）

{

t[i][i]=0;

}

for（intr=2;r<=n;r++）//r为当前计算的链长（子问题规模）

{

for（inti=1;i<=n-r+1;i++）//n-r+1为最后一个r链的前边界

{

intj=i+r-1;//计算前边界为r，链长为r的链的后边界

t[i][j]=t[i+1][j]+Weight（i-1,i,j）;//将链ij划分为A（i）*（A[i+1:

j]）这里实际上就是k=i

s[i][j]=i;

for（intk=i+1;k

//将链ij划分为（A[i:

k]）*（A[k+1:

j]）

intu=t[i][k]+t[k+1][j]+Weight（i-1,k,j）;

if（u

t[i][j]=u;

s[i][j]=k;

}

}

}

}

returnt[1][N-2];

}

voidTraceback（inti,intj,int**s）{

if（i==j）return;

Traceback（i,s[i][j],s）;

Traceback（s[i][j]+1,j,s）;

cout<<"三角剖分顶点：

V"<

}

intWeight（inta,intb,intc）{

returnweight[a][b]+weight[b][c]+weight[a][c];

}5-4数字三角形最短路径

#include#include#include"string.h"#defineMax101

usingnamespacestd;

intD[Max][Max];intnum;

intMaxSum（intnum）{

inti,j;

for（i=num-1;i>=1;i--）

for（j=1;j<=i;j++）{

D[i][j]=max（D[i+1][j],D[i+1][j+1]）+D[i][j];

}

returnD[1][1];

}

intmain（intargc,charconst*argv[]）{

inti,j;

cin>>num;

for（i=1;i<=num;i++）

for（j=1;j<=i;j++）

cin>>D[i][j];

cout<

return0;}

5-2游艇租赁问题

#include

usingnamespacestd;

#defineN210

intcost[N][N];

intm[N];

intmain（）

{

intn,i,j;

while（cin>>n）

{

for（i=1;i

for（j=i+1;j<=n;j++）

cin>>cost[i][j];

m[1]=0;

intmin;

for（i=2;i<=n;i++）

{

min=cost[1][i];

for（j=1;j<=i-1;j++）

{

if（cost[j][i]!

=0&&m[j]+cost[j][i]

min=m[j]+cost[j][i];

}

m[i]=min;

}

cout<

}

return0;

}

5-6合唱队形问题

#include   

1.using namespace std;  

2.  

3.//用于保存子问题最优解的备忘录  

4.typedef struct    

5.{  

6.    int maxlen; //当前子问题最优解  

7.    int prev;   //构造该子问题所用到的下一级子问题序号（用于跟踪输出最优队列）  

8.}Memo;  

9.  

10.//用于递归输出Memo B中的解  

11.void Display（int* A, Memo* M, int i）  

12.{  

13.    if （M[i].prev == -1）  

14.    {  

15.        cout<

16.        return;  

17.    }  

18.    Display（A, M, M[i].prev）;  

19.    cout<

20.}  

21.  

22.//算法主要部分  

23.void GetBestQuence（int* A, int n）  

24.{  

25.    //定义备忘录 并作必要的初始化  

26.    Memo *B = new Memo[n];              //B[i]代表从A[0]到A[i]满足升序剔除部分元素后能得到的最多元素个数  

27.    Memo *C = new Memo[n];              //C[i]代表从A[i]到A[n-1]满足降序剔除部分元素后能得到的最多元素个数  

28.    B[0].maxlen = 1;        //由于B[i]由前向后构造 初始化最前面的子问题  （元素本身就是一个满足升序降序的序列）  

29.    C[n-1].maxlen = 1;      //同样C[i]由后向前构造  

30.    for （int i=0; i

31.                            //用于在跟踪路径时终止递归或迭代（因为我们并不知道最终队列从哪里开始）  

32.    {  

33.        B[i].prev = -1;  

34.        C[i].prev = -1;  

35.    }  

36.  

37.    for （i=1; i

38.    {  

39.        int max=1;  

40.        for （int j=i-1; j>=0; j--）               //查看前面的子问题 找出满足条件的最优解 并且记录  

41.        {  

42.            if （A[j]max）  

43.            {  

44.                max = B[j].maxlen+1;            //跟踪当前最优解  

45.                B[i].prev = j;                  //跟踪构造路径  

46.            }  

47.        }  

48.        B[i].maxlen = max;                      //构造最优解  

49.    }  

50.      

51.    for （i=n-1; i>0; i--）  

52.    {  

53.        int max=1;  

54.        for （int j=i; j

55.                            //否则我们得到的最优解始终为B[n-1]+C[n-1]  

56.        {  

57.            if （A[j]max）   //比当前长度更长 记录并构造  

58.            {  

59.                max = C[j].maxlen+1;  

60.                C[i].prev = j;  

61.            }  

62.        }  

63.        C[i].maxlen = max;  

64.    }  

65.  

66.    //遍历i 得到最大的B[i]+C[i]-1（-1是因为我们在B[i]和C[i]中 均加上了A[i]这个数 因此需要减去重复的）  

67.    int maxQuence = 0;  //记录当前最优解  

68.    int MostTall;       //记录i 用于跟踪构造路径   

69.    for （i=0; i

70.    {  

71.        if （B[i].maxlen+C[i].maxlen-1 > maxQuence）  

72.        {  

73.            maxQuence = B[i].maxlen+C[i].maxlen-1;  

74.            MostTall = i;  

75.        }  

76.    }  

77.      

78.    cout<<"最大合唱队形长度:

 "<

79.      

80.    //B由前向后构造 因此prev指向前面的元素 需要递归输出  

81.    Display（ A, B, MostTall）;  

82.    //C的prev指向后面元素 直接迭代输出  

83.    while （C[MostTall].prev !

= -1）  

84.    {  

85.        MostTall = C[MostTall].prev;  

86.        cout<

87.    }  

88.    cout<

89.      

90.    delete []B;  

91.    delete []C;  

92.}  

93.int main（）  

94.{  

95.    //测试  

96.    int *A;  

97.    int n;  

98.    cout<<"请输入合唱队员个数:

 "<

99.    cin>>n;  

100.  

101.    A = new int[n];  

102.    cout<<"输入队员身高 :

"<

103.    for （int i=0; i

104.    {  

105.        cin>>A[i];  

106.    }  

107.    GetBestQuence（A, n）;  

108.    delete []A;  

109.    return 0;  

110.}  

5-7买票问题

状态转移方程是f[i]:

=min（f[i-1]+t[i],f[i-2]+r[i-1]）;{i=2~n}

初值f[0]:

=0;f[1]:

=t[1];

const

maxn=1000;

vari,j,n:

longint;

f,t,r:

array[0..maxn]oflongint;

functionmin（a,b:

longint）:

longint;

beginifa

begin

readln（n）;

fori:

=1tondoread（t[i]）;

fori:

=1ton-1doread（r[i]）;

f[0]:

=0;f[1]:

=t[1];

fori:

=2tondo

f[i]:

=min（f[i-1]+t[i],f[i-2]+r[i-1]）;

writeln（f[n]）;

end.

伪代码

BuyTicks（T,R）

1n←length[T]

2f[0]←0

3f[1]←T[1]

4fori←2tondo

5f[i]←f[i-2]+R[i-1]

6iff[i]>f[i-1]+T[i]then

7f[i]←f[i-1]+T[i]

8returnf

5-8最大子段和问题

#include

#include

intmax_sum（intn,int*a,int*besti,int*bestj）{

int*b=（int*）malloc（n*sizeof（int））;

intsum=0;inti=-1;inttemp=0;

for（i=0;i<=n-1;i++）{

if（temp>0）

temp+=a[i];

else

temp=a[i];

b[i]=temp;

}

sum=b[0];

for（i=1;i<=n-1;i++）{

if（sum

sum=b[i];

*bestj=i;

}

}

for（i=*bestj;i>=0;i--）{

if（b[i]==a[i]）{

*besti=i;

break;

}

}

free（b）;

returnsum;

}

intmain（void）

{

inta[]={-2,1,-4,13,-5,-2,-10,20,100};

intlength=sizeof（a）/sizeof（int）;

intsum=-1;

intbesti=-1;

intbestj=-1;

sum=max_sum（length,a,&besti,&bestj）;

printf（"besti=%d,bestj=%d,max_sum=%d\n",besti,bestj,sum）;

return0;

}

5-9装箱问题

发现就是0-1背包问题每个物品的体积就是花费同时也是价值，也就是说这题可以转化为在总体积为w下，可以得到最大的价值最后用总体积减去最大的价值就是剩下最少的空间状态转移方程d[j]=max（d[j],d[j-a[i]]+a[i]）;

第二行为一个整数，表示有n个物品；

　　接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式　　一个整数，表示箱子剩余空间。

#include#include

usingnamespacestd;

intn;

intd[20005];

inta[35];

intmain（）{

    intw;

    scanf（"%d%d",&w,&n）;

    inti,j;

    for（i=0;i

        scanf（"%d",&a[i]）;

    }

    memset（d,0,sizeof（d））;

    for（i=0;i

        for（j=w;j>=a[i];j--）

            d[j]=max（d[j],d[j-a[i]]+a[i]）;

    }

    printf（"%d\n",w-d[w]）;

    return0;

}

6-10表格乘法

#include"stdio.h"#definenum50

voidchengji_1（int（*a）[num][3],intn,charb[]）;

int_tmain（）{

 inta[num][num][3];

 charb[num];

 inti,j,k,n;

 charc;

 printf（"intputthenumofarray:

"）;

 scanf（"%d",&n）;

 getchar（）;

 for（i=0;i

  for（j=0;j

   for（k=0;k<3;k++）

    a[i][j][k]=0;

 i=0;

 while（（c=getchar（））!

='/n'）

 {

  b[i]=c;i++;

 }

 chengji_1（a,n,b）;

 printf（"reslutis:

%d",a[0][n-1][0]）;

 getchar（）;

}

voidchengji_1（int（*a）[num][3],intn,charb[]）{

 inti,j,k,t;

 for（i=0;i

  *（*（*（a+i）+i）+（b[i]-'a'））=1;

 for（k=1;k

  for（i=0;i

  {

   j=i+k;

   for（t=i;t

   {

    *（*（*（a+i）+j）+0）+=（（*（*（*（a+i）+t）+0））*（*（*（*（a+t+1）+j）+2））+（*（*（*（a+i）+t）+1））*（*（*（*（a+t+1）+j）+2））+（*（*（*（a+i）+t）+2））*（*（*（*（a+t+1）+j）+0）））;

    *（*（*（a+i）+j）+1）+=（（*（*（*（a+i）+t）+0））*（*（*（*（a+t+1）+j）+0））+（*（*（*（a+i）+t）+0））*（*（*（*（a+t+1）+j）+1））+（*（*（*（a+i）+t）+1））*（*（*（*（a+t+1）+j）+1）））;

    *（*（*（a+i）+j）+2）+=（（*（*（*（a+i）+t）+1））*（*（*（*（a+t+1）+j）+0））+（*（*（*（a+i）+t）+2））*（*（*（*（a+t+1）+j）+1））+（*（*（*（a+i）+t）+2））*（*（*（*（a+t+1）+j）+2）））;

   } }

}

11最长滑雪道问题

#include

usingnamespacestd;

intdata[102][102],longetr[102][102];

intm,n;

intcal（inti,intj）{

intmax=0;

if（longetr[i][j]>0）

//如果该点已经计算过直接返回路径长度，保存已有的计算结果这是动态规划优越之处

returnlongetr[i][j];

if（j-1>=0&&data[i][j]>data[i][j-1]&&max

max=cal（i,j-1）;//向左走

if（j+1data[i][j+1]&&max

max=cal（i,j+1）;//向右走

if（i-1>=0&&data[i][j]