Posted on 2007-12-21 10:19
Fox 阅读(3337)
评论(10) 编辑 收藏 引用 所属分类:
G游戏编程
Author: Fox
对于(1+2+...+N) 的求和,最早就是看高斯的故事,而且说实话,我是没有这样的智商的:
sum(1+2+...+N) = N*(N+1)/2
刚看了一篇研究该级数求和的文章,虽为调侃,但实在感觉文中纰漏太多,不禁在此多言。
文中的第一种方法自称标准,而且还能使“全班2/3的同学都用俺的标准应付老师和试卷”,我大为惊诧:
1 int i, sum = 0
;
2 for(i = 1;i < N;i ++)sum +=
i;
3 printf("1-N的级数和是: %i",sum);
显然,printf的结果是N-1个数的和,此处,我更愿意相信是文中的笔误而已。
第二种和第三种方法让人觉得奇怪:
1 float
sum;
2 sum = (N ^ 2) / 2 + N / 2
;
3 printf("1-N的级数和是: %i",(int
)sum);
4
5 float
sum;
6 sum = N * (N / 2 + 0.5
);
7 printf("1-N的级数和是: %i",(int)sum);
前面的写法纯属恶搞,^在C/C++中是异或位操作,相信接触过位运算的人都知道这一点,而且当N为奇数时,sum的结果将比真实值少1。后面的写法更是荒唐,当N为奇数时,sum的结果将比真实值相去更远(有兴趣的可以仔细看看)。
对于后面两种写法,我想说的重点不是这些明显的错误,因为这样的错误只可博众君一笑。但文中定义sum使用float的做法,让我百思不得其解。对于计算机的运算,浮点运算的耗时和整型运算的耗时,那不是一个数量级的。对于该级数运算,我们完全可以避免浮点运算,而且方法在文章一开始,就已经给出了:
1 int
sum;
2 sum = N*(N+1)/2
;
3 printf("1-N的级数和是: %i", sum);
无论N为奇数还是偶数,N*(N+1)一定是偶数,因此,上述方法不存在浮点运算,而且系统会自动将/2的操作优化为右移1位。
不知怎么,忽然就想到了递归,想到了Fibonacci数列。讲递归的教材都会拿上面的级数求和和Fibonacci数列做例子。其实,我个人感觉这是不恰当的,但想想为了让学生掌握递归算法,也只能举类似的简单的例子。我们也知道,递归计算对于堆栈调用是非常频繁而耗时的,对于求Hanoi塔这样的复杂问题,我不知道不用递归有没有更好的方法,但如果计算Fibonacci数列还是使用递归,在初学递归时是可以原谅的。简单点的方法可以是这样:
1 int fib_odd = 0, fib_even = 1
;
2 int n = (N+1)/2
;
3 for(int i=0; i<n; i++
)
4
{
5 fib_odd +=
fib_even;
6 fib_even +=
fib_odd;
7
}
8 int nFib = 0
;
9 if( N % 2
)
10 nFib =
fib_odd;
11 else
12 nFib =
fib_even;
13 printf("Fibonacci数列前N项和是: %i",nFib);
上面的两段代码中sum和nFib的值不能太大:)。
常言道,言过必失。但自私一点讲,把自己的错误暴露给别人,可以让自己更好的进步:),因此,我写下来,提醒自己也提醒大家,更欢迎大家多批评指正。