C++题目描述一般来说一个正整数可以拆分成若干个正整数的和。例如1=110=1+2+3+4等。对于正整数n的一种特定拆分我们称它为优秀的当且仅当在这种拆分下n被分解为了若干个不同的2的正整数次幂。注意一个数x能被表示成2的正整数次幂当且仅当x能通过正整数个2相乘在一起得到。例如10=8+2=2^3+2^1是一个优秀的拆分。但是7=4+2+1=2^2+2^1+2^0就不是一个优秀的拆分因为1不是2的
解题思路: 首先判断给定的数n是否是2的正整数次幂,如果是,则输出n的二进制表示即可,因为任何一个2的正整数次幂都可以表示为2的幂次方的和。
如果n不是2的正整数次幂,那么我们需要找到拆分后的数中是否存在相同的数,如果存在,则输出-1,表示不存在优秀的拆分。
具体的做法是,对于每个数i从2开始,判断n是否可以被i的幂次方整除,如果可以,则将i的幂次方加入到拆分方案中,同时将n除以i的幂次方得到新的n,继续判断新的n是否可以被i的幂次方整除,直到n无法被i的幂次方整除为止。
如果拆分方案中存在相同的数,则输出-1,否则将拆分方案按照从大到小的顺序输出即可。
C++代码实现如下:
#include <iostream>
#include <vector>
using namespace std;
bool isPowerOfTwo(int n) {
return n > 0 && (n & (n - 1)) == 0;
}
vector<int> excellentPartition(int n) {
vector<int> partition;
if (isPowerOfTwo(n)) {
for (int i = 0; i < 32; i++) {
if ((n >> i) & 1) {
partition.push_back(1 << i);
}
}
} else {
for (int i = 2; i <= n; i++) {
while (n % i == 0) {
partition.push_back(i);
n /= i;
}
}
if (partition.size() > 1) {
for (int i = 1; i < partition.size(); i++) {
if (partition[i] == partition[i-1]) {
partition.clear();
partition.push_back(-1);
break;
}
}
}
}
return partition;
}
int main() {
int n;
cin >> n;
vector<int> partition = excellentPartition(n);
for (int i = partition.size() - 1; i >= 0; i--) {
cout << partition[i] << " ";
}
return 0;
}
``
原文地址: http://www.cveoy.top/t/topic/iWwS 著作权归作者所有。请勿转载和采集!