暴力尋找 完全數 程式設計練習

1. 練習運用 迴圈 設計程式, 讓 CPU 重複執行你指定的工作

2. 運用 函數 模組化/結構化/簡化你程式的運作邏輯

我們說一個正整數是 完全數 (perfect number) 如果這個數字等於所有小於它本身的因數的和, 例如 6 是一個 完全數 因為 6 = 1 + 2 + 3.

請寫一個程式, 使用者由鍵盤輸入一個正整數, 程式判斷小於等於這個整數的所有正整數中

1. 哪幾個數字是 完全數, 並且在螢幕上每三個數字一列, 印出所找到的完全數,
2. 印出在這個範圍中有幾個完全數,
3. 印出它們的總和並且計算以十進位表示這個總和時有幾位數。

範例執行程式 版本1, 版本2 (速度比較快一些)

如果你看了上面這個題目, 執行上面的範例程式以後還是沒有什麼想法, 看看下面這些敘述會不會有一點幫助:

撰寫這個程式的時候你需要想像如果你是電腦的話你要怎樣來完成這個題目的要求? (你可能沒有很好的公式或是很好的數學定理可以讓你很快地完成這個工作, 但是你有很快的運算速度, 可以用很簡單但是很暴力的作法來達成上面的要求)

1. 先弄清楚範圍 (先讀取使用者要求的數字上限)
2. 一個數字一個數字來判斷是否為完全數 (也許需要把每個數字的真因數都找到)
3. 每次看到一個完全數就列印到螢幕上, 順便計算一下總和還有總個數, 因為每一列只能印三個數字, 你還要根據目前找到的是第幾個數字決定要不要列印換行字元 (\n)
4. 範圍內所有的數字都測試過以後, 把總個數還有總和印出來

上面提到的 "找到一個正整數所有的真因數" 不是一個很容易的事, 有一些經典的篩檢 (Sieve) 的方法可以加快速度, 不過在這個實習裡沒有希望你去探討這些方法,這裡只希望你用 "暴力" 的方法去做, 就是一個數字一個數字去除看看來判斷是否為因數, 當然如果是你用筆來做的話你是不會想要這樣做的, 不過現在你是用電腦來做, 不要太擔心它累壞了, 先做看看就是了, 目標是先學會怎樣用 "迴圈" 這種語法! (教聰明人開始寫程式是有一些挑戰的, 因為聰明人常常以為電腦什麼都會, 幫它定義一下什麼是完全數, 幫它定義一下什麼是因數, 它難道不會自己去找嗎? 不會! 就是不會! 你要一步一步告訴它需要做什麼, 它會聽你的話去做的, 這就是為什麼 Basic, C, Pascal, Fortran 這些語言要叫做 "命令式的語言 (imperitive language)" 的原因, 程式設計者使用這些語言直接命令電腦執行加減乘除、輸入輸出的基本動作來完成各種要求, 如果你不想個方法運用這些加減乘除的基本動作來完成要求的話, 電腦什麼都不會做)

先撰寫一個函數 isPerfect(int) 來判斷傳遞給它的整數參數是否為一個 完全數

1. 函式參數和回傳值: 唯一的輸入參數是所要判斷的那個整數, 輸出是真(1) / 假(0)

int isPerfect(int number)
{
}

2. 撰寫一個迴圈用 "試除法" 來判斷哪些整數是目標整數 number 的因數 (顯然大於 number/2 的數字沒有機會是因數), 如果是因數的話, 把它加總起來

sum = 1; // 1 也是 number 的真因數
for (i=2; i<=number/2; i++)
    if ((number%i) == 0)
        sum += i;

3. 在函式最前面加上所有用到變數的定義

    int i, sum;

4. 檢查所有真因數的總和是不是等於 number

if (sum == number)
    return 1;
else
    return 0;

5. 由於你現在有交談式的程式開發環境可以使用, 在你還不熟悉語法的時候, 你應該每寫一小段程式就編譯測試一下你的程式, 所以在這個時候你也可以寫一小段程式來測試這個 isPerfect() 函數。你可以寫一個 main() 函數, 呼叫 isPerfect() 測試已知的完全數, 例如: isPerfect(8128) 或是 isPerfect(6), 以及非完全數, 例如: isPerfect(95)

#include <stdio.h>
#include <stdlib.h>

int isPerfect(int);
int main(void)
{
    if (isPerfect(6))
        printf("6 is a perfect number\n");

    system("pause");
    return 0;
}

接下來我們嘗試撰寫 main() 函數裡讀取輸入以及主要的完全數測試迴圈:

1. 輸出訊息要求使用者由鍵盤輸入一個在 2 到 1000000 之間的正整數 n 來定義檢查完全數的範圍 [1..n] (1000000 這個數字是考量 1. 整數變數 int 型態所能存放的數值 還有更重要的 2. 太大了我們這個暴力的方法會做不完)

    printf("Please input an integer in the range [2,1000000]: ");

2.寫一個 do-while 迴圈來讀取建議範圍內的整數上限值

succeed = 0;
do
{
    printf("Please input an integer in the range [2,1000000]: ");
    scanf("%d", &iMaximal);
    if (iMaximal < 2)
        printf("the number should not be smaller than 2\n");
    else if (iMaximal > 1000000)
        printf("the number should be smaller than 1000000\n");
    else
        succeed = 1;
}
while (!succeed);

/*
 * Returns the first integer between n_min and n_max entered as data.
 * Pre : n_min <= n_max
 * Post: Result is in the range n_min through n_max.
 */
int get_int (int n_min, int n_max)
{
    int  in_val,         /* input - number entered by user   */
          status;        /* status value returned by scanf   */
    char skip_ch;        /* character to skip    */
    int  error;          /* error flag for bad input */
    /* Get data from user until in_val is in the range. */
    do 
    {
         /* No errors detected yet. */
         error = 0;
         /* Get a number from the user. */
         printf("Enter an integer in the range from %d ", n_min);
         printf("to %d inclusive> ", n_max);
         status = scanf("%d", &in_val);

         /* Validate the number. */
         if (status != 1) 
         {  /* in_val didn't get a number */
             error = 1;
             scanf("%c", &skip_ch);
             printf("Invalid character <<%c>>. ", skip_ch);
             printf("Skipping rest of line.\n");
         } 
         else if (in_val < n_min  ||  in_val > n_max) 
         {
             error = 1;
             printf("Number %d is not in range.\n", in_val);
         }

         /* Skip rest of data line. */
         do
              scanf("%c", &skip_ch);
         while (skip_ch != '\n');
    } 
    while (error);

    return (in_val);
}

3. 編譯並且測試範圍 [1, n] 之內的數字是不是一個完全數

for (i=1; i<=iMaximal; i++)
    if (isPerfect(i))
        printf("%d ",i);

4. 當你測試比較大的數字時, 例如 1000000, 你的程式可能會執行一段時間. 這表示程式的演算法不太有效率,等一下到步驟 7 時我們會稍微討論一下這個問題

在螢幕上列印完全數, 每三個數字一列:

你可以準備一個變數來計算每一列目前輸出了幾個數字, 如果已經印出三個數字就列印一個換列的字元 '\n', 然後把這個變數重設為 0;

int count_per_line;
count_per_line = 0;
for (i=1; i<=iMaximal; i++)
    if (isPerfect(i))
    {
        printf("%d ",i);
        count_per_line += 1;
        if (count_per_line == 3)
        {
            printf("\n");
            count_per_line = 0;
        } 
    }

[1, n] 範圍內有多少個完全數? 他們的總和是多少?

請設計一個獨立的變數在尋找完全數的過程中, 記錄找到的完全數的個數; 再設計一個變數, 順便把找到的完全數加總起來完全數加總起來

int iCount, iSum;
...
iCount = 0;
iSum = 0;
for (i=1; i<=iMaximal; i++)
    if (isPerfect(i))
    {
        printf("%d ",i);
        iCount++;
        iSum += i;
    } 

當我們把 sum 變數的數值用十進位列印在螢幕上時, 共有多少位數呢?

我們知道如果變數 sum 裡面的數值滿足: sum < 10^k 且 sum >= 10^k-1, 那麼當你在螢幕上列印這個數字時就是十進位時的 k 位數字, 這部份程式不是要你用眼睛去看有幾位數, 而是希望程式自動去計算 sum 變數裡面存放的數值有幾位數

基本上有兩種方法可以完成這個功能:

1. 你可以寫一個迴圈, 運用 math.h 函數庫裡面的 double pow(double, double) 函數來測試變數裡面存放資料的範圍

for (nDigits=1; nDigits<12; nDigits++)
    if (sum < pow(10, nDigits)) 
        break;

2. 你也可以寫一個 do-while 迴圈來計算到底有幾位數, 而不使用 pow() 函數:

nDigits = 0;
do
{
   nDigits += 1;
   sum = sum / 10;
} 
while (sum>0);

事實上, 上面這個範例的 isPerfect() 函數一點都不完美, 在測試一個數字是否為完全數的時候浪費太多時間在尋找它的因數, 我們可以很快地修改一下程式來加快執行的速度, 雖然還是很暴力, 沒有用什麼好方法, 不過你應該已經可以感覺到速度的差異了, 我們可以運用

"如果一個整數 x 整除 n, 當然就是存在一個整數 y 使得 n = x y, 如此可知一個數字 n 的因數一定會小於這個數字開根號 "

所以在尋找因數的時候你應該只需要測試到 根號 n 就可以了, 同時如果 x 整除 n, 當然 n/x 也是整除 n 的 (x 和 n/x 是一對整除 n 的數字)。

max = (int) sqrt((double)number);
for (i=2; i<=max; i++)
	if ((number%i) == 0)
	{
		sum += i;
		if (number/i != i)
			sum += number/i;
	}

請編譯並且執行, 感覺一下速度的差異, 還有其他簡單的方式可以加速嗎?

下面是程式執行的結果:

6, 28, 496, 8128, 33550336, 8589869056, 137438691328, ...

最後讓我們加一小段程式來計算程式執行花了多少時間:

當你開始測試你剛才寫的這個程式時, 你應該會發現當數字變大時它慢得可以, 不要懷疑你花了不少錢買的機器, 不是它的不好, 是因為這個程式用的方法實在是太陽春了, 有一點點濫用你的機器的能力, 不過你應該也不用擔心會不會把它累壞了, 它本來就可以這樣子全速執行很長一段時間的...

你可以執行你的程式, 輸入一個相當大的數字, 然後就可以睡覺去了, 不會那麼快結束的, 下次你記起來的時候可以看一看它有沒有找到新的完全數。

如果你想要自動地量一下這個程式每次找到一個新的完全數需要花多少時間, 你可以運用 <time.h> 函數庫裡面的 clock(void) 函數

每一次你呼叫 clock() 函數, 它會回傳一個整數數值, 代表這個執行的程式從開始到呼叫的時候共花了多少單位的時間 (一個單位是 1/CLOCKS_PER_SEC 秒, CLOCKS_PER_SEC 是一個定義在 time.h 裡面的常數, 或是 CLK_TCK 也可以).

下面是一個測量迴圈執行時間的範例程式:

#include <stdio.h> /* printf */
#include <stdlib.h> /* system */
#include <time.h>  /* clock_t, clock(), CLOCKS_PER_SEC, CLK_TCK */

int main(void)
{
   int     i = 60000000;
   clock_t start, finish;
   double  duration;

   printf( "Time to do %ld empty loops is ", i );

   start = clock();

     while( i-- ) 
      ;

   finish = clock();
   duration = (double)(finish - start) / CLOCKS_PER_SEC;/* 或是 CLK_TCK */

   printf( "%2.1f seconds\n", duration );

   system("pause");
   return 0;
}

Sample execution result:
Time to do 60000000 empty loops is  0.2810 seconds

請修改你的程式來加上度量所花時間的功能。

上面這個 clock() 函數所使用的計時裝置 (是一個很便宜的積體電路晶片: 8253) 的精確度不是很高, 只可以精確到 1/18.2 秒 (55 毫秒), CLOCKS_PER_SEC 是 1000, 好像可以精確到 1 毫秒, 但是實際量到的數值會是 55 毫秒的倍數; 在現在的個人電腦上有其它更精確的計時方法, 例如使用 Time stamp counter RDTSC 指令或是 _emit(0x3F) _emit(0x31) 計算 CPU內部時脈週期, GetTickCount Win32 API, mmsys.h 裡面的 timeGetTime, 或是 kernel32.lib 中的QueryPerformaceCounter 及 QueryPerformanceFrequency API (計算一秒鐘有幾個 CPU時脈週期), 不過對於這個應用來說 clock() 已經足夠了。