BCC-16 (in Chinese) 計算機概論十六講 C -- more iterations

C 教材：更多的迭代範例

在這一節裡面，我們列舉許多使用迭代語法結構 (亦即 while 或 for) 的基本數學計算範例。讀者透過反覆的觀察、模擬與練習，務必掌握這些最基本的語法。

【例一】一個關於高斯 (Carl Gauss) 的著名軼事，是他在八歲的時候，發明了一個很聰明的辦法，計算

1 + 2 + 3 + ... + 99 + 100 = 50 * 101 = 5050

如果我們沒有高斯那麼聰明，但是至少我們有電腦和程式語言。現在我們寫一個程式來計算 1 + 2 + 3 + ... + 99 + 100。純粹是為了練習，我們要電腦笨笨地做 99 次加法，不要用聰明的高斯算法或任何數學公式。先看 while 版本：

#include <stdio.h>
main() {
    int n, sum;
    n = 1;
    sum = 0;
    while (n <= 100) {
        sum = sum + n;
        n = n + 1;
    }
    printf("%d\n", sum);
}

再來個 for 版本：

#include <stdio.h>
main() {
    int n, sum;
    sum = 0;
    for (n=1; n <= 100; ++n) {
        sum = sum + n;
    }
    printf("%d\n", sum);
}

其實上面的程式可以寫得更短。首先， sum = 0; 這一句可以合併到宣告語句裡面，也可以合併到 for 的 INITIAL 部分。其次，for 迴圈的 STATEMENTS_ 部分只有一個指令，可省略大括號。因此可以縮短成以下的樣子：

#include <stdio.h>
main() {
    int n, sum;
    for (n=1, sum=0; n <= 100; ++n)
        sum = sum + n;
    printf("%d\n", sum);
}

以下的例子，都可以有 while 和 for 兩種版本，但是我們都只挑一種語法來寫。請讀者自行練習另外一種。而且，以下的例子，我們都不刻意縮短程式，請讀者自行練習縮短的語法。

【例二】計算

$\sum_{n=1}^{1000} \frac1{n^2}$

並輸出答案到小數點下第四位。

#include <stdio.h>
main() {
    int n;
    double sum;
    sum = 0.0;
    for (n=1; n <= 1000; ++n) {
        sum = sum + 1.0/(n*n);
    }
    printf("%.4f\n", sum);  
}

輸出應該是 1.6439。

以上那種類型的程式，初學者最常犯的錯誤有：

沒有把 sum 變數宣告成小數類型 (例如 float)
忘記定義 sum 的初始值
寫成整數除法指令 1/(n*n)，這樣的除法結果，只要 n > 1，就得到 0
*衝惘a將平方寫成 n^2，但是 C 沒有這種平方符號
忘記加括號，寫成 1.0/n*n，這其實是 (1.0/n) * n 的意思

請讀者務必警惕這些常犯的錯誤。

【例三】計算

$x = \sum_{n=1}^{500} {1\over n(n+1)}$

並以 %f 格式輸出。我們早就知道 1/(n*(n+1)) = 1/n - 1/(n+1)；所以上述連和可以化簡成 1 - 1/501 = 0.99800399... 不過我們還是可以令程式語言笨笨地做 500 項的加法：

#include <stdio.h>
main() {
    int n;
    double x;
    x = 0.0;
    n = 1;
    while (n <= 500) {
	x = x + 1.0/(n*(n+1));
	n = n + 1;
    }
    printf("%f\n", x);
}

輸出應該是 0.998004。我們再次提醒初學者，不要忘了括號。很多人會不慎寫成 1.0/n*(n+1)，這句話等於是 (1.0/n) * (n+1)，不符題意。

【例四】計算 x，並以 %f 格式輸出。

$\begin{displaymath}x = \sum_{n=0}^{500} {1\over 2n+1}$

#include <stdio.h>
main() {
    int n;
    double x;
    x = 0.0;
    for (n=0; n<=500; ++n) {
        x = x + 1.0/(2*n+1);
    }
    printf("%f\n", x);
}

輸出應該是 4.090058。這個題目看起來非常簡單，但是許多初學者會直覺地寫成 1.0/(2n+1)，這樣不符合 C 的語法。

【例五】計算 x，並以 %f 格式輸出。

$x = \sum_{n=1}^{500} {n\over n^2+1}$

#include <stdio.h>
main() {
    int n;
    double x;
    x = 0.0;
    for (n=1; n <= 500; ++n) {
        x = x + n/(n*n+1.0);
    }
    printf("%f\n", x);
}

輸出應該是 6.120959。注意上面我們寫了 n/(n*n+1.0)。如果不慎只寫 n/(n*n+1) 則 n*n+1 的計算結果還是整數，然後 n/(n*n+1) 的除法就是整數除法，得到整數商 (其實都是 0)。如果說 n*n+1.0，則雖然 n*n 的結果是整數，但是 n*n+1.0 的結果就成了浮點數 (小數部分是 0)，因此 n/(n*n+1.0) 的除法就是小數除法。

其實，像前一題那種題目，也可以直接將 n 宣告成浮點數就算了。如下。

#include <stdio.h>
main() {
    double n, x;
    x = 0.0;
    for (n=1; n <= 500; ++n) {
        x = x + n/(n*n+1);
    }
    printf("%f\n", x);
}

如果 n 是浮點數型態的變數，則 n=1 的效果和 n=1.0 其實是一嘿的。而且 n <= 500 和 ++n 也都可以得到正確結果。

【例六】計算 8! = 1*2*3*4*5*6*7*8。其實我們可以就只寫
printf("%d\n", 1*2*3*4*5*6*7*8);
但是為了練習，我們仍然用迭代迴圈來做。答案是 40320

#include <stdio.h>
main() {
    int fac, n;
    fac = 1;
    for (n=1; n <= 8; ++n) {
	fac = fac*n;
    }
    printf("%d\n", fac);
}

【例七】計算 2, 4, 6, ..., 16 的連乘積。答案是 2⁸*(8!) = 256 * 40320 = 10321920。純粹為了練習，我們要電腦笨笨地做 2*4*8*...*16。

#include <stdio.h>
main() {
    int n, prod;
    prod = 1;
    n = 2;
    while (n <= 16) {
	prod = prod * n;
	n = n+2;
    }
    printf("%d\n", prod);
}

【例八】計算 2!, 3!, 4!, ..., 10!。比 10 更高的階乘，很快就超過了 int 資料型態的上限，我們就不在這裡討論了。

#include <stdio.h>
main() {
    int n, fac, k;
    n = 2;
    while (n <= 10) {
        fac = 1;
        for (k=1; k <= n; ++k) {
            fac = fac*k;
	}
	printf("%2d! = %10d\n", n, fac);
	n = n + 1;
    }
}

輸出應該是

 2! =          2
 3! =          6
 4! =         24
 5! =        120
 6! =        720
 7! =       5040
 8! =      40320
 9! =     362880
10! =    3628800

【例九】計算 x，並以 %f 格式輸出。

$\begin{displaymath}x = \prod_{n=1}^{500} {2n-1\over 2n+1}$

其實讓分子與分母相消，就得到 (1/3)*(3/5)*(5/7)...(999/1001) = 1/1001 = 0.000999001... 現在純粹為了練習，我們要電腦笨笨地做 500 項連乘。

#include <stdio.h>
main() {
    int n;
    double x;
    x = 1;
    for (n=1; n<=500; ++n) {
        x = x * (2*n-1) / (2*n+1);
    }
    printf("%f\n", x);
}

輸出應該是 0.000999

習題

計算 x，並以 %.4f 格式輸出。輸出應該是 1.0747
$x = \sum_{n=1}^{500} {1\over n^2+1}$
計算 x，並以 %.4f 格式輸出。輸出應該是 2.1161
$x = \sum_{n=1}^{500} {1\over 3n+1}$
計算 x，並以 %.4f 格式輸出。輸出應該是 1.1843
$x = \sum_{n=1}^{500} {1\over 6n-1}$
計算 x，並以 %.4f 格式輸出。輸出應該是 0.6127
$x = \sum_{n=1}^{500} {1\over n(2n+1)}$
計算 x，並以 %.4f 格式輸出。輸出應該是 2.6104
$x = \sum_{n=1}^{500} {1\over 4n-3}$
計算 x，並以 %.4f 格式輸出。輸出應該是 4.7988
$x = \sum_{n=1}^{500} {n\over (n+1)(n+2)}$
計算 1, 3, 5, 7, ..., 17 的連乘積。
計算 x，並以 %.4f 格式輸出。輸出應該是 0.0151
$\begin{displaymath}x = \prod_{n=0}^{500} {4n+1\over 4n+3}$
計算以下乘積，並以 %.6f 格式輸出。
$\begin{displaymath} \prod_{n=2}^{500} (1-\frac1{n}) \end{displaymath}$

單維彰 (2001/01/06) --- 04/05/19 (單)