如果要你写个程序计算 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、时间效率高与存储量低。