思路是 用一个数组存储所有的分解项 随后不断比较更新得到长度最大的最小序列 细节写在注释里了
代码如下:
//一个正整数 N 的因子中可能存在若干连续的数字.给定任一正整数 N,
//要求编写程序求出最长连续因子的个数,并输出最小的连续因子序列。
#include<iostream>
using namespace std;
//数据到2的31次方,最多31个2乘起来 数组开到31
int arr[31];
//begin是最小序列开始处 max是序列长度最大值
int Begin, Max=0;
//最终最小序列数组
int* Sequence;
//计算数组中最长因子的个数
void Count(int* arr,int index) {
//begin和max是两个替身
int begin=0;
int max = 0;
int count = 1;
for (int i = 0; i < index; i++) {
//是连续的就继续计算
if (arr[i] + 1 == arr[i + 1]) {
count++;
}
//不是连续的,判断max,更新
else {
if (max < count) {
max = count;
begin = i - max +1;
}
count = 1;
}
}
//如果这个替身比当前的要大 等于不考虑 之前的肯定是更小序列
if (Max < max) {
Max = max;
Begin = begin;
Sequence = new int[Max];
for (int i = 0; i < Max; i++) {
Sequence[i] = arr[Begin + i];
}
}
}
//index : 当前数组下标
//current : 当前分解值
//rest : 当前剩余值
void decompose(int index,int current,int rest) {
//出口 rest == 1代表分解完毕
if (rest == 1) {
Count(arr,index);
}
//找准一个数作为本次分解的值(要比大于等于之前的),不断递归直到分完
else {
//和判断素数一样,判断到平方根就可以
for (int i = current; i <= rest; i++) {
//如果当前的这个能整除 作为因子进递归
if (rest % i == 0) {
arr[index] = i;
current = i;
decompose(index + 1, current, rest / i);
}
}
}
}
int main() {
int n;
cin >> n;
decompose(0,2,n);
//把最大值和数组按格式打印出来
cout << Max << endl;
for (int i = 0; i < Max; i++) {
if (i != Max - 1) {
cout << Sequence[i] << "*";
}
else {
cout << Sequence[Max - 1];
}
}
}
测试用例运行结果
请问这种做法有什么问题?