编写一个程序，读入一个正整数，把所有的连续的，和与给定的正整数相等的正整数们找出来。例如，如果输入为27，于是发现2+3+4+5+6+7，8+9+10,13+14为27，那么共有3个组合。如果输入的数字是10000，那么就有18加到142，297加到1328，388加到412以及1998加到2002这4组。
通常的算法是，将所有小于n/2的连续正整数的和的情况算出来与n比较。
#include <stdlib.h>
void main()
{
char line[100];
long sum, i, j, n;
int count = 0;
printf("请输入整数n:");
gets(line);
n = atol(line);
for(i=1; i< =n/2+1; i++)
{
for(sum=i,j=i+1; j<=n/2+1; j++)
{
sum += j;
if(sum == n)
{
printf("%d -- %d\n", i, j);
count++;
continue;
}
}
}
if(count > 0)
printf("共有%d种连续整数和等于%ld\n", count, n);
else
printf("没有解\n");
}
但是这样的算法太慢速了！进行了太多的加法！因为在程序中，i与j的关系永远满足1< =i<=n,i+1<=j<=n/2+1,i 如何减少加法的次数呢？可以参考等值首尾和的算法思路。 先求出一个和，sum是1+2加到i,并且sum是第一个大于等于给定值n的整数和。例如，如果n为27,那么sum=1+2+3+4+5+6+7=28。于是，如果i+(i+1)加到j大于n 那么去掉小的一端，及sum变为(i+1)+(i+2)加到j。相应的如果小于sum小于n，则大的一端在增加,即sum=i+(i+1)加到j+(j+1)。不断重复，直到i大于n/2。 代码如下：
#include <stdlib.h>
void main()
{
long left, right;
long sum;
long n;
int count = 0;
char line[100];
printf("请输入n:");
gets(line);
n = atol(line);
for(sum=0,right=1; sum<n ; sum+=right++);
for(left=1, right--; left<=n/2; )
{
if(sum > n)
sum -= (left++);
else
{
if(sum == n)
{
printf("%d -- %d\n", left, right);
count++;
}
sum += (++right);
}
}
if(count > 0)
printf("共有%d种连续整数和等于%ld\n", count, n);
else
printf("没有解\n");
}Related posts
这么晚来笨笨居然还有沙发坐，很可惜笨笨不懂C语言，否则还可以和博主侃侃。。
没事情，看看就知道了。
KADA加油~过年了就放松下吧，换个内容写写哈！
呵呵呵呵！真实让我难堪阿！
来看看！技术活！
等到有人回复，多么开心啊！
…你更新的忒快咯
有点像数学
小学的。
呵呵，加油加油 ~
Pingback 引用通告： C语言名题系列：连续整数和 | 扯蛋簙