browser icon
You are using an insecure version of your web browser. Please update your browser!
Using an outdated browser makes your computer unsafe. For a safer, faster, more enjoyable user experience, please update your browser today or try a newer browser.

从高斯数列谈代码效率

Posted by on 2002 年 04 月 18 日

你可以任意转载本文,但请在转载后的文章中注明作者和原始链接。
媒体约稿请联系 titilima_AT_163.com(把“_AT_”换成“@”)。

很多有关编程的书上说过,算法的高速与代码的短小往往是不可兼得的;特别是在当前的硬件环境(高速的CPU与大容量的硬盘)下,不必计较算法是否既是最快的又是最短的,一般来说,能达到二者之一就行了。然而我认为,在某些情况下,鱼与熊掌是可以兼得的——只需在算法中做一点人为的“手脚”。以下我将用一个简单的例子来谈这个问题,但我的前提是我决不使用那种spaghetti式的算法,即使能够获得高效的代码。

例:求1+2+3+……+100。

解1:用for循环来求(用C++来实现算法,下同)。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
using namespace std;
 
int main(void)
{
    int i, sum = 0;
    for (i = 1; i < 101; i++)
    {
        sum += i;
    }
    cout << "sum = " << sum << endl;
    return 0;
}

解2:用递归来求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int getsum(int x)
{
    if (1 == x)
    {
        return 1;
    }
    else
    {
        return (x + getsum(x - 1));
    }
}
 
int main(void)
{
    int sum = getsum(100);
    cout << "sum = " << sum << endl;
    return 0;
}

很明显,以上两种算法中解2的效率较低,因为在递归中消耗了太多的系统资源。解1的效率确实很高,然而我要告诉你,它并不是效率最高的算法!现在请看我的代码,是我从一本入门级的教材上得到的灵感:

1
2
3
4
5
6
7
8
9
#include <iostream>
using namespace std;
 
int main(void)
{
    int sum = (1 + 100) * 100 / 2;
    cout << "sum = " << sum << endl;
    return 0;
}

是的,这是高斯求和公式。但你看了这样的"算法",也许会很不舒服,并告诉我:这不能算做一个好的算法,因为它没有体现出计算机的优越性。没错,你说得很对,那本教材举的这个例子也正是反例,并且不提倡这样编程,理由正如你所说的一样。
但是,不管你乐意不乐意,你都必须承认:这段代码是合法的,并且它不是spaghetti,可读性也很强;最重要的一点是它的效率非常高——它没有做100次循环,只做了三步运算,而且还节省出了一个变量(i)的存储单元。
教材是教材,编程是编程。教材的目的是让你设计出如何让计算机做更多工作的算法,而你甚至可以连高斯求和公式都不必知道,只让计算机不厌其烦地循环100次;编程的目的是以尽可能高效的算法得到正确答案,而不必计较应该采用循环还是高斯求和公式。然而两者又不能完全分离:如果一个程序员只注重前者,那么他的代码难免冗长或低速;如果他一味追求后者,那么他难免写出没几人看懂的高效spaghetti。
我想谈的东西到此为止。总之在程序的设计中,在特定的情况下,完全可以采用类似的方法来提高效率,这没有什么不好——毕竟,程序是用来求解的,而不是用来体现计算机的优越性的。从这里说开去,如果让你设计一个程序,打印1~100的素数,你如何处理“2”呢?
当然,如果针对本例(高斯数列)而言,最高效的代码应该如下: 

1
2
3
4
5
6
7
8
#include <iostream>
using namespace std;
 
int main(void)
{
    cout << "sum = " << 5050 << endl;
    return 0;
}

订阅本站

7 Comments

  • At 2008.03.28 00:59, LL said:

    呵呵,你也这么认为啊?我当时刚学C的时候,老师出了道从1+到100的题,我就想过用高斯数列,但老师说我这不是编程,而是偷机取巧小聪明。。。

    • At 2008.08.19 15:52, 31956286 said:

      hehe ……

      • At 2008.09.09 10:05, dijaska said:

        非常同意您的观点>

        程序员应该替计算机思考, 计算机应该为程序员计算。。

        还有那个汉诺塔的例子,要我写的话我直接写:
        return (1<

        • At 2010.05.23 16:43, Магсн said:

          过了N年来看这个问题,记得一个搞汇编的人说,写一个程序,不一定全部用汇编,等你用c写完程序,发现哪个地方用汇编效率会提高很多,那么用汇编重写这段,这才是最高明的。

          • At 2012.04.19 14:24, 罗青 said:

            如果那个不叫高斯公式,叫做等差序列的话是不是就可以了。

            • At 2012.04.24 09:20, 李马 said:

              不明白你的意思。说法变了,算法会变吗?

            • […] 仅列代码,不予评论。当然,如果你对这个话题感兴趣,可以点这里看我另一篇类似的博文。 […]

              (Required)
              (Required, will not be published)