Posted on 2007-12-21 10:19
Fox 閱讀(3378)
評論(10) 編輯 收藏 引用 所屬分類:
G游戲編程
Author: Fox
對于(1+2+...+N) 的求和，最早就是看高斯的故事，而且說實話，我是沒有這樣的智商的：
????????????????sum(1+2+...+N) = N*(N+1)/2
剛看了一篇研究該級數(shù)求和的文章，雖為調(diào)侃，但實在感覺文中紕漏太多，不禁在此多言。
文中的第一種方法自稱標準，而且還能使“全班2/3的同學(xué)都用俺的標準應(yīng)付老師和試卷”，我大為驚詫：
1?int?i,?sum?=?0
;
2?for(i?=?1;i?<?N;i?++)sum?+=
?i;
3?printf("1-N的級數(shù)和是:?%i",sum);
顯然，printf的結(jié)果是N-1個數(shù)的和，此處，我更愿意相信是文中的筆誤而已。
第二種和第三種方法讓人覺得奇怪：
1?float
?sum;
2?sum?=?(N?^?2)?/?2?+?N?/?2
;
3?printf("1-N的級數(shù)和是:?%i",(int
)sum);
4?
5?float
?sum;
6?sum?=?N?*?(N?/?2?+?0.5
);
7?printf("1-N的級數(shù)和是:?%i",(int)sum);
前面的寫法純屬惡搞，^在C/C++中是異或位操作，相信接觸過位運算的人都知道這一點，而且當(dāng)N為奇數(shù)時，sum的結(jié)果將比真實值少1。后面的寫法更是荒唐，當(dāng)N為奇數(shù)時，sum的結(jié)果將比真實值相去更遠（有興趣的可以仔細看看）。
對于后面兩種寫法，我想說的重點不是這些明顯的錯誤，因為這樣的錯誤只可博眾君一笑。但文中定義sum使用float的做法，讓我百思不得其解。對于計算機的運算，浮點運算的耗時和整型運算的耗時，那不是一個數(shù)量級的。對于該級數(shù)運算，我們完全可以避免浮點運算，而且方法在文章一開始，就已經(jīng)給出了：
1?int
?sum;
2?sum?=?N*(N+1)/2
;
3?printf("1-N的級數(shù)和是:?%i",?sum);
無論N為奇數(shù)還是偶數(shù)，N*(N+1)一定是偶數(shù)，因此，上述方法不存在浮點運算，而且系統(tǒng)會自動將/2的操作優(yōu)化為右移1位。
不知怎么，忽然就想到了遞歸，想到了Fibonacci數(shù)列。講遞歸的教材都會拿上面的級數(shù)求和和Fibonacci數(shù)列做例子。其實，我個人感覺這是不恰當(dāng)?shù)模胂霝榱俗寣W(xué)生掌握遞歸算法，也只能舉類似的簡單的例子。我們也知道，遞歸計算對于堆棧調(diào)用是非常頻繁而耗時的，對于求Hanoi塔這樣的復(fù)雜問題，我不知道不用遞歸有沒有更好的方法，但如果計算Fibonacci數(shù)列還是使用遞歸，在初學(xué)遞歸時是可以原諒的。簡單點的方法可以是這樣：
?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數(shù)列前N項和是:?%i",nFib);?
上面的兩段代碼中sum和nFib的值不能太大:)。
常言道，言過必失。但自私一點講，把自己的錯誤暴露給別人，可以讓自己更好的進步:)，因此，我寫下來，提醒自己也提醒大家，更歡迎大家多批評指正。