« 上一篇下一篇 »

数据结构-认识算法

如果要你写个程序计算 1+2+3+...+99+100,你会怎么写?

这还不容易,对于我而言,毫不迟疑的做法就是用循环呗,大家来看:

int i,sum = 0;
int n = 100;
for(i = 1;i <= n;i++)
{
    sum = sum + i;
}

有没有其他更为简洁的方法呢?当然有,请看下面:

    sum =   1   +  2 + ... + 99 + 100

    sum = 100 + 99 + ... + 2  +   1

2*sum = 101 + 101 + 101 + ... + 101

                            共100个

所以    sum = 101 * 100 / 2 = 5050

这是数学家高斯的童年故事,老师让他算这个加法,他一下子就给解决了,为啥我就从来没想到过呢?

程序实现如下:

int sum = 0, n = 100;
sum = (1 + n) * n / 2;

是不是简洁多了?第1个程序的处理部分执行次数为n,而这里仅仅是1,而且这个方法还可以推广到一千、一万、甚至更大的数值,也只是一步而已,这就是算法。

算法具有5个基本特性:输入、输出、有穷性、确定性、可行性。

设计算法的要求:

1、正确性:算法程序对于非法的输入数据能够得出满足规格说明的结果。一般情况下,这就是算法的是否正确的判断标准。

2、可读性:算法设计的另一目的是为了便于阅读、理解和交流。可读性是算法好坏很重要的标志

3、健壮性:对待不合理的输入数据也有相应的处理结果,而不是异常结果。

4、时间效率高与存储量低。