【解題】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 看到標題，卻直接說：「寫程式就是如此，一直寫下去，不知盡頭在那」。雖然這並不是我當初更名的本意，但是我想，或許這句話對一個程式人、對一個程式設計的網誌來說，也是再好不過的註腳了。

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