PAT-ADVANCED1103——Integer Factorization

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805364711604224

题目描述：

题目翻译：

1103 整数分解

整数N的K-P分解是把N写成K个数的P次的和。你需要写一个程序对任意的整数N、K和P，能够找出N的K-P分解。

输入格式：

每个输入文件只有1行，其中有3个正整数N（<= 400），K（<= N）和P（1 < P <= 7）。一行中的数字由一个空格分隔。

输出格式：

对每个测试用例，如果结果存在，则按以下形式输出：

N = n[1]^P + ... n[K]^P

这里n[i](i = 1, ..., K)是第i个因子。所有的因子必须以非増序输出。

提示：解决方案可能不唯一。举个例子，169的5-2分解有9种解决方案，比如12 ^ 2 + 4 ^ 2+2 ^ 2 + 2 ^ 2 + 1 ^ 2，或11 ^ 2 + 6 ^ 2 + 2 ^ 2 + 2 ^ 2 + 2 ^ 2，还有更多。你需要输出因子和最大的解决方案。如果有输出因子相同的解决方案，你需要输出最大因子序列。如果存在1 <= L <= K使得对于i < L有ai = bi且aL > bL，则定义序列{ a1,a2,⋯,aK }比序列{ b1,b2,⋯,bK }要大。

输入样例1：

169 5 2

输出样例1：

169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2

输入样例2：

169 167 3

输出样例2：

Impossible

知识点：回溯

思路：用一个vector<int> nums存储所有的n ^ P值

由于P不小于2，并且在单次运行中是固定的，因此不妨开一个vector<int> nums，在输入P之后就预处理所有不超过N的n ^ P。为了方便下标与元素有直接的对应，这里应把0也存进去。于是对N = 10、P = 2来说，nums[0] = 0、nums[1] = 1、nums[2] = 4、nums[3] = 9。

为了让结果能保证字典序大的序列优先被选中，我们对nums的遍历应后往前，这样就能优先选中nums中较大的数了。

用一个vector<int> sequence来存储递归过程当前的因子组合，用另一个vector<int> result来存储和最大的因子组合，用int optValue来存储最大的因子和，其初值设为0。

在递归函数中，我们需要传递4个变量，int sum，记录当前的因子P次方和；int value，记录当前因子和；int size，记录当前因子组合sequence中的因子数；int index，记录当前我们正在考虑nums中的第几个因子。

递归的终止条件：

当sum >= N或size >= K时，递归终止。如果此时有sum == N且size == K，则找到了一个解决方案，对该解决方案的value与optValue值进行比较。否则，直接return。

递归过程：

对nums中索引为index的值，我们可以选取它，也可以不选取它，这就对应两种方案，因此我们需要两种情况递归调用。

（1）选取索引为index的值，需要将index加入sequence中，在递归调用dfs(sum + nums[index], value + index, size + 1, index)，然后pop_back()出sequence中的最后一个元素。

（2）接着考虑不选取索引为index的值，则不需要对sequence进行加入元素和pop_back()元素的操作，只需要递归调用dfs(sum, value, size, index - 1)即可。

时间复杂度是O(2 ^ K)。空间复杂度是O(K)。

C++代码：

#include<iostream>
#include<cmath>
#include<vector>

using namespace std;

int N;
int K;
int P;
vector<int> nums;
vector<int> sequence;
vector<int> result;
int optValue = 0;

void dfs(int sum, int value, int size, int index);

int main() {
	cin >> N >> K >> P;
	for(int i = 0; ; i++) {
		int num = (int)pow(i, P);
		if(num > N) {
			break;
		}
		nums.push_back(num);
	}
	dfs(0, 0, 0, nums.size() - 1);
	if(result.size() == 0) {
		cout << "Impossible" << endl;
	} else {
		cout << N << " = ";
		for(int i = 0; i < result.size(); i++) {
			cout << result[i] << "^" << P;
			if(i != result.size() - 1) {
				cout << " + ";
			}
		}
		cout << endl;
	}
	return 0;
}

void dfs(int sum, int value, int size, int index) {
	if(sum >= N || size >= K) {
		if(size == K && sum == N) {
			if(value > optValue) {
				optValue = value;
				result = sequence;
			}
		}
		return;
	}
	if(index - 1 >= 0){
		sequence.push_back(index);
		dfs(sum + nums[index], value + index, size + 1, index);
		sequence.pop_back();
		dfs(sum, value, size, index - 1);
	}
}

C++解题报告：

PAT-ADVANCED1103——Integer Factorization

PAT-ADVANCED1103——Integer Factorization

思路：用一个vector<int> nums存储所有的n ^ P值

相关推荐