C 教材：序列計算的範例

因為我們還不會輸入資料，所以下面這個範例，我們將一個序列的值寫在程式裡面。 注意，在宣告序列的時候，可以順便定義它的值。這些數值是某班學生的某科成績。 以下的程式示範一些敘述統計的計算，包括總和、平均、標準差、最大、最小、 列出超過「平均 + 標準差」的值、列出不到「平均 - 標準差」的值。 

#include <stdio.h>
#include <math.h>
#define N 58
 
/* Do some descriptive statistics on an array. (demo-stats.c) */
main() {
    int i, x[N]={61,99,67,80,65,61,60,70,66,61,15,64,74,94,61,60,77,
                 64,71,83,17,70,72,48,45,81,88,86,83,82,71,61,98,93,
                 47,60,78,69,81,99,72,70,73,44,69,99,89,82,99,14,15,
                 47,60,80,82,68,98,43};
    int sum, max, min;
    float mean, var, cut;
  
    /* 計算總和、最大、最小、平均 */
    sum = max = 0;
    min = 100;
    for (i=0; i<N; ++i) {
        sum = sum + x[i];
        if (x[i] > max)
            max = x[i];
        if (x[i] < min)
            min = x[i];
    }
    mean = (sum*1.0)/N;
    printf("Sum  = %4d\n", sum);
    printf("MAX  = %4d\n", max);
    printf("MIN  = %4d\n", min);
    printf("MEAN = %7.2f\n", mean);
  
    /* 計算標準差 */
    var = 0;
    for (i=0; i<N; ++i)
        var = var + (x[i] - mean)*(x[i] - mean);
    var = sqrt(var / (N-1));
    printf("VAR  = %7.2f\n", var);
  
    /* 列出盈與不足 */
    printf("HIGH =  ");
    cut = mean + var;
    for (i=0; i<N; ++i)
        if (x[i] > cut)
            printf("%3d", x[i]);
    putchar('\n');
    printf("LOW  =  ");
    cut = mean - var;
    for (i=0; i<N; ++i)
        if (x[i] < cut)
            printf("%3d", x[i]);
    putchar('\n');
}

注意 mean = (sum*1.0)/N; 的語法，這是因為 sum 和 N 都是整數型態，但 mean 需要算出小數。這是解決的方法之一， 以後還會知道其他的解法。因為計算標準差的時候要開根號， 所以 #include <math.h>， 記得在編譯的時候要用 -lm 這個參數。

以上程式當然還有許多改進的空間，但是此處我們只是示範序列的計算而已。 其他不在此處多談。

其次，我們再觀察一個程式，它會列出前 1000 個質數 (從 2 開始)。 

#include <stdio.h>
#define SIZE 1000

/* Calculate the first SIZE primes.  Let the first prime be 2. (prime.c) */
main() {
    int p[SIZE], q, n, i, j, isprime;
    p[j=0] = n = 2;
    while (j < SIZE) {
        ++n;
        isprime = 1;
        q = p[i=0];
        while (isprime && q*q <= n)
            if (n%q == 0)
                isprime = 0;
            else
                q = p[++i];
        if (isprime)
            p[++j] = n;
    }
    for (j=0; j<SIZE; ++j)
        printf("%4d:%5d\n", j+1, p[j]);
}

這個程式，讓 p[0] 和 n 都從 2 開始，逐一增加 n， 檢查它是否為質數。如果是，就儲存到 p[] 裡面。 所以，如果 SIZE 過大，有可能產生錯誤。 (C 的內建資料型態無法產生非常大的整數來檢查是否為質數)。 所謂質數，就是不能用比它自己的平方根還要小之質數所整除。 這就是 prime.c 的工作原則。

程式的設計，使用到一個旗標 (flag) 性質的變數 isprime。 它用來記錄 n 是一個質數 (isprime == 1) 或不是質數 (isprime == 0)。 q*q <= n 就是在檢查測試用的質數 q 不超過根號 n， 但是這樣寫可以省去呼叫 sqrt() 的麻煩。 而 if(n%q == 0) 就是說「若 n 被 q 整除的意思」。 其實這句話可以簡寫成 if(!(n%q))。 n%q 就是 q 除 n 的餘數。 如果整除，就是 0，也就是邏輯的 False；反之若不整除，就是一個正數， 也就是邏輯的 True (只要不是 0 就是 True)。 因此，if(!(n%q)) 在邏輯上和 if(n%q == 0) 是等價的。 if(n%q == 0) 那一整句話的意思就是說 「若 n 被 q 整除的意思，知道 n 不是質數，否則令 q 是下一個已知的質數。」

習題

  1. 計算向量 (3, 5, 9, 4, -2, -4) 的「長度」，亦即歐幾里得模 (Euclidean norm)。
  2. 在前 1000 個質數中，列出所有 4n+3 形式的質數，並且從 1 開始編號。例如 
    1: 3
2: 7
3: 11
4: 19
...
  3. 在前一千個質數中，列出前一百對孿生質數 (twin primes)，並且從 1 開始編號。 連續兩個奇數都是質數者，稱為一對孿生質數。例如 
    1: (3,5)
2: (5,7)
3: (11,13)
...

單維彰 (2001/02/23) --- [Prev] [Next] [Up]