【演算】老鼠走迷宮 - Mouse in a Maze

　　老鼠走迷宮是訓練使用堆疊(或是遞迴)的一種經典題型。老鼠可以往上、下、左、右四個方向前進，你必須讓這隻老鼠在迷宮中，由給定的起點走到終點。

　　而這題最簡單的作法，就是由起點開始向四個方向測試，並將走過的路徑做個標示，以防止走過相同的路。一旦發現現在的走法無法走到終點，則追朔回之前的路徑，並將當前的標示清除。

　　這樣敘述或許比較抽象。假設迷宮的起點在(X_S, Y_S)、終點在(X_E, Y_E)。迷宮存在 maze 這個二維陣列之中，若 maze[x][y] = 1 則代表牆壁，maze[x][y] = 0 則代表可以通行。那麼，解題的虛擬碼就像這樣：

bool visit(index x, index y)
{
    bool success = false;

    gone[x][y] = true;

    if ((maze[x][y + 1] != 1 and visit(x, y + 1) = true) or
        (maze[x + 1][y] != 1 and visit(x + 1, y) = true) or
        (maze[x][y - 1] != 1 and visit(x, y - 1) = true) or
        (maze[x - 1][y] != 1 and visit(x - 1, y) = true))
    {
        success = true;
    }
    else
    {
        gone[x][y] = false;
    }

    return success;
}

　　假如還是不太瞭解，我有使用 C++ 以這個方式，作出一個老鼠走迷宮的範例：

　　

　　程式採用標準輸入，第一行的兩個數字 n, m 代表迷宮的高與寬。接下來的 n * m 個數字代表迷宮，1 代表牆壁、0 代表可以通行。最後的四個數字分別代表起點的 x 座標、起點的 y 座標、終點的 x 座標、終點的 y 座標。

　　附屬的文字檔是我做出來的範例迷宮。假如要使用則在命令列模式，至該檔案目錄輸入以下指令：

　　Maze < Maze.txt

　　除此之外，若是想看到老鼠尋路的方式，可以輸入以下指令(紅字請自行更改，代表每一步延遲多久。單位是千分之ㄧ秒)：

　　Maze < Maze.txt 500

【解題】Points in Figures: Rectangles and Circles

ACM Volume IV 477 - Points in Figures: Rectangles and Circles


The Problem

Given a list of figures (rectangles and circles) and a list of points in the x-y plane, determine for each point which figures (if any) contain the point.


Input

There will be n(≦10) figures descriptions, one per line. The first character will designate the type of figure (``r'', ``c'' for rectangle or circle, respectively). This character will be followed by values which describe that figure.

* For a rectangle, there will be four real values designating the x-y coordinates of the upper left and lower right corners.
* For a circle, there will be three real values, designating the x-y coordinates of the center and the radius.

The end of the list will be signalled by a line containing an asterisk in column one.

The remaining lines will contain the x-y coordinates, one per line, of the points to be tested. The end of this list will be indicated by a point with coordinates 9999.9 9999.9; these values should not be included in the output.

Points coinciding with a figure border are not considered inside.


Output

For each point to be tested, write a message of the form:

Point i is contained in figure j

for each figure that contains that point. If the point is not contained in any figure, write a message of the form:

Point i is not contained in any figure

Points and figures should be numbered in the order in which they appear in the input.


Sample Input

r 8.5 17.0 25.5 -8.5
c 20.2 7.3 5.8
r 0.0 10.3 5.5 0.0
c -5.0 -5.0 3.7
r 2.5 12.5 12.5 2.5
c 5.0 15.0 7.2
*
2.0 2.0
4.7 5.3
6.9 11.2
20.0 20.0
17.6 3.2
-5.2 -7.8
9999.9 9999.9


Sample Output

Point 1 is contained in figure 3
Point 2 is contained in figure 3
Point 2 is contained in figure 5
Point 3 is contained in figure 5
Point 3 is contained in figure 6
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 5 is contained in figure 2
Point 6 is contained in figure 4


Diagrama of sample input figures and data points


解題思考

　　這題算是 476 的進階版(?)，所以我的解題方式基本上也大致相同。

　　些許不同的是，我將之前定義矩形的 struct "rectangle" 改成 "figure"，並加入兩個成員。其中一個用以代表圖形的類別(矩形或是圓形)，另一個則代表圓形的半徑(假如圖形是矩形則用不到)。

　　接著，同樣宣告出一個大小為 10 的 figure 結構陣列，再根據輸入資料依序將圖形資料存入陣列中。

　　判斷點在矩形中的方式，在 476 那題我已經做了解釋，在這裡不在贅述。

　　而點在圓形中的判斷法，就要用到圓形的平面座標方程式，也就是若點(X', Y')在圓心為(X, Y)的時候 [(X' - X)² + (Y' - Y)²]^1/2 < r 成立。由於開根號(A^1/2)結果較不精準，因此我們可以將之改寫成 (X' - X)² + (Y' - Y)² < r²。

　　最後，同樣照著題目要求輸出答案。這一題就解完了。


參考解答(C++)

#include <iostream>

using namespace std;

// 宣告圖形結構
struct figure
{
    char kind;
    double x1, x2, y1, y2, r;
};

int main(void)
{
    figure figs[10];

    // 圖形輸入迴圈
    int size;
    for (int i = 0; ; i++)
    {
        char c;
        cin >> c;

        if (c == '*')
        {
            size = i;
            break;
        }

        // 輸入是矩形
        else if (c == 'r')
        {
            cin >> figs[i].x1 >> figs[i].y1 >> figs[i].x2 >> figs[i].y2;
        }

        // 輸入是圓
        else if (c == 'c')
        {
            cin >> figs[i].x1 >> figs[i].y1 >> figs[i].r;
        }

        figs[i].kind = c;
    }

    // 點輸入迴圈
    for (int i = 1; ; i++)
    {
        double x, y;
        bool contained = false;

        cin >> x >> y;

        if (x == 9999.9 && y == 9999.9) { break; }

        // 判別點在哪個圖形中
        for (int j = 0; j < size; j++)
        {
            if (figs[j].kind == 'r')
            {
                if (x > figs[j].x1 && x < figs[j].x2 &&
                    y > figs[j].y2 && y < figs[j].y1)
                {
                    cout << "Point " << i << " is contained in figure " << j + 1 << endl;
                    contained = true;
                }
            }

            if (figs[j].kind == 'c')
            {
                double a = (x - figs[j].x1), b = (y - figs[j].y1);
                if (a * a + b * b < figs[j].r * figs[j].r)
                {
                    cout << "Point " << i << " is contained in figure " << j + 1 << endl;
                    contained = true;
                }
            }
        }

        // 假如不在任何圖形中
        if (!contained)
        {
            cout << "Point " << i << " is not contained in any figure" << endl;
        }
    }

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

【解題】Points in Figures: Rectangles

ACM Volume IV 476 - Points in Figures: Rectangles


The Problem

Given a list of rectangles and a list of points in the x-y plane, determine for each point which figures (if any) contain the point.


Input

There will be n(≦10) rectangles descriptions, one per line. The first character will designate the type of figure (``r'' for rectangle). This character will be followed by four real values designating the x-y coordinates of the upper left and lower right corners.

The end of the list will be signalled by a line containing an asterisk in column one.

The remaining lines will contain the x-y coordinates, one per line, of the points to be tested. The end of this list will be indicated by a point with coordinates 9999.9 9999.9; these values should not be included in the output.

Points coinciding with a figure border are not considered inside.


Output

For each point to be tested, write a message of the form:

Point i is contained in figure j

for each figure that contains that point. If the point is not contained in any figure, write a message of the form:

Point i is not contained in any figure

Points and figures should be numbered in the order in which they appear in the input.


Sample Input

r 8.5 17.0 25.5 -8.5
r 0.0 10.3 5.5 0.0
r 2.5 12.5 12.5 2.5
*
2.0 2.0
4.7 5.3
6.9 11.2
20.0 20.0
17.6 3.2
-5.2 -7.8
9999.9 9999.9


Sample Output

Point 1 is contained in figure 2
Point 2 is contained in figure 2
Point 2 is contained in figure 3
Point 3 is contained in figure 3
Point 4 is not contained in any figure
Point 5 is contained in figure 1
Point 6 is not contained in any figure


Diagrama of sample input figures and data points


解題思考

　　這題我的方式，就是先定義出一個矩形的結構(struct) "rectangle"。接著，宣告出一個大小為 10 (因為題目給定的 n 是大於等於 10 的)的 rectangle 結構陣列。之後再根據輸入資料依序將矩形資料存入陣列中。

　　之後就是如何判斷點在矩形中了。其實判斷的原理相當簡單，就是點的 x 座標介於矩形的兩個 x 座標之間，且點的 y 座標介於矩形的兩個 y 座標之間。接著再根據題目要求輸出判斷結果，這題就解完了。


參考解答(C++)

#include <iostream>

using namespace std;

// 宣告矩形結構
struct rectangle
{
    double x1, x2, y1, y2;
};

int main(void)
{
    rectangle rects[10];

    // 圖形輸入迴圈
    int size;
    for (int i = 0; ; i++)
    {
        char c;
        cin >> c;

        if (c == '*')
        {
            size = i;
            break;
        }
        else if (c == 'r')
        {
            cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
        }
    }

    // 點輸入迴圈
    for (int i = 1; ; i++)
    {
        double x, y;
        bool contained = false;

        cin >> x >> y;

        if (x == 9999.9 && y == 9999.9) { break; }

        // 判別點在哪個圖形中
        for (int j = 0; j < size; j++)
        {
            if (x > rects[j].x1 && x < rects[j].x2 &&
                y > rects[j].y2 && y < rects[j].y1)
            {
                cout << "Point " << i << " is contained in figure " << j + 1 << endl;
                contained = true;
            }
        }

        // 假如不在任何圖形中
        if (!contained)
        {
            cout << "Point " << i << " is not contained in any figure" << endl;
        }
    }

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

【轉貼】勤勉之人、輕量之人

　　這是 Ruby 之父兼日本 Ruby 協會會長(日本 Ruby の会)高橋征義 2007 年來台的演講，談到程式開發人員的兩種分類：勤勉之人(使用 Cobol、C/C++、Java)、輕量之人(使用 Perl、Python、Ruby)。

　　高橋通篇使用英文演講。影片雜音很多，不過搭配投影片，內容應不難理解。影片中也可以見識到傳說中的高橋流(高橋メソッド)簡報，其簡單大方的風格真有特色。


高橋メソッド in 中文


Diligent people, Lightweight people

　　簡報本身還滿幽默的。連涼宮春日(涼宮 ハルヒ)都可以搬出來講，真是服了他了。

【演算】連結串列 - Linked List

　　當你需要儲存一串同型資料時，使用陣列或許是一個最簡單的方法。但是由於陣列在宣告時，就需要明確的指定大小。在資料不多(比陣列大小小)時，就容易造成記憶體的浪費。反之資料多(比陣列大小大)時，也會出現記憶體空間上使用限制。

　　而連結串列(linked list)，可以說就是為了解決這些缺陷而出現的。串列的最大特色，就是其大小可因應需求動態配置記憶體，避免記憶體的浪費。不過相對的，串列的實現與操作也較陣列麻煩許多。

　　串列中的每一個元素稱之為節點(node)，每一個節點都包含了儲存資料的變數，以及連結其他節點的連結指標(linked list 之名便是有此而來)。


　　根據不同情況，比較常見的串列有單向連結串列(singly-linked lists)、雙向連結串列(doubly-linked lists)與環狀連結串列(circularly-linked lists)。

　　單向連結串列是一個最基本的串列，每一個節點都包含一個指向下一個節點的指標。



　　一個節點的宣告方式大致如下：

struct Node
{
    Type data;
    Node *next;
}

　　而串列的操作，大致有插入(insert)跟移除(remove)這兩種方式。

　　插入操作的進行，其實只是指標指向的轉移。假設現在欲在 A 與 C 節點中插入一個 B 節點，則先將 B 節點的連結指標指向 C，再將 A 節點的連結指標指向 B。



　　相同的，移除操作也是藉由指標指向的轉移達成。假設現在我們要將 A 與 C 節點中的 B 節點移除，則將 A 節點的連結指標指向 C 即可。



　　以上兩種操作的虛擬碼大致如下：

void insert(Node* n1, Node* n2)
{
    // 將 n2 插入在 n1 之後
    n2->next = n1->next;
    n1->next = n2;
}

void remove(Node* n1)
{
    // 刪除 n1 的下一個節點
    n1->next = n1->next->next;
}

　　以下是使用 C 語言的實作單向連結串列的使用實例：

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

// 宣告節點結構
typedef struct ns
{
    int data;
    struct ns* next;
} node;

// 宣告相關函式
node* create_node(int);
void insert_node(node*, node*);
void remove_node(node*);
void print_lists(node*);
void free_lists(node*);

int main(void)
{
    // 宣告節點
    node* lists = create_node(0);
    node* a = create_node(1);
    node* b = create_node(2);
    node* c = create_node(3);
    node* d = create_node(4);
    node* e = create_node(5);

    // 0 -> 5
    insert_node(lists, e);

    // 0 -> 1 -> 5
    insert_node(lists, a);

    // 1 -> 2 -> 5
    insert_node(a, b);

    // 1 -> 3 -> 2
    insert_node(a, c);

    // 5 -> 4
    insert_node(e, d);

    print_lists(lists);
    free_lists(lists);

    system("pause");
}

node* create_node(int data)
{
    // 動態配置記憶體
    node* n = (node*)malloc(sizeof(node));

    n->data = data;
    n->next = NULL;

    return n;
}

void insert_node(node* n1, node* n2)
{
    n2->next = n1->next;
    n1->next = n2;
}

void remove_node(node* n1)
{
    n1->next = n1->next->next;
}

void print_lists(node* lists)
{
    node* n = lists;

    // 依序印出節點內容
    while (n != NULL)
    {
        printf("%d ", n->data);

        n = n->next;
    }

    printf("\n");
}

void free_lists(node* lists)
{
    // 遞迴刪除串列所有節點
    if (lists->next != NULL)
    {
        free_lists(lists->next);
    }

    free(lists);
}

　　至於雙向連結串列，則是結點比單向連結串列多了一個連結指標，指向的是這個節點的前一個節點。



　　而環狀連結串列跟單向連結串列僅有唯一不同點，就是環狀連結串列的最後一個節點指標指向的是第一個節點。



　　至於這兩種連結串列的操作，基本上與單向連結串列大同小異，這裡我們不再多花篇幅解釋(格主想睡了)。


　　儘管連結串列在資料的新增與移除上，較陣列來的彈性許多，它也是具有許多缺點的。

　　除了一開始我所提到的操作麻煩之外，由於串列沒有索引值，因此要提取某節點存放的變數值會相當不方便。而且若是一個連結串列的節點相當多，每一個節點指標所佔用的記憶體也相當龐大。

　　因此，根據不同的情況，判斷何時用陣列、何時用串列，也是相當重要的。

【演算】佇列 - Queue

　　與堆疊(stack)類似，佇列(queue)也是一種是一種同質元素集合的資料結構。與之不同的是，佇列只允許資料在後端(rear)進行插入(add)操作、在前端(front)進行刪除(delete)操作。

　　同樣的，讓我們舉個實例：相對於堆疊的疊盤子，你可以把佇列想像成一個正在排隊買甜甜圈的隊伍。每執行一次 "delete" 的動作就像是隊伍最前端，成功的買到甜甜圈而離開隊伍。而執行一次 "add" 就像是多了一個想買甜甜圈的客人，而在隊伍的最後端開始排隊(請忽略掉插隊問題)。

　　也因此，不同於堆疊的 LIFO，佇列的操作方式被稱為 FIFO (First In First Out，先入先出)。換句話說，就是越早加入佇列的人(資料)會越早離開佇列。

　　所以，佇列的應用範圍也相當廣泛。從剛剛舉例說明的排隊、圖形的廣度追蹤、使用印表機時的列印佇列等等，都可以見到佇列應用的蹤影。


　　而模擬一個佇列的運作，最簡單的方式還是使用陣列。同樣定義一個大小為 MAX_SIZE 的陣列，並使用兩個變數 front 與 rear 分別代表佇列的前後端。以下是一個簡易佇列實現的虛擬碼實例：

void add(Queue &queue, Type data)
{
    Index front, rear;

    if (rear = MAX_SIZE)
    {
        print("The queue is full!");
    }
    else
    {
        stack[rear] = data;
        rear = rear + 1;
    }
}

void delete(Queue &queue)
{
    Index front, rear;

    if (front = rear)
    {
        print "The queue is empty!";
    }
    else
    {
        front = front + 1;
    }
}

　　同樣的，陣列之外模擬方式與 C++ STL 實現的佇列相關函式這裡我們不討論，請有興趣者自行查詢相關資料。

　　以下是 C 使用陣列實現的原始碼，可以參考看看：

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

#define MAX_SIZE 10

void addQ(int);
void deleteQ(void);

int queue[MAX_SIZE], front = 0, rear = 0;

int main(void)
{
    addQ(0);
    addQ(1);
    deleteQ();
    addQ(2);
    addQ(3);
    addQ(4);
    deleteQ();
    deleteQ();
    addQ(5);
    addQ(6);
    addQ(7);
    deleteQ();
    deleteQ();
    deleteQ();
    deleteQ();
    deleteQ();

    system("pause");
}

void addQ(int data)
{
    if (rear == MAX_SIZE)
    {
        printf("The queue is full!\n");
    }
    else
    {
        queue[rear++] = data;
    }
}

void deleteQ(void)
{
    if (front == rear)
    {
        printf("The stack is empty!\n");
    }
    else
    {
        printf("%d\n", queue[front++]);
    }
}

【演算】堆疊 - Stack

　　堆疊(stack)是一種同質元素(像是相同型態的變數)集合的資料結構，只允許在結構的一端，進行推入(push)或是彈出(pop)兩種資料操作。



　　讓我們舉個實例：想像現在有一疊盤子，每當執行一次 "push" 就相當於往上再疊上一個盤子，而執行一次 "pop" 則像是拿走最上面的那一個盤子。

　　因此，我們可以發現：由於越晚疊入的盤子(資料)在越上層，因此是這個盤子(資料)是越早被取下來的。而這種資料操作方式，我們就稱之為 LIFO (Last In First Out，後入先出)。

　　也因為這種特性，堆疊的應用範圍相當的廣。像是程式設計函式(function)的呼叫(call)與返回(return)、河內塔(Towers of Hanoi)、算術式轉換等等。這些應用我以後會找機會一一說明，在此不加贅述。


　　在程式語言中，要實現堆疊有許多種方法，最簡單的方式就是使用陣列模擬。即定義一個大小為 MAX_SIZE 的陣列，並使用一個變數 top 來表示堆疊的頂端。而資料操作的方式可以參考以下虛擬碼：

void push(Stack &stack, Type data)
{
    Index top;

    if (top = MAX_SIZE)
    {
        print "The stack is full!";
    }
    else
    {
        stack[top] = data;
        top = top + 1;
    }
}

void pop(Stack &stack)
{
    Index top;

    if (top = 0)
    {
        print "The stack is empty!";
    }
    else
    {
        top = top - 1;
    }
}

　　當然，除了陣列之外，你也可以使用其他資料結構(例如：連結串列，linked list) 來模擬。另外，在 C++ 的 STL(Standard Template Library，標準樣板庫) 中，也早已實現了堆疊結構及相關函式。不過這些都不在本篇的討論範圍中，有興趣的人就自行摸索囉。

　　以下是 C 以陣列實現的堆疊原始碼，可以參考看看：

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

#define MAX_SIZE 10

void push(int);
void pop(void);

int stack[MAX_SIZE], top = 0;

int main(void)
{
    push(0);
    push(1);
    push(2);
    pop();
    pop();
    push(3);
    push(4);
    pop();
    pop();
    pop();
    push(5);
    push(6);
    push(7);
    pop();
    pop();
    pop();

    system("pause");
}

void push(int data)
{
    if (top == MAX_SIZE)
    {
        printf("The stack is full!\n");
    }
    else
    {
        stack[top++] = data;
    }
}

void pop(void)
{
    if (top == 0)
    {
        printf("The stack is empty!\n");
    }
    else
    {
        printf("%d\n", stack[--top]);
    }
}

【轉貼】程式高手的八大奧秘

　　不知不觉做软件已经做了十年，有成功的喜悦，也有失败的痛苦，但总不敢称自己是高手，因为和我心目中真正的高手们比起来，还差的太远。世界上并没有成为高手的快捷方式，但一些基本原则是可以遵循的。


1、扎实的基础

　　数据结构、离散数学、编译原理，这些是所有计算机科学的基础，如果不掌握它们，很难写出高水平的程序。程序人人都会写，但当你发现写到一定程度很难再提高的时候，就应该想想是不是要回过头来学学这些最基本的理论。不要一开始就去学OOP，即使你再精通OOP，遇到一些基本算法的时候可能也会束手无策。因此多读一些计算机基础理论方面的书籍是非常有必要的。


2、丰富的想像力

　　不要拘泥于固定的思维方式，遇到问题的时候要多想几种解决问题的方案，试试别人从没想过的方法。丰富的想像力是建立在丰富的知识的基础上，除计算机以外，多涉猎其他的学科，比如天文、物理、数学等等。开阔的思维对程序员来说很重要。


3、最简单的是最好的

　　这也许是所有科学都遵循的一条准则，复杂的质能转换原理在爱因斯坦眼里不过是一个简单得不能再简单的公式：E=mc2。简单的方法更容易被人理解，更容易实现，也更容易维护。遇到问题时要优先考虑最简单的方案，只有简单方案不能满足要求时再考虑复杂的方案。


4、不钻牛角尖

　　当你遇到障碍的时候，不妨暂时远离电脑，看看窗外的风景，听听轻音乐，和朋友聊聊天。当我遇到难题的时候会去玩游戏，当负责游戏的那部分大脑细胞极度亢奋的时候，负责编程的那部分大脑细胞就得到了充分的休息。当重新开始工作的时候，我会发现那些难题现在竟然可以迎刃而解。


5、对答案的渴求

　　人类自然科学的发展史就是一个渴求得到答案的过程，即使只能知道答案的一小部分也值得我们去付出。只要你坚定信念，一定要找到问题的答案，你才会付出精力去探索，即使最后没有得到答案，在过程中你也会学到很多东西。


6、多与别人交流

　　三人行必有我师，也许在一次和别人不经意的谈话中，就可以迸出灵感的火花。多上上网，看看别人对同一问题的看法，会给你很大的启发。


7、良好的编程风格

　　注意养成良好的习惯，代码的缩进编排，变量的命名规则要始终保持一致。大家都知道如何排除代码中错误，却往往忽视了对注释的排错。注释是程序的一个重要组成部分，它可以使你的代码更容易理解，而如果代码已经清楚地表达了你的思想，就不必再加注释了，如果注释和代码不一致，那就更加糟糕。


8、韧性和毅力

　　这也许是“高手”和一般程序员最大的区别。高手们并不是天才，他们是在无数个日日夜夜中磨炼出来的。成功能给我们带来无比的喜悦，但过程却是无比的枯燥乏味。你不妨做个测试，找个10000以内的素数表，把它们全都抄下来，然后再检查三遍，如果能够不间断地完成这一工作，你就可以满足这一条。


　　这些是我这几年程序员生涯的一点体会，希望能够给大家有所帮助。

　　作者：金蝶中间件公司 CTO 袁红岗
　　出處：高手谈做程序员的基本原则

【介紹】ACM - What's Wrong

　　在之前，我們已經介紹過 ACM 與 Online Judge 的使用方式。但是，你的程式提交結果並不一定就是正解，因此系統會回報你一個 Verdict，讓你知道你的程式結果是否正確，或是發生了什麼錯誤。所以在這裡，讓我們來看看這些解題結果的狀態說明。


Accepted (AC):
　　恭喜你！出現這個結果代表你的程式沒有發生錯誤，且執行結果完全正確。

Accepted (P.E.)(Presentation Error):
　　同上，出現這個結果代表你的答案是正確的，不過有格式上的錯誤。像是多餘的空白、換行等等。根據官方討論區的說明文件所言，這個結果只適用實際比賽，對於線上裁判系統而言，這只是個警告，不必太過擔心。

Wrong Answer (WA):
　　程式成功的執行了，但是你的輸出資料結果是錯誤的。

Runtime Error (RE):
　　程式成功編譯，但發生執行期錯誤(非法操作記憶體、除以 0 等等問題)。

Time Limit Exceeded (TL):
　　你的程式執行時間太久了。目前 Online Judge 的執行限制時間似乎是 3 秒內，試著改善解題的演算法吧。

Memory Limit Exceeded (ML):
　　程式執行的需求記憶體超過系統限制。不過官方文件寫著，假如你確定有這些記憶體需求，可以試著跟管理員聯繫。至於實際狀況如何，我就不得而知了。

Output Limit Exceeded (OL):
　　你的程式輸出資料量超過系統限制。通常是無窮迴圈造成的結果(我就曾經如此過，不過狀態寫的是 Time Limit Exceeded，所以這種執行結果真的可能出現嗎？)。

Restricted Function (RF):
　　你的原始碼使用到系統不允許使用的函式(例如 fork()、fopen() 等等)。

Compile Error (CE):
　　編譯錯誤。由於系統使用的編譯器是 gcc，若是使用不同編譯器可能會有語法上的不同，在提交前要多注意。

Submission Error (SE):
　　題號、使用者 ID(新版的 Online Judge 應該不會有此問題)、或是使用的語言未填。

Can't Be Judged (CJ):
　　系統沒有該問題的輸出入資料(不確定)。

Access Denied (AD):
　　你的網址不允許你提交問題(完全不懂，麻煩知道的人告知我一聲)。

Non Authenticated (NA):
　　你的電子郵件無法認證，或是提交工具沒有寄出認證消息。假如你不是 Hacker，請跟管理員聯繫(這應該只有設定"開啟電子郵件接收執行結果"才會出現。實際上我也沒使用過，所以也只能照著文件翻譯)。

Out Of Contest Time (OC):
　　這個訊息只有實際比賽會出現，代表超過比賽時間。

Delayed (DL):
　　系統忙碌，因此結果會延遲出現。這個時候請不要再一次提交結果。

Judge Disabled:
　　系統維修中(不確定)。

Judge Not Ready!:
　　因為某些原因，系統剛剛重新啟動。所以 Judge 還沒有載入到系統中。

　　以上這些參考自官方討論區的 How to understand the Online Judge answers。不過由於大多數的回報狀態我都沒碰過，因此也不能做完全正確的解說。假如有哪裡解釋錯誤請告知一聲，我立即改正。

【解題】Joana and the Odd Numbers

ACM Volume IX 913 - Joana and the Odd Numbers


Background

Joana loves playing with odd numbers. In the other day, she started writing, in each line, an odd number of odd numbers. It looked as follows:

1
3 5 7
9 11 13 15 17
19 21 23 25 27 29 31
...

On a certain line Joana wrote 55 odd numbers. Can you discover the sum of the last three numbers written in that line? Can you do this more generally for a given quantity of odd numbers?


The Problem

Given the number N of odd numbers in a certain line, your task is to determine the sum of the last three numbers of that line.


Input

The input is a sequence of lines, one odd number N (1 < N < 1000000000) per line.


Output

For each input line write the sum of the last three odd numbers written by Joana in that line with N numbers. This sum is guaranteed to be less than 2⁶³.


Sample Input

3
5
7


Sample Output

15
45
87


解題思考

　　這題與其說是考程式設計，不如說是考數學。

　　首先，題目要的是某行的最後 3 個數字和，我們可以直接當作該行倒數第 2 個數字乘以 3。

　　至於這個數字該怎麼得到呢？我們需要先知道的是他是從 1 開始的第幾個數字。從題目可以知道，數列的第 k 行有 2k - 1 個數字。因此，當某列有 N 個數字時，該列的最後一個數字是第幾個數字可由等差級數和求得：{(N + 1) * [(N + 1) / 2]} / 2 = (N + 1)² / 4。

　　再來，從題目可以知道，這個數列的第 k 個數字之值為 2k - 1，將剛剛得出的結果減 1(因為我們要的是倒數第二個數字) 代入 k，就可以得到此數字為 2 * {[(N + 1)² / 4] - 1} = [(N + 1)² / 2] - 3。接著再將這個數字乘以 3 就得到題目要的結果了。

　　需要特別注意的一點是，由於數字相當大，因此這裡的整數要宣告成 "long long"。不過這個 "long long" 我之前完全沒看過，查了一下 Wikipedia，看起來是 64 位元新增的資料型態，支援的數字範圍為 -2^{64 - 1} ~ 2^{64 - 1} - 1。Well，相當神奇。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    // 注意, 這裡要宣告成 "long long"
    long long n;
    while (cin >> n)
    {
        cout << 3 * ((n + 1) * (n + 1) / 2 - 3) << endl;
    }

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

    return 0;
}

【解題】Kindergarten Counting Game

ACM Volume IV 494 - Kindergarten Counting Game


The Problem

Everybody sit down in a circle. Ok. Listen to me carefully.

``Woooooo, you scwewy wabbit!''

Now, could someone tell me how many words I just said?


Input and Output

Input to your program will consist of a series of lines, each line containing multiple words (at least one). A ``word'' is defined as a consecutive sequence of letters (upper and/or lower case).

Your program should output a word count for each line of input. Each word count should be printed on a separate line.


Sample Input

Meep Meep!
I tot I taw a putty tat.
I did! I did! I did taw a putty tat.
Shsssssssssh ... I am hunting wabbits. Heh Heh Heh Heh ...


Sample Output

2
7
10
9


解題思考

　　這一題的重點在於判斷字元是否是英文字母。

　　作法是先利用一個 boolean 變數，代表 "是否已讀到一個 Word"。只要碰到非英文字母，且此變數為真時，就代表在此之前的是符合題意的 "Word" ，因此將記錄的總字數遞增。

　　只要將這種解題思維釐清，這一題也就迎刃而解了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    string get;
    while (getline(cin, get))
    {
        int n = 0;
        bool word = false;
        for (int i = 0; i < get.size(); i++)
        {
            if ((get[i] >= 'a' && get[i] <= 'z') ||
                (get[i] >= 'A' && get[i] <= 'Z'))
            {
                word = true;
            }
            else if (word)
            {
                word = false;
                n++;
            }
        }

        if (word) { n++; }

        cout << n << endl;
    }

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

    return 0;
}

【介紹】ACM - How to Start

　　在介紹完 ACM 之後，是否躍躍欲試了呢？所以在這裡，讓我們看看該如何註冊、使用 UVa Online Judge System。由於在之前 UVa Online Judge 遷站了，包含註冊、程式上傳的介面都做了改變。因此我花了點時間拍了圖，做了這一篇(極為難得的)圖文教學。不詳盡之處還請見諒。




　　首先，打開 UVa Online Judge 的首頁。在開始解題之前，你需要先註冊一個帳號，請按下首頁左方選單的 "Register"。



　　接著，你會看到常見的填寫資料表單。表單內容依序是：姓名、帳號、電子郵件地址、密碼、確認密碼。

　　至於倒數第二個輸入框，是給 Online Judge 的舊會員填寫的，在這裡輸入舊帳號的 ID 之後，系統就會幫你把你之前的解題統計轉到這裡來(僅翻譯，未確認)。假如你是新會員，那麼就直接輸入 "00000" 即可。

　　而最後一欄的 Result email 是指每次你提交一題的程式碼，系統就會發一封 email 告訴你結果如何。假如需要這個功能，就把核取方塊打勾。

　　都填寫完之後，按下下方的 "Send Registration" 。假如填寫無誤，系統會發一封 email 給你，裡面包含了帳號的驗證網址，只要點進去就成功完成註冊啦！



　　接著回到首頁，在左邊的 Login 使用剛註冊好的帳號及密碼，就可以登錄了。


　　帳號註冊好之後，就是解題的時間了！



　　在左邊的選單中，點選 "Browse Problems" 就會出現試題的根目錄。



　　選取一個分類後，就會看到題目列表。後方的數據分別是：總提交次數／解決百分比 與 總提交人數／解決百分比。



　　任選一個題目，點進去，就可以看到題目內容了。看到圖片中有三個小圖示，第一個圖示是提交程式的按鈕，第二個是 PDF 文件格式的題目全文。而最後一個按鈕則是這一題的相關統計，包含了程式語言的使用比例、執行速度前二十快、你程式的執行速度與排行等等。


　　現在，我們要將已寫好程式提交，所以請按下第一個圖示，會出現圖中這個畫面。



　　接著在 Language 選擇你所使用的語言，並在下方的文字框貼上你的程式碼。



　　或是使用下方的 upload 直接上傳你的程式(未嘗試過，暫時無法說明)。完成之後按下 "Submit" 送出。



　　然後又會回到題目的內文頁，最上方那排紅底字代表的是你的程式提交 ID。



　　不過，要怎麼知道結果呢？一樣在左邊的選單中，點選 "My Submissions"。看到最上方，拿了個 Accepted(正解)，開心吧(其實開心的是我)！

　　但是，你的程式也可能會發生錯誤(就是 Accepted 之外的結果)。至於要怎麼解讀這些錯誤的結果訊息，我會在下一篇 ACM - What's Wrong 中說明。這裡我們先跳過這個問題。


　　另外，點選選單的 "My Statistics"，會以圖表加上數據幫你做一個簡單的統計。包含你解了多少題目、嘗試了多少題目、使用的語言比例、提交結果的比例等等，可以更方便的掌握你解題的進展與弱點(發現哪種問題特別多)。



　　最後，想知道自己在 Online Judge 的實力如何嗎？點選左方選單的 "Site Statistics"，就會出現 Online Judge 所有會員的總排名。找找看，自己位於哪個位置吧！

【解題】The Decoder

ACM Volume IV 458 - The Decoder


The Problem

Write a complete program that will correctly decode a set of characters into a valid message. Your program should read a given file of a simple coded set of characters and print the exact message that the characters contain. The code key for this simple coding is a one for one character substitution based upon a single arithmetic manipulation of the printable portion of the ASCII character set.


Input and Output

For example: with the input file that contains:

1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5

your program should print the message:

*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.

Your program should accept all sets of characters that use the same encoding scheme and should print the actual message of each set of characters.


Sample Input

1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5


Sample Output

*CDC is the trademark of the Control Data Corporation.
*IBM is a trademark of the International Business Machine Corporation.
*DEC is the trademark of the Digital Equipment Corporation.


解題思考

　　這題的解法超簡單，其實只是 ASCII 碼的偏移而已。

　　只要對照題目輸出入檔的英文字部分，就可以發現每個字都差了 7 個字母(例如 input 的 'J' 到了 output 就變成了 'C')。所以只要讀入每個字元，並將其 ASCII 碼減 7 就算完成了。


參考解答(C++)

#include <iostream>

using namespace std;

int main(void)
{
    string str;

    while (getline(cin, str))
    {
        for (int i = 0; i < str.size(); i++)
        {
            cout << (char)(str[i] - 7);
        }

        cout << endl;
    }

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

【介紹】ACM - What's This

　　ACM (Association for Computing Machinery，美國電腦協會) 是一個電腦科學研究組織，致力於發展科學性及教育性的電腦研究，且出版了大量的專門期刊，並舉辦了多場的會議、會談。在資訊界中不只有名，還具有舉足輕重的地位。

　　每一年，ACM 都會舉辦一場 ICPC (International Collegiate Programming Contest，國際大學生程式設計競賽)，目的是為了考驗世界各地的大學生團隊合作，並在有限的時間內使用 C、C++、Java 或是 Pascal 分析並解決程式問題。直到現在，ACM-ICPC 已然成為國際上相當具有影響力的大學資訊競賽。也因為這場比賽的高影響力，世界上有許多大專院校，收集了歷年 ACM-ICPC 競賽的試題，開發出各式各樣「Online Judge System」供學生做練習使用。



　　那麼，什麼是 Online Judge 呢？如同其字面上的意義，它是一套"線上裁判"的系統。只要你認為解出了其中的某一題，你就可以將你的程式碼提交給系統。系統會幫你判斷程式的正確性，以及答對題數的統計。而其中最有知名度的，大概就是 UVa Online Judge 這個系統了。

　　UVa Online Judge 目前由西班牙的瓦薩利大學 (Universidad de Valladolid) 所維護。對臺灣而言，也算是最廣為人知的了。許多資訊科系的學生 (其實也不乏許多高中生) 會以此作為磨練自我的管道，也有教授會將此當作上課的教材。

　　不過有趣的是，似乎許多人都誤把這套系統的名字搞錯了。直接把它叫作 ACM。久而久之，「ACM 網站」也就變成這套系統的代名詞了。無論如何，不管你是高中生、大學生、或是在職人士，有自信挑戰 ICPC 的題目，並在 ACM 的全球排行榜中脫穎而出嗎？

Try it now：
　UVa Online Judge - http://icpcres.ecs.baylor.edu/onlinejudge/

　　以下是一些參考資料，有興趣的人可以參閱：

．Association for Computing Machinery - Wikipedia
．International Collegiate Programming Contest - Wikipedia
．Online judge - Wikipedia
．Online Judge System 起源與由來
．ACM Online Judge Guide

【解題】TeX Quotes

ACM Volume II 272 - TeX Quotes


The Problem

TeX is a typesetting language developed by Donald Knuth. It takes source text together with a few typesetting instructions and produces, one hopes, a beautiful document. Beautiful documents use `` and " to delimit quotations, rather than the mundane " which is what is provided by most keyboards. Keyboards typically do not have an oriented double-quote, but they do have a left-single-quote ` and a right-single-quote '. Check your keyboard now to locate the left-single-quote key ` (sometimes called the ``backquote key") and the right-single-quote key ' (sometimes called the ``apostrophe" or just ``quote"). Be careful not to confuse the left-single-quote ` with the ``backslash" key \. TeX lets the user type two left-single-quotes `` to create a left-double-quote `` and two right-single-quotes '' to create a right-double-quote ''. Most typists, however, are accustomed to delimiting their quotations with the un-oriented double-quote ".

If the source contained:

"To be or not to be," quoth the bard, "that is the question."

then the typeset document produced by TeX would not contain the desired form:

``To be or not to be," quoth the bard, ``that is the question."

In order to produce the desired form, the source file must contain the sequence:

``To be or not to be,'' quoth the bard, ``that is the question.''

You are to write a program which converts text containing double-quote (") characters into text that is identical except that double-quotes have been replaced by the two-character sequences required by TeX for delimiting quotations with oriented double-quotes. The double-quote (") characters should be replaced appropriately by either `` if the " opens a quotation and by '' if the " closes a quotation. Notice that the question of nested quotations does not arise: The first " must be replaced by ``, the next by '', the next by ``, the next by '', the next by ``, the next by '', and so on.


Input and Output

Input will consist of several lines of text containing an even number of double-quote (") characters. Input is ended with an end-of-file character. The text must be output exactly as it was input except that:

　　* the first " in each pair is replaced by two ` characters: `` and 　　* the second " in each pair is replaced by two ' characters: ''.


Sample Input

"To be or not to be," quoth the Bard, "that
is the question".
The programming contestant replied: "I must disagree.
To `C' or not to `C', that is The Question!"


Sample Output

``To be or not to be,'' quoth the Bard, ``that
is the question''.
The programming contestant replied: ``I must disagree.
To `C' or not to `C', that is The Question!''


解題思考

　　我的作法是，先使用一個 boolean 變數紀錄現在接著要輸出左單引還是右單引。

　　再來，既然「"」才是重點，就直接使用 string 的搜尋函式找「"」。輸出之前的內容之後，再根據 boolean 變數判斷輸出的單引號。跳過輸出這個「"」之後重複上述動作，直到搜尋完字串為止。

　　別懷疑，只要這樣這題就算完成了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
    bool quote = true;
    string str;

    while (getline(cin, str))
    {
        int search[2] = {0, 0};

        while ((search[1] = str.find("\"", search[0])) != string::npos)
        {
            cout << str.substr(search[0], search[1] - search[0]);

            if (quote)  { cout << "``"; }
            else        { cout << "''"; }

            quote = !quote;
            search[0] = search[1] + 1;
        }

        cout << str.substr(search[0], str.size() - search[0]);

        cout << endl;
    }

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

【解題】Stacking Boxes

ACM Volume I 103 - Stacking Boxes


Background

Some concepts in Mathematics and Computer Science are simple in one or two dimensions but become more complex when extended to arbitrary dimensions. Consider solving differential equations in several dimensions and analyzing the topology of an n-dimensional hypercube. The former is much more complicated than its one dimensional relative while the latter bears a remarkable resemblance to its ``lower-class'' cousin.


The Problem

Consider an n-dimensional ``box'' given by its dimensions. In two dimensions the box (2,3) might represent a box with length 2 units and width 3 units. In three dimensions the box (4,8,9) can represent a box 4 * 8 * 9 (length, width, and height). In 6 dimensions it is, perhaps, unclear what the box (4,5,6,7,8,9) represents; but we can analyze properties of the box such as the sum of its dimensions.

In this problem you will analyze a property of a group of n-dimensional boxes. You are to determine the longest nesting string of boxes, that is a sequence of boxes b₁, b₂, ..., b_k such that each box b_i nests in box b_{i + 1} (1 ≦ i ＜ k).

A box D = (d₁, d₂, ..., d_n) nests in a box E = (e₁, e₂, ..., e_n) if there is some rearrangement of the d_i such that when rearranged each dimension is less than the corresponding dimension in box E. This loosely corresponds to turning box D to see if it will fit in box E. However, since any rearrangement suffices, box D can be contorted, not just turned (see examples below).

For example, the box D = (2,6) nests in the box E = (7,3) since D can be rearranged as (6,2) so that each dimension is less than the corresponding dimension in E. The box D = (9,5,7,3) does NOT nest in the box E = (2,10,6,8) since no rearrangement of D results in a box that satisfies the nesting property, but F = (9,5,7,1) does nest in box E since F can be rearranged as (1,9,5,7) which nests in E.

Formally, we define nesting as follows: box D = (d₁, d₂, ..., d_n) nests in box E = (e₁, e₂, ..., e_n) if there is a permutation π of 1...n such that (d_π(1), d_π(2), ..., d_π(n)) ``fits'' in (e₁, e₂, ..., e_n) i.e., if d_π(i) < e_i for all .


The Input

The input consists of a series of box sequences. Each box sequence begins with a line consisting of the the number of boxes k in the sequence followed by the dimensionality of the boxes, n (on the same line.)

This line is followed by k lines, one line per box with the n measurements of each box on one line separated by one or more spaces. The i^th line in the sequence (1 ≦ i ≦ k) gives the measurements for the i^th box.

There may be several box sequences in the input file. Your program should process all of them and determine, for each sequence, which of the k boxes determine the longest nesting string and the length of that nesting string (the number of boxes in the string).

In this problem the maximum dimensionality is 10 and the minimum dimensionality is 1. The maximum number of boxes in a sequence is 30.


The Output

For each box sequence in the input file, output the length of the longest nesting string on one line followed on the next line by a list of the boxes that comprise this string in order. The ``smallest'' or ``innermost'' box of the nesting string should be listed first, the next box (if there is one) should be listed second, etc.

The boxes should be numbered according to the order in which they appeared in the input file (first box is box 1, etc.).

If there is more than one longest nesting string then any one of them can be output.

Sample Input

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9


Sample Output

5
3 1 2 4 5
4
7 2 5 6


解題思考

　　首先，看到問題描述，我們需要判斷一個盒子能不能"放入"另一個盒子中。也就是說，兩種序列組合d, e的某一種重排，能使得 d_i > e_i 恆成立。由於我們不想花時間去不斷重排、測試，因此在測試前我們先統一將序列內容從小排到大(或是從大排到小也行)。

　　接著，再使用一個 boolean 陣列 nest[i][j]，判別序列 j 是否可以"放入"序列 i 之中。至於怎麼判斷，由於序列都是相同的由小排到大(或由大排到小)，因此直接用迴圈去一一比對即可。

　　最後，就是分別選擇不同的盒子當最外層，使用遞迴的方式。每遞迴一層就相當於在盒子最內層再"塞"進一個盒子。接著只要找出能套入最多盒子的組合，並把組合的串列輸出出來，就達成題目的要求了。


參考解答(C++)

#include <iostream>

using namespace std;

int compare(const void *, const void *);
bool stack(int);

int maxn, k, n, **box, *list, num;
bool **nest;

int main(void)
{
    while (cin >> k)
    {
        cin >> n;

        maxn = num = 0;

        // 動態配置記憶體
        list = new int[k];

        box = new int *[k];
        for (int i = 0; i < k; i++)
        {
            box[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                cin >> box[i][j];
            }

            // 將內容從小排到大
            qsort(box[i], n, sizeof(int), compare);
        }

        nest = new bool *[k];
        for (int i = 0; i < k; i++)
        {
            // 設定 i 是否可容納 j 的布林變數
            nest[i] = new bool[k];
            for (int j = 0; j < k; j++)
            {
                if (i == j)
                {
                    nest[i][j] = false;
                    continue;
                }

                nest[i][j] = true;
                for (int t = 0; t < n; t++)
                {
                    if (box[i][t] >= box[j][t])
                    {
                        nest[i][j] = false;
                        break;
                    }
                }
            }
        }

        // 呼叫遞迴函式
        for (int i = 0; i < k; i++)
        {
            if (stack(i)) { list[0] = i; }
        }

        // 輸出執行結果
        cout << maxn << endl;
        for (int i = 0; i < maxn; i++)
        {
            cout << list[i] + 1;

            if (i < maxn - 1) { cout << " "; }
            else { cout << endl; }
        }

        // 釋放記憶體空間
        delete [] list;

        for (int i = 0; i < k; i++) { delete [] box[i]; }
        delete [] box;

        for (int i = 0; i < k; i++) { delete [] nest[i]; }
        delete [] nest;
    }

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

int compare(const void *a, const void *b)
{
    int *arg1 = (int *)a;
    int *arg2 = (int *)b;

    if(*arg1 < *arg2)       { return -1; }
    else if(*arg1 == *arg2) { return 0; }
    else                    { return 1; }
}

bool stack(int now)
{
    bool ok = false;

    num++;
    for (int i = 0; i < k; i++)
    {
        // 假如可以 i 放入 now
        if (nest[now][i])
        {
            nest[now][i] = false;

            if (stack(i))
            {
                list[num] = i;
                ok = true;
            }

            nest[now][i] = true;
        }
    }

    num--;

    // 得到最長套入串列長度
    if (num + 1 > maxn)
    {
        maxn = num + 1;
        return true;
    }

    return ok;
}

【演算】大數運算 Part 4

　　介紹完加法、減法、乘法之後，最後就是除法了。當初要作加減法時，我都可以在短時間內迅速構思、完成。作乘法時雖然碰上了 9 位相乘就會當掉的問題，不過也沒花上太多時間就解決了。到最後，最令我苦惱(或許是我頭腦不太靈光？)該怎麼實現的，就是除法了。


　　除法該怎麼實現呢？首先，我們應該要知道的是，因為是整數除法的關係，所以相除結果亦是整數，小數點的部份會無條件捨去。因此以下解釋 A / B 時，皆是 A ≧ B 的情況(若 A < B 則結果必為 0)。

　　我的作法是，先將 B 乘以 10^{n - m}。再使用迴圈，找出一個數字 i 符合 B * i ≦ A ＜ B * (i + 1)。此時的這個 i 就是商的第 n - m + 1 位數字。之後，我們再將 A 減去 B * i，並將 B 除以 10，並重複以上動作，即可得到商的第 n - m 位數字 。接著再重複一次以上的動作......。直到求出商的第 1 位數字為止。而這些運算所得的各位數字，就是我們需要求得的答案。

　　不太瞭？看看下圖：



　　熟悉吧！這個是長除法。我剛剛說明的拉裡拉扎一大串，其實就是長除法形式的實現。為了給大家一點思考時間(也給我一點偷懶空間)，在這裡我不解釋，請自行把我上面的文字，對照到實際的長除法上，你就會發現兩者間的共通性。假如有不懂的部份可以提出來。


　　以下是實現除法運算的程式虛擬碼：

void div(large A, large B)
{
    Index i, j;

    B = B * 10 ^ (A 的位數 - B 的位數 + 1);
    for (i = A 的位數 - B 的位數 + 1 to 1)
    {
        for (j = 1 to 10)
        {
            if (B * j > A)
            {
                A = A - B * (j - 1);
                break;
            }
        }

        C 的第 i 位 = j mod 10;

        B = B / 10;
    }

    print C;
}

※注意：以上虛擬碼的「^」符號代表的是「次方」的意思。

　　做一個小小的總結。費了幾天時間，把我自己實作大數運算的大致想法打出來。假如有哪裡不太好懂，我為我拙劣的文字表達致歉。並請把不懂的地方隨時提出來，好讓我知道有哪裡可以加以改進。

　　以上公佈的這些都只是我個人的實現法而已，並沒有什麼統一的寫法。或許我的方法有某些優點，或是某些缺失。重點是該如何學習別人的想法，並與自己的想法結合，寫出屬於自己的程式。你也可以有你自己的方法，提出你的意見，我們可以討論討論！

　　對於四則運算以外的內容，像是標準輸出、標準輸入、與邏輯運算等，我想暫時是不會把這些實現想法貼出來了。這部份就請各位自行去挖掘囉。

　　至於我自己寫出來的結果，已經張貼在這篇文章裡了，有興趣的人歡迎使用看看。

The End.