将整数分解成为连续的自然数之和

Bertha 。 2022-07-03 16:22 183阅读 0赞

From: http://www.blker.com/?p=745

找到的讲的最细致的一篇博文。

不过文里面代码变量w声明类型应该是double，

#include <stdio.h> #include <math.h> int main(int argc, char* argv[]) { // 等差数列求和公式 Sum = n*aFirst + n*(n-2)/2; // Sum 为要拆分的整数， // n 为拆分后连续自然数个数 // aFirst 为连续自然数中的第一位数 int Sum, aFirst; int i,j; int k,m; double w; printf("请输入要分解的自然数Sum: "); scanf("%d",&Sum); for(i = 1; i <= Sum/2; i++) //由于是连续自然数，所以首项必定不可能大于sum/2 { aFirst = i; w = (2*aFirst-1) * (2*aFirst-1) + 8*Sum; k = (int)sqrt(w); m = k - 2*aFirst + 1; int intw=(int)w; if(k*k != intw) // k是一个平方数 continue; else if(m %2 !=0) // m必须为偶数 continue; else { printf("可以分解%d个连续自然数：/n",m/2); for(int j=1;j<=m/2;j++) { printf("%d ",i+j-1); } printf("/n"); } } return 0; }

方法利用了等差数列的性质，输入的整数是等差数列的和，假如这个数列是所求结果，数列中元素的个数就是结果的元素个数。

\-----------------------------------------------------------------------------------------粉葛先------------------------------------------------------------------------------------------------

下面这个方法看似更加简洁一些：

根据等差数列，求一个数列长度的上界，然后枚举数列长度，满足条件的输出即可。

from：http://hi.baidu.com/ken2008huang/blog/item/099abd09e365e6a92eddd4b4.html

#include <stdio.h> #include <math.h> int main() { int t,inum,M,res,n; int i; scanf("%d",&t); for(t;t>0;t--) { scanf("%d%d",&inum,&M); res = 0 ; n = (int)sqrt((double)M*2); for(i=2;i<=n;i++) { if(M*2%i==0 && M*2/i+1-i>0 && (M*2/i+1-i)%2==0 ) { //既然i已经算出，那么元素个数就是i，计算出来a，就知道整个数列是多少了 double ddd=(2*M/i+1-i)/2; int a=(int)ddd; for(int j=0;j<i;j++) { printf("%d ",a+j); } printf("\n"); res++; } } printf("%d %d\n",inum,res); } return 0; }

\--------------------------------

看这里：[http://blog.csdn.net/kennyrose/article/details/6544518][http_blog.csdn.net_kennyrose_article_details_6544518]

这篇文章里写的比较明白。

用等差数列的时候，将公式写出来，然后满足那个公式的所有aFirst都是满足条件的。

整个算法的时间复杂度为O(n)。

[http_blog.csdn.net_kennyrose_article_details_6544518]: http://blog.csdn.net/kennyrose/article/details/6544518