Use C++ to design n integer matrices M1..Mn for continuous multiplication. The dimension of each matrix is between 1-200, the number of matrices n is between 5-180, and the matrix elements are non-negative integers of at most 2 digits. Each matrix and the result matrix are stored in the form of text files. The file names are M1…Mn and M. The optimal multiplication order, the minimum number of multiplications, the optimal continuous multiplication time, and the complete C++ code and comments are output.
//First edition
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <climits>
#include <chrono>
using namespace std;
struct Matrix {
int rows;
int cols;
};
// Generate a random integer matrix and save it to a file
void RandomMatrix(int n) {
srand(time(nullptr));
for (int i = 1; i <= n; i + + ) {
int rows = rand() % 200 + 1;
int cols = rand() % 200 + 1;
string filename = "M" + to_string(i) + ".txt";
ofstream matrixFile(filename);
matrixFile << rows << " " << cols << endl;
for (int r = 0; r < rows; r + + ) {
for (int c = 0; c < cols; c + + ) {
matrixFile << rand() % 100 << " ";
}
matrixFile << endl;
}
matrixFile.close();
}
}
// Calculate the best multiplication order and the minimum number of multiplications
void MatrixOrder(const vector<Matrix> & amp; matrices, vector<vector<int>> & amp; m, vector<vector<int>> & amp; s) {
int n = matrices.size();
for (int i = 1; i < n; i + + ) {
m[i][i] = 0;
}
\t
for (int chainLen = 2; chainLen < n; chainLen + + ) {
for (int i = 1; i < n - chainLen + 1; i + + ) {
int j = i + chainLen - 1;
m[i][j] = INT_MAX;
for (int k = i; k < j; k + + ) {
int cost = m[i][k] + m[k + 1][j] + matrices[i - 1].rows * matrices[k].cols * matrices[j].cols;
if (cost < m[i][j]) {
m[i][j] = cost;
s[i][j] = k;
}
}
}
}
}
//Perform matrix multiplication
vector<vector<int>> MatrixMulti(const vector<Matrix> & amp; matrices, const vector<vector<int>> & amp; s) {
int n = matrices.size();
vector<vector<vector<int>> > dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
for (int i = 1; i < n; i + + ) {
dp[i][i][0] = matrices[i - 1].rows;
dp[i][i][1] = matrices[i - 1].cols;
}
\t
for (int len = 2; len < n; len + + ) {
for (int i = 1; i <= n - len; i + + ) {
int j = i + len - 1;
int k = s[i][j];
dp[i][j][0] = dp[i][k][0] * dp[k + 1][j][0];
dp[i][j][1] = dp[k + 1][j][1];
}
}
\t
vector<vector<int>> resultMatrix(n - 1, vector<int>(n - 1));
for (int i = 1; i < n; i + + ) {
resultMatrix[i - 1] = dp[i][n - 1];
}
return resultMatrix;
}
// Output the best multiplication order
void PrintOpt(const vector<vector<int>> & amp; s, int i, int j, ofstream & amp; output) {
if (i == j) {
output << "M" << i;
} else {
output << "(";
PrintOpt(s, i, s[i][j], output);
PrintOpt(s, s[i][j] + 1, j, output);
output << ")";
}
}
int main() {
int n;
cout << "Please enter the number of matrices (between 5-180): ";
cin >> n;
\t
if (n < 5 || n > 180) {
cout << "The number of matrices is not within the allowed range." << endl;
return 1;
}
\t
// Generate a random integer matrix and save it to a file
RandomMatrix(n);
\t
vector<Matrix> matrices(n);
for (int i = 0; i < n; i + + ) {
string filename = "M" + to_string(i + 1) + ".txt";
ifstream matrixFile(filename);
matrixFile >> matrices[i].rows >> matrices[i].cols;
matrixFile.close();
}
\t
vector<vector<int>> m(n, vector<int>(n, 0));
vector<vector<int>> s(n, vector<int>(n, 0));
\t
// Calculate the best multiplication order and the minimum number of multiplications
MatrixOrder(matrices, m, s);
\t
// Calculate the multiplication operation and output the result
auto start = chrono::high_resolution_clock::now();
vector<vector<int>> resultMatrix = MatrixMulti(matrices, s);
auto end = chrono::high_resolution_clock::now();
auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
\t
// Output the best multiplication sequence and results to file M.txt
ofstream output("M.txt");
if (output.is_open()) {
output << "Best multiplication order: ";
PrintOpt(s, 1, n - 1, output);
output << endl;
output << "Minimum number of multipliers: " << m[1][n - 1] << endl;
output << "Final result matrix:\
";
for (int i = 0; i < n - 1; i + + ) {
for (int j = 0; j < n - 1; j + + ) {
output << resultMatrix[i][j] << " ";
}
output << endl;
}
output << "Time spent on optimal multiplication (microseconds): " << duration.count() << " μs" << endl;
output.close();
cout << "The optimal multiplication sequence, results and calculation time have been saved in the M.txt file." << endl;
} else {
cout << "Cannot open file to save results." << endl;
}
\t
return 0;
}
//second edition
#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
#include <cstdlib>
#include <climits>
#include <chrono>
#include <filesystem>
using namespace std;
namespace fs = std::filesystem;
struct Matrix {
int rows;
int cols;
};
// Generate a random integer matrix and save it to a file
void RandomMatrix(int n) {
fs::create_directory("matrices");
srand(time(nullptr));
for (int i = 1; i <= n; i + + ) {
int rows = rand() % 200 + 1;
int cols = rand() % 200 + 1;
std::string filename = "matrices/M" + std::to_string(i) + ".txt";
std::ofstream matrixFile(filename);
matrixFile << rows << " " << cols << std::endl;
for (int r = 0; r < rows; r + + ) {
for (int c = 0; c < cols; c + + ) {
int randomValue = (rand() % 99) + 1; // Generate a random integer between 1 and 99
matrixFile << randomValue << " ";
}
matrixFile << std::endl;
}
matrixFile.close();
}
}
// Calculate the best multiplication order and the minimum number of multiplications
void MatrixOrder(const vector<Matrix> & amp; matrices, vector<vector<int>> & amp; m, vector<vector<int>> & amp; s) {
int n = matrices.size();
for (int i = 1; i < n; i + + ) {
m[i][i] = 0;
}
\t
for (int chainLen = 2; chainLen < n; chainLen + + ) {
for (int i = 1; i < n - chainLen + 1; i + + ) {
int j = i + chainLen - 1;
m[i][j] = INT_MAX;
for (int k = i; k < j; k + + ) {
int cost = m[i][k] + m[k + 1][j] + matrices[i - 1].rows * matrices[k].cols * matrices[j].cols;
if (cost < m[i][j]) {
m[i][j] = cost;
s[i][j] = k;
}
}
}
}
}
//Perform matrix multiplication
vector<vector<int>> MatrixMulti(const vector<Matrix> & amp; matrices, const vector<vector<int>> & amp; s) {
int n = matrices.size();
vector<vector<vector<int>> > dp(n, vector<vector<int>>(n, vector<int>(2, 0)));
for (int i = 1; i < n; i + + ) {
dp[i][i][0] = matrices[i - 1].rows;
dp[i][i][1] = matrices[i - 1].cols;
}
\t
for (int len = 2; len < n; len + + ) {
for (int i = 1; i <= n - len; i + + ) {
int j = i + len - 1;
int k = s[i][j];
dp[i][j][0] = dp[i][k][0] * dp[k + 1][j][0];
dp[i][j][1] = dp[k + 1][j][1];
}
}
\t
vector<vector<int>> resultMatrix(n - 1, vector<int>(n - 1));
for (int i = 1; i < n; i + + ) {
resultMatrix[i - 1] = dp[i][n - 1];
}
return resultMatrix;
}
// Output the best multiplication order
void PrintOpt(const vector<vector<int>> & amp; s, int i, int j, ofstream & amp; output) {
if (i == j) {
output << "M" << i;
} else {
output << "(";
PrintOpt(s, i, s[i][j], output);
PrintOpt(s, s[i][j] + 1, j, output);
output << ")";
}
}
int main() {
int n;
std::cout << "Please enter the number of matrices (between 5-180): ";
std::cin >> n;
\t
if (n < 5 || n > 180) {
std::cout << "The number of matrices is not within the allowed range." << std::endl;
return 1;
}
\t
// Generate a matrix of random integers and save it to a folder
RandomMatrix(n);
\t
std::vector<Matrix> matrices(n);
for (int i = 0; i < n; i + + ) {
std::string filename = "matrices/M" + std::to_string(i + 1) + ".txt";
std::ifstream matrixFile(filename);
matrixFile >> matrices[i].rows >> matrices[i].cols;
matrixFile.close();
}
\t
std::vector<std::vector<int>> m(n, std::vector<int>(n, 0));
std::vector<std::vector<int>> s(n, std::vector<int>(n, 0));
\t
// Calculate the best multiplication order and the minimum number of multiplications
MatrixOrder(matrices, m, s);
\t
// Calculate the multiplication operation and output the result
auto start = std::chrono::high_resolution_clock::now();
std::vector<std::vector<int>> resultMatrix = MatrixMulti(matrices, s);
auto end = std::chrono::high_resolution_clock::now();
auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
\t
// Output the best multiplication sequence and results to file M.txt
std::ofstream output("matrices/M.txt");
if (output.is_open()) {
output << "Best multiplication order: ";
PrintOpt(s, 1, n - 1, output);
output << std::endl;
output << "Minimum number of multipliers: " << m[1][n - 1] << std::endl;
output << "Final result matrix:\
";
for (int i = 0; i < n - 1; i + + ) {
for (int j = 0; j < n - 1; j + + ) {
output << resultMatrix[i][j] << " ";
}
output << std::endl;
}
output << "Time spent on optimal multiplication (microseconds): " << duration.count() << " μs" << std::endl;
output.close();
std::cout << "The best multiplication order, results and calculation time have been saved to the M.txt file in the matrices folder." << std::endl;
} else {
std::cout << "Cannot open file to save results." << std::endl;
}
\t
return 0;
}