大家好,我是Ace,这篇文章是《离散数学及其应用》第二章 计算与探索的源码,希望大家喜欢。
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页中,用到了容斥原理,还需要用到排列组合的知识,内部的原理直接在书上学习就好啦!