算法概论作业2.4

算法概论作业

6.1

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；

代码如下：

 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. 设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 <int> 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;
 }

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

代码如下：

 int main()
 {
    int m[n];//距离高速公路起点的距离
    int p[n];//可带来的利润
    int k  = 50;
    vector <int> 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;
 }

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入队；

    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;