求大神解答 pat甲级 1103 Integer Factorization (30分)
程序员文章站
2022-06-11 12:18:28
...
思路:回溯算法
这个题还是习惯用自己的思路做
有点像N皇后
建树:
节点的两个属性:1.选择列表 2.路径
选择列表就是n^2 <= N时,所有的n,假设有m个
对array[1],总共有m个选择。选完之后,再对array[2]选……一直到array[K]。对array[n]的选择类似于对N皇后的第n行随机放皇后。
还做过一个转盘锁的问题,用其思路,假设K = 5,初始是0 0 0 0 0,旋转之后又1 0 0 0 0, 0 1 0 0 0,0 0 1 0 0……共5中情况,然后继续旋转直到得到解。这个方法运行超时,不使用。
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool flag = false;
void Init(vector<int>& selectList, int N, int P) {
int k = 1; /*这里没有理解正整数的范围,k 不能从0开始。如果从0开始,会导致测试点5超时*/
while (1) {
if (pow(k, P) <= N) selectList.push_back(pow(k ++, P));
else break;
}
}
int maxSum = 0; //最大底数和
vector<int> bestVt;
int N, K, P;
//mini起剪枝作用
void DFS(vector<int>& path, vector<int>& selectList, int count, int nowK, int nowSum, int mini) {
if (count == N && nowK == K) {
flag = true;
if (nowSum > maxSum) {
bestVt = path;
maxSum = nowSum;
}
return ;
}
if (count > N || nowK > K || (count == N && nowK != K)) return ;
for (int i = mini; i >= 0; i --) {
if (count + selectList[i] > N || nowK + 1 > K || (count + selectList[i] == N && nowK + 1 != K)) continue;
path.push_back(selectList[i]);
DFS(path, selectList, count + selectList[i], nowK + 1, nowSum + sqrt(selectList[i]), i);
path.pop_back();
}
}
int main() {
cin >> N >> K >> P;
vector<int> path;
vector<int> selectList;
Init(selectList, N, P);
DFS(path, selectList, 0, 0, 0, selectList.size() - 1);
if (!flag) cout << "Impossible" << endl;
else {
cout << N << " = ";
for (int i = 0; i < K; i ++) {
if (i != K - 1) cout << sqrt(bestVt[i]) << "^" << P << " + ";
else cout << sqrt(bestVt[i]) << "^" << P << endl;
}
}
return 0;
}
测试点6答案错误,求解答