算法概论作业2.4

发表于 | 分类于

#6.1

1
2
3
4
5
1. 定义一维数组a[n]
2. 用dist[i]来存放到a[i]结尾的子序列的最大和
3. 求出dist[]中的最大值，即为最大连续子序列的和
4. 每次dist[i-1] + array[i] <= array[i]时，将begin = i；
5. 每次sum<dist[i]时，end = i；

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
int main()
{
  int array[n];
  srand((unsigned)time(NULL));
  for (int i = 0; i<n; i++)   //生成串
  {
      int temp = rand()%50-20;
      array[i] = temp;
      cout<<array[i]<<" ";
 }

 int dist[n] = {0};
 int sum = 0;
 int end;
 int begin;
 for (i = 1; i<n; i++)
 {
     if (dist[i-1] + array[i] > array[i])
     {
         dist[i] = dist[i-1]+array[i]; 
     }
     else
     {
         dist[i] = array[i];
         begin = i;  
     }
     if (sum<dist[i])
     {
         sum = dist[i];
         end = i;
     }
 }
 cout<<endl;
 cout<<”最大相连子序列：”;
 for(i = begin; i<=end ; i++)
 {
      cout<<array[i]<<” ”;
 }
 cout<<endl;
 cout<<"最大和为："<<sum<<endl;

 return 0;
}

#6.2
思想：

1
2
3
4
1. 设p[i]为停留在第i个旅店的总最小惩罚
2. 枚举上一个落脚点位置j，则有p[i] = min(p[j] + (200-(a[i] – a[j]))2)，并将min存放入容器route中，用于存放路径。
3. p[n]即为总最小惩罚。 
```

int main()
{
int array[n];
vector route;
srand((unsigned)time(NULL));
array[0] = 0;
for (int i = 1; i<n; i++) //随机产生英里数
{
int temp = rand()%100+10;
array[i] = temp;
cout<<array[i]<<” “;
}

int dist[n] = {0};
int min ;
for (i = 1; i<=n; i++)
{
    for(int j = 1 ; j<=i ;j++)  //枚举上一个落脚点位置j
    {    
        if (array[i]-array[j]<=200)  //行走距离不得超过200
        {
            if (dist[j] + (200-(array[i]-array[j])* (array[i]-array[j])) < dist[j-1] + (200-(array[i]-array[j-1])* (array[i]-array[j-1])))
            {
                dist[i] = dist[j] + (200-(array[i]-array[j])* (array[i]-array[j])); 
                min = j;
            }
        }
    }

    if (min>0 && min<n )   //保存路径
    {
        route.push_back(min);
    }
}
cout<<endl;
cout<<"总最小惩罚为："<<dist[n]<<endl;
for (i = 0; i< route.size()-1; i++)
{
    cout<<route[i]<<"->";
}
cout<<route[route.size()-1];
return 0;

}

1
2
3


#6.3
  1. 设r[i]表示前i个位置开分店的最大总利润，且r0 = 0;
  2. 若j为上一个满足mi-mj≥k的位置;
  3. 则ri = max{ri-1,rj+pi};
    若取rj+pi，说明要在i点建酒店，则将i放入容器route

  4. 最大总利润即为rn

    1
    代码如下：

    int main()
    {
    int m[n];//距离高速公路起点的距离
    int p[n];//可带来的利润
    int k = 50;
    vector route;
    srand((unsigned)time(NULL));
    m[0] = 0;
    p[0] = 0;
    int i,j = 0;
    for (i = 1; i<n; i++)
    {

    int temp  = rand()%100+20;
int temp2 = rand()%1000+100;
m[i] = m[i-1]+ temp;
p[i] = temp2;
cout<<i<<"  距离： "<<m[i]<<" 利润："<<p[i]<<endl;

    }

    int r[n] = {0};
    int max ;
    for (i = 1; i<=n; i++)
    {

    for(j = 0; j <= i; j++)//遍历之前的点
{
    if (m[i]-m[j]>=k)
    {
        if(r[i-1]>r[j]+p[i])
        {
            r[i] = r[i-1];
        }
        else
        {
            r[i] = r[j]+p[i];
            route.push_back(i);//将要建造的点入队
        }
    }
}

    }
    cout<<endl;
    cout<<r[n]<<endl;
    for (i = 1; i<route.size()-1;i++)//输出建造点
    {

    if (route[i]!=route[i-1])
{
    cout<<route[i]<<"->";
}

    }
    cout<<route[route.size()-1]<<endl;
    return 0;
    }

1
2

6.4
  1. 设vi表示前i个字符组成的子串能否被有效分割；
  2. dict[i][j] ==1 为从第i个元素到第j个元素课组成合法字符串；
  3. 若dict[j][i]==1 && v[j] == 1，则v[i] = 1，即前i个字符可被有效分割，并将j入队；
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    ```
        vector <int> route;
     	string s = "itwasthebest";
     	bool dict[n][n] = 
     	{{1,1,0,0,0,0,0,0,0,0,0,0},/*i*/
     	{0,0,0,0,0,0,0,0,0,0,0,0},/*t*/
     	{0,0,0,0,1,1,0,0,0,0,0,0},/*w*/
     	{0,0,0,1,1,0,0,0,0,0,0,0},/*a*/
     	{0,0,0,0,0,0,0,0,0,0,0,0},/*s*/
     	{0,0,0,0,0,0,0,1,0,0,0,0},/*t*/
     	{0,0,0,0,0,0,0,1,0,0,0,0},/*h*/
     	{0,0,0,0,0,0,0,0,0,0,0,0},/*e*/
     	{0,0,0,0,0,0,0,0,0,1,0,1},/*b*/
     	{0,0,0,0,0,0,0,0,0,0,0,0},/*e*/
     	{0,0,0,0,0,0,0,0,0,0,0,0},/*s*/
     	{0,0,0,0,0,0,0,0,0,0,0,0}};/*t*/
     	int v[n] = {1};
     	for (int i=0; i<n;i++)
     	{
     		for (int j=0; j<i; j++)
     		{
     			if (dict[j][i]==1 && v[j] == 1)
     			{
     				v[i] = 1;
     				route.push_back(j);
     			}
     		}
     	}
     	cout<<v[n-1]<<endl;
     	for (i = 0; i<route.size();i++)
     	{
     		cout<<route[i]<<"->";
     	}
     	cout<<endl;
     	return 0;