Posted on 2007-12-21 10:19
Fox 阅读(3346)
评论(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的值不能太大:)。
常言道，言过必失。但自私一点讲，把自己的错误暴露给别人，可以让自己更好的进步:)，因此，我写下来，提醒自己也提醒大家，更欢迎大家多批评指正。