问题: 对于一个任意的自然数,问是否能将其拆分成2个或2个以上的连续自然数之和,写出所有的等式。
解题思路: 第一种解法是推导出数学公式,因为连续的自然数可以用等差数列Sn求和公式,判断可行性。公式推导以及证明过程:数学解法;
第二种解法是直接穷举解法,不过对于较大的数字复杂度O(n^2)可能不够解决,由于连续的自然数一定是递增状态,我们可以用尺取法,也就是双指针法将复杂度降低到O(n)
双指针解法:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void print_Answer (ll l, ll r) {
printf("AC Answer is : ");
for (ll i = l; i<= r; i++) {
printf("%d%c", i, " \n"[i==r]);
}
}
//写法1
void get_Answer (ll goal) {
ll i, j, tmp, flag;
i = 1, j = 1;
flag = 0;
//搜索首项i和尾项j
while (i <= goal/2 && j <= goal) {
tmp = (i+j)*(j-i+1)/2;
if(tmp == goal) {
print_Answer(i,j);
flag = 1;
i++;
j++;
continue;
}
if(tmp > goal) {
i++;
continue;
}
j++;
}
if(flag == 0) {
printf("不存在该数的拆分策略!\n");
}
return ;
}
//写法2
void get_Answer2 (ll goal) {
ll i, j, sum, flag = 0;
i = j = 1;
sum = 0;
while (i <= goal/2) {
while (j <= goal && sum < goal) {
sum += j;
j++;
}
if(sum < goal) {
break;
}
if(sum == goal) {
print_Answer(i,j-1);
flag = 1;
}
sum -= i++; //移位
}
if(flag == 0) {
printf("不存在该数的拆分策略!\n");
}
return ;
}
int main() {
int N;
scanf("%d", &N);
printf("写法1:\n");
get_Answer(N);
printf("\n写法2:\n");
get_Answer2(N);
return 0;
}