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

不得不说，计算与探索和计算机课题的难度还是有一定差别的。

接下来会给出第一章计算与探索中的第1到3题的实现：

Q1：找出这样的正整数：它不是9个不同的正整数的立方和。

当然，我们不用蛮力法来解题，手写9层循环也是很累的呀！（我当然不会告诉你我其实一开始用的就是蛮力法）

好了，进入正题：

我们需要找到9个不同的正整数，而且能够尽量节约时间，那么我们可以在《离散数学及其应用》的114页找到“集合的计算机表示”这一节，这一节介绍了集合其实可以用二进制位来表示，每个二进制位代表一个元素。

我们可以发现，假如我们有一个3元素的集合，每一个元素对应的位是否为1，可以表示它是否存在，例如一个集合有元素0、1和2，分别对应二进制位的第0位、第1位和第2位，那么二进制数000表示三个元素都不存在，001表示元素0存在，其他两个都不存在，010代表元素1存在，其他两个不存在，直到111代表三个都存在。那么从000~111的二进制数刚好代表3个元素的集合的所有子集。

结论：

n位二进制数的所有表示形式和有n个元素的集合的所有子集是一一对应的关系，并且我们假定对应位为1该元素存在，对应位为0该元素不存在。

我们知道：n个元素的所有子集数是 2^n 个，n位二进制数能表示所有不同的数也是 2^n 个。

我们想要从有1到20的所有正整数的集合中找出所有刚好含有9个元素的子集，就可以转换为从20位的二进制数中找到刚好有9个二进制位为1的所有二进制数，那么我们就直接借助计算机的整型数来表示二进制位，遍历从 0到 2^20-1 的所有二进制数，再从中找到刚好有9个二进制位为1的二进制位串，就可以找到刚好含有9个元素的子集。这个过程完全可以用计算机内置的加法来完成，并且解析的时候可以使用位操作进行解析，不需要更高层次的抽象机制，不会给程序带来很大的负担。

接下来是源码：

C++实现：

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <string>
#include <cmath>

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

// 返回x的二进制的1的个数
inline uint64_t BitCount(uint64_t x)
{
  uint64_t sum = 0;
  uint64_t mask = 0x1111111111111111; // Now mask equals to 0x 1111 1111 1111 1111
  sum += x & mask;
  sum += (x >> 1) & mask;
  sum += (x >> 2) & mask;
  sum += (x >> 3) & mask;
  // 4 bits a group
  mask = 0xffffffff;  // Now mask equals to 0x ffff ffff
  sum = (sum & mask) + ((sum >> 32) & mask);
  // 8 bits a group
  mask = 0x0f0f0f0f;  // Now mask equals to 0x 0f0f 0f0f
  sum = (sum & mask) + ((sum >> 4) & mask);
  mask = 0xffff;
  sum = (sum & mask) + ((sum >> 16) & mask);
  mask = 0xff;
  sum = (sum & mask) + ((sum >> 8) & mask);
  return sum;
}

// 将数据存储到硬盘中
template<typename T>
inline void SaveData(T &numVec, string filename)
{
  ofstream txt_Out(filename, ofstream::out | ofstream::trunc);
  txt_Out << "Size: " << numVec.size() << endl;
  txt_Out << "Element: " << endl ;
  for (auto &num : numVec)
    txt_Out << num << endl;
  txt_Out.close();
}
/* 求出不可重复的正整数集合次幂和，返回值为存有这些数的集合
 * pow表示需要求的整数的幂次数，cntBitSet表示每次有几个数参与运算，maxCandiNum表示候选数的最大值，也就是集合的元素个数，程序使用的64位的无符号数，所以不能超过64位
 */
set<uint64_t> NonRepeatedPosiIntPowerSum(const uint32_t powNum, const uint32_t cntBitSet, const uint32_t maxCandiNum)
{
  // maxBitSet是循环的次数，maxBitSet的值等于2^n，
  // numOne是辅助移位变量，字面值1编译器默认认为它为32位数
  const uint64_t numOne = 1;
  const uint64_t maxBitSet = numOne << maxCandiNum;
  // allNumVec存放所有满足条件的数字,由于数字量很大，首先分配一些内存提高程序性能
  vector<uint64_t> allNumVec;
  allNumVec.reserve(200000);

  // 用 bitSet的二进制位串表示一个集合，最低位表示数字元素1，最高位表示数字元素64，防止出现算术移位，所以使用无符号类型 
  // 二进制位为1代表存在该数字元素，为0代表不存在，00101代表存在数字1和3,并且2、3和4不存在 
  for (uint64_t bitSet = 0; bitSet != maxBitSet + 1; ++bitSet)
  {
    // 如果位串的1个数不为cntBitSet个，那么跳过本次循环 
    if (BitCount(bitSet) != cntBitSet)
      continue;
    // 用numVec保存本次循环被选出的9个元素
    vector<uint32_t> numVec;
    numVec.reserve(cntBitSet);
    // bit_loc 代表现在处理的是哪个位置的二进制位，但是对应的数字是bit_loc+1 
    for (uint32_t bit_loc = 0; bit_loc != maxCandiNum; ++bit_loc)
      // 通过位运算筛选出本次循环的9个数字元素，存放到numArray中
      if ((bitSet >> bit_loc & 1) == 1)
        numVec.push_back(bit_loc + 1);
    uint64_t sum = 0;
    for (const uint32_t &num : numVec)
      sum += pow(num, powNum);
    allNumVec.push_back(sum);
  }

  

  // 由于数值很可能存在重复，所以定义集合来保存唯一的数值，并且按照升序排序
  set<uint64_t> setAllNum;
  for (const uint64_t &num : allNumVec)
    setAllNum.insert(num);
  return setAllNum;
}

int main()
{
  // pow表示需要求的整数的幂次数
  const uint32_t powNum = 3;
  // cntBitSet表示每次有几个数参与运算 
  const uint32_t cntBitSet = 9;
  // maxCandiNum表示候选数的最大值，也就是集合的元素个数，程序使用的64位的无符号数，所以不能超过64位
  const uint32_t maxCandiNum = 30;
  
  set<uint64_t> setAllNum;
  setAllNum = NonRepeatedPosiIntPowerSum(powNum, cntBitSet, maxCandiNum);

  // 找出setAllNum的最大值
  uint64_t maxNum = 0;
  for (const uint64_t &num : setAllNum)
    if (num > maxNum)
      maxNum = num;

  cout << "1~" << maxNum << "范围内是" << cntBitSet << "个正整数的" << powNum << "次方和的数一共有：" << setAllNum.size() << "个" << endl;

  // otherNumVec存放所有不满足条件的数字
  vector<uint64_t> otherNumVec;
  otherNumVec.reserve(200000);

  uint32_t cnt = 0;
  for (uint32_t num = 1; num != maxNum + 1; ++num)
  {
    // 如果遇到满足条件的元素就跳过,count会返回该数值的个数，为1就跳过本次循环
    if (setAllNum.count(num))
      continue;
    otherNumVec.push_back(num);
  }
  cout << "1~" << maxNum << "范围内是" << cntBitSet << "个正整数的" << powNum << "次方和的数一共有：" << otherNumVec.size() << "个" << endl;

  string path = "是" + std::to_string(cntBitSet) + "个数的" + std::to_string(powNum) + "次方和的数.txt";
  cout << path << endl;
  SaveData(setAllNum, path);
  path = "不是" + std::to_string(cntBitSet) + "个数的" + std::to_string(powNum) + "次方和的数.txt";
  cout << path << endl;
  SaveData(otherNumVec, path);

  return 0;
}

里面的BitCount函数的实现可以自己用一个例子代入尝试一下整个算法流程就可以很好的理解啦。

Q2：找出大于79的正整数：它不是18个正整数的四次幂的和。

这次的要求的是18个正整数，也就是可以存在重复的情况，18个数用蛮力法就更不行啦。

那这一题可以用整型数的二进制位串来做吗？当然可以，首先请大家看《离散数学及其应用》第358页中“有重复的组合”这一节，介绍了有重复的组合是如何表示的，是如何计算的，作者写得很好，我就不搬运了，请大家看完之后再看下面。

我们现在知道了，要求解n个元素的集合的可重复的r组合数，就是n-1个分隔栏和r个元素的组合数，那我们就把二进制位串中的1当作分隔栏，0当作存在的元素（当然反过来也可以的），按照之前的思路，我们如果想从20个元素的集合中找出可以重复的10个元素的组合，这时候至少需要20-1+10=29位二进制位来表示，我们就遍历从0到  的所有数，找出其中二进制位为1个数为20-1=19个的所有数，就可以找出所有20个元素的集合的可重复的10组合的表示。这个过程和上一题类似，只需要每次对整型数加1，并且用位操作进行解析就可以完成。

接下来是源码：

C++实现：

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <string>
#include <cmath>

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

/* 可以借鉴1.1的思想，将可以重复的组合仍然映射为位串，由于可以n元素可以重复的组合r组合可以看作，r个元素和n-1个栅栏的组合，就把r个元素当作0，把n-1个栅栏当作1，
 * 反过来也可以，再用BitCount就可以，就需要改一下解析的部分，把1看作分隔栏，最右边的1是1和2的分隔栏，它右边的1的是2和3的分隔栏，看它们中间有多少个1就可以知道
 * 相应位置（例如数字1）有多少个了，然后就可以了。
 */


// 返回x的二进制的1的个数
inline uint64_t BitCount(uint64_t x)
{
  uint64_t sum = 0;
  uint64_t mask = 0x1111111111111111; // Now mask equals to 0x 1111 1111 1111 1111
  sum += x & mask;
  sum += (x >> 1) & mask;
  sum += (x >> 2) & mask;
  sum += (x >> 3) & mask;
  // 4 bits a group
  mask = 0xffffffff;  // Now mask equals to 0x ffff ffff
  sum = (sum & mask) + ((sum >> 32) & mask);
  // 8 bits a group
  mask = 0x0f0f0f0f;  // Now mask equals to 0x 0f0f 0f0f
  sum = (sum & mask) + ((sum >> 4) & mask);
  mask = 0xffff;
  sum = (sum & mask) + ((sum >> 16) & mask);
  mask = 0xff;
  sum = (sum & mask) + ((sum >> 8) & mask);
  return sum;
}

// 将数据存储到硬盘中
template<typename T>
inline void SaveData(T &numVec, string filename)
{
  ofstream txt_Out(filename, ofstream::out | ofstream::trunc);
  txt_Out << "Size: " << numVec.size() << endl;
  txt_Out << "Element: " << endl;
  for (auto &num : numVec)
    txt_Out << num << endl;
  txt_Out.close();
}

/* 求出可重复的正整数集合次幂和，返回值为存有这些数的集合
 * pow表示需要求的整数的幂次数，cntBitSet表示每次有几个数参与运算，maxCandiNum表示候选数的最大值，也就是集合的元素个数，程序使用的64位的无符号数，所以不能超过64位
 */
set<uint64_t> RepeatedPosiIntPowerSum(const uint32_t powNum, const uint32_t cntBitSet, const uint32_t maxCandiNum)
{
  // 计算每次需要用到多少二进制位
  // 由于n个元素集合可以重复的的r组合一共需要用maxCandiNum-1+cntBitSet位来表示，程序使用的64位的无符号数，所以这个和不能超过64位
  const uint32_t maxBitNum = maxCandiNum - 1 + cntBitSet;
  // maxBitSet是循环的次数，maxBitSet的值等于2^maxBitNum，因为遍历的是1到2^maxBitNum-1的二进制位，就可以找到所有满足条件的集合
  // numOne是辅助移位变量，字面值1编译器默认认为它为32位数
  const uint64_t numOne = 1;
  const uint64_t maxBitSet = numOne << maxBitNum;
  // allNumVec存放所有满足条件的数字,由于数字量很大，首先分配一些内存提高程序性能
  vector<uint64_t> allNumVec;
  allNumVec.reserve(200000);

  // 用 bitSet的二进制位串表示一个集合，最低位表示数字元素1，最高位表示数字元素64，防止出现算术移位，所以使用无符号类型 
  // 二进制位为1代表分隔栏，为0代表存在数字
  for (uint64_t bitSet = 0; bitSet != maxBitSet + 1; ++bitSet)
  {
    // 如果位串的1个数不为maxCandiNum - 1个(即位串代表分隔的1数不合适，1代表所有候选数中的分隔栏)，那么跳过本次循环 
    if (BitCount(bitSet) != maxCandiNum - 1)
      continue;
    // 用 numVec保存本次循环的位串中，maxCandiNum个元素（从1~maxCandiNum）的每个元素有几个，假如numVec[0]=1，那么数字元素1就有一个，并且初始化其全为0
    vector<uint64_t> numVec(maxCandiNum,0);
    // 保存当前在处理1~cntBitSet中的哪个数字,0代表数字元素1，1代表数字元素2，类推
    uint32_t numProcessing = 0;
    for (uint32_t cntBit = 0; cntBit != maxBitNum; ++cntBit)
    {
      // 当第cntBit位为1时，即需要变化处理的数字位
      if ((bitSet >> cntBit & 1))
        ++numProcessing;
      // 当第cntBit位为0时，该位串中的第numProcessing个数字相应的元素的总数就加1
      else
        ++numVec.at(numProcessing);
    }
    uint64_t sum = 0;
    for (uint32_t num = 1; num != maxCandiNum + 1; ++num)
      sum += static_cast<uint64_t>(numVec.at(num - 1) * pow(num, powNum));
    allNumVec.push_back(sum);
  }
  // 由于数值很可能存在重复，所以定义集合来保存唯一的数值，并且按照升序排序
  set<uint64_t> setAllNum;
  for (const uint64_t &num : allNumVec)
    setAllNum.insert(num);
  return setAllNum;
}

int main()
{
  // pow表示需要求的整数的幂次数
  const uint32_t powNum = 4;
  // cntBitSet表示每次有几个数参与运算 
  const uint32_t cntBitSet = 18;
  // maxCandiNum表示候选数的最大值，也就是集合的元素个数
  const uint32_t maxCandiNum = 10;
  
  set<uint64_t> setAllNum;
  setAllNum = RepeatedPosiIntPowerSum(powNum, cntBitSet, maxCandiNum);

  // 找出setAllNum的最大值
  uint64_t maxNum = 0;
  for (const uint64_t &num : setAllNum)
    if (num > maxNum)
      maxNum = num;
  cout << "1~" << maxNum << "范围内是" << cntBitSet <<"个正整数的" << powNum << "次方和的数一共有：" << setAllNum.size() << "个" << endl;

  // allNumNeededVec存放所有不满足条件的数字
  vector<uint64_t> otherNumVec;
  otherNumVec.reserve(200000);

  uint32_t cnt = 0;
  for (uint64_t num = 1; num != maxNum + 1; ++num)
  {
    // 如果遇到满足条件的元素就跳过,count会返回该数值的个数，为1就跳过本次循环
    if (setAllNum.count(num))
      continue;
    otherNumVec.push_back(num);
  }
  cout << "1~" << maxNum << "范围内是" << cntBitSet << "个正整数的" << powNum << "次方和的数一共有：" << otherNumVec.size() << "个" << endl;

  string path = "是" + std::to_string(cntBitSet) + "个数的" + std::to_string(powNum) + "次方和的数.txt";
  cout << path << endl;
  SaveData(setAllNum, path);
  path = "不是" + std::to_string(cntBitSet) + "个数的" + std::to_string(powNum) + "次方和的数.txt";
  cout << path << endl;
  SaveData(otherNumVec, path);

  return 0;
}

Q3：找出尽可能多的正整数：它可以用两种不同的方式写成正整数的立方和，1729就具有这个性质。

这一题和第二题类似，是可以重复的情况，那么我们就可以调用第二题的封装好的函数就可以做这一题啦。在第三题实现的时候我稍微改了一下那个函数，便于后面查重，大家就看代码好啦！

接下来是源码：
C++实现：

#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using std::vector;
using std::sort;
using std::set;
using std::string;
using std::ofstream;
using std::cout;
using std::endl;

// 返回x的二进制的1的个数
inline uint64_t BitCount(uint64_t x)
{
  uint64_t sum = 0;
  uint64_t mask = 0x1111111111111111; // Now mask equals to 0x 1111 1111 1111 1111
  sum += x & mask;
  sum += (x >> 1) & mask;
  sum += (x >> 2) & mask;
  sum += (x >> 3) & mask;
  // 4 bits a group
  mask = 0xffffffff;  // Now mask equals to 0x ffff ffff
  sum = (sum & mask) + ((sum >> 32) & mask);
  // 8 bits a group
  mask = 0x0f0f0f0f;  // Now mask equals to 0x 0f0f 0f0f
  sum = (sum & mask) + ((sum >> 4) & mask);
  mask = 0xffff;
  sum = (sum & mask) + ((sum >> 16) & mask);
  mask = 0xff;
  sum = (sum & mask) + ((sum >> 8) & mask);
  return sum;
}

// 将数据存储到硬盘中
template<typename T>
inline void SaveData(T &numVec, string filename)
{
  ofstream txt_Out(filename, ofstream::out | ofstream::trunc);
  txt_Out << "Size: " << numVec.size() << endl;
  txt_Out << "Element: " << endl;
  for (auto &num : numVec)
    txt_Out << num << endl;
  txt_Out.close();
}

/* 求出可重复的正整数集合次幂和，返回值为存有这些数的向量
 * pow表示需要求的整数的幂次数，cntBitSet表示每次有几个数参与运算，maxCandiNum表示候选数的最大值，也就是集合的元素个数，程序使用的64位的无符号数，所以不能超过64位
 */
vector<uint64_t> RepeatedPosiIntPowerSum(const uint32_t powNum, const uint32_t cntBitSet, const uint32_t maxCandiNum)
{
  // 计算每次需要用到多少二进制位
  // 由于n个元素集合可以重复的的r组合一共需要用maxCandiNum-1+cntBitSet位来表示，程序使用的64位的无符号数，所以这个和不能超过64位
  const uint32_t maxBitNum = maxCandiNum - 1 + cntBitSet;
  // maxBitSet是循环的次数，maxBitSet的值等于2^maxBitNum，因为遍历的是1到2^maxBitNum-1的二进制位，就可以找到所有满足条件的集合
  // numOne是辅助移位变量，字面值1编译器默认认为它为32位数
  const uint64_t numOne = 1;
  const uint64_t maxBitSet = numOne << maxBitNum;
  // allNumVec存放所有满足条件的数字,由于数字量很大，首先分配一些内存提高程序性能
  vector<uint64_t> allNumVec;
  allNumVec.reserve(200000);

  // 用 bitSet的二进制位串表示一个集合，最低位表示数字元素1，最高位表示数字元素64，防止出现算术移位，所以使用无符号类型 
  // 二进制位为1代表分隔栏，为0代表存在数字
  for (uint64_t bitSet = 0; bitSet != maxBitSet + 1; ++bitSet)
  {
    // 如果位串的1个数不为maxCandiNum - 1个(即位串代表分隔的1数不合适)，那么跳过本次循环 
    if (BitCount(bitSet) != maxCandiNum - 1)
      continue;
    // 用 numVec保存本次循环的位串中，maxCandiNum个元素（从1~maxCandiNum）的每个元素有几个，假如numVec[0]=1，那么数字元素1就有一个，并且初始化其全为0
    vector<uint64_t> numVec(maxCandiNum, 0);
    // 保存当前在处理1~cntBitSet中的哪个数字,0代表数字元素1，1代表数字元素2，类推
    uint32_t numProcessing = 0;
    for (uint32_t cntBit = 0; cntBit != maxBitNum; ++cntBit)
    {
      // 当第cntBit位为1时，即需要变化处理的数字位
      if ((bitSet >> cntBit & 1))
        ++numProcessing;
      // 当第cntBit位为0时，该位串中的第numProcessing个数字相应的元素的总数就加1
      else
        ++numVec.at(numProcessing);
    }
    uint64_t sum = 0;
    for (uint32_t num = 1; num != maxCandiNum + 1; ++num)
      sum += static_cast<uint64_t>(numVec.at(num - 1) * pow(num, powNum));
    allNumVec.push_back(sum);
  }

  sort(allNumVec.begin(), allNumVec.end());

  return allNumVec;
}
int main()
{
  // pow表示需要求的整数的幂次数
  const uint32_t powNum = 3;
  // maxCandiNum表示候选数的最大值，也就是集合的元素个数
  const uint32_t maxCandiNum = 30;

  vector<uint64_t> numVec(RepeatedPosiIntPowerSum(powNum, 2, maxCandiNum));
  vector<uint64_t> neededNum;
  vector<uint64_t> testVec;
  testVec.reserve(numVec.size());
  set<uint64_t> numSet;
  uint32_t cnt = 0;
  for (uint32_t i = 0; i != numVec.size(); ++i)
  {
    uint64_t num = numVec.at(i);
    numSet.insert(num);
    testVec.push_back(num);
    if (numSet.size() + cnt != testVec.size())
    {
      neededNum.push_back(numVec.at(i));
      ++cnt;
    }
  }
  cout << cnt << "个" << endl;
  for (const uint64_t &num : neededNum)
    cout << num << endl;
  return 0;
}