【解題】Oil Deposits

ACM Volume V 572 - Oil Deposits


The Problem

The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil.

A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.


Input

The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 ≦ m ≦ 100 and 1 ≦ n ≦ 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either `*', representing the absence of oil, or `@', representing an oil pocket.


Output

For each grid, output the number of distinct oil deposits. Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. An oil deposit will not contain more than 100 pockets.


Sample Input

1 1
*
3 5
*@*@*
**@**
*@*@*
1 8
@@****@*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
0 0


Sample Output

0
1
2
2


解題思考

　　一般來說，這一題我會使用遞迴，利用 DFS(depth-first search，深度優先搜尋)求解。不過，因為某人堅持要我用我不擅長的 BFS(breadth-first search，廣度優先搜尋)來寫......。

　　Anyway，其實核心想法都是差不多的。


　　顯然的，這一題的問題點在於：判斷哪幾個 pocket 屬於同一個 oil deposit。

　　首先，我們需要利用迴圏找到一個 pocket，並把所有跟這個 pocket 相鄰的 pocket 推進一個 BFS 的佇列(或是 DFS 的堆疊)中。在推入的同時，我們還需要為這個 pocket 標上一個「搜尋過」的記號(在這裡我是利用把 pocket 標記消掉的方式)。

　　直到佇列(或堆疊)為空，就代表我們已經搜遍同一個 oil deposit 的所有 pocket 了。所以，我們繼續執行迴圈，找到下一個沒有被搜尋過的 pocket，再同樣進行搜尋相鄰 pocket 的動作。再繼續執行迴圈，重覆相同的動作。直到找遍所有的 pocket 為止。

　　有了這種想法，題目所要求的解也就呼之欲出了！


參考解答(C++)

#include <iostream>
#include <queue>

using namespace std;

struct coord
{
    coord(int i, int j) { x = i; y = j; };

    int x, y;
};

int main(void)
{
    while (1)
    {
        int m, n;
        cin >> m >> n;

        if (!m && !n) { break; }

        // 動態配置記憶體
        bool **oil = new bool*[m + 2];
        for (int i = 0; i < m + 2; i++)
        {
            oil[i] = new bool[n + 2];

            // 陣列初始化
            memset(oil[i], 0, n + 2);
        }

        // 讀入每一個 pocket
        char *get = new char[n + 1];
        for (int i = 1; i <= m; i++)
        {
            cin >> get;
            for (int j = 1; j <= n; j++)
            {
                oil[i][j] = (get[j - 1] == '@');
            }
        }

        delete [] get;

        int num = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (oil[i][j])
                {
                    oil[i][j] = false;

                    num++;

                    // 利用 BFS 找出相鄰的 pocket
                    queue bfs;
                    bfs.push(coord(i, j));

                    do
                    {
                        int &x = bfs.front().x, &y = bfs.front().y;
                        for (int p = -1; p <= 1; p++)
                        {
                            for (int q = -1; q <= 1; q++)
                            {
                                if (oil[x + p][y + q])
                                {
                                    oil[x + p][y + q] = false;

                                    // 推入相鄰的 pocket 進佇列中
                                    bfs.push(coord(x + p, y + q));
                                }
                            }
                        }

                        bfs.pop();
                    } while (bfs.size());
                }
            }
        }

        cout << num << endl;

        // 釋放記憶體空間
        for (int i = 0; i < m + 2; i++)
        {
            delete [] oil[i];
        }

        delete [] oil;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

【語言】陣列是什麼 - What is Array?

　　在前幾篇文章中，我們已經介紹過變數了。但是，假設現在出現了這種情況：現在班上有 30 個人，而你想要寫一個程式，記錄班上所有人的期中考成績，並計算出全班總平均。

　　於是，你可能會這麼寫：

input score1;
input score2;
input score3;
......
......
input score30;

average = score1 + score2 + score3 + ... + score30;

　　喔，這樣的程式看起來真討厭！

　　若是現在班上不只 30 個人，而是 300 個人，你就得重複寫 300 次這種類似 "input scoreX" 這種敘述。無論對於撰寫或是閱讀而言，這種情況都是相當麻煩的一件事。

　　不過，我們可以利用陣列(array)來解決這個問題。


　　陣列所代表的是一串佔用連續記憶體的變數集合。我們可以只利用一個名稱(陣列名稱)來表示這些變數，以省去大量變數命名的麻煩。

　　而在存取時，我們只需要透過指定索引(index)值的方式，就可以取得陣列中的某個元素。換句話說，在某些情況下我們也可以利用迴圈(loop)，來對整個陣列的元素進行處理。

　　例如，上面期中考成績的程式，我們可以利用陣列改寫成這樣：

for (i = 1 to 30)
{
    input score[i];
    total = total + score[i];
}

average = total / 30;

　　由上面可以看到，我們可以直接利用 for 迴圈來依次取得使用者的輸入，並根據索引值 i 存進適當的陣列元素中，同時計算出全班的分數總和以得出平均分數。這樣的寫法是不是簡潔、俐落多了呢？


　　接下來，情況改變一下。若是你現在要記錄的不止是全班期中考成績，而是全年級 15 個班(假設人數皆為 30 人)的期中考成績，那麼該怎麼做呢？

　　別想得那麼難！其實我們只需要將 score 改成一個「陣列的陣列」，也就是一個二維陣列(two-dimensional array)就可以了：

for (i = 1 to 15)
{
    for (j = 1 to 30)
    {
        input score[i][j];
        total[i] = total[i] + score[i][j];
    }

    average[i] = total[i] / 30;
}

　　外圍的 for 迴圈用來控制代表「班級」的索引值 i，內層的 for 迴圈用來控制代表「座號」的索引值 j。於是，我們便可以利用 score[i][j] 來存取 i 班 j 號同學的成績了。


　　那麼，要記錄全校 3 個年級的學生成績呢？要記錄全區域 10 所學校的學生成績呢？當然，你也可以建立出三維、四維等多維陣列，它們的想法都是差不多的。

【語言】控制流程敘述 - Control Flow Statement

　　對於程式語言而言，敘述通常被認為是一支程式的最小組成單位。例如簡單的指派(assignment) x = 5 或是斷言(assertion) a < b 都屬於一個敘述。


　　不過，其實程式語言總歸而言只具有三種敘述結構，被稱為控制流程(control flow)敘述。分別為循序(sequence)結構、條件(condition，或稱 selection)結構、與重複(iteration，或稱 repetition)結構。

　　循序結構相當直覺且簡單。由字面上解釋，即代表程式以由上而下、有順序性的方式一個敘述接著一個敘述執行。例如：

print "這是第一行，程式會先執行這裏";
print "這是第二行，我會在第一行執行之後執行";
print "這是第三行，我會在第二行執行之後執行";

　　條件結構則是代表程式在執行時，會依據條件值來改變程式執行的順序。當滿足條件時，會執行某一敘述區塊，若條件不滿足時，則執行另一敘述區塊。例如常見的 if 與 switch 敘述：

input a, b;
if (a > b)
{
    print "a 大於 b";
}
else if (a < b)
{
    print "a 小於 b";
}
else
{
    print "a 等於 b";
}

input select;
switch (select)
{
    case 1:
        print "你選了選項 1";

    case 2:
        print "你選了選項 2";

    case 3:
        print "你選了選項 3";

    default:
        print "你選了 1~3 以外的選項";
}

　　至於重複結構，就是指反覆執行程式中的某一敘述區塊，直到符合某項條件(利用條件結構)為止。常見的重複結構則分為前測式迴圈(pre-test loop)、後測式迴圈(post-test loop)、與計數式迴圈(count-controlled loop)三種。

　　前測式迴圈是先測試條件。若條件為真，才執行敘述區塊。當敘述區塊執行完畢後，會再回到測試條件重新測試。若條件仍成立，則再一次執行敘述區塊。如此週而復始下去，直到條件不成立為止。例如常見的 while loop 敘述：

input a, b;
while (a > b)
{
    print a;
    a = a + 1;
}

　　後測式迴圈與前測式迴圈類似。唯一的不同點為：其會先執行敘述區塊一次，然後再測試條件。若條件為真，則重複執行，直到條件不成立才會離開迴圈。因此，迴圈內的敘述至少會被執行一次。例如常見的 do-while loop 敘述：

input a, b;
do
{
    print a;
    a = a + 1;
} while (a > b);

　　而計數式迴圈則不同於兩者。其會利用一個計數器(counter)來記錄迴圈執行的次數，以用於可預測執行次數的情況。例如常見的 for loop 敘述：

input n;
for (i = 1 to n)
{
    print i;
}

　　其實，除了這三種結構之外，還有一個可以進行無條件跳躍的 goto 敘述。

　　所謂的無條件跳躍指令，指的是無條件將程式執行的順序改變，跳到指定的地方繼續執行。它不像前面提到的迴圈或選擇敘述必須經過判斷，才能決定程式執行的順序，因此威力非常的強大。

　　這樣的指令看似方便，卻容易造成程式難以閱讀，也難以除錯。例如：

label:
......
......
goto label;
......
......
goto label;
......
......
goto label;

　　因為這樣子的寫法，我們並不能夠清楚的知道：此時究竟是由哪一個 goto 跳到 label 的。所以一般來說，goto 這類無條件跳躍指令是不太被建議使用的。

【語言】函式是什麼 - What is Function?

　　開發程式時，或許在程式很小的情況，把所有功能通通寫在一個同區塊(block)中是一個可行的方法。但是，一旦程式的規模越變越大，若仍舊將所有內容都寫在一個區塊中，將會導致程式變得難以除錯與閱讀。



　　讓我們舉個例來說明，假設在某個程式中，你需要將幾個變數(variable)做初始化的動作。如以下所示：

score = 0;
life = 3;
item = 50;
win = false;
pause = false;

　　而且，或許你在整個程式中不只要作一次類似的動作：

......
......
score = 0;
life = 3;
item = 50;
win = false;
pause = false;
......
......
score = 0;
life = 3;
item = 50;
win = false;
pause = false;
......
......
score = 0;
life = 3;
item = 50;
win = false;
pause = false;
......
......

　　如此一來，程式不但看起來相當冗長，而且一旦程式有任何錯誤或是更動(例如，我們現在要將 "life = 3" 改成 "life = 5")，就需要一一將每個相同的部分做修改。萬一在修改時又有疏失，對於程式的維護與除錯來說，都是相當不方便的。

　　為了解決這種問題，我們可以將重複性高，或是邏輯概念類似的部分分離成一個函式(function)，並在需要的地方呼叫(call)函式以執行函式內容。




　　函式又稱為副程式(subroutine)，概念有點類似於數學上的「函數」，代表的是一串程式區段的集合。例如上面我們所提到的例子，就可以利用函式改寫成這樣：

function initialize()
{
    score = 0;
    life = 3;
    item = 50;
    win = false;
    pause = false;
}

......
......
initialize();
......
......
initialize();
......
......
initialize();
......
......

　　首先，我們可以看到，一個基本的函式包含兩個部份：函式的名稱與主體。其中，"initialize"是這個函式的名稱。由上面的例子我們可以知道：當我們要執行一個函式時，是需要透過其名稱來做呼叫的。而函式主體，理所當然就是函式所包含的程式區段了。


　　除此之外，我們也可以傳入一些資料到函式裡。

　　例如現在有一個方程式 f(x) = 3x² - 6x + 1，則利用函式可以這麼寫：

function f(x)
{
    return 3 * x * x - 6 * x + 1;
}

print f(5);

　　在這裡，x 稱之一個為參數(parameter)，在意義上有點類似數學中代入函數的數值：我們可以在呼叫函式的同時，傳入適當的參數(變數或是常數)，來得到代入之後的結果。

　　當然，在得出運算的結果之後，我們還必須把這個結果傳回去。而這個傳回的結果，我們稱之為返回(return)值。而在這個例子中，f() 函式的返回值就是 x 代入 3x² - 6x + 1 之後得出的結果。


　　經過以上這些說明，我們可以知道：善加利用函式的方式，程式也會因此變得比較好維護。因為一旦程式有錯誤或是更動，我們不需要再一一更改所有相同的部份，只需要修改函式中的程式碼就可以了。

　　與之前提過的變數相同，函式的使用與規範也隨著程式語言而有所不同。因此大部分的細節這裡並不多提，讓我們留待之後再做解釋。

【演講】The Yahoo! User Interface Library

　　今天有幸能夠聽到 Yahoo! 科技推廣"傳教士" Joseph Chiang 所帶來的演講，主題是 Yahoo! 自家建立的 YUI(The Yahoo! User Interface Library) 推廣、實作入門與應用實例。

　　YUI 是一套以 BSD 授權的 Open Source 的 JavaScript 函式庫，包含了 CSS、AJAX、DOM 等技術，提供與平臺(作業系統或是瀏覽器)無關的網頁互動功能。


　　其實早在一段時間之前，我就曾經聽朋友提過 YUI 這套開放源碼的 Library。但是實際上，我也沒有實際去研究 YUI 到底是做什麼用的。直到經過今天這場演講的介紹，發現 YUI 還真的是個有趣又功能強大的東西。

　　我個人的感覺是 YUI 的寫法簡潔、直覺，加上官方的文件相當齊全(這大概是最吸引我的地方)，撰寫網頁的速度相當快速，也難怪當初朋友要強力推崇了。

　　看起來又多個新東西可以玩了，其實還滿想找個時間來寫個範例玩玩。


　　以下是今天 Joseph Chiang 來本校演講的投影片，有興趣的人可以看看：


YUI 介紹 @YZU

相關連結：
．YUI 中文首頁 - http://tw.developer.yahoo.com/yui.html
．YUI 英文首頁 - http://developer.yahoo.com/yui/
．Joseph Chiang's Blog - http://josephj.com/
．Joseph 公開的投影片 - http://www.slideshare.net/josephj/slideshows

【解題】Box of Bricks

ACM Volume V 591 - Box of Bricks


The Problem

Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. ``Look, I've built a wall!'', he tells his older sister Alice. ``Nah, you should make all stacks the same height. Then you would have a real wall.'', she retorts. After a little con- sideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?




Input

The input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1 ≦ n ≦ 50 and 1 ≦ h_i≦ 100.

The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.

The input is terminated by a set starting with n = 0. This set should not be processed.


Output

For each set, first print the number of the set, as shown in the sample output. Then print the line ``The minimum number of moves is k.'', where k is the minimum number of bricks that have to be moved in order to make all the stacks the same height.

Output a blank line after each set.


Sample Input

6
5 2 4 1 7 5
0


Sample Output

Set #1
The minimum number of moves is 5.


解題思考

　　這一題要我們求出：把現有的這些方塊堆成每堆一樣高時，所需移動的最少方塊數。

　　其實，也只需要將每堆的平均方塊數(總積木數 / 堆)，再計算高於(或是低於也行)平均方塊數量的方塊數量總和，結果就出來了。


參考解答(C++)

#include <iostream>
#include <iomanip>

using namespace std;

int main(void)
{
    int c = 0;
    while (1)
    {
        c++;

        int n;
        cin >> n;
        if (n == 0) { break; }

        int average = 0;
        int *brick = new int[n];
        for (int i = 0; i < n; i++)
        {
            cin >> brick[i];
            average += brick[i];
        }

        average /= n;

        int move = 0;
        for (int i = 0; i < n; i++)
        {
            if (brick[i] > average)
            {
                move += brick[i] - average;
            }
        }

        cout << "Set #" << c << endl;
        cout << "The minimum number of moves is " << move << "." << endl << endl;
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

【語言】變數是什麼 - What is Variable?

　　變數(variable)是什麼？從字面上解釋，變數就是「可變的數」，也就是其值可以隨著時間而改變。假如用更精確的說法來解釋，程式設計上的變數，代表的就是一個擁有名稱的記憶體儲存空間。


　　或許你曾經在計算機概論，或是電腦原理的相關書籍中讀到過。我們可以將電腦的記憶體想像成一個一個小格子(cell)。其中的每一個格子都由 8 個存放著 0 或 1 的位元(bit)組成，稱之為一個位元組(byte)。

　　當然了，為了能夠對每一個記憶體空間進行儲存及存取的動作，因此每一個格子也都擁有一個絕對且唯一的地址(address)。



　　在機器語言或是組合語言這些低階語言中，我們可以直接利用記憶體的地址進行儲存及存取的動作。然而在高階語言的觀念，基於程式設計師撰寫與閱讀的方便上，我們並不希望如此(不管怎麼說，要記憶各個值的存放地址實在是太不直覺了)。

　　取而代之的，我們會給這些需要使用的記憶體空間一個「名字」，使我們能夠直接利用這個名字，對其所對應的記憶體進行操作。而這個擁有名字的記憶體，也就是所謂的「變數」了。

　　但是，不同類型的資料，例如表示字元(character)的變數與表示整數(integer)的變數，所使用到的記憶體空間大小可能就不盡相同。為了有效利用記憶體空間，也就有了各種不同的資料型態(data type)。

　　至於有哪些不同的資料型態，實際上是根據不同程式語言而有所差異的。所以關於變數，剩下的內容就留待介紹各種程式語言時再做說明了。

【演算】快速排序法 - Quicksort

快速排序法(quicksort)是目前被認為效率最高的排序演算法(sorting algorithm)。與合併排序法(mergesort)類似，快速排序法也是利用分治法(divide and conquer，D&C)，不斷地將資料分成兩部分以解決問題的例子。


首先，快速排序法會從所有資料中選擇一個支點(pivot)(支點的挑選往往決定了快速排序法的執行效率。為了簡單起見，這裡我們都直接挑選最左邊的資料為支點)。然後，(假設我們需要將資料由小排到大)我們需要把所有小於支點的資料移動到支點之前、並把所有大於支點的資料移動到支點之後。

至於要怎麼移動呢？首先，我們先從資料的最左邊開始，尋找一個比支點還大的數字。並且同樣的，從資料的最右邊開始，尋找一個比支點還小的數字。接著，將兩筆資料交換。並重複同樣的動作，直到資料已分為「比支點小」與「比支點大」兩堆後，再將支點移動到兩者之間即可。

移動完成之後，我們將資料根據支點分割(partition)成兩份，再分別對其進行相同的挑選支點並移動的動作，直到完全排序完成為止。


舉例來說，若我們需要將以下資料由小排到大：

26 13 73 31 38

我們先從資料中挑選一個支點：

26 13 73 31 38

使「比支點小」與「比支點大」的兩堆資料分別移動至支點的兩邊：

13 26 73 31 38

將資料根據支點分成兩邊：

(13) 26 (73 31 38)

左邊的資料完成排序。從右邊的資料挑選支點：

13 26 (73 31 38)

使「比支點小」與「比支點大」的兩堆資料分別移動至支點的兩邊：

13 26 (38 31 73)

將資料根據支點分成兩邊：

13 26 (38 31) 73

接下來以此類推：

13 26 (38 31) 73

13 26 (31 38) 73

13 26 (31) 38 73

直到排序完成：

13 26 31 38 73

虛擬碼大致如下：

void quicksort(Type data[1..n], Index left, Index right)
{
    if (left >= right) { return; }

    Type pivot = data[left];

    Index i = left + 1;
    Index j = right;
    while (1)
    {
        while (i <= right)
        {
            if (data[i] > pivot)
            {
                break;
            }

            i = i + 1;
        }

        while (j > left)
        {
            if (data[j] < pivot)
            {
                break;
            }

            j = j - 1;
        }

        if (i > j) { break; }

        exchange data[i] and data[j]
    }

    exchange data[left] and data[j]

    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);
}

與先前介紹的合併排序法相同的，快速排序法比較的次數不易去計算，所以我們省略這個過程。不過需要知道的是，在最差情況時，快速排序法的執行時間會隨著資料大小為 n 的變化，形成 n² 曲線成長。

雖然看起來執行效率不佳，但是在平均情況下，快速排序法執行時間的成長速率卻只有 n log n！可見在大多數情況下，快速排序法的效率仍然是相當優秀的。


以下是使用 C 語言的實現：

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

void quicksort(int *data, int left, int right);
void swap(int *a, int *b);

int main(void)
{
    int i, n, data[10];

    printf("請輸入資料筆數 n(<= 10): ");
    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        printf("請輸入第 %d 筆資料: ", i + 1);
        scanf("%d", &data[i]);
    }

    // 執行快速排序法
    quicksort(data, 0, n - 1);

    printf("\n排序後的結果: ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", data[i]);
    }

    printf("\n");
    system("pause");
}

void quicksort(int *data, int left, int right)
{
    int pivot, i, j;

    if (left >= right) { return; }

    pivot = data[left];

    i = left + 1;
    j = right;

    while (1)
    {
        while (i <= right)
        {
            if (data[i] > pivot)
            {
                break;
            }

            i = i + 1;
        }

        while (j > left)
        {
            if (data[j] < pivot)
            {
                break;
            }

            j = j - 1;
        }

        if (i > j) { break; }

        swap(&data[i], &data[j]);
    }

    swap(&data[left], &data[j]);

    quicksort(data, left, j - 1);
    quicksort(data, j + 1, right);
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

【作品】大數運算 - Large Integer

　　在比完今年(96 年)的資訊學科能力測驗後，有一題因為需要輸出 122 位的整數而無法得分。後來才發現，這種超過變數所能代表的最大整數，稱為超長整數，或通稱為大數運算。

　　因為沒解出來的怨念，所以過了不久，我就花了幾個晚上，使用類別的方式將它完成了。


程式說明

　　這支程式(或者該說是一個函式庫)宣告了一個large類別。成員變數包含一個代表正負號的布林(boolean)變數，以及一個用來"裝"數字的"字元向量(vector)容器字串(string)"。

　　至於大數的運算，我使用重載運算子(operator overloading)重載了許多的運算符號，因此可以直覺的使用運算符號來做大數的演算。

Constructors：

‧建構子
large(void);
large(const int &); UPDATE
large(const char[]); UPDATE
large(const std::string &); NEW
large(const large &); NEW

‧解構子
~large(void);

Operators：

‧指派運算子(支援大數、整數或C式字串)
void operator=(int);
void operator=(const char *);
void operator=(const std::string &); NEW

‧正負號
large operator+(void);
large operator-(void);

‧四則運算、取餘數
large operator+(large);
large operator-(large);
large operator*(large);
large operator/=(large);
large operator%(large);

‧複合運算子
large operator+=(large);
large operator-=(large);
large operator*=(large);
large operator/(large);
large operator%=(large);

‧(前置/後置)遞增、遞減
large operator++(int);
large operator++(void);
large operator--(int);
large operator--(void);

‧邏輯運算
bool operator>(large);
bool operator>=(large);
bool operator<(large);
bool operator<=(large);
bool operator==(large);
bool operator!=(large);

‧位元運算(使用十進位，非二進位)
large operator>>(int);
large operator<<(int);

‧標準輸入、標準輸出
friend std::istream& operator>>(std::istream &, large &);
friend std::ostream& operator<<(std::ostream &, const large &);

‧隱式型別轉換(large → char *)
operator char *(void);

Functions：

‧取得大數長度
int size(void);
int length(void); NEW

‧取絕對值
large abs(void);

‧傳回是否為負數
bool is_negative(void); NEW

‧傳回是否為零
bool is_zero(void); UPDATE

　　要使用這個類別，直接引括"large.h"這個標頭檔，並在編譯器連結指令加上"-llarge"，就可以了。

　　以下是一個大數運算的使用範例：

#include <iostream>
#include "large.h"

using namespace std;

int main(void)
{
    large a, b;

    cout << "Please ENTER two number a and b: ";
    cin >> a >> b;
    cout << endl;

    cout << "a = "      << a        << endl;
    cout << "b = "      << b        << endl << endl;

    cout << "a > b ? "  << (a > b)  << endl;
    cout << "a < b ? "  << (a < b)  << endl;
    cout << "a = b ? "  << (a == b) << endl << endl;

    cout << "a + b = "  << a + b    << endl;
    cout << "a - b = "  << a - b    << endl;
    cout << "a * b = "  << a * b    << endl;
    cout << "a / b = "  << a / b    << endl;
    cout << "a % b = "  << a % b    << endl << endl;

    cout << "a++ = "    << a++      << endl;
    cout << "a   = "    << a        << endl;
    cout << "++a = "    << ++a      << endl;
    cout << "a   = "    << a        << endl << endl;

    cout << "b-- = "    << b--      << endl;
    cout << "b   = "    << b        << endl;
    cout << "--b = "    << --b      << endl;
    cout << "b   = "    << b        << endl << endl;

    cout << "a << 4 = " << (a << 4) << endl;
    cout << "a >> 1 = " << (a >> 1) << endl << endl;

    system("pause");
}

　　假如有遺漏什麼運算子，麻煩提醒我。若是有什麼錯誤跟意見，也歡迎提出來。


程式下載

　　


更新紀錄：

‧08/04/05 正式貼出此類別庫。
‧08/05/04 將類別庫從 big 改名(正名？)為 large。
‧08/09/19 將程式改寫成可標準輸入超過 500 位的數字。
‧08/11/07 將代表數字的 vector<char> 改成 string。
‧08/11/07 部分函式內容改寫、更名。

【語言】直譯與編譯 - Interpretation and Compilation

　　之前，我們提到過高階語言(high-level language)須經由轉換的動作，將原始的程式碼「翻譯」成機器看得懂的二進位機器碼。一般而言，我們可以因這種轉換的動作的不同，將程式語言分為編譯式語言(compiled language)和直譯式語言(interpreted language)兩種。


　　編譯式語言(如 C、C++、Pascal、Delphi 等)利用編譯器(compiler)針對原始程式先進行分析(analysis)以及前置處理(preprocess)的動作，並檢查程式中是否存在文法錯誤之後，再將之全部轉換為某種中介的目標語言(target language)，稱之為目的檔(object file)。

　　將原始碼轉換為目的檔之後，我們還需要經由連結器(linker)連結一個或多個目的檔與外部函式庫(library)，轉換成機器碼以形成可執行檔(executable file)。此後除非程式有所更改，否則不需要再次進行編譯的動作，便可以直接利用可執行檔執行使用了。


　　而直譯式語言(如 VB、Python、REBOL、Ruby 等)相對於編譯式語言，其執行前並不會產生任何目的檔或是可執行檔，而是在執行當中才利用直譯器(interpreter)將執行到的區塊進行解析（parse），再執行對應的機器碼。因此，其執行效率相較於編譯式語言是比較低的。


　　讓我們將高階語言比喻為英文、機器語言比喻為中文，以「演講」為範例描述兩種方式的區別。

　　若是一名演講者有一份英文的演說稿，但是必須以我們聽得懂的中文(假設我們只聽得懂中文)進行演說，則以「編譯」的方式，這名演講者必須先將整篇文章讀過，且全部翻譯成中文的演說稿(意義近似於前面提到的「可執行檔」)。此後，除非演講的內容改變，無論演講者作幾次演說，他都不需要將演講稿重新翻譯。因為他已經有中文的演說稿了！

　　而若以「直譯」的方式，這名演講者在演講前，並不會對這篇演講稿進行任何翻譯的動作。而是在實際演講時，才逐步翻譯目前演講到的內容。所以，這名演講者每次進行演說時，都需要將演講稿重新翻譯一次。


　　由以上這些，我們可以知道：由於編譯式語言需要一次將原始碼全部「翻譯」，因此會先花上較長的時間進行編譯的動作。而直譯式語言則因為執行時才將原始碼進行轉換，因此實際上的執行效率相較於編譯式語言是比較低的。

　　（對直譯的理解有誤，舉例不適當。感謝網友 mitnick 指正。）


　　當然，除了編譯式語言與直譯式語言之外，近來也出現了介於兩者之間的「混合式語言(hybrid language)」，例如著名的 Java 與 C#。

　　其原理為先將原始程式碼「編譯」成其虛擬機器(virtual machine，VM)的「機器語言」(這裡指的是虛擬機器的機器語言，不是實際上的機器語言)。等到要執行程式時，其再藉由虛擬機器「直譯」這些虛擬機器碼。理所當然的，這種程式語言的執行效率也就落在直譯式語言與編譯式語言之間。

　　然而，在某些主流平台(例如 x86)上，程式在第一次執行時可以透過即時編譯(just-in-time compilation，JIT)的方式，編譯成其所在平台的機器碼。經過這個步驟，其執行速度是可以相當於、甚至是優於編譯式語言的。(感謝網友 kgame 補充，mitnick 指正。)


　　而不論是編譯式語言、直譯式語言、還是混合式語言，都各擁有其優點與缺點。至於孰優孰劣，就只能視情況、見仁見智囉。

【語言】程式語言簡介 - Introduction of Programming Language

　　語言(language)，時常是人與人之間賴以溝通的橋樑。正如日常生活中，三五好友間的哈拉閒聊、講台上教授的口述講解、或是我現在寫出來的這一篇文章，都是利用語言做為「你」與「我」之間，互相溝通、交流的管道。

　　同樣的，在電腦蓬勃發展的現代，我們也需要有一種方式，能夠與電腦做「溝通」，讓電腦能夠理解並遵循使用者的命令，以完成某些特定的「任務」。而程式語言(programming language)便是這種人與電腦溝通的「媒介」。


　　由於電腦其實只「看得懂」二進位(binary)數字(0 跟 1)。因此，在早期，程式設計師都是使用一連串 0 跟 1 所組成的機器語言(machine language)來撰寫程式。舉例來說：假設 "0010" 代表「相加(add)」，則 "0010 0001 0110" 這樣的一串指令，就表示著「把記憶體位置 0001 的值加上 6 (0110₂)」。

　　雖然因為這種方式是電腦可以直接理解的，所以使用機器語言撰寫的程式執行效率相當的高；但是，也正因為這串指令對人而言是如此的難以理解，且相當容易出錯。因此對人而言，使用機器語言來寫程式是相當費力的。


　　為了改善機器語言的缺點，組合語言(assembly language)誕生了。組合語言將機器語言的二進位指令，以一對一的方式轉換成簡單的符號或是英文的簡寫，使得指令更容易被人所記憶。於是，我們可以直接使用類似 "ADD 1 6" 的指令，來達成與前面提到的機器碼同樣的動作。

　　而在執行之前，只需要透過組譯器(assembler)將組合語言轉換為機器語言，電腦就看得懂了。雖然因為經過轉換的動作，組合語言的程式執行效率會比機器語言來的差一些，但是程式也因此變得好懂、好寫許多。


　　縱使如此，組合語言對一般人而言還是難以學習。而且，機器語言與組合語言都有一個缺點，就是他們都是「依賴於機器的(machine dependent)」。換句話說，可能你的機器語言(組合語言)程式移到別的機器上，它就不能執行了！

　　因此，相對於機器語言和組合語言這類低階語言(low-level language)，高階語言(high-level language)出現了。(對電腦科學來說，高階與低階僅用於表達其「接近機器的程度」，並無優劣褒貶之意。)包含了常見的 BASIC、Pascal、Fortran、C、C++、Java 等等。


　　高階語言不像低階語言，其採用較接近人類所使用的自然語言(natural language)，以人較容易閱讀理解的文法規則來編寫程式。雖然高階語言比起低階語言執行速度較慢，但是也因此減少了許多程式的學習難度與開發時間。

　　而且，高階語言在不同的平台上，都可以藉由不同平台上的編譯器(compiler)或直譯器(interpreter)被轉換為適當的機器語言，使得程式不再只因轉移平台，就需要將程式全部重新撰寫的情形。




　　自從高階語言出現以來，許許多多不同的程式概念與寫法不斷被提出、修正、改良。直到現今，仍然有許多代表著不同想法的高階語言不斷被創造出來。程式設計學術之盛，由此可見一斑。

【雜記】莫忘初衷

　　從今年二月申請 blogger 帳號，開了現在這個 blog、三月開始寫文章、貼程式。歷經高三的 TOI、學測、指考，大學的暑假、開學、NCPC。這樣斷斷續續的寫寫停停，直到現在，也已經八個月了。好不容易，終於到達目前的第一百篇(雖然廢話佔了不少篇)。

　　最初開始寫這個部落格，其實只是單純的想要放上自己的作品。一段時間之後，出於對那些在網誌分享知識的人的嚮往，我開始試著將自己所學、所想寫出來，貼在網誌上分享給其它人。那時候的想法也很簡單：希望所有想學程式設計的人，都可以用簡單的方式入門，再透過網誌留言討論互相切磋、進步。也因此，我為這個網誌定下了「世界，你好！」這個名字。

　　等到真正開始之後，才更深刻的知道寫網誌的困難。自己蒐集資料、整理資料，揉合自己的想法，用自己的口吻與文字表達出來。一篇篇的文章寫了又刪、刪了又寫，有時一耗就是一整個晚上。寫得越久，也越發現自己能力的不足、發現自己並沒有學得透徹。偶爾稍有空閒，我會再回頭去看看以前寫的文章。總是會有許多缺點與漏洞，時常讓我差點禁不住衝動，想要一次砍光。

　　再加上，由於基礎的教學文章難寫，常常是耗了半天，遲遲寫不出滿意的內容。無奈之下，我也只得以解題文章充數。因為如此，說不定我從一開始就偏離了「簡單入門」的目標。而且，在開創以來的前幾個月，其實並不如我所期望的，有任何程式設計愛好者的討論與交流。只見網誌的文章數徒增，留言區卻依舊冷冷清清，這種「文章不知寫給誰看」的感覺，實在是相當難過。

　　這一次，在整個網誌改版之後，我順勢把網誌換了個名字 - Infinite Loop。代表著我對往後的自己能夠有所突破(break)所做的期許。不過，沒想到 Tory 看到標題，卻直接說：「寫程式就是如此，一直寫下去，不知盡頭在那」。雖然這並不是我當初更名的本意，但是我想，或許這句話對一個程式人、對一個程式設計的網誌來說，也是再好不過的註腳了。

　　假借一百篇的名義，我特地將這些想法、這些理念訴諸文字，寫在這裡。與未來的自己、以及所有喜愛程式的同好共勉之。