《离散数学及其应用》第二章 计算与探索

C++实现:

1.

由于只用实现两个有限集的笛卡尔积，应该就是回顾概念吧。

#include <iostream>
#include <map>
#include <set>
#include <string>

using std::cout;
using std::endl;
using std::set;
using std::string;

// 显示笛卡尔积
template<typename T1, typename T2>
void CertesianProduct(const set<T1> &inputSet1, const set<T2> &inputSet2)
{
  // 遍历元素，进行或操作
  for (const auto &ele1 : inputSet1)
    for (const auto &ele2 : inputSet2)
      cout << ele1 << " " << ele2 << endl;
}

int main()
{
  // 初始化集合
  const set<string> A{ "a","b","c","d" };
  const set<string> B{ "e","f","g","h" };
  CertesianProduct(A, B);
  return 0;
}

2.

这一题用到了使用位串来表示集合的所有子集的思想，详细的解释我在《离散数学及其应用》第一章 计算与探索里面写到了，可以去看一下，剩下就贴代码吧。

#include <iostream>
#include <set>
#include <map>
#include <string>

#include <boost/dynamic_bitset.hpp>
#include <boost/utility.hpp>

using std::cout;
using std::endl;
using std::set;
using std::map;
using std::string;

using boost::dynamic_bitset;

// 若需要传入64个以上的元素，需要考虑为dynamic_bitset实现自增运算
template<typename T>
void DisplayPowerSet(const set<T> &inputSet)
{
  const size_t size = inputSet.size();
  map<size_t, T> setMap;
  // 将集合的每个元素和一个自然数建立一一对应的关系，并且自然数从0开始，每次递增1
  size_t cnt = 0;
  for (const auto &ele : inputSet)
    setMap[cnt++] = ele;
  // 求出可变位串的最大值
  const size_t bitSetMax = 1 << size;
  // 遍历0到bitSetMax-1求出所有幂集，并显示
  for (uint64_t bitSetNum = 0; bitSetNum != bitSetMax; ++bitSetNum)
  {
    dynamic_bitset<> bitSet(size, bitSetNum);
    cout << bitSet << endl;
    for (size_t index = 0; index != size; ++index)
    {
      if (bitSetNum == 0)
      {
        cout << "空集";
        break;
      }				
      // 如果index对应的位为1，说明该元素存在，就输出
      if (bitSet[index])
        cout << setMap[index] << " ";
    }
    cout << endl;
  }
}

int main()
{
  const set<string> testSet{ "a","b","c","d","e","f","g" };
  DisplayPowerSet(testSet);

  return 0;
}

3.

第三题的公式我暂时还没有找到，作者把这个题放到这里应该是让大家先思考思考吧，如果有人找到了可以告诉我，我补充上来。

4.

第四题的公式在《离散数学及其应用》的470页中，用到了容斥原理，还需要用到排列组合的知识，内部的原理直接在书上学习就好啦！