今天在KADA的博客看到一篇C算法题,就分析了一下下!这是我个人理解(白话文),就是为了做一下分析记录,话说从CPP以来,除了后续几章的什么队列呀,链表啊之类的我就没看过算法code,今天看了一下,很有兴趣!

:cool:
编写一个程序,读入一个正整数(就是不带负号的整数),把所有的连续的(比如:12345!{上山打老虎}),和与给定的正整数相等的正整数们找出来。例如,如果输入为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比较。(为啥N/2?举例一下,比如21吧要是N不/2的话,那么就会有11+12,12+13但是他们和21不相等,所以超过11以后就没有机会相加得21了。所以能就N/2来减少穷举次数,提升程序运行速度啦)

上面和下面的就不废话了,就说中间的那段核心吧.for循环

#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++)//说下n/2+1.因为有些特殊的数字比如27,27/2就是13啦,若不加1那么13&lt;=13,循环从这里就over了,所以就没有13+14的这样组合那么就少计数一个组合
    {
        for(sum=i,j=i+1; j<=n/2+1; j++)//因为是连续正整数和,所以j比i永远多1,这就是有j=i+1的由来
        {
            sum += j;//sum=sum+j,i赋值给sum和j相加,类似2+3+4+5+6+7,然后总值赋值给sum.
            if(sum == n)//由sum和n比较,如果sum=27,也就是2+3+4+5+6+7=27就执行if里面的语句,计数器并加1,跳出里层的for循环,执行外层for。
            {
                printf("%d -- %d\n", i, j);
                count++;
                continue;
            }
        }
    }
    if(count > 0)//for执行完毕后,计数器大于0输出结果
        printf("共有%d种连续整数和等于%ld\n", count, n);
    else
        printf("没有解\n");
}

就逻辑到这里..还有一种算法比这更好,不过我还未理解!等我理解了再把那种算法分析写出来.这篇日志作为分析记录,若我分析的不对,请指出哦! :evil:

§34 · February 18, 2010 · 扯蛋志 · Tags: · [Print]

9 Comments to “C语言名题系列:连续整数和”

  1. 超人 says:

    C.. 厉害哇!!! :twisted: :twisted: :twisted: :twisted:

  2. 扯帅锅 says:

    :mad: 以前学过一点点 呵呵

  3. Kada says:

    其实N/2的原因是:加到N/2就够了,如果再往后加,光N/2+N/2+1都已经比N还大了。因为int类型/运算向下是取整的,所以这里是<N/2+1,来保证N的一半在无论N是奇数偶数时,都能被计算到。

  4. 扯帅锅 says:

    还是你牛啊,突然发现那个20的例子就是个错误,改改去!

  5. Kada says:

    你的主页有点问题。

  6. 泡面 says:

    博客不错,支持一下!

  7. Kada says:

    主题不错,不要博客了两篇就阳痿啊!

  8. 扯帅锅 says:

    @Kada 别激动.晚上写文章 :evil:

  9. [...] 上篇博文分析C语言名题系列:连续整数和正常人思考的算法…就是1+2+3+4+5…然后和N比较,跟N相等就输出不等就不输出… [...]

Leave a Reply