算法分析上机作业

源码

最接近S的中位数的n/4个元素

给定由n个数组成的集合S，从中找出最接近S的中位数的n/4个元素。请设计一个最坏情况下时间复杂度为O(n)的算法。

算法实现代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <bits/stdc++.h>
using namespace std;

inline int Partition(vector<double>& a, int l, int r) {  // 快排的分割函数，使a[r]排定
  int x = a[r], i = l - 1;
  for (int j = l; j < r; ++j) {
    if (a[j] <= x) {
      swap(a[++i], a[j]);
    }
  }
  swap(a[i + 1], a[r]);
  return i + 1;
}
inline int RandomPartition(vector<double>& a, int l, int r) {  // 随机划分
  int i = rand() % (r - l + 1) + l;                            // 随机选择排定元素
  swap(a[i], a[r]);
  return Partition(a, l, r);
}

double QuickSelect(vector<double>& a, int l, int r, int index) {  // 选择函数
  int q = RandomPartition(a, l, r);
  if (q == index) {
    return a[q];
  }
  if (q < index) {
    return QuickSelect(a, q + 1, r, index);
  }
  return QuickSelect(a, l, q - 1, index);
}

inline int Partition(vector<double>& a, int low, int high, double x) {  //这里数组a是[low,high)的，注意右边界最多到a[high-1]，
  /*利用x将数组划分为2部分*/
  int i = low;
  high--;
  while (a[i] != x) i++;
  swap(a[low], a[i]);  //将基准移到首位置
  while (low < high) {
    while (low < high && a[high] >= x) high--;
    a[low] = a[high];
    while (low < high && a[low] <= x) low++;
    a[high] = a[low];
  }
  a[low] = x;
  return low;
}
double Select(vector<double>& a, int low, int high, int k) {
  int n = high - low;  // n为数组a[low...high]元素个数,注意右边最多取到a[high-1]
  if (n < 5) {         //元素小于5时候单独处理
    sort(a.begin() + low, a.begin() + high);
    return a[low + k - 1];
  }
  for (int i = 0; i < n / 5; i++) {
    sort(a.begin() + low + i * 5, a.begin() + low + i * 5 + 5);  //对每组数据排序
    swap(a[low + i], a[low + i * 5 + 2]);                        //中位数移到前面
  }
  double x = Select(a, low, low + n / 5, n / 10 + 1);  //寻找中位数的中位数、n/10+1非常重要，避免n<10时n/10==0此时会出现问题
  int j = Partition(a, low, high, x);                  //根据x将数组a划分为2部分，j为x所在数组下标
  int q = j - low + 1;                                 // q为小于或者等于x元素的个数
  if (q == k)
    return x;
  else if (q > k)
    return Select(a, low, j + 1, k);
  else
    return Select(a, j + 1, high, k - q);
}

double FindKthSmallest(vector<double> nums, int k) {  // 找到第k小的数（数组升序排定后a[k])
  // return QuickSelect(nums, 0, nums.size() - 1, k);
  return Select(nums, 0, nums.size(), k + 1);
}

vector<double> AlgorithmImpl(vector<double> data) {
  int size = static_cast<int>(data.size());
  int result_size = size / 4;
  vector<double> result;
  result.reserve(size);
  vector<double> diff;
  diff.reserve(size);

  double median = (FindKthSmallest(data, size / 2) + FindKthSmallest(data, (size - 1) / 2)) / 2;  // 计算中位数
  for (int num : data) {                                                                          // 计算各数与中位数中间差值的绝对值
    diff.emplace_back(abs(num - median));
  }
  double k_smallest_diff = FindKthSmallest(diff, result_size);  // 找到差值中第k小的数
  vector<double> k_smallest;
  for (int i = 0; i < size; i++) {
    if (diff[i] < k_smallest_diff) {  // 差值更小的数，加入结果集
      result.emplace_back(data[i]);
    }
    if (diff[i] == k_smallest_diff) {  // 记录差值刚好为第k小的数
      k_smallest.emplace_back(data[i]);
    }
  }
  int cnt = result_size - result.size();
  result.insert(result.end(), k_smallest.begin(), k_smallest.begin() + cnt);  // 加入差值恰好为第k小的数
  return result;
}

算法测试代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

// 生成测试数据，group为测试数据组数
vector<vector<double>> GenerateTestData(int group) {
  vector<vector<double>> res;
  int data_size;
  int rand_data;
  for (int i = 0; i < group; i++) {
    data_size = rand() % 20 + 10;  // 测试数据规模为10-30
    vector<double> tmp;
    tmp.reserve(data_size);
    for (int j = 0; j < data_size; j++) {
      rand_data = rand() % 100;  // 测试数据在0-100之间
      tmp.emplace_back(rand_data);
    }
    res.emplace_back(tmp);
  }
  return res;
}

// 输出提示信息与测试数据
void PrintInfo(const vector<double>& data, string info) {
  cout << info << endl;
  for (auto num : data) {
    cout << num << " ";
  }
  cout << endl;
}
double GetMedian(vector<double> data) {  // 获取数组中位数
  int size = static_cast<int>(data.size());
  sort(data.begin(), data.end());

  double median = (data[size / 2] + data[(size - 1) / 2]) / 2;
  return median;
}
// 获取测试数据与中位数相近的n/4个数，不考虑时间复杂度
vector<double> GetTestAnswer(vector<double> test_data) {
  int size = static_cast<int>(test_data.size());

  double median = GetMedian(test_data);
  auto compare_fun = [&](double n1, double n2) {  // 比较函数，离中位数越近则越靠前
    if (abs(n1 - median) < abs(n2 - median)) {
      return true;
    }
    return false;
  };
  sort(test_data.begin(), test_data.end(), compare_fun);                // 将数组按比较函数排定
  vector<double> res(test_data.begin(), test_data.begin() + size / 4);  // 选取前size / 4个数
  return res;
}

// 设计的算法实现
vector<double> AlgorithmImpl(vector<double> test_data);  // 函数声明

// 判断两种解法结果是否相同
bool IsEqual(vector<double> v1, vector<double> v2, double median) {
  int size = static_cast<int>(v1.size());
  vector<double> diff1;
  vector<double> diff2;
  diff1.reserve(size);
  diff2.reserve(size);
  for (int i = 0; i < size; i++) {
    diff1.emplace_back(abs(v1[i] - median));
    diff2.emplace_back(abs(v2[i] - median));
  }

  sort(diff1.begin(), diff1.end());
  sort(diff2.begin(), diff2.end());
  for (int i = 0; i < size; i++) {  // 判断两个解法的绝对差值是否一致（不要求元素一致）
    if (diff1[i] != diff2[i]) {
      return false;
    }
  }
  return true;
}

// 测试函数
void TestFunc() {
  int group = 1000;
  auto datas = GenerateTestData(group);  // 获取测试数据
  for (int i = 0; i < group; i++) {
    auto answer = GetTestAnswer(datas[i]);         // 获取正确结果
    auto algorithm_res = AlgorithmImpl(datas[i]);  // 获取算法结果
    double median = GetMedian(datas[i]);
    bool equal = IsEqual(answer, algorithm_res, median);  // 比较两结果
    if (equal == false) {
      cout << "************************" << endl;
      cout << "test failed" << endl;
    } else {
      cout << "************************" << endl;
      cout << "test success" << endl;
    }
    cout << "************************" << endl;
    PrintInfo(datas[i], "test data");
    cout << "data size:" << datas[i].size() << endl;
    cout << "median:" << median << endl;
    sort(datas[i].begin(), datas[i].end());
    PrintInfo(datas[i], "sorted test data");
    PrintInfo(answer, "answer");
    PrintInfo(algorithm_res, "my algorithm res");
  }
}
int main() {
  srand(time(0));  // 随机种子
  TestFunc();
}

不被任何其他点支配的点

给定二维平面上的n个点(x1,y1),(x2,y2),……,(xn,yn)，假定所有点之间的纵横坐标均不相同。对于任意两个点(xi,yi)和(xj,yj)，如果xi>xj且yi>yj，则称(xi,yi)支配(xj,yj)。不被任何其他点支配的点称为maxima。请设计一个贪心算法，能够在O(nlogn)时间内找出所有的maxima。

算法实现与测试代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

class Point {
 public:
  bool operator>(const Point& p) const {           // 重载大于运算符
    if (x_ > p.x_ || (x_ == p.x_ && y_ < p.y_)) {  // 特别注意的是x越大，y越小越在前列
      return true;
    }
    return false;
  }
  bool operator!=(const Point& p) const { return !(x_ == p.x_ && y_ == p.y_); }  // 重载!=运算符
  bool IsDominated(const Point& p) const {                                       // 该点是否被点p支配
    if (x_ < p.x_ && y_ < p.y_) {
      return true;
    }
    return false;
  }
  Point() = default;
  Point(int x, int y) : x_(x), y_(y) {}
  int x_;
  int y_;
};

vector<Point> FindMaximasUseGreed(vector<Point> points) {  // 使用贪婪算法找到所有maxima
  vector<Point> result;
  sort(points.begin(), points.end(), greater<Point>());  // 从大到小排序
  int max_y = -(1 << 30);                                // 记录遍历时出现的最大y值
  for (auto& p : points) {
    if (p.y_ >= max_y) {  // 不会被前面的点支配，其x又>=其后的点，故为maxima
      result.emplace_back(p);
      max_y = p.y_;
    }
  }
  return result;
}
vector<Point> FindMaximasUseEnumerate(vector<Point> points) {
  vector<Point> result;
  bool is_maxima;
  for (auto& p1 : points) {  // 两层循环遍历，找到所有可能点对
    is_maxima = true;
    for (auto& p2 : points) {
      if (p1.IsDominated(p2)) {  // p1被p2支配
        is_maxima = false;
        break;
      }
    }
    if (is_maxima) {
      result.emplace_back(p1);
    }
  }
  return result;
}
// 生成测试数据，group为测试数据组数
vector<vector<Point>> GenerateTestData(int group) {
  vector<vector<Point>> res;
  int data_size;
  int rand_data;
  int x, y;
  for (int i = 0; i < group; i++) {
    data_size = rand() % 20 + 10;  // 测试数据规模为10-30
    vector<Point> tmp;
    tmp.reserve(data_size);
    for (int j = 0; j < data_size; j++) {
      x = rand() % 100;  // 测试数据在0-100之间
      y = rand() % 100;  // 测试数据在0-100之间
      tmp.emplace_back(Point{x, y});
    }
    res.emplace_back(tmp);
  }
  return res;
}
bool IsEqual(vector<Point> p1, vector<Point> p2) {
  int size = static_cast<int>(p1.size());
  sort(p1.begin(), p1.end(), greater<Point>());
  sort(p2.begin(), p2.end(), greater<Point>());
  for (int i = 0; i < size; i++) {
    if (p1[i] != p2[i]) {
      return false;
    }
  }
  return true;
}
// 输出提示信息与测试数据
void PrintInfo(const vector<Point>& points, string info) {
  cout << info << endl;
  for (auto p : points) {
    printf("(%d,%d)", p.x_, p.y_);
  }
  cout << endl;
}
// 测试函数
void TestFunc() {
  int group = 1000;
  auto datas = GenerateTestData(group);  // 获取测试数据
  for (int i = 0; i < group; i++) {
    auto answer = FindMaximasUseEnumerate(datas[i]);     // 获取正确结果
    auto algorithm_res = FindMaximasUseGreed(datas[i]);  // 获取算法结果

    bool equal = IsEqual(answer, algorithm_res);  // 比较两结果
    if (equal == false) {
      cout << "************************" << endl;
      cout << "test failed" << endl;
    } else {
      cout << "************************" << endl;
      cout << "test success" << endl;
    }
    cout << "************************" << endl;
    PrintInfo(datas[i], "test data");
    cout << "data size:" << datas[i].size() << endl;
    sort(datas[i].begin(), datas[i].end(), greater<Point>());
    PrintInfo(datas[i], "sorted test data");
    PrintInfo(answer, "answer");
    PrintInfo(algorithm_res, "my algorithm res");
  }
}
int main() {
  srand(time(0));  // 随机种子
  TestFunc();
}

三序列最短公共超序列

设A[1…M],B[1…N],C[1…L]是三个任意序列，A、B、C的公共超序列定义为一个包含A、B、C为子序列的序列。请设计实现一个动态规划算法，找出A、B、C的最短公共超序列。

算法实现代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
#include <bits/stdc++.h>
using namespace std;
const int kInf = 1 << 20;  // 无穷大

int GetMinVal(vector<int> v) {  // 求序列最小值
  int min_val = *min_element(v.begin(), v.end());
  return min_val;
}

vector<vector<int>> GetStateMatrix(string s1, string s2) {  // 构建两个序列的最短公共超序列，返回dp数组
  int size1 = s1.size();
  int size2 = s2.size();
  int max_size = max(size1, size2) + 1;
  vector<vector<int>> dp(max_size, vector<int>(max_size, kInf));  // 将数组均设为正无穷
  for (int i = 0; i < max_size; i++) {                            // 设成初始值
    dp[i][0] = dp[0][i] = i;
  }
  for (int i = 1; i < size1; i++) {
    for (int j = 1; j < size2; j++) {
      if (s1[i] == s2[j]) {  // 字符相等时，多一种状态转移可能
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }
      dp[i][j] = GetMinVal({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i][j]});
    }
  }
  return dp;
}

string GetCommonSeqString(string s1, string s2, vector<vector<int>> dp, int start1, int start2) {  // 以dp数组重构公共超序列
  string ans;
  int i = start1;
  int j = start2;
  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i - 1][j - 1] + 1 && s1[i] == s2[j])  //相等时
    {
      ans.push_back(s1[i]);
      i--;
      j--;
    } else if (dp[i][j] == dp[i - 1][j] + 1)  //来自s1
    {
      ans.push_back(s1[i]);
      i--;
    } else if (dp[i][j] == dp[i][j - 1] + 1)  //来自s2
    {
      ans.push_back(s2[j]);
      j--;
    }
  }
  while (i > 0)  // s1未选完
  {
    ans.push_back(s1[i]);
    i--;
  }
  while (j > 0) {  // s2未选完
    ans.push_back(s2[j]);
    j--;
  }
  return ans;
}

string ShortestCommonSeqForThree(string s1, string s2, string s3) {  // 求三个的最短超序列
  int size1 = s1.size();
  int size2 = s2.size();
  int size3 = s3.size();
  // 在字符串前填充一个字符，使索引对齐
  s1 = '0' + s1;
  s2 = '0' + s2;
  s3 = '0' + s3;
  auto dp12 = GetStateMatrix(s1, s2);
  auto dp13 = GetStateMatrix(s1, s3);
  auto dp23 = GetStateMatrix(s2, s3);
  int max_size = max(max(size1, size2), size3) + 1;
  int dp[max_size][max_size][max_size];
  for (int i = 0; i <= size1; i++) {  // 将dp数组设置为正无穷，而后以两个序列的最短超序列初始化dp数组
    for (int j = 0; j <= size2; j++) {
      for (int k = 0; k <= size3; k++) {
        dp[i][j][k] = kInf;
        if (i == 0) {
          dp[i][j][k] = dp23[j][k];
        } else if (j == 0) {
          dp[i][j][k] = dp13[i][k];
        } else if (k == 0) {
          dp[i][j][k] = dp12[i][j];
        }
      }
    }
  }
  for (int i = 1; i <= size1; i++) {  // 关键代码：状态转移，总共有7种状态转移可能
    for (int j = 1; j <= size2; j++) {
      for (int k = 1; k <= size3; k++) {
        if (s1[i] == s2[j] && s1[i] == s3[k]) {  // 三个字母均相等
          dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
        }
        if (s1[i] == s2[j]) {  // 两个字母相等
          dp[i][j][k] = min(dp[i - 1][j - 1][k] + 1, dp[i][j][k]);
        }
        if (s1[i] == s3[k]) {  // 两个字母相等
          dp[i][j][k] = min(dp[i - 1][j][k - 1] + 1, dp[i][j][k]);
        }
        if (s2[j] == s3[k]) {  // 两个字母相等
          dp[i][j][k] = min(dp[i][j - 1][k - 1] + 1, dp[i][j][k]);
        }
        dp[i][j][k] = GetMinVal({dp[i - 1][j][k] + 1, dp[i][j - 1][k] + 1, dp[i][j][k - 1] + 1, dp[i][j][k]});  // 选取状态转移后最小值
      }
    }
  }
  int i = size1;
  int j = size2;
  int k = size3;

  string ans;
  while (i > 0 && j > 0 && k > 0) {  // 反向重构最短超序列
    if (dp[i][j][k] == dp[i - 1][j - 1][k - 1] + 1 && (s1[i] == s2[j] && s1[i] == s3[k])) {
      ans.push_back(s1[i]);
      i--;
      j--;
      k--;
    } else if (dp[i][j][k] == dp[i - 1][j - 1][k] + 1 && s1[i] == s2[j]) {
      ans.push_back(s1[i]);
      i--;
      j--;

    } else if (dp[i][j][k] == dp[i - 1][j][k - 1] + 1 && s1[i] == s3[k]) {
      ans.push_back(s1[i]);
      i--;
      k--;
    } else if (dp[i][j][k] == dp[i][j - 1][k - 1] + 1 && s2[j] == s3[k]) {
      ans.push_back(s2[j]);
      j--;
      k--;
    } else {
      int min_val = GetMinVal({dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]});
      if (dp[i - 1][j][k] == min_val) {
        ans.push_back(s1[i]);
        i--;
      } else if (dp[i][j - 1][k] == min_val) {
        ans.push_back(s2[j]);
        j--;
      } else {
        ans.push_back(s3[k]);
        k--;
      }
    }
  }
  if (i == 0) {  // 一个序列为空，使用两序列方法重构超序列
    ans.append(GetCommonSeqString(s2, s3, dp23, j, k));
  } else if (j == 0) {
    ans.append(GetCommonSeqString(s1, s3, dp13, i, k));
  } else if (k == 0) {
    ans.append(GetCommonSeqString(s1, s2, dp12, i, j));
  }

  // for (int i = 0; i <= size1; i++) {
  //   for (int j = 0; j <= size2; j++) {
  //     for (int k = 0; k <= size3; k++) {
  //       cout << i << j << k << " " << dp[i][j][k] << endl;
  //     }
  //   }
  // }
  reverse(ans.begin(), ans.end());  // 将结果翻转，得到最终超序列
  return ans;
}

算法测试代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
string ShortestCommonSeqForThree(string s1, string s2, string s3);  // 函数声明

string MergeSubsequence(string s) {  // 序列归并，将临近相同的字符合并成一个字符
  string ans;
  char last = '\0';
  for (auto c : s) {
    if (c != last) {
      last = c;
      ans.push_back(c);
    }
  }
  return ans;
}

bool IsSubsequence(string str, string sub) {  // 一个字符串是否为另一个字符串的子序列
  int len = sub.length();
  int i = 0;
  bool flag = false;
  for (auto& c : str) {
    if (sub[i] == c) {
      i++;
    }
    if (i == len) {
      flag = true;
      break;
    }
  }
  return flag;
}
// 字符串是否为三个字符串的公共超序列
bool IsAllSubsequence(string str, string sub1, string sub2, string sub3) { return IsSubsequence(str, sub1) && IsSubsequence(str, sub2) && IsSubsequence(str, sub3); }

void GetPossibleSequence(vector<string>& res, string s, int start, int end) {  // 得到所有可能的排列方式
  if (start == end) {
    res.emplace_back(s);
  } else {
    for (int i = start; i <= end; i++) {
      swap(s[start], s[i]);  // 交换序列首部
      GetPossibleSequence(res, s, start + 1, end);
      swap(s[i], s[start]);  // 还原顺序
    }
  }
}

string SubsequenceEnumeration(string s1, string s2, string s3) {  // 使用枚举法找到最短公共超序列
  string s = s1 + s2 + s3;
  vector<string> sequence;
  GetPossibleSequence(sequence, s, 0, s.length() - 1);  // 找到所有可能排列可能(9个字符36280种可能排列)
  int min_len = s.length();
  string min_common_seq = "";
  for (auto& seq : sequence) {
    seq = MergeSubsequence(seq);              // 序列归并
    if (IsAllSubsequence(seq, s1, s2, s3)) {  // 恰好为公共超序列
      if (seq.length() < min_len) {
        min_common_seq = seq;
        min_len = seq.length();
      }
    }
  }
  return min_common_seq;
}

std::string RandString() {
  int len = 3;  // 字符串长度需设小，避免枚举时间过长
  std::string str;
  char c;
  /*循环向字符串中添加随机生成的字符*/
  for (int i = 0; i < len; i++) {
    c = 'a' + rand() % 6;  // 字母可能为abcdef
    str.push_back(c);
  }
  return str;
}

void TestFunc() {
  int times = 10;
  for (int i = 0; i < times; i++) {
    string s1 = RandString();
    string s2 = RandString();
    string s3 = RandString();
    cout << "test data " << endl << s1 << " " << s2 << " " << s3 << endl;
    string ans = SubsequenceEnumeration(s1, s2, s3);        // 枚举答案
    string my_ans = ShortestCommonSeqForThree(s1, s2, s3);  // 算法答案
    if (!IsAllSubsequence(ans, s1, s2, s3)) {               // 是否为公共超序列
      cout << "something worng" << endl;
    }
    if (!IsAllSubsequence(my_ans, s1, s2, s3)) {  // 是否为公共超序列
      cout << "not common sequence" << endl;
    }
    cout << "answer:    " << ans << endl;
    cout << "my answer: " << my_ans << endl;
    cout << "seq length: " << ans.length() << endl;
    if (ans.length() < my_ans.length()) {  // 长度是否一致
      cout << "test failed" << endl;
    }
  }
}
int main() {
  TestFunc();
  return 0;
}

用给定的整数和运算符生成一个算术表达式

设有a,b,c,d,e五个整数和+,-,*,/四个运算符。对于任意给定的整数n，请设计一个算法，用给定的5整数和运算符生成一个算术表达式（每个整数和每个运算法只使用1次），使其运算结果等于n。

算法实现与测试代码

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <bits/stdc++.h>
using namespace std;

enum Operator { kAdd, kSub, kMul, kDiv };
double Calculate(double lhs, double rhs, Operator op) {  // 计算简单表达式
  double ans;
  switch (op) {
    case kAdd:
      return lhs + rhs;
    case kSub:
      return lhs - rhs;
    case kMul:
      return lhs * rhs;
    case kDiv:
      return lhs / rhs;
  }
  return -1;
}

double CalculateExpr(vector<double> num, vector<Operator> ops) {  // 计算复杂表达式
  stack<double> num_stack;
  stack<Operator> op_stack;
  double lhs;
  double rhs;
  double res;
  Operator op;
  num_stack.emplace(num[0]);
  int size = num.size();
  for (double i = 0; i < size - 1; i++) {
    if (ops[i] == kMul || ops[i] == kDiv) {  // 若为乘除，直接计算
      lhs = num_stack.top();
      num_stack.pop();
      rhs = num[i + 1];
      res = Calculate(lhs, rhs, ops[i]);
      num_stack.emplace(res);
    } else {  // 若为加减，先入栈
      num_stack.emplace(num[i + 1]);
      op_stack.emplace(ops[i]);
    }
  }
  while (!op_stack.empty()) {  // 将符号栈的操作符一一弹出，进行计算
    op = op_stack.top();
    op_stack.pop();
    rhs = num_stack.top();
    num_stack.pop();
    lhs = num_stack.top();
    num_stack.pop();
    res = Calculate(lhs, rhs, op);
    num_stack.emplace(res);
  }
  return num_stack.top();  // 得到表达式最终结果
}
template <typename T>
void GetPossibleSequence(vector<vector<T>>& res, vector<T> seq, int start, int end) {  // 得到所有可能的排列方式
  if (start == end) {
    res.emplace_back(seq);
  } else {
    for (int i = start; i <= end; i++) {
      swap(seq[start], seq[i]);  // 交换序列首部
      GetPossibleSequence(res, seq, start + 1, end);
      swap(seq[i], seq[start]);  // 还原顺序
    }
  }
}
void PrintExpr(vector<double> num, vector<Operator> ops) {  // 输出表达式
  int size = ops.size();
  for (int i = 0; i < size; i++) {
    cout << " " << num[i] << " ";
    switch (ops[i]) {
      case kAdd:
        cout << '+';
        break;
      case kSub:
        cout << '-';
        break;
      case kMul:
        cout << '*';
        break;
      case kDiv:
        cout << '/';
        break;
    }
  }
  cout << " " << num[size] << " " << endl;
}
void GetExpr(vector<double> num, int n) {
  vector<vector<double>> possible_nums;
  vector<vector<Operator>> possible_ops;
  vector<Operator> operators = {kAdd, kSub, kMul, kDiv};
  GetPossibleSequence(possible_nums, num, 0, num.size() - 1);             // 得到可能的数字排列集合
  GetPossibleSequence(possible_ops, operators, 0, operators.size() - 1);  // 得到可能的运算符排列集合
  bool find = false;
  for (auto& nums : possible_nums) {  // 双重循环，计算所有可能的表达式
    for (auto& ops : possible_ops) {
      double res = CalculateExpr(nums, ops);
      if (res == n) {  // 若与目标值一致，输出表达式
        PrintExpr(nums, ops);
        find = true;
      }
    }
  }
  if (!find) {  // 未找到相应的表达式
    cout << "No suitable expression was found" << endl;
  }
}
int main() {
  cout << 17 << endl;
  GetExpr({1, 2, 3, 4, 5}, 17);
  cout << 19 << endl;
  GetExpr({1, 2, 3, 4, 5}, 19);
  cout << 38 << endl;
  GetExpr({1, 2, 3, 4, 5}, 38);
  return 0;
}

实验报告

最接近S的中位数

问题描述

给定由n个数组成的集合S，从中找出最接近S的中位数的n/4个元素。请设计一个最坏情况下时间复杂度为O(n)的算法。

问题分析

解决这个问题之前需要先找到线性时间内解决选择问题（在n个数中选择第k个顺序统计量）的算法，而算法导论中已经给出了期望时间为线性的选择算法和最坏情况下为线性的选择算法。在假设已经获得线性选择算法后只需计算集合的中位数，而后计算集合中各元素与中位数的绝对差值，找到绝对差值第n/4小的数，选择绝对差值小于该数的元素即可。

算法设计与实现

选择算法

《算法导论》第九章中位数与顺序统计学中给出了两种选择算法。第一种算法使用了快排的划分算法，快速排序递归地处理划分的两边，而选择算法只需处理划分的一边。其代码实现如下：

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
inline int Partition(vector<double>& a, int l, int r) {  // 快排的分割函数，使a[r]排定
  int x = a[r], i = l - 1;
  for (int j = l; j < r; ++j) {
    if (a[j] <= x) {
      swap(a[++i], a[j]);
    }
  }
  swap(a[i + 1], a[r]);
  return i + 1;
}
inline int RandomPartition(vector<double>& a, int l, int r) {  // 随机划分
  int i = rand() % (r - l + 1) + l;                            // 随机选择排定元素
  swap(a[i], a[r]);
  return Partition(a, l, r);
}

double QuickSelect(vector<double>& a, int l, int r, int index) {  // 选择函数
  int q = RandomPartition(a, l, r);
  if (q == index) {
    return a[q];
  }
  if (q < index) {
    return QuickSelect(a, q + 1, r, index);
  }
  return QuickSelect(a, l, q - 1, index);
}

第二种算法为最坏情况下为线性时间的选择算法。

Step 1：把数组划分为若干个子数组，每个子数组里包含5个数，因为会有无法整除的可能，所以最后一个子数组会小于5.

Step 2：用插入排序把这5个数排序，然后找出中位数，也就是第3个。

Step 3：把获得的中位数又排序（这个地方错误，不是排序，应该递归调用SELECT），找出中位数的中位数x（如果有偶数个中位数，为了方便，约定ｘ是较小的中位数）。

Step 4：把原来的数组使用类似快排的方法，分成两个部分。让ｋ比划分的低区中的元素数目多１，因此ｘ是第ｋ小元素，并且有ｎ-ｋ个元素在划分的高区.

Step 5：如果i =ｋ，返回ｘ。如果 i < k， 则在低区递归调用来找出第ｉ小的元素．如果ｉ> ｋ，则在高区递归查找第ｉ- ｋ小的元素．

整个过程中，第1,2,4步所需时间为O(n)， 注意第2步的复杂度不为O(n^2)，第3步的复杂度为 T(n/5)，第五步的复杂度为 T(7n/10)。

注意这里第2步虽然我们使用的是插入排序，但是待排的序列长度为常数5，所以对一组的排序时间花费为O(1),对于n/5个组,其时间预期是O(n/5),即O(n)。

时间预期为：

​ T(n) <= T( n/5 ) + T(7n/10+6) + O(n)

其代码实现如下：

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
//这里数组a是[low,high)的，注意右边界最多到a[high-1]
inline int Partition(vector<double>& a, int low, int high, double x) {  
  /*利用x将数组划分为2部分*/
  int i = low;
  high--;
  while (a[i] != x) i++;
  swap(a[low], a[i]);  //将基准移到首位置
  while (low < high) {
    while (low < high && a[high] >= x) high--;
    a[low] = a[high];
    while (low < high && a[low] <= x) low++;
    a[high] = a[low];
  }
  a[low] = x;
  return low;
}
double Select(vector<double>& a, int low, int high, int k) {
  int n = high - low;  // n为数组a[low...high]元素个数,注意右边最多取到a[high-1]
  if (n < 5) {         //元素小于5时候单独处理
    sort(a.begin() + low, a.begin() + high);
    return a[low + k - 1];
  }
  for (int i = 0; i < n / 5; i++) {
    sort(a.begin() + low + i * 5, a.begin() + low + i * 5 + 5);  //对每组数据排序
    swap(a[low + i], a[low + i * 5 + 2]);                        //中位数移到前面
  }
  //寻找中位数的中位数、n/10+1非常重要，避免n<10时n/10==0此时会出现问题
  double x = Select(a, low, low + n / 5, n / 10 + 1); 
  int j = Partition(a, low, high, x);                  //根据x将数组a划分为2部分，j为x所在数组下标
  int q = j - low + 1;                                 // q为小于或者等于x元素的个数
  if (q == k)
    return x;
  else if (q > k)
    return Select(a, low, j + 1, k);
  else
    return Select(a, j + 1, high, k - q);
}

选择问题：

1
2
3
4
double FindKthSmallest(vector<double> nums, int k) {  // 找到第k小的数（数组升序排定后a[k])
  // return QuickSelect(nums, 0, nums.size() - 1, k);
  return Select(nums, 0, nums.size(), k + 1);
}

最接近S的中位数的n/4个元素

在实现选择算法之后，找到集合中的中位数，而后计算各元素与中位数之间的绝对差值。找到差值集合中第n/4的差值（设为diff），将差值小于diff的元素加入结果集合。这个部分需要注意的地方有两点：

1：由于中位数可能是小数，所以使用浮点数存储元素。

2：如果最终结果集合的数目小于n/4，则需要加入差值恰好为diff的元素

算法调用了3次选择算法，遍历了两次S集合，故算法的时间复杂度为O(n)。

代码实现如下：

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
vector<double> AlgorithmImpl(vector<double> data) {
  int size = static_cast<int>(data.size());
  int result_size = size / 4;
  vector<double> result;
  result.reserve(size);
  vector<double> diff;
  diff.reserve(size);
    
  // 计算中位数
  double median = (FindKthSmallest(data, size / 2) + FindKthSmallest(data, (size - 1) / 2)) / 2;  
  for (int num : data) {             
    diff.emplace_back(abs(num - median)); // 计算各数与中位数中间差值的绝对值
  }
  double k_smallest_diff = FindKthSmallest(diff, result_size);  // 找到差值中第k小的数
  vector<double> k_smallest;
  for (int i = 0; i < size; i++) {
    if (diff[i] < k_smallest_diff) {  // 差值更小的数，加入结果集
      result.emplace_back(data[i]);
    }
    if (diff[i] == k_smallest_diff) {  // 记录差值刚好为第k小的数
      k_smallest.emplace_back(data[i]);
    }
  }
  int cnt = result_size - result.size();
  result.insert(result.end(), k_smallest.begin(), k_smallest.begin() + cnt);  // 加入差值恰好为第k小的数
  return result;
}

算法测试

为验证算法的正确性，对算法进行测试。测试数据的大小与规模随机选择，将测试数据以元素与中位数的绝对差值的大小进行排序，得出结果集。将排序算法得出的结果集与设计的算法得出的结果集进行比对。需要注意的是，这两个算法得出的结果不一定完全一致，因为如果两个数与中位数的距离一样，则选取任意一个都是正确的。只需要其绝对差值完全一致即可！

其代码实现如下：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
// 生成测试数据，group为测试数据组数
vector<vector<double>> GenerateTestData(int group) {
  vector<vector<double>> res;
  int data_size;
  int rand_data;
  for (int i = 0; i < group; i++) {
    data_size = rand() % 20 + 10;  // 测试数据规模为10-30
    vector<double> tmp;
    tmp.reserve(data_size);
    for (int j = 0; j < data_size; j++) {
      rand_data = rand() % 100;  // 测试数据在0-100之间
      tmp.emplace_back(rand_data);
    }
    res.emplace_back(tmp);
  }
  return res;
}

// 输出提示信息与测试数据
void PrintInfo(const vector<double>& data, string info) {
  cout << info << endl;
  for (auto num : data) {
    cout << num << " ";
  }
  cout << endl;
}
// 获取数组中位数
double GetMedian(vector<double> data) {  
  int size = static_cast<int>(data.size());
  sort(data.begin(), data.end());

  double median = (data[size / 2] + data[(size - 1) / 2]) / 2;
  return median;
}
// 获取测试数据与中位数相近的n/4个数，不考虑时间复杂度
vector<double> GetTestAnswer(vector<double> test_data) {
  int size = static_cast<int>(test_data.size());

  double median = GetMedian(test_data);
  auto compare_fun = [&](double n1, double n2) {  // 比较函数，离中位数越近则越靠前
    if (abs(n1 - median) < abs(n2 - median)) {
      return true;
    }
    return false;
  };
  sort(test_data.begin(), test_data.end(), compare_fun);                // 将数组按比较函数排定
  vector<double> res(test_data.begin(), test_data.begin() + size / 4);  // 选取前size / 4个数
  return res;
}

// 设计的算法实现
vector<double> AlgorithmImpl(vector<double> test_data);  // 函数声明

// 判断两种解法结果是否相同
bool IsEqual(vector<double> v1, vector<double> v2, double median) {
  int size = static_cast<int>(v1.size());
  vector<double> diff1;
  vector<double> diff2;
  diff1.reserve(size);
  diff2.reserve(size);
  for (int i = 0; i < size; i++) {
    diff1.emplace_back(abs(v1[i] - median));
    diff2.emplace_back(abs(v2[i] - median));
  }

  sort(diff1.begin(), diff1.end());
  sort(diff2.begin(), diff2.end());
  for (int i = 0; i < size; i++) {  // 判断两个解法的绝对差值是否一致（不要求元素一致）
    if (diff1[i] != diff2[i]) {
      return false;
    }
  }
  return true;
}

// 测试函数
void TestFunc() {
  int group = 1000;					   // 测试数据组数
  auto datas = GenerateTestData(group);  // 获取测试数据
  for (int i = 0; i < group; i++) {
    auto answer = GetTestAnswer(datas[i]);         // 获取正确结果
    auto algorithm_res = AlgorithmImpl(datas[i]);  // 获取算法结果
    double median = GetMedian(datas[i]);
    bool equal = IsEqual(answer, algorithm_res, median);  // 比较两结果
    if (equal == false) {
      cout << "************************" << endl;
      cout << "test failed" << endl;
    } else {
      cout << "************************" << endl;
      cout << "test success" << endl;
    }
    cout << "************************" << endl;
    PrintInfo(datas[i], "test data");
    cout << "data size:" << datas[i].size() << endl;
    cout << "median:" << median << endl;
    sort(datas[i].begin(), datas[i].end());
    PrintInfo(datas[i], "sorted test data");
    PrintInfo(answer, "answer");
    PrintInfo(algorithm_res, "my algorithm res");
  }
}

测试1000组数据均通过，一定程度上证明了算法的正确性。部分测试结果如下：

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
44
45
46
47
48
49
50
51
52
************************
test success
************************
test data
79 3 98 4 65 88 16 75 7 42 76 71 44 97 45 95 41 15 59 99 37 90 26 
data size:23
median:59
sorted test data
3 4 7 15 16 26 37 41 42 44 45 59 65 71 75 76 79 88 90 95 97 98 99 
answer
59 65 71 45 44 
my algorithm res
65 71 44 45 59 
************************
test success
************************
test data
60 57 78 36 11 88 41 90 44 40 46 9 80 14 36 40 
data size:16
median:42.5
sorted test data
9 11 14 36 36 40 40 41 44 46 57 60 78 80 88 90 
answer
41 44 40 40 
my algorithm res
41 44 40 40 
************************
test success
************************
test data
64 11 5 14 56 0 7 23 60 6 12 2 32 79 62 42 9 50 53 
data size:19
median:23
sorted test data
0 2 5 6 7 9 11 12 14 23 32 42 50 53 56 60 62 64 79 
answer
23 14 32 12 
my algorithm res
14 23 12 32 
************************
test success
************************
test data
44 95 94 36 93 55 16 7 43 56 68 8 67 74 22 75 74 81 99 86 
data size:20
median:67.5
sorted test data
7 8 16 22 36 43 44 55 56 67 68 74 74 75 81 86 93 94 95 99 
answer
67 68 74 74 75 
my algorithm res
68 67 74 75 74

不被任何其他点支配的点

问题描述

给定二维平面上的n个点(x1,y1),(x2,y2),……,(xn,yn)，假定所有点之间的纵横坐标均不相同。对于任意两个点(xi,yi)和(xj,yj)，如果xi>xj且yi>yj，则称(xi,yi)支配(xj,yj)。不被任何其他点支配的点称为maxima。请设计一个贪心算法，能够在O(nlogn)时间内找出所有的maxima。

算法实现与测试

本实验较为简单，故简要介绍即可。我设计的算法步骤如下：将各点以横坐标为主序从大到小排序，而后顺序遍历，遍历时中记录出现的最大纵坐标，若某点纵坐标大于等于最大纵坐标，则将该点加入结果集合。以下对算法进行进一步说明：

第一步：排序以横坐标为主序，纵坐标为次序，需特别注意的是，==横坐标越大越靠前，而纵坐标越大则越靠后==。这是因为某点不会被和它横坐标或纵坐标相同的点所支配，若纵坐标越大越靠前，若两个点横坐标相同，纵坐标不同，纵坐标较小的点就永远不会被选中。

第二步：遍历需考虑与最大纵坐标相等的点，这与上述理由一致。

该算法之所以正确是因为当某点的纵坐标大于或等于前面点的最大纵坐标时，它就不会被前面的点支配，而其横坐标是大于或等于其后的点的，故它也不会被其后的点支配。假如某点不满足该性质，也就是说它的纵坐标小于前面点的最大纵坐标，则它一定会被最大纵坐标的那个点所支配，它就不可能是maxima。由此可以证明算法可以恰好找到所有的maxima。

以下为代码实现：

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
class Point {
 public:
  bool operator>(const Point& p) const {           // 重载大于运算符
    if (x_ > p.x_ || (x_ == p.x_ && y_ < p.y_)) {  // 特别注意的是x越大，y越小越在前列
      return true;
    }
    return false;
  }
  bool operator!=(const Point& p) const { return !(x_ == p.x_ && y_ == p.y_); }  // 重载不等于运算符
  bool IsDominated(const Point& p) const {                                       // 该点是否被点p支配
    if (x_ < p.x_ && y_ < p.y_) {
      return true;
    }
    return false;
  }
  Point() = default;
  Point(int x, int y) : x_(x), y_(y) {}
  int x_;
  int y_;
};

vector<Point> FindMaximasUseGreed(vector<Point> points) {  // 使用贪婪算法找到所有maxima
  vector<Point> result;
  sort(points.begin(), points.end(), greater<Point>());  // 从大到小排序
  int max_y = -(1 << 30);                                // 记录遍历时出现的最大y值
  for (auto& p : points) {
    if (p.y_ >= max_y) {  // 不会被前面的点支配，其横坐标又大于等于其后的点，故为maxima
      result.emplace_back(p);
      max_y = p.y_;
    }
  }
  return result;
}

其测试方法实现也非常简单，直接枚举所有的点对，不被任何点支配的即为maxima

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<Point> FindMaximasUseEnumerate(vector<Point> points) {
  vector<Point> result;
  bool is_maxima;
  for (auto& p1 : points) {  // 两层循环遍历，找到所有可能点对
    is_maxima = true;
    for (auto& p2 : points) {
      if (p1.IsDominated(p2)) {  // p1被p2支配
        is_maxima = false;
        break;
      }
    }
    if (is_maxima) {
      result.emplace_back(p1);
    }
  }
  return result;
}

算法测试代码与实验一类似

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 生成测试数据，group为测试数据组数
vector<vector<Point>> GenerateTestData(int group) {
  vector<vector<Point>> res;
  int data_size;
  int rand_data;
  int x, y;
  for (int i = 0; i < group; i++) {
    data_size = rand() % 20 + 10;  // 测试数据规模为10-30
    vector<Point> tmp;
    tmp.reserve(data_size);
    for (int j = 0; j < data_size; j++) {
      x = rand() % 100;  // 测试数据在0-100之间
      y = rand() % 100;  // 测试数据在0-100之间
      tmp.emplace_back(Point{x, y});
    }
    res.emplace_back(tmp);
  }
  return res;
}
bool IsEqual(vector<Point> p1, vector<Point> p2) {
  int size = static_cast<int>(p1.size());
  sort(p1.begin(), p1.end(), greater<Point>());
  sort(p2.begin(), p2.end(), greater<Point>());
  for (int i = 0; i < size; i++) {
    if (p1[i] != p2[i]) {
      return false;
    }
  }
  return true;
}
// 输出提示信息与测试数据
void PrintInfo(const vector<Point>& points, string info) {
  cout << info << endl;
  for (auto p : points) {
    printf("(%d,%d)", p.x_, p.y_);
  }
  cout << endl;
}
// 测试函数
void TestFunc() {
  int group = 1000;
  auto datas = GenerateTestData(group);  // 获取测试数据
  for (int i = 0; i < group; i++) {
    auto answer = FindMaximasUseEnumerate(datas[i]);     // 获取正确结果
    auto algorithm_res = FindMaximasUseGreed(datas[i]);  // 获取算法结果

    bool equal = IsEqual(answer, algorithm_res);  // 比较两结果
    if (equal == false) {
      cout << "************************" << endl;
      cout << "test failed" << endl;
    } else {
      cout << "************************" << endl;
      cout << "test success" << endl;
    }
    cout << "************************" << endl;
    PrintInfo(datas[i], "test data");
    cout << "data size:" << datas[i].size() << endl;
    sort(datas[i].begin(), datas[i].end(), greater<Point>());
    PrintInfo(datas[i], "sorted test data");
    PrintInfo(answer, "answer");
    PrintInfo(algorithm_res, "my algorithm res");
  }
}

部分测试结果如下：

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
************************
test success
************************
test data
(57,91)(90,23)(50,59)(14,52)(37,90)(6,7)(13,25)(25,89)(56,54)(72,17)(68,51)
data size:11
sorted test data
(90,23)(72,17)(68,51)(57,91)(56,54)(50,59)(37,90)(25,89)(14,52)(13,25)(6,7)
answer
(57,91)(90,23)(68,51)
my algorithm res
(90,23)(68,51)(57,91)
************************
test success
************************
test data
(18,36)(14,54)(53,27)(46,55)(37,90)(97,60)(92,56)(75,44)(93,17)(2,0)(30,28)(78,19)(36,84)
data size:13
sorted test data
(97,60)(93,17)(92,56)(78,19)(75,44)(53,27)(46,55)(37,90)(36,84)(30,28)(18,36)(14,54)(2,0)
answer
(37,90)(97,60)
my algorithm res
(97,60)(37,90)
************************
test success
************************
test data
(54,52)(46,69)(23,82)(83,77)(88,10)(76,95)(99,66)(92,60)(58,48)(87,54)(94,56)(56,46)(86,36)
data size:13
sorted test data
(99,66)(94,56)(92,60)(88,10)(87,54)(86,36)(83,77)(76,95)(58,48)(56,46)(54,52)(46,69)(23,82)
answer
(83,77)(76,95)(99,66)
my algorithm res
(99,66)(83,77)(76,95)

三序列最短公共超序列

问题描述

设A[1..M], B[1..N],C[1..L]是三个任意序列，A、B、C的公共超序列定义为一个包含A、B、C为子序列的序列。请设计实现一个动态规划算法，找出A、B、C的最短公共超序列。

问题分析

解决三个序列的算法较为复杂，先简要分析两个序列的最短超序列。使用dp[i][j]表示两序列长度分别为i j时最短公共序列长度，两个序列的最短超序列问题的状态转移来源只有两个：s1[i] == s2[j] 与 s1[i] != s2[j]，如果两字符相等，此时只需填充一个字符，dp[i][j]可由dp[i-1][j-1]转移而来，若s1[i] != s2[j] 时，则只能有dp[i-1][j]或dp[i][j]转移而来

代码表示如下如下：

1
2
3
4
if (s1[i] == s2[j]) {  // 字符相等时，多一种状态转移可能
    dp[i][j] = dp[i - 1][j - 1] + 1;
}
dp[i][j] = GetMinVal({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i][j]});

与之类似的，三个序列的状态转移来源有7个。分别为三个字符均相等，两个字符相等（3个），三个字符均不等（3个）。使用dp[i][j][k]表示三个序列长度分别为i j k时最短公共超序列的长度。其状态转移方程用代码表示如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (s1[i] == s2[j] && s1[i] == s3[k]) {  // 三个字母均相等
    dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
}
if (s1[i] == s2[j]) {  // 两个字母相等
    dp[i][j][k] = min(dp[i - 1][j - 1][k] + 1, dp[i][j][k]);
}
if (s1[i] == s3[k]) {  // 两个字母相等
    dp[i][j][k] = min(dp[i - 1][j][k - 1] + 1, dp[i][j][k]);
}
if (s2[j] == s3[k]) {  // 两个字母相等
    dp[i][j][k] = min(dp[i][j - 1][k - 1] + 1, dp[i][j][k]);
}
 // 选取状态转移后最小值
dp[i][j][k] = GetMinVal({dp[i - 1][j][k] + 1, dp[i][j - 1][k] + 1, dp[i][j][k - 1] + 1, dp[i][j][k]}); 
}

在得到dp数组后，由于动态规划是没有后效性的，所以需要结合状态定义倒推得到最终的公共超序列。

算法实现

三序列算法在初始化 寻找最终公共超序列时需使用两序列算法，故先简要实现两序列算法。需特别注意的是，dp数组初始化时应先设为无穷大，而后再对某序列为空时进行初始化，这是因为状态转移时需与初值进行比较。

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
44
45
46
47
48
49
50
51
// 构建两个序列的最短公共超序列，返回dp数组
vector<vector<int>> GetStateMatrix(string s1, string s2) {  
  int size1 = s1.size();
  int size2 = s2.size();
  int max_size = max(size1, size2) + 1;
  vector<vector<int>> dp(max_size, vector<int>(max_size, kInf));  // 将数组均设为正无穷
  for (int i = 0; i < max_size; i++) {                            // 设成初始值
    dp[i][0] = dp[0][i] = i;
  }
  for (int i = 1; i < size1; i++) {
    for (int j = 1; j < size2; j++) {
      if (s1[i] == s2[j]) {  // 字符相等时，多一种状态转移可能
        dp[i][j] = dp[i - 1][j - 1] + 1;
      }
      dp[i][j] = GetMinVal({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i][j]});
    }
  }
  return dp;
}
// 以dp数组重构公共超序列
string GetCommonSeqString(string s1, string s2, vector<vector<int>> dp, int start1, int start2) {  
  string ans;
  int i = start1;
  int j = start2;
  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i - 1][j - 1] + 1 && s1[i] == s2[j])  //相等时
    {
      ans.push_back(s1[i]);
      i--;
      j--;
    } else if (dp[i][j] == dp[i - 1][j] + 1)  //来自s1
    {
      ans.push_back(s1[i]);
      i--;
    } else if (dp[i][j] == dp[i][j - 1] + 1)  //来自s2
    {
      ans.push_back(s2[j]);
      j--;
    }
  }
  while (i > 0)  // s1未选完
  {
    ans.push_back(s1[i]);
    i--;
  }
  while (j > 0) {  // s2未选完
    ans.push_back(s2[j]);
    j--;
  }
  return ans;
}

而后实现三序列算法，其大体流程如下：

  1. dp数组全部设置为无穷大
  2. 使用两序列算法对某一序列长度为0时的值进行初始化
  3. 进行三序列的状态转移
  4. 序列长度均大于0时的状态回溯
  5. 某序列长度为0，使用两序列算法的重构算法
  6. 将结果翻转，得到最终的最短公共超序列

需注意的是，算法在每个序列之前填充一个字符，使得dp数组索引与序列索引能够对齐。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
string ShortestCommonSeqForThree(string s1, string s2, string s3) {  // 求三个的最短超序列
  int size1 = s1.size();
  int size2 = s2.size();
  int size3 = s3.size();
  // 在字符串前填充一个字符，使索引对齐
  s1 = '0' + s1;
  s2 = '0' + s2;
  s3 = '0' + s3;
  auto dp12 = GetStateMatrix(s1, s2);
  auto dp13 = GetStateMatrix(s1, s3);
  auto dp23 = GetStateMatrix(s2, s3);
  int max_size = max(max(size1, size2), size3) + 1;
  int dp[max_size][max_size][max_size];
  for (int i = 0; i <= size1; i++) {  // 将dp数组设置为正无穷，而后以两个序列的最短超序列初始化dp数组
    for (int j = 0; j <= size2; j++) {
      for (int k = 0; k <= size3; k++) {
        dp[i][j][k] = kInf;
        if (i == 0) {
          dp[i][j][k] = dp23[j][k];
        } else if (j == 0) {
          dp[i][j][k] = dp13[i][k];
        } else if (k == 0) {
          dp[i][j][k] = dp12[i][j];
        }
      }
    }
  }
  for (int i = 1; i <= size1; i++) {  // 关键代码：状态转移，总共有7种状态转移可能
    for (int j = 1; j <= size2; j++) {
      for (int k = 1; k <= size3; k++) {
        if (s1[i] == s2[j] && s1[i] == s3[k]) {  // 三个字母均相等
          dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
        }
        if (s1[i] == s2[j]) {  // 两个字母相等
          dp[i][j][k] = min(dp[i - 1][j - 1][k] + 1, dp[i][j][k]);
        }
        if (s1[i] == s3[k]) {  // 两个字母相等
          dp[i][j][k] = min(dp[i - 1][j][k - 1] + 1, dp[i][j][k]);
        }
        if (s2[j] == s3[k]) {  // 两个字母相等
          dp[i][j][k] = min(dp[i][j - 1][k - 1] + 1, dp[i][j][k]);
        }
        // 选取状态转移后最小值
        dp[i][j][k] = GetMinVal({dp[i - 1][j][k] + 1, dp[i][j - 1][k] + 1, dp[i][j][k - 1] + 1, dp[i][j][k]});  
      }
    }
  }
  int i = size1;
  int j = size2;
  int k = size3;

  string ans;
  while (i > 0 && j > 0 && k > 0) {  // 反向重构最短超序列
    if (dp[i][j][k] == dp[i - 1][j - 1][k - 1] + 1 && (s1[i] == s2[j] && s1[i] == s3[k])) {
      ans.push_back(s1[i]);
      i--;
      j--;
      k--;
    } else if (dp[i][j][k] == dp[i - 1][j - 1][k] + 1 && s1[i] == s2[j]) {
      ans.push_back(s1[i]);
      i--;
      j--;

    } else if (dp[i][j][k] == dp[i - 1][j][k - 1] + 1 && s1[i] == s3[k]) {
      ans.push_back(s1[i]);
      i--;
      k--;
    } else if (dp[i][j][k] == dp[i][j - 1][k - 1] + 1 && s2[j] == s3[k]) {
      ans.push_back(s2[j]);
      j--;
      k--;
    } else {
      int min_val = GetMinVal({dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1]});
      if (dp[i - 1][j][k] == min_val) {
        ans.push_back(s1[i]);
        i--;
      } else if (dp[i][j - 1][k] == min_val) {
        ans.push_back(s2[j]);
        j--;
      } else {
        ans.push_back(s3[k]);
        k--;
      }
    }
  }
  if (i == 0) {  // 一个序列为空，使用两序列方法重构超序列
    ans.append(GetCommonSeqString(s2, s3, dp23, j, k));
  } else if (j == 0) {
    ans.append(GetCommonSeqString(s1, s3, dp13, i, k));
  } else if (k == 0) {
    ans.append(GetCommonSeqString(s1, s2, dp12, i, j));
  }

  // for (int i = 0; i <= size1; i++) {
  //   for (int j = 0; j <= size2; j++) {
  //     for (int k = 0; k <= size3; k++) {
  //       cout << i << j << k << " " << dp[i][j][k] << endl;
  //     }
  //   }
  // }
  reverse(ans.begin(), ans.end());  // 将结果翻转，得到最终超序列
  return ans;
}

测试

测试时最关键一点就是找到绝对正确的算法，那这自然而然是枚举。枚举算法的思路是列出序列和（三个序列简单拼接）的所有可能排列情况，而后将相同字符进行合并，最后判断该序列是否为三个序列的公共超序列，以此找到最短的公共超序列。其实现代码如下：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
string MergeSubsequence(string s) {  // 序列归并，将临近相同的字符合并成一个字符
  string ans;
  char last = '\0';
  for (auto c : s) {
    if (c != last) {
      last = c;
      ans.push_back(c);
    }
  }
  return ans;
}

bool IsSubsequence(string str, string sub) {  // 一个字符串是否为另一个字符串的子序列
  int len = sub.length();
  int i = 0;
  bool flag = false;
  for (auto& c : str) {
    if (sub[i] == c) {
      i++;
    }
    if (i == len) {
      flag = true;
      break;
    }
  }
  return flag;
}
// 字符串是否为三个字符串的公共超序列
bool IsAllSubsequence(string str, string sub1, string sub2, string sub3) { return IsSubsequence(str, sub1) && IsSubsequence(str, sub2) && IsSubsequence(str, sub3); }

void GetPossibleSequence(vector<string>& res, string s, int start, int end) {  // 得到所有可能的排列方式
  if (start == end) {
    res.emplace_back(s);
  } else {
    for (int i = start; i <= end; i++) {
      swap(s[start], s[i]);  // 交换序列首部
      GetPossibleSequence(res, s, start + 1, end);
      swap(s[i], s[start]);  // 还原顺序
    }
  }
}

string SubsequenceEnumeration(string s1, string s2, string s3) {  // 使用枚举法找到最短公共超序列
  string s = s1 + s2 + s3;
  vector<string> sequence;
  GetPossibleSequence(sequence, s, 0, s.length() - 1);  // 找到所有可能排列可能(9个字符36280种可能排列)
  int min_len = s.length();
  string min_common_seq = "";
  for (auto& seq : sequence) {
    seq = MergeSubsequence(seq);              // 序列归并
    if (IsAllSubsequence(seq, s1, s2, s3)) {  // 恰好为公共超序列
      if (seq.length() < min_len) {
        min_common_seq = seq;
        min_len = seq.length();
      }
    }
  }
  return min_common_seq;
}

测试代码如下：

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
std::string RandString() {
  int len = 3;  // 字符串长度需设小，避免枚举时间过长
  std::string str;
  char c;
  /*循环向字符串中添加随机生成的字符*/
  for (int i = 0; i < len; i++) {
    c = 'a' + rand() % 6;  // 字母可能为abcdef
    str.push_back(c);
  }
  return str;
}

void TestFunc() {
  int times = 10;
  for (int i = 0; i < times; i++) {
    string s1 = RandString();
    string s2 = RandString();
    string s3 = RandString();
    cout << "test data " << endl << s1 << " " << s2 << " " << s3 << endl;
    string ans = SubsequenceEnumeration(s1, s2, s3);        // 枚举答案
    string my_ans = ShortestCommonSeqForThree(s1, s2, s3);  // 算法答案
    if (!IsAllSubsequence(ans, s1, s2, s3)) {               // 是否为公共超序列
      cout << "something worng" << endl;
    }
    if (!IsAllSubsequence(my_ans, s1, s2, s3)) {  // 是否为公共超序列
      cout << "not common sequence" << endl;
    }
    cout << "answer:    " << ans << endl;
    cout << "my answer: " << my_ans << endl;
    cout << "seq length: " << ans.length() << endl;
    if (ans.length() < my_ans.length()) {  // 长度是否一致
      cout << "test failed" << endl;
    }
  }
}

程序输出如下：

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
44
45
46
47
48
49
50
test data 
bed bfb ead
answer:    befbad
my answer: beafbd
seq length: 6
test data 
bcb cbf eaa
answer:    bcbeafa
my answer: eaabcbf
seq length: 7
test data 
eef cdd ccc
answer:    ecefdcdc
my answer: cccddeef
seq length: 8
test data 
bbb faa afd
answer:    bfbabafd
my answer: afdaabbb
seq length: 8
test data 
beb edd dfc
answer:    bebdfdc
my answer: bedfcdb
seq length: 7
test data 
bcc faf ebc
answer:    faebcfc
my answer: efafbcc
seq length: 7
test data 
cdc ceb ddc
answer:    cdebdc
my answer: dcebdc
seq length: 6
test data 
dcf edb fad
answer:    dcfeadb
my answer: faedbcf
seq length: 7
test data 
adc dcc dcb
answer:    adcbc
my answer: adcbc
seq length: 5
test data 
aac cad fcb
answer:    acadfcb
my answer: fcbadac
seq length: 7

经过随机字符串的测试证明，设计算法基本正确。

整数和运算符生成一个算术表达式

问题描述

设有a,b,c,d,e五个整数和+,-,*,/四个运算符。对于任意给定的整数n，请设计一个算法，用给定的5整数和运算符生成一个算术表达式（每个整数和每个运算法只使用1次），使其运算结果等于n。

算法实现与测试

该实验我使用的算法是枚举法，实现较为简单。枚举算法分为两个部分，第一部分找到可能的数字排列和运算符排列。在这我使用是实验三测试时类似的枚举算法，找到所有可能排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
// 得到所有可能的排列方式
void GetPossibleSequence(vector<vector<T>>& res, vector<T> seq, int start, int end) {  
  if (start == end) {
    res.emplace_back(seq);
  } else {
    for (int i = start; i <= end; i++) {
      swap(seq[start], seq[i]);  // 交换序列首部
      GetPossibleSequence(res, seq, start + 1, end);
      swap(seq[i], seq[start]);  // 还原顺序
    }
  }
}

第二部分就是计算表达式，这个只需利用栈扫描一遍数字集合与运算符集合，遇到乘除则直接运算，加减则数字与运算符压栈。而后将运算符弹栈，将两个数字弹栈，计算结果后重新压栈，直至运算符栈为空。

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
44
45
46
47
48
49
enum Operator { kAdd, kSub, kMul, kDiv };
double Calculate(double lhs, double rhs, Operator op) {  // 计算简单表达式
  double ans;
  switch (op) {
    case kAdd:
      return lhs + rhs;
    case kSub:
      return lhs - rhs;
    case kMul:
      return lhs * rhs;
    case kDiv:
      return lhs / rhs;
  }
  return -1;
}

double CalculateExpr(vector<double> num, vector<Operator> ops) {  // 计算复杂表达式
  stack<double> num_stack;
  stack<Operator> op_stack;
  double lhs;
  double rhs;
  double res;
  Operator op;
  num_stack.emplace(num[0]);
  int size = num.size();
  for (double i = 0; i < size - 1; i++) {
    if (ops[i] == kMul || ops[i] == kDiv) {  // 若为乘除，直接计算
      lhs = num_stack.top();
      num_stack.pop();
      rhs = num[i + 1];
      res = Calculate(lhs, rhs, ops[i]);
      num_stack.emplace(res);
    } else {  // 若为加减，先入栈
      num_stack.emplace(num[i + 1]);
      op_stack.emplace(ops[i]);
    }
  }
  while (!op_stack.empty()) {  // 将符号栈的操作符一一弹出，进行计算
    op = op_stack.top();
    op_stack.pop();
    rhs = num_stack.top();
    num_stack.pop();
    lhs = num_stack.top();
    num_stack.pop();
    res = Calculate(lhs, rhs, op);
    num_stack.emplace(res);
  }
  return num_stack.top();  // 得到表达式最终结果
}

而后只需调用这两个函数，完成算法。

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
void PrintExpr(vector<double> num, vector<Operator> ops) {  // 输出表达式
  int size = ops.size();
  for (int i = 0; i < size; i++) {
    cout << " " << num[i] << " ";
    switch (ops[i]) {
      case kAdd:
        cout << '+';
        break;
      case kSub:
        cout << '-';
        break;
      case kMul:
        cout << '*';
        break;
      case kDiv:
        cout << '/';
        break;
    }
  }
  cout << " " << num[size] << " " << endl;
}
void GetExpr(vector<double> num, int n) {
  vector<vector<double>> possible_nums;
  vector<vector<Operator>> possible_ops;
  vector<Operator> operators = {kAdd, kSub, kMul, kDiv};
  GetPossibleSequence(possible_nums, num, 0, num.size() - 1);             // 得到可能的数字排列集合
  GetPossibleSequence(possible_ops, operators, 0, operators.size() - 1);  // 得到可能的运算符排列集合
  bool find = false;
  for (auto& nums : possible_nums) {  // 双重循环，计算所有可能的表达式
    for (auto& ops : possible_ops) {
      double res = CalculateExpr(nums, ops);
      if (res == n) {  // 若与目标值一致，输出表达式
        PrintExpr(nums, ops);
        find = true;
      }
    }
  }
  if (!find) {  // 未找到相应的表达式
    cout << "No suitable expression was found" << endl;
  }
}

由于是枚举法，所以只用几个简单数据进行测试

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
44
45
46
int main() {
  cout << 17 << endl;
  GetExpr({1, 2, 3, 4, 5}, 17);
  cout << 19 << endl;
  GetExpr({1, 2, 3, 4, 5}, 19);
  cout << 38 << endl;
  GetExpr({1, 2, 3, 4, 5}, 38);
  return 0;
}
// 测试结果如下：
19
 2 / 1 + 4 * 5 - 3 
 2 / 1 + 5 * 4 - 3 
 2 + 4 / 1 * 5 - 3 
 2 + 4 * 5 / 1 - 3 
 2 + 4 * 5 - 3 / 1 
 2 + 5 * 4 - 3 / 1 
 2 + 5 * 4 / 1 - 3 
 2 + 5 / 1 * 4 - 3 
 4 / 1 * 5 + 2 - 3 
 4 * 5 / 1 + 2 - 3 
 4 * 5 + 2 / 1 - 3 
 4 * 5 + 2 - 3 / 1 
 5 * 4 + 2 - 3 / 1 
 5 * 4 + 2 / 1 - 3 
 5 * 4 / 1 + 2 - 3 
 5 / 1 * 4 + 2 - 3 
17
 3 / 1 * 5 + 4 - 2 
 3 * 5 / 1 + 4 - 2 
 3 * 5 + 4 / 1 - 2 
 3 * 5 + 4 - 2 / 1 
 4 + 3 / 1 * 5 - 2 
 4 + 3 * 5 / 1 - 2 
 4 + 3 * 5 - 2 / 1 
 4 / 1 + 3 * 5 - 2 
 4 / 1 + 5 * 3 - 2 
 4 + 5 * 3 / 1 - 2 
 4 + 5 * 3 - 2 / 1 
 4 + 5 / 1 * 3 - 2 
 5 * 3 + 4 - 2 / 1 
 5 * 3 + 4 / 1 - 2 
 5 * 3 / 1 + 4 - 2 
 5 / 1 * 3 + 4 - 2 
38
No suitable expression was found