Posted on 2007-12-21 10:19
Fox 閱讀(3389)
評論(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的值不能太大:)。
常言道，言過必失。但自私一點講，把自己的錯誤暴露給別人，可以讓自己更好的進步:)，因此，我寫下來，提醒自己也提醒大家，更歡迎大家多批評指正。