算法第三章作业

2018/11/10 20:09
阅读数 1.4K

算法第三章作业

如果一个问题可以用动态规划算法解决,则总是可以在多项式时间内解决的。

T         F

1-2

最优二叉搜索树的根结点一定存放的是搜索概率最高的那个关键字。

 F

1-3

用动态规划而非递归的方法去解决问题时,关键是将子问题的计算结果保存起来,使得每个不同的子问题只需要被计算一次。子问题的解可以被保存在数组或哈希散列表中。

T      

 

 

D、在动态规划中,我们要推导出一个子问题的解与其他子问题解的递推关系。要将这种关系转换为自底向上的动态规划算法,我们需要以正确的顺序填写子问题解的表格,使得在解任一子问题时,所有它需要的子问题都已经被解决了。在下列关系式中,哪一个是不可能被计算的? (2)

 

A(i,j)=min(A(i1,j),A(i,j1),A(i1,j1))

A(i,j)=F(A(min{i,j}1,min{i,j}1),A(max{i,j}1,max{i,j}1))

A(i,j)=F(A(i,j1),A(i1,j1),A(i1,j+1))

A(i,j)=F(A(i2,j2),A(i+2,j+2))

2-2

C、给定递推方程 f

i,j,k

​​ =f

i,j+1,k

​​ +min

0lk

​​ {f

i1,j,l

​​ +w

j,l

​​ }

D、要通过循环解此方程,我们一定不能用下列哪种方法填表? (2)

 

for k in 0 to n: for i in 0 to n: for j in n to 0

for i in 0 to n: for j in 0 to n: for k in 0 to n

for i in 0 to n: for j in n to 0: for k in n to 0

for i in 0 to n: for j in n to 0: for k in 0 to n

2-3

切原木问题:给定一根长度为N米的原木;另有一个分段价格表,给出长度L=1,2,,M对应的价格P

L

​​ 。要求你找出适当切割原木分段出售所能获得的最大收益R

N

​​ 。例如,根据下面给出的价格表,若要出售一段8米长的原木,最优解是将其切割为2米和6米的两段,这样可以获得最大收益R

8

​​ =P

2

​​ +P

6

​​ =5+17=22。而若要出售一段3米长的原木,最优解是根本不要切割,直接售出。

 

Length L 1 2 3 4 5 6 7 8 9 10

Price P

L

​​ 1 5 8 9 10 17 17 20 23 28

下列哪句陈述是错的?(3)

 

此问题可以用动态规划求解

NM,则有R

N

​​ =max{P

N

​​ ,max

1i<N

​​ {R

i

​​ +R

Ni

​​ }}

N>M,则有R

N

​​ =max

1i<N

 {Ri+RNM }算法的时间复杂度是O(N2 )

 

单调递增最长子序列

设计一个O(n2)时间的算法,找出由n个数组成的序列的最长单调递增子序列。

#include <iostream>

using  namespace std;

 

int dl(int a[], int b[],int n) {

      

  for (int i = 1; i < n; i++) {

 

for (int j = 0; j < i; j++)

{

if (a[j] < a[i]&& b[j]>b[i] - 1) {

b[i] = b[j] + 1;

}

}

}

    int t = b[1];

for (int  k = 0; k < n; k++)

{

           

 if (b[k] > t) {

 t = b[k];

 }

}

return t;

}

 

 

int main() {

int n;

cin >> n;

int *a = new int[n];

int *b = new int[n]();//置为0

for (int i = 0; i < n; i++) {

 

b[i]++;

}

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

cout << dl(a, b, n);

system("pause");

}

 

 租用游艇问题 17 分)

题目来源:王晓东,《算法设计与分析》

 

长江游艇俱乐部在长江上设置了n个游艇出租站12,…,n。游客可在这些游艇出租站租用游艇,并在下游的任何一个游艇出租站归还游艇。游艇出租站i到游艇出租站j之间的租金为r(i,j),1<=i<j<=n。试设计一个算法,计算出从游艇出租站1 到游艇出租站n所需的最少租金。

 

#include <iostream>

int dp[100][100];

int main()

{

int n;

scanf("%d",&n);

for(int i=1;i<n;i++)  

    {

    for(int j=i+1;j<=n;j++)

    {

scanf("%d",&dp[i][j]);

}

}

 

for(int k=2;k<n;k++)

{

for(int i=1;i<=n-k;i++)

{

int j=i+k;

for(int z=i+1;z<=j;z++)

{

int temp=dp[i][z]+dp[z][j];

if(dp[i][j]>temp)

dp[i][j]=temp;

}

}

}

 

printf("%d\n",dp[1][n]);

return 0;

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部