Ace
好好学习，天天向上。

Ace的快乐屋

《离散数学及其应用》第二章 计算机课题

2019年11月16日 681次阅读 共14001个字   0条评论 0人点赞 Ace
大家好，我是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;
}

 

本作品采用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 进行许可
点赞
最后编辑：2019年11月16日

发表评论

昵称和uid可以选填一个，填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

18 + 17 =