A40799. 无方集合
填空题
困难
知识点
题目描述
无方集合
题目描述
小明不是很喜欢完全平方数，他甚至不喜欢加起来是完全平方数的两个数。
今天，他想从1到100 中选择一些数组成一个集合，要求不选择任何一个完全
平方数，集合中任意两个数相加也不能是完全平方数。请问，小明最多能选出多少个数。
参考答案
#include <iostream>
#include <cmath>
using namespace std;
// 全局常量：限定数组最大长度（1-100最多100个数，足够用）
const int MAX_SIZE = 100;
// 全局变量：存储1-100中不是完全平方数的候选数 + 有效长度
int validNums[MAX_SIZE];
int validSize = 0;
// 全局变量：回溯时存储当前选中的数 + 当前长度
int path[MAX_SIZE];
int currentLen = 0;
// 全局变量：记录符合条件的最大集合大小
int maxCount = 0;
// 判断一个数是否是完全平方数
bool isPerfectSquare(int n) {
int sqrt_n = sqrt(n);
return sqrt_n * sqrt_n == n;
}
// 回溯函数：递归枚举所有合法子集（无vector版）
// index：当前处理到候选数的第index个位置
void backtrack(int index) {
// 更新最大集合大小
if (currentLen > maxCount) {
maxCount = currentLen;
}
// 遍历从index开始的所有候选数（避免重复组合）
for (int i = index; i < validSize; i++) {
// 检查当前数能否加入：和已选数的和都不是完全平方数
bool canAdd = true;
for (int j = 0; j < currentLen; j++) {
if (isPerfectSquare(path[j] + validNums[i])) {
canAdd = false;
break;
}
}
// 如果可以加入，就选择当前数并递归
if (canAdd) {
path[currentLen++] = validNums[i]; // 选择当前数（长度+1）
backtrack(i + 1); // 处理下一个数
currentLen--; // 回溯：撤销选择（长度-1）
}
}
}
int main() {
// 第一步：筛选候选数（排除完全平方数，存入数组）
for (int i = 1; i <= 100; i++) {
if (!isPerfectSquare(i)) {
validNums[validSize++] = i; // 存入数组，有效长度+1
}
}
// 第二步：回溯寻找最大合法集合
backtrack(0);
// 输出结果
cout << "最多能选出的数的个数是：" << maxCount << endl;
return 0;
}
上一题
下一题