Creative Commons License
本Blog采用 知识共享署名-非商业性使用-禁止演绎 3.0 Unported许可协议 进行许可。 —— Fox <游戏人生>

游戏人生

游戏人生 != ( 人生 == 游戏 )
站点迁移至:http://www.yulefox.com。请订阅本博的朋友将RSS修改为http://feeds.feedburner.com/yulefox
posts - 62, comments - 508, trackbacks - 0, articles - 7

也说说级数求和(1+2+3...N)和其他

Posted on 2007-12-21 10:19 Fox 阅读(3326) 评论(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的值不能太大:)。

常言道,言过必失。但自私一点讲,把自己的错误暴露给别人,可以让自己更好的进步:),因此,我写下来,提醒自己也提醒大家,更欢迎大家多批评指正。

Feedback

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2007-12-21 11:15 by bluefly
哈……
一笑而过

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2007-12-21 11:29 by Enoch
有时候别人的无知,更好地提醒自己需要多学习,多改进,多请教,多谦虚,多提问。
谢谢lz提醒了我们。

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2007-12-21 14:12 by winsty
呵呵
确实搞笑

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2008-01-07 16:46 by newrain
呵呵,如果采用查表的方式得到Fibonacci中前面的数据,速度还是不错的,占用的空间估计与递归调用也没有差多少。

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2008-01-07 16:55 by Fox
@newrain
能不能详细说一下怎么查表啊?

# re: 也说说级数求和(1+2+3...N)和其他[未登录]  回复  更多评论   

2008-02-05 21:52 by Felicia
fibonacci数列求和可以用logn的算法,楼主怎么不介绍?
o(∩_∩)o...

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2008-02-15 09:12 by Fox
不是不介绍,是我不知道。。介绍一下吧:D

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2008-07-09 16:37 by ljune
什么东西?要那么复杂的去计算吗?真是的
简单点用递归法让人家也看得明明白白。
int i,n,sum;
for(i=0;i<n;i++)
{
sum=sum+i;
}
printf("Fibonacci数列前N项和是: %i",sum);

# re: 也说说级数求和(1+2+3...N)和其他  回复  更多评论   

2008-07-10 17:42 by Fox
Fn = (phi^n)/(5^(1/2)), phi = 1/2(1+(5^(1/2))).
——计算机程序设计艺术. 第一卷. sec. 1.2.8

# 福娃免费空间 http://h.8wa.com[未登录]  回复  更多评论   

2009-07-04 14:06 by 123
福娃免费空间 http://h.8wa.com

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理