NOTICE

 任何跟文章無關的閒聊,請愛用 留言板(Guestbook)

 想要快速瀏覽主題,請點選單 目錄 標籤。

 停止更新ing,請見諒。 <(_ _)>


12月 05, 2008

【目錄】程式設計

@
程式設計相關一覽


概論

程式語言簡介 - Introduction of Programming Language
直譯與編譯 - Interpretation and Compilation
控制流程敘述 - Control Flow Statement
變數是什麼 - What is Variable?
函式是什麼 - What is Function?
陣列是什麼 - What is Array?
指標是什麼 - What is Pointer?


介紹

新書「程式之美」
程式語言的「熱門」排行榜


雜記

漫談程式設計
由 TOI 回顧我的過往
莫忘初衷


演講

The Yahoo! User Interface Library


轉貼

程式高手的八大奧秘
勤勉之人、輕量之人
程設師遇到 BUG 的回應
資工系KTV必點歌曲
遊戲程設之路
明星程設師的十大特質

【語言】指標是什麼 - What is Pointer?

@
  在前面的文章中,我們已經瞭解到變數是什麼。而在這裡,我們要特別把一種特殊的變數獨立出來解釋。這種特殊的變數,就是所謂的指標(pointer)

  首先,我們知道:每一個變數都具有一個唯一的記憶體位址,以及一個變數的值。而所謂的指標,就代表其變數值所儲存的,是某個變數的記憶體位址




  那麼,指標有什麼用處呢?

  或許你還記得,在先前我們曾經提到過的「陣列」。其實,陣列就是指標的一個實現。在使用陣列時,我們所使用的陣列名稱,實際上就是一個指標變數。

  而這個指標所指向的,就是這一群陣列元素的最前端。而陣列的索引值則代表的是指標的偏移,也就是指標所指位置後的第幾個元素。


  除此之外,指標也能夠在某些特定的資料結構(data structure)中,扮演控制存取資料元素,或是連結記憶體的角色。

  例如在我曾經提過的堆疊佇列、與連結串列中,指標都具有相當大的功用。


  儘管指標如此便利,但也因此帶來一些不必要的問題。例如:我們可能會因為不當的指標偏移,使得程式不正確的覆蓋掉記憶體所存的值。即使是程式經驗的老手,也可能會因為指標的誤用,導致難以發現的程式錯誤。

  也就因為如此,在某些程式語言(例如 Java)中,指標就被廢除、為其他方法所替代了。

11月 29, 2008

【解題】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
}

11月 27, 2008

【語言】陣列是什麼 - 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 所學校的學生成績呢?當然,你也可以建立出三維、四維等多維陣列,它們的想法都是差不多的。

11月 25, 2008

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

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


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

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

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

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

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) = 3x2 - 6x + 1,則利用函式可以這麼寫:

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

print f(5);

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

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


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

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

11月 20, 2008

【演講】The Yahoo! User Interface Library

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

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


  其實早在一段時間之前,我就曾經聽朋友提過 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