二
08

C语言名题系列：连续整数和

Kada C/C++ 2010-02-08

　　编写一个程序，读入一个正整数，把所有的连续的，和与给定的正整数相等的正整数们找出来。例如，如果输入为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 <stdio.h>
#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 <stdio.h>
#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

, , ,
Address: http://blog.okkey.net/1081.html，转载请注明出处。
«
»
Trackback

11 comments untill now

  1. 笨笨 @ 2010-02-08 15:45

    这么晚来笨笨居然还有沙发坐，很可惜笨笨不懂C语言，否则还可以和博主侃侃。。

    [回复]

    Kada 回复:
    二月 8th, 2010 at 5:42 下午

    没事情，看看就知道了。

    [回复]

  2. 泡面 @ 2010-02-08 16:34

    KADA加油~过年了就放松下吧，换个内容写写哈！

    [回复]

    Kada 回复:
    二月 8th, 2010 at 5:39 下午

    呵呵呵呵！真实让我难堪阿！

    [回复]

  3. GEZ鸽子 @ 2010-02-08 22:28

    来看看！技术活！

    [回复]

    Kada 回复:
    二月 8th, 2010 at 10:33 下午

    等到有人回复，多么开心啊！

    [回复]

  4. 漠岚 @ 2010-02-09 00:39

    …你更新的忒快咯

    [回复]

  5. 好名字要隐藏 @ 2010-02-09 15:34

    有点像数学

    [回复]

    Kada 回复:
    二月 9th, 2010 at 10:06 下午

    小学的。

    [回复]

  6. evlos @ 2010-02-09 23:27

    呵呵，加油加油 ~

    [回复]

  7. C语言名题系列：连续整数和 | 扯蛋簙 @ 2010-02-19 00:35

    [...] C语言名题系列：连续整数和 今天在KADA的博客看到一篇C算法题，就分析了一下下！这是我个人理解（白话文），就是为了做一下分析记录，话说从CPP以来，除了后续几章的什么队列呀，链表啊之类的我就没看过算法code,今天看了一下，很有兴趣! [...]

Add your comment now