欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求大神解答 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;
}

求大神解答 pat甲级 1103 Integer Factorization (30分)
测试点6答案错误,求解答

相关标签: 算法