大家好,我是Ace,这篇文章是《离散数学及其应用》第二章 计算机课题的源码,希望大家喜欢。
C++实现:
由于标准库只支持定长位串,使用可变位串表示集合更加灵活,所以使用了C++的准标准库Boost库中的可变位串,用定长位串来代替也是可以的。
1.
#include <iostream> #include <boost/dynamic_bitset.hpp> #include <boost/utility.hpp> using std::cout; using std::endl; using boost::dynamic_bitset; int main() { // 集合元素数 const size_t n = 32; // 初始化A为n位的0...0011 dynamic_bitset<> A(n, BOOST_BINARY(011)); // 初始化A为n位的0...0110 dynamic_bitset<> B(n, BOOST_BINARY(110)); cout << "A的补集:" << ~A << endl; cout << "A与B的并集:" << (A | B) << endl; cout << "A与B的交集:" << (A & B) << endl; cout << "A与B的差集:" << (A - B) << endl; cout << "A与B的异或:" << (A ^ B) << endl; return 0; }
2.
#include <iostream> #include <map> #include <set> #include <string> using std::cout; using std::endl; using std::set; using std::map; using std::string; // 多重集合并集: template<typename T> void MultiSetAnd(map<T, size_t> &inputSet1, map<T, size_t> &inputSet2, map<T, size_t> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet1) { T key = ele.first; size_t cnt1 = inputSet1[key]; size_t cnt2 = inputSet2[key]; if (cnt1 < cnt2) outputSet[key] = cnt1; else outputSet[key] = cnt2; } } // 多重集合交集: template<typename T> void MultiSetOr(map<T, size_t> &inputSet1, map<T, size_t> &inputSet2, map<T, size_t> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet1) { T key = ele.first; size_t cnt1 = inputSet1[key]; size_t cnt2 = inputSet2[key]; if (cnt1 > cnt2) outputSet[key] = cnt1; else outputSet[key] = cnt2; } } // 多重集合差集: template<typename T> void MultiSetMinus(map<T, size_t> &inputSet1, map<T, size_t> &inputSet2, map<T, size_t> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet1) { T key = ele.first; size_t cnt1 = inputSet1[key]; size_t cnt2 = inputSet2[key]; // 防止无符号数溢出 if (cnt1 <= cnt2) outputSet[key] = 0; else outputSet[key] = cnt1 - cnt2; } } // 多重集合和集: template<typename T> void MultiSetAdd(map<T, size_t> &inputSet1, map<T, size_t> &inputSet2, map<T, size_t> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet1) { T key = ele.first; outputSet[key] = inputSet1[key] + inputSet2[key]; } } int main() { // 指定全集元素 const set<string> U{ "a","b","c","d" }; // 使用map(键值对)分别来保存集合元素和元素个数 map<string, size_t> A, B, C; // 给A和B分别赋值 size_t cnt = 0; for (const auto &ele : U) { A[ele] = cnt; B[ele] = U.size() - cnt++; } // 检验赋值是否正确 cout << "A:" << endl; for (const auto &ele : A) cout << ele.first << ":" << ele.second << endl; cout << "B:" << endl; for (const auto &ele : B) cout << ele.first << ":" << ele.second << endl; cout << "多重集合交集:" << endl; MultiSetOr(A, B, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; cout << "多重集合并集:" << endl; MultiSetAnd(A, B, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; cout << "多重集合差集:" << endl; MultiSetMinus(A, B, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; cout << "多重集合和集:" << endl; MultiSetAdd(A, B, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; return 0; }
3.
#include <iostream> #include <map> #include <set> #include <string> using std::cout; using std::endl; using std::set; using std::map; using std::string; // 模糊集合并集: template<typename T> void FuzzySetAnd(map<T, double> &inputSet1, map<T, double> &inputSet2, map<T, double> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet1) { T key = ele.first; double cnt1 = inputSet1[key]; double cnt2 = inputSet2[key]; if (cnt1 < cnt2) outputSet[key] = cnt1; else outputSet[key] = cnt2; } } // 模糊集合交集: template<typename T> void FuzzySetOr(map<T, double> &inputSet1, map<T, double> &inputSet2, map<T, double> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet1) { T key = ele.first; double cnt1 = inputSet1[key]; double cnt2 = inputSet2[key]; if (cnt1 > cnt2) outputSet[key] = cnt1; else outputSet[key] = cnt2; } } // 模糊集合补集: template<typename T> void FuzzySetComple(map<T, double> &inputSet, map<T, double> &outputSet) { outputSet.clear(); // 遍历元素,进行或操作 for (const auto &ele : inputSet) outputSet[ele.first] = 1 - ele.second; } int main() { // 指定全集元素 const set<string> U{ "a","b","c","d" }; // 使用map(键值对)分别来保存集合元素和元素个数 map<string, double> A, B, C; // 给A和B分别赋值,并将其所有值归一化到0到1之间 double cnt = 0; for (const auto &ele : U) { A[ele] = cnt / U.size(); B[ele] = (U.size() - cnt++) / U.size(); } // 检验赋值是否正确 cout << "A:" << endl; for (const auto &ele : A) cout << ele.first << ":" << ele.second << endl; cout << "B:" << endl; for (const auto &ele : B) cout << ele.first << ":" << ele.second << endl; cout << "模糊集合交集:" << endl; FuzzySetOr(A, B, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; cout << "模糊集合并集:" << endl; FuzzySetAnd(A, B, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; cout << "A的补集:" << endl; FuzzySetComple(A, C); for (const auto &ele : C) cout << ele.first << ":" << ele.second << endl; return 0; }
4、5和6题应该只需要根据定义,遍历映射关系即可实现判断。
7.
#include <iostream> #include <vector> #include <cstdint> #include <stdexcept> using std::cout; using std::endl; using std::vector; using std::runtime_error; /* 功能:矩阵乘法 * 参数:matrix_left为矩阵乘法左侧的矩阵,matrix_right为矩阵乘法右侧的矩阵 类型均为vector<vector<double>>类型 * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<double>> Multi_Matrix(vector<vector<double>> matrix_left, vector<vector<double>> matrix_right) { if (matrix_left.empty() || matrix_right.empty()) { throw runtime_error("Matrix cannot be empty!"); } else if (matrix_left.at(0).empty() || matrix_right.at(0).empty()) { throw runtime_error("Matrix Error!"); } int32_t Row_matrix_left = matrix_left.size(), Col_matrix_left = matrix_left.at(0).size(); int32_t Row_matrix_right = matrix_left.size(), Col_matrix_right = matrix_left.at(0).size(); if (Col_matrix_left != Row_matrix_right) { throw runtime_error("Matrices cannot multiply!"); } vector<double> init_vector(Col_matrix_right, 0); init_vector.shrink_to_fit(); vector<vector<double>> Answer_matrix(Row_matrix_left, init_vector); Answer_matrix.shrink_to_fit(); // 上面保证了结果矩阵的大小不会错 for (int32_t row = 0; row < Row_matrix_left; ++row) { for (int32_t col = 0; col < Col_matrix_right; ++col) { for (int32_t cnt = 0; cnt < Col_matrix_left; ++cnt) { Answer_matrix[row][col] += matrix_left[row][cnt] * matrix_right[cnt][col]; } } } return Answer_matrix; } int main() { vector<double> col(9, 0); vector<vector<double>> matrix1(9, col), matrix2(9, col); for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { matrix1[i][j] = j + 9 * i; } } for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { if (i == j) { matrix2[i][j] = 1; } } } matrix2 = Multi_Matrix(matrix1, matrix2); for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { cout << matrix2[i][j] << " "; } cout << endl; } return 0;
8.
#include <iostream> #include <vector> #include <cstdint> #include <stdexcept> using std::cout; using std::endl; using std::vector; using std::runtime_error; /* 功能:矩阵乘法 * 参数:matrix_left为矩阵乘法左侧的矩阵,matrix_right为矩阵乘法右侧的矩阵 类型均为vector<vector<double>>类型 * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<double>> Multi_Matrix(vector<vector<double>> matrix_left, vector<vector<double>> matrix_right) { if (matrix_left.empty() || matrix_right.empty()) { throw runtime_error("Matrix cannot be empty!"); } else if (matrix_left.at(0).empty() || matrix_right.at(0).empty()) { throw runtime_error("Matrix Error!"); } int32_t Row_matrix_left = matrix_left.size(), Col_matrix_left = matrix_left.at(0).size(); int32_t Row_matrix_right = matrix_left.size(), Col_matrix_right = matrix_left.at(0).size(); if (Col_matrix_left != Row_matrix_right) { throw runtime_error("Matrices cannot multiply!"); } vector<double> init_vector(Col_matrix_right, 0); init_vector.shrink_to_fit(); vector<vector<double>> Answer_matrix(Row_matrix_left, init_vector); Answer_matrix.shrink_to_fit(); // 上面保证了结果矩阵的大小不会错 for (int32_t row = 0; row < Row_matrix_left; ++row) { for (int32_t col = 0; col < Col_matrix_right; ++col) { for (int32_t cnt = 0; cnt < Col_matrix_left; ++cnt) { Answer_matrix[row][col] += matrix_left[row][cnt] * matrix_right[cnt][col]; } } } return Answer_matrix; } /* 功能:方阵幂 * 参数:matrix为方阵,类型为vector<vector<double>>类型,n为幂次数,类型为int32_t * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<double>> Power_Matrix(vector<vector<double>> matrix, int32_t n) { if (matrix.empty()) { throw runtime_error("Matrix cannot be empty!"); } int32_t Row_matrix = matrix.size(), Col_matrix = matrix.at(0).size(); if (Row_matrix != Col_matrix) { throw runtime_error("Matrix is not square!"); } vector<vector<double>> copy_matrix = matrix; for (int32_t cnt = 2; cnt < n; ++cnt) { matrix = Multi_Matrix(matrix, copy_matrix); } return matrix; } int main() { vector<double> col(9, 0); vector<vector<double>> matrix1(9, col), matrix2(9, col); for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { matrix1[i][j] = j + 9 * i; } } for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { if (i == j) { matrix2[i][j] = 1; } } } // matrix2 = Multi_Matrix(matrix1, matrix2); matrix2 = Power_Matrix(matrix2, 20); for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { cout << matrix2[i][j] << " "; } cout << endl; } return 0; }
9.
#include <iostream> #include <vector> #include <cstdint> #include <stdexcept> using std::cout; using std::endl; using std::vector; using std::runtime_error; /* 功能:矩阵乘法 * 参数:matrix_left为矩阵乘法左侧的矩阵,matrix_right为矩阵乘法右侧的矩阵 类型均为vector<vector<double>>类型 * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<double>> Multi_Matrix(vector<vector<double>> matrix_left, vector<vector<double>> matrix_right) { if (matrix_left.empty() || matrix_right.empty()) { throw runtime_error("Matrix cannot be empty!"); } else if (matrix_left.at(0).empty() || matrix_right.at(0).empty()) { throw runtime_error("Matrix Error!"); } int32_t Row_matrix_left = matrix_left.size(), Col_matrix_left = matrix_left.at(0).size(); int32_t Row_matrix_right = matrix_left.size(), Col_matrix_right = matrix_left.at(0).size(); if (Col_matrix_left != Row_matrix_right) { throw runtime_error("Matrices cannot multiply!"); } vector<double> init_vector(Col_matrix_right, 0); init_vector.shrink_to_fit(); vector<vector<double>> Answer_matrix(Row_matrix_left, init_vector); Answer_matrix.shrink_to_fit(); // 上面保证了结果矩阵的大小不会错 for (int32_t row = 0; row < Row_matrix_left; ++row) { for (int32_t col = 0; col < Col_matrix_right; ++col) { for (int32_t cnt = 0; cnt < Col_matrix_left; ++cnt) { Answer_matrix[row][col] += matrix_left[row][cnt] * matrix_right[cnt][col]; } } } return Answer_matrix; } /* 功能:方阵幂 * 参数:matrix为方阵,类型为vector<vector<double>>类型,n为幂次数,类型为int32_t * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<double>> Power_Matrix(vector<vector<double>> matrix, int32_t n) { if (matrix.empty()) { throw runtime_error("Matrix cannot be empty!"); } int32_t Row_matrix = matrix.size(), Col_matrix = matrix.at(0).size(); if (Row_matrix != Col_matrix) { throw runtime_error("Matrix is not square!"); } vector<vector<double>> copy_matrix = matrix; for (int32_t cnt = 2; cnt < n; ++cnt) { matrix = Multi_Matrix(matrix, copy_matrix); } return matrix; } /* 功能:判断是否对称 * 参数:matrix为方阵,类型为vector<vector<double>>类型, * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ bool isSymmetrical(vector<vector<double>> matrix) { if (matrix.empty()) { throw runtime_error("Matrix cannot be empty!"); } int32_t Row_matrix = matrix.size(), Col_matrix = matrix.at(0).size(); if (Row_matrix != Col_matrix) { throw runtime_error("Matrix is not square!"); } for (int32_t row = 0; row < Row_matrix; ++row) { for (int32_t col = 0; col < Col_matrix; ++col) { if (matrix[row][col] != matrix[col][row]) { return false; } } } return true; } int main() { vector<double> col(9, 0); vector<vector<double>> matrix1(9, col), matrix2(9, col); for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { matrix1[i][j] = j + 9 * i; } } for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { if (i == j) { matrix2[i][j] = 1; } } } // matrix2 = Multi_Matrix(matrix1, matrix2); matrix2 = Power_Matrix(matrix2, 20); cout << isSymmetrical(matrix1) << endl; cout << isSymmetrical(matrix2) << endl; for (int32_t i = 0; i < 9; ++i) { for (int32_t j = 0; j < 9; ++j) { cout << matrix2[i][j] << " "; } cout << endl; } return 0; }
10、11和12题的合并实现:
#include <iostream> #include <vector> #include <cstdint> #include <stdexcept> using std::cout; using std::endl; using std::vector; using std::runtime_error; /* 功能:布尔矩阵交 * 参数:matrix_1为矩阵1,matrix_2为矩阵2,类型均为vector<vector<bool>>类型 * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<bool>> Or_Bool_Matrix(vector<vector<bool>> matrix_1, vector<vector<bool>> matrix_2) { if (matrix_1.empty() || matrix_2.empty()) { throw runtime_error("Matrix cannot be empty!"); } else if (matrix_1.at(0).empty() || matrix_2.at(0).empty()) { throw runtime_error("Matrix Error!"); } int32_t Row_matrix_1 = matrix_1.size(), Col_matrix_1 = matrix_1.at(0).size(); int32_t Row_matrix_2 = matrix_2.size(), Col_matrix_2 = matrix_2.at(0).size(); if (Row_matrix_1 != Row_matrix_2 || Col_matrix_1 != Col_matrix_2) { throw runtime_error("Matrices do not have same size!"); } for (int32_t row = 0; row < Row_matrix_1; ++row) { for (int32_t col = 0; col < Col_matrix_1; ++col) { matrix_1[row][col] = matrix_1[row][col] || matrix_2[row][col]; } } return matrix_1; } /* 功能:布尔矩阵并 * 参数:matrix_1为矩阵1,matrix_2为矩阵2,类型均为vector<vector<bool>>类型 * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<bool>> And_Bool_Matrix(vector<vector<bool>> matrix_1, vector<vector<bool>> matrix_2) { if (matrix_1.empty() || matrix_2.empty()) { throw runtime_error("Matrix cannot be empty!"); } else if (matrix_1.at(0).empty() || matrix_2.at(0).empty()) { throw runtime_error("Matrix Error!"); } int32_t Row_matrix_1 = matrix_1.size(), Col_matrix_1 = matrix_1.at(0).size(); int32_t Row_matrix_2 = matrix_2.size(), Col_matrix_2 = matrix_2.at(0).size(); if (Row_matrix_1 != Row_matrix_2 || Col_matrix_1 != Col_matrix_2) { throw runtime_error("Matrices do not have same size!"); } for (int32_t row = 0; row < Row_matrix_1; ++row) { for (int32_t col = 0; col < Col_matrix_1; ++col) { matrix_1[row][col] = matrix_1[row][col] && matrix_2[row][col]; } } return matrix_1; } /* 功能:布尔矩阵乘法 * 参数:matrix_left为矩阵乘法左侧的矩阵,matrix_right为矩阵乘法右侧的矩阵 类型均为vector<vector<bool>>类型 * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<bool>> Multi_Bool_Matrix(vector<vector<bool>> matrix_left, vector<vector<bool>> matrix_right) { if (matrix_left.empty() || matrix_right.empty()) { throw runtime_error("Matrix cannot be empty!"); } else if (matrix_left.at(0).empty() || matrix_right.at(0).empty()) { throw runtime_error("Matrix Error!"); } int32_t Row_matrix_left = matrix_left.size(), Col_matrix_left = matrix_left.at(0).size(); int32_t Row_matrix_right = matrix_left.size(), Col_matrix_right = matrix_left.at(0).size(); if (Col_matrix_left != Row_matrix_right) { throw runtime_error("Matrices cannot multiply!"); } vector<bool> init_vector(Col_matrix_right, 0); init_vector.shrink_to_fit(); vector<vector<bool>> Answer_matrix(Row_matrix_left, init_vector); Answer_matrix.shrink_to_fit(); // 上面保证了结果矩阵的大小不会错 for (int32_t row = 0; row < Row_matrix_left; ++row) { for (int32_t col = 0; col < Col_matrix_right; ++col) { for (int32_t cnt = 0; cnt < Col_matrix_left; ++cnt) { Answer_matrix[row][col] = Answer_matrix[row][col] || (matrix_left[row][cnt] && matrix_right[cnt][col]); } } } return Answer_matrix; } /* 功能:方阵幂 * 参数:matrix为方阵,类型为vector<vector<bool>>类型,n为幂次数,类型为int32_t * 备注:matrix[0][1]代表0行1列,若出现错误,则会抛出错误,请注意。 */ vector<vector<bool>> Power_Bool_Matrix(vector<vector<bool>> matrix, int32_t n) { if (matrix.empty()) { throw runtime_error("Matrix cannot be empty!"); } int32_t Row_matrix = matrix.size(), Col_matrix = matrix.at(0).size(); if (Row_matrix != Col_matrix) { throw runtime_error("Matrix is not square!"); } vector<vector<bool>> copy_matrix = matrix; for (int32_t cnt = 2; cnt < n; ++cnt) { matrix = Multi_Bool_Matrix(matrix, copy_matrix); } return matrix; }