[演算法] Floyd-Warshall 演算法

以下記錄我研究著名的 Floyd-Warshall 演算法自己整理的心得：

Floyd-Warshall Algorithm
1.   在All-Pairs Shortest Path的問題中，為了減低 DP 的時間複雜度，可使用Floyd-Warshall演算法。這種演算法，在edge weight為正或負時皆可實行。

2.   假如要從 i 節點走到 j 節點，且中間有可能經過 k 個中間節點(intermediate vertex)。那麼從 i 到 j 的最短路徑長度等於(設中間節點數目不等於0)：

min { (i 不經過第 k 個 intermediate vertex但有經過其他k-1個intermediate vertex 走到 j 的最短路徑) , (先到第 k 個intermdiate vertex 且經過其他 k-1個中間節點的最短路徑 + 由第 k 個點過 k-1 個 intermediate vertex 到達 j 的最短路徑) }

如圖所示：

整體而言就是決定是否要經過第 k 個點而已。如果經過第 k 個 intermediate vertex會讓總長度變小，那麼就選擇經過第 k 個點。如果 k = 0 當然最短路徑長就是 i 跟 j 之間的 weight。

3.   predecessor matrix 裡存的是到達 j 點時， j 點的前一個 vertex 是誰。這又分為兩種情況，如果最短路徑是不經過第 k 點的，那麼predecessor matrix要檢查的區間就是 i~j 之間(經過k-1個intermediate vertex)，反之有經過第 k 點，檢查區間為 k~j 之間(經過k-1個intermediate vertex)。

[演算法] Constraint graphs

以下整理Constraint Graph的觀念：
1.   Ax <= b，Constraint graph的vertices數目為x向量內元素個數+1。
2.   額外多出來的vertex為v0，目的為確保vertex之間都能互通。
3.   Constraint graph中的edge對應一組Constraint。
4.   weight的表示法：w(vi,vj) = bk，代表xj - xi = bk。(i、j、k為下標的index)。
5.   只要用找出v0到各vertex的shortest path的方法，且不能有負的edge weight，就可以找出每個vertex對應的xi的解。

[Vim] 複製、貼上、搜尋、復原

Vim的複製、貼上、搜尋是簡單的指令，也是常用的指令：
        選擇一段文字，可以在一般模式下鍵入大寫V，或者小寫v來選擇文字區塊。鍵入大寫V是游標經過一行就選擇一行，小寫v則是游標經過的位置就選擇起來。
        選擇好文字區塊後，按下小寫y可以複製起選擇的文字，按下d可以刪除掉選取的文字。
        在想要貼上文字的地方，按下p就可以貼上剛才複製好的文字。
        如果要復原剛才的動作，可以在一般模式下鍵入u。
        要搜尋字串，可以在一般模式下輸入"/"，並在斜線後方鍵入要搜尋的字串，並按下Enter。當找到一個符合的字串後，若要繼續往下搜尋，可以鍵入小寫n。

[嵌入式系統] Linux kernel內的資料Export到外部

在撰寫嵌入式系統的驅動程式(以linux為系統)時，我們有時候需要將kernel內的變數Export給我們自己撰寫的驅動程式，也就是我們可以在Linux的kernel內定義extern變數或函式，來給外部自己定義的module使用。
要將變數或函式Export給外部使用，必須做以下2個步驟：
1.   用EXPORT_SYMBOL()函式，將自己定義的Variable1匯出給外部使用。例如我們可以在 linux/kernel/net/netsyms.c內，將Variable1 Export出來：
//要先 #include <linux/module.h>
int Variable1 = 0;
EXPORT_SYMBOL(Variable1);
可以研究一下netsyms.c這個檔案，裡面會發現都是整理一系列的EXPORT_SYMBOL的動作。

2.   在kernel內的檔案內定義extern的變數，將剛剛Export出來的變數，直接拿來操作。
例如在for PCM7230的linux kernel內，可以在linux/kernel/net/core/dev.c內定義extern：
extern int Variable1;
接著就可以將Variable1拿來使用了。
在自己撰寫的驅動程式裡面，也可是一樣先在變數前寫上"extern"，就可以操作從kernel導出的變數。我們可以在驅動程式的程式碼內，修改從kernel Export出來的變數，也可以用create_proc_entry函式新增一個程序在linux的文件系統 /proc 裡面，並且將create_proc_entry函式回傳的指標，來將這個程序的參數，指定為在驅動程式的程式碼內自己定義的函式。

[Bug研究] Merge Sort的Bug

        我寫過很多次Merge Sort，有時寫完會有一些Bug。
以下是我這次用C++寫的一個有Bug的Merge Sort函式，這個錯誤一開始我並沒有很快找出：

---

   1: void MergeSort(int *A, int p, int r)

   2: {

   3:      int q = 0;

   4:      if(p<r)

   5:      {

   6:             q = ((p+r)/2);

   7:             MergeSort(A,p,q);

   8:             MergeSort(A,q+1,r);

   9:             Merge(A,p,q,r);

  10:      }

  11: }

  12: void Merge(int *A, int p, int q, int r)

  13: {

  14:      int n1 = q-p+1;   //number of elements of left array. Include q.

  15:      int n2 = r-q;     //number of elements of right array.

  16:      int L[n1+1];

  17:      int R[n2+1];

  18:      

  19:      for(int i=0;i<n1;i++)

  20:      {

  21:              L[i] = A[p+i];

  22:      }

  23:      for(int j=0;j<n2;j++)

  24:      {

  25:              R[j] = A[q+j];

  26:      }

  27:      L[n1] = infinite;

  28:      R[n2] = infinite;

  29:      int i = 0;  int j = 0;

  30:      

  31:      for(int k=p;k<=r;k++)

  32:      {

  33:              if(L[i]<=R[j])

  34:              {

  35:                  A[k] = L[i];

  36:                  i++;

  37:              }

  38:              else

  39:              {

  40:                  A[k] = R[j];

  41:                  j++;

  42:              }

  43:      }

  44: }

---

這個程式執行結果會是錯的，原因是第25行：

  25:              R[j] = A[q+j];

在複製陣列內容到R array時，應該要寫：

  25:              R[j] = A[q+j+1];

因為L陣列裡面已經包含index為 q 的element了。只要更改這一行，就是一個完整的Merge Sort的code了。

我將這種bug歸類為"陣列index的錯誤問題"。這種bug通常簡單，但簡單的錯誤難免發生。為了避免類似的錯誤，我之後將會使用特定格式的註解(先將此註解法則命名為Uncle註解法好了...)，來表示出陣列操作時的操作範圍，例如
，以此Merge Sort為例：
   
      R[j] = A[q+j+1];       // A[] : q+1<->q+n2 // j : 0<->n2-1 // total # : n2

上面這一行的註解中 A[] : q+1<->q+n2代表陣列A的索引值在for迴圈中從q+1一直trace到q+n2範圍，每一部分的註解描述用雙斜線 "//" 分開，j : 0<->n2-1代表j從0一直到n2-1，最後 total # : n2代表整體迴圈操作次數有n2+1次操作。

一直以來我都想定義一個共同的註解規範，能夠註解的格式統一，方便debug，我希望從現在開始實現這個願望，目前註解法的格式還在制定中。

[演算法] Loop Invariants

        Loop Invariant 是證明某個不變的條件(稱為Invariant Condition)，這個條件在程式進入迴圈前跟進入迴圈後，此條件仍不變。

通常以while迴圈為例子。
假如有一個while迴圈如下：

while( A )
{
        //Body..
}

        那麼假設一個 Invariant 條件叫做 X ，這個X條件在while檢查A條件時都維持原狀，一進入Body 時可能改變X條件，但一執行完 Body 後 X 又恢復原貌，這種條件就是一個典型的 Invariant Condition。

• 證明Loop Invariant需要三個步驟：
  1.   Initialization：描述 Invariant Condition 在迴圈執行第一個 iteration前，就成立。
  2.   Maintenance：描述 Invariant Condition 在迴圈的任一iteration執行前跟執行後都維持成立。
  3.   Termination：迴圈執行結束後，Invariant Condition 能夠展示整體演算法的正確性。

[演算法] 以UVA第10107程式題目複習Insertion Sort

首先複習一下 Insertion Sort。

Insertion Sort       
Insertion Sort的精神是當在排序一個數字陣列時，每當處理一個數字，就代表在這個數字之前的數都已經排序好了。因此只需要將這個數字跟前面排好的數字序列比較，並將目前處理的這個數字insert到之前排序好的序列中，就像一般在玩撲克牌時通常會使用的排序法。

        以下是我練習將InsertionSort的Code用C++寫出：
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
UVA #10107(What is the median)
這個題目給的Sample Input跟Sample Output如下：

Sample Input

1
3
4
60
70
50
2

Sample Output

1
2
3
3
4
27
4

        本題的目標為每從Sample Input讀進一個數字到序列中，就找出當下的中位數(median)，如果總共有奇數個數字，則將取排序好的數列的中間兩個數字相加除以2，除以2後只取整數部分。

思考方式：
        使用Insertion Sort的原因，是因為這題是每讀到一個數字就做排序，所以當讀進一個新數字時，之前的讀過的數字都已經排序好了，所以只須將新讀入的數字Insert到前面排序好的序列的適當位置，這很符合Insertion Sort的基本概念。

以下是我解決此題目的Code：(implement using C++)

//main.cpp
//The excution result is correct, and is accepted by UVA Online Judge.
//This is the code for UVA Online Judge #10107
//This code was created by Uncle on 2012/03/03
#include<iostream>
#include<sstream>
#include<fstream>
using namespace std;
int *data = NULL;
int size = 0;

int *Expand(int *arrReceive,int &s,int key)
{
    int *newArr = new int [s+1];
    for(int i=0;i<s;i++)
    {
        newArr[i] = arrReceive[i];
    }
    newArr[s] = key;
    delete []arrReceive;
    s++;
    return newArr;
}
void InsertionSort()
{
     int key = 0;
     for(int j=1;j<size;j++)
     {
             key = data[j];
             int i = j-1;
             while(i>=0 && data[i]>key)
             {
                        data[i+1] = data[i];
                        i--;
             }
             data[i+1] = key;
     }
}
int main()
{
    int key;
    ifstream inputFile;
    //inputFile.open("input.txt",ifstream::in);
    while(cin >> key)
    {
                    data = Expand(data,size,key);
                    InsertionSort();
                    if(size%2)  //total size is odd
                    {
                              cout << data[size/2] << endl;
                    }
                    else
                    {
                        int tmp = data[(size/2)-1] + data[size/2];
                        tmp = tmp/2;
                        cout << tmp << endl;
                    }
    }
    //getchar();
    return 0;
}

---

[C++] 各種文字檔的讀取方法整理

我將各種文字檔的讀取方式做整理，有想到其他的再補上來。
我寫過的作業裡，測試資料分為：
1.  文字檔案裡面第一行代表資料個數，第二行是資料的內容，例如假設要做資料排序：

5    6 7 1 3 5    3    11 7 3

    第一行的5代表下一行將會有五個數字，然後第二行給予5個數字請程式來排序。接著第三行的3代表有三個數字，並在第四行給予這三個數字的值給程式來排序。
    我讀取這樣的文字檔通常直接使用ifstream直接將資料推入int型態的變數：

int size = 0;     int *data = NULL;     ifstream inputFile(“input.txt”);     while(inputFile >> size)     {         data = new int[size];          for(int i=0;i<size;i++)         {             inputFile >> data[i];         }         //在這裡對data陣列做想要的operation.         delete[] data;         data = 0;     }

這是屬於同一系列的資料被分為許多行的情況。
2.   文字檔中同一系列的資料在同一行，例如：

2 3 9 5 11 3 6             5 4 0 7 2             ．．．

同一系列的資料在同一行，我會立刻用getline：

void readData() {      ifstream inputFile;      inputFile.open("input.txt",ifstream::in);      string line;      int lineNumber = 0;      data = new int[size];           while(getline(inputFile,line))      {          lineNumber++;          istringstream token(line);          int key;          while(token >> key)          {                      //在這裡對token做處理。          }      } } //ok

3.    遇到文字檔案內的資料不是以空白區隔，而是以其他符號區隔（例如逗號），此時可以使用我之前文章所寫的方法，使用getline：

string str = "19 82 37 55 167";       stringstream stream1(str);       string token;       while(1)       {           getline(stream1, token, ' ');   //指定用空白隔開，                                                         //可指定其他分隔字元           if (stream1.fail())           break;           istringstream forInt(token);                            int tmp = 0;           forInt >> tmp;           cout << tmp << endl;       }

4.     stringstream、istringstream、ostringstream使用上的差別：
假設建立一個 istringstream變數 iss，則可以把一個string字串塞給stream1，然後這個 iss 就可以把那個字串裡的東西再轉換給其他型態的變數，例如int或者float等等，像上面第３點的範例就是一個字串轉換成整數的例子。
　　要將字串str塞給 iss，方法有：
　　　　istringstream iss(str);
        或者
　　　　istringstream iss;
                iss.str(str);
簡單說就是字串--->送給istringstream--->送給其他型態的小變數。
　　同理，若有一個ostringstream型態的變數叫做oss，則可以將字串或者int等型態變數一直塞給oss，然後再一次將oss裡的東西設給一個新的字串。例如：
                string str = “test”;
　　　　ostringstream oss;
                oss << 2 << str;
                str = oss.str();
亦即各種型態的小變數--->送給ostringstream--->結合起來設給一個string。而stringstream則是兼具istringstream跟ostringstream的輸入及輸出功能。
另外stringstream、istringstream、ostringstream都具有clear()函式，可以清除error的狀態，也可以清空整個stream內部存的資料。

[演算法] Stupid Sort

    新的學期開學了，這學期修了高等演算法的課程，將之前學過的演算法整理複習一遍，並學更多演算法的應用。
Stupid Sort   
Stupid Sort的排序過程，雖然可視為比人類自己排序還慢，然而這種演算法的好處，是當電腦執行到一半因為某種緣故中斷執行程序後，下次要啟動排序流程時，可以直接從上一次排序到一半的那個狀態繼續執行下去，而不需要再輸入每筆資料重頭開始排序，因此在實際應用上，這種Stupid演算法有它的好處。
Stupid Sort程式碼很短，我將Stupid Sort用C++寫出來，函式如下：
void StupidSort()
{
    int i = 0;
    while(i<(size-1))
    {
           if(data[i] > data[i+1])
          {
                 int tmp = data[i];
                data[i] = data[i+1];
                data[i+1] = tmp;
                i = 0;
          }
          else
         {
               i++;
         }
     }
}
這就是我這學期寫的第一個程式，希望這學期能學到很多東西。

[演算法] LZ77壓縮技術研究與心得

以下簡單記錄我對LZ77資料壓縮技術的理解。

---

簡介
LZ77壓縮技術，是一種運用Dictionary Method的無失真壓縮技術，其基本的精神為記錄”重複性多的資料位置座標”來減低檔案大小。解壓縮過程為先讀入檔案Stream資料並記錄其位置，之後從檔案一直讀進Stream並與之前已經讀入的資料作比對，遇到之前的有重複的資料片段，就記錄下之前那筆資料與目前所處理的重複資料片段之間的相對位移量(offset)。如此解壓縮時就可以根據相對位移去從以前的已經讀過的資料去取出重複的資料，因此可壓縮檔案大小。
Sliding Window
LZ77使用Sliding Window的觀念。Sliding Window可以用一個Queue實現，如下圖所示，將一個Window分隔為兩部分，左邊部分是已經處理完的資料，稱為search buffer，右邊是仍待處理的資料串，稱為look-ahead buffer。資料從右邊一個個讀入，從左邊滑出。好像用一個Window鏡片由左到右滑過一份文件一樣：

Sliding Window示意圖

Token資料結構
LZ77建立一種token的資料結構，來維護檔案中的每筆資料。以上圖的Sliding Window為例，在look-ahead buffer裡目前處理到’A’這個字元，壓縮演算法會從左邊的search buffer裡搜尋有 'A' 這個字元所在位置，並且與look-ahead buffer中的 'A' 開頭以下接續的字元比對，盡可能找出與look-ahead buffer裡相同最長字串，也就是 "ABC" 。而token即儲存這個 "ABC" 字串位置的資料結構。
Token裡儲存著三筆資訊，分別為：位移(offset)、比對出的最大相同字串長度，以及緊接在這個相同字串後的字元。
從search buffer最右邊往左搜尋，一直往左找到 "ABC" 是最長的相同字串，而這個 "ABC" 中的A是search buffer從右數過來第8個字元，所以offset就是8， "ABC" 長度是3，於是token資料裡就儲存著：(8, 3, '_' )的訊息。接著，就將look-ahead buffer裡的 "ABC_" 四個字元往左shift到search buffer內。下一次就從 'U' 這個字元開始繼續往下處理。
因此由token內所維護的前兩筆資料( '8' 跟 '3' )，在解壓縮這個token時，就先將offset往左第八個字元( 'A' )輸出到output stream，並將那個字元以下的3個字元都輸出，且由token儲存的第三個資訊得知最後要output的字元是 '_' 。
並且LZ77壓縮演算法從search buffer中比對字元時，可以往右比對到look-ahead buffer裡的字元，最長可以比對到look-ahead buffer長度減一的位置。由上圖為例，search buffer可以往右比對到look-ahead buffer中從右數過來第一個 '0' 的位置(包括 '0' )。
因此在重複性高的文件裡，可大大壓縮資料量。然而此演算法在比對重複字串時，只能在Window範圍內比對，故控制Window範圍勢必會影響整個壓縮的效率。
心得
今年我暑假偶而會閱讀一些有趣的演算法。目前對於資料壓縮的演算法只對Huffman Code比較熟悉。據我所知ZIP壓縮技術是由Huffman Code跟LZ77一起結合改良出的演算法，希望透過學習不久就可實作出一些解壓縮的程式來玩玩。

[研究] 一個文件壓縮軟體Beta

      這是我寫的一個作業。
      我寫了一個可以壓縮文件的軟體，只支援 Ascii 碼文件。目前測試沒有Bug(只要文件內容都是嚴謹的ASCII碼的話)。
本程式功能：將ASCII文件壓縮為一個壓縮檔，檔案夠大時，文件大小可以壓縮約為原檔案的60%。
本程式執行環境為unix-liked系統。

本程式在freebsd下跑完全正常，但在windows系統下，解壓縮回來偶爾會有幾個字有顯示的問題。
使用方法：
輸入 compress [fileName]：可以將當前資料夾內的 [fileName] 檔案壓縮名為output.ufp的檔案，並存放在當前目錄下。

輸入 decompress可以將當前目錄下名為output.ufp檔解壓回原文件，並命名為decompress.txt，並存放在當前目錄下。
輸入 /help：可以查看指令。
之前的下載位置的檔案有問題，現在更新了：
免費檔案下載位置：http://www.sendspace.com/file/m9oqrc

[C++] 動態陣列擴充時，容易犯錯的指標傳遞

        在動態擴充陣列大小時，如果透過很多函式來傳遞，要注意指標的問題。
        舉例來說，寫一個函式Expand用來擴充陣列，需傳給此函式一個指標代表陣列，然而如果宣告參數時只寫一個星號，則Expand內部會自動產生一個新的指標(假設叫做A)並將傳遞進來的指標(假設叫做B)內所存的位址複製一份在新的指標變數A內。
        在這種情況下要注意，如果在Expand內將A指標指向一個新的位址，那麼就指標B並沒有指向新的位址，這是容易讓程式當掉的地方。
        因此Expand可以在宣告參數時，給予參數兩個星號，如此傳遞進來的，就是B指標的位址，因此只要更改此位址指向的那個位置，就可以把原來傳遞進來的陣列更改。
用言語表達此觀念似乎不太清楚，用實例來表達如下：
以下是我打的一個範例程式碼：
//////////////////////////////////////////////////////
#include<iostream>
using namespace std;
void Expand1(int **arrReceive,int &size,int key)
{
    int *old = *arrReceive;
    *arrReceive = new int [size+1];
    for(int i=0;i<size;i++)
    {
        (*arrReceive)[i] = old[i];
    }
    (*arrReceive)[size] = key;
    size++;
    delete []old;
}
int *Expand2(int *arrReceive,int &size,int key)
{
    int *newArr = new int [size+1];
    for(int i=0;i<size;i++)
    {
        newArr[i] = arrReceive[i];
    }
    newArr[size] = key;
    delete []arrReceive;
    size++;
    return newArr;
}
void changeArr(int **arrReceive,int &size)
{
    Expand1(&(*arrReceive),size,123);
    (*arrReceive) = Expand2(*arrReceive,size,456);
}
int main()
{
    int size = 3;
    int *a = new int [size];  //不能寫int a[] = {1,2,3}; 會有問題。
    cout << "original array:" << endl;
    for(int i=0;i<size;i++)
    {
        a[i] = i;
        cout << " " << a[i];
    }
    cout << endl;
    changeArr(&a,size);
    cout << "after change:" << endl;
    for(int i=0;i<size;i++)
    {
        cout << " " << a[i];
    }
    cout << endl;
}
//////////////////////////////////////////////////////////
執行結果>>
original array:
0 1 2
after change:
0 1 2 123 456

---

Expand1跟Expand2的都可以安全的擴充陣列。
1.   Expand1是：將指向原陣列第一個元素的指標，這個指標有一個位址，把這個位址丟給Expand1來接，Expand1會產生一個新的指標並把這個位址指向的位址做更改。因此元陣列整個都被更改了。
2.   Expand2是直接在Expand2函式內產生一個新的陣列指標，並把舊的陣列指標指向的地方delete，回傳新的指標給原指標接收，也可以擴充陣列。

[演算法] heap sort

以下的心得，以Max-heap為例：
1.   max heap的特性：
      一個node的parent的索引值是這個node的索引值除以2之後取floor。一個node的左邊child是這個node索引值乘以2，右邊的child的索引值是當前node索引值乘以2之後再加上1。
     因此可以定義macro：
     #define Parent(i) i/2
     #define Left(i) 2*i
     #define Right(i) (2*i)+1
2.   以下方法，可以很快地寫出一個heap sort：
      首先迅速建立heap，要維持一個heap，只須有2個部分：
      第一部份，要有一個函式可以調整任意一個node往下樹的下方移動，使整個樹維持max heap的特性。做到這一點只要比較這個node跟其兩個child三者之中誰最大，將要調整的node與其child中最大的數值調換。如此將node往下調整移動後，再將剛剛調換過的child那個位置，傳入自己這個函式，遞迴呼叫自己，繼續從那個位置往下調整。
      第二部分，要建立一個heap，需要定義這個heap的大小，整個heap中有幾個node一定要知道。將整個陣列視為heap時：

   
這樣子的排法， heap圖內的索引值，注意是從1開始算，在這種情況下，最大的索引值就是整個陣列的size。在建立heap時，要從索引值為 (size/2) 的那個node，開始往索引值小的node去將每個node檢查並往下調整，使整個tree有max-heap之特性。索引值大於size/2的那些node，通通都是樹葉(leaf)，樹葉不用調整。
由以上的觀念可以迅速建立heap。
3.   用heap來排序，就是heap sort。非常容易，只是將root取出，然後把最後一個node(最後一片樹葉)，摘下來貼到root的位置，然後從root往下調整，使整個heap維持max-heap的特性。注意此時要更新size的大小，將整個heap的size減1。

[C++] token

將string類別切成token的方式我學到的有兩種：
1.    while( getline(inputFile,line))
       {
           istringstream token(line);
           string word;
           while(token >> word)
           {
               //……
           }
       }
       //此為使用istringstream。
2.   使用stringstream：
      string str = "0 1 2 3 4 5";
      stringstream ss(str);
      string token;
      while(1)
      {
          getline(ss, token, ' ');   //指定用空白隔開，亦可指定其他分隔字元
          if (ss.fail())
          break;

          istringstream convert(token);
                 //用istringstream可以將字串轉成整數或其他型態數字
                 //用stringstream也可用同樣方法將string轉成int。
          int tmp = 0;
          convert >> tmp;
          cout << tmp << endl;
      }
      執行結果：
      0
      1
      2
      3
      4
      5

[演算法] MergeSort跟QuickSort的程式架構

1.   Merge Sort的精神就是把陣列切割。所以演算法如下：
      以下的start、mid、end都是陣列的索引值。
      void merge(int *data, int start, int mid, int end)
      {
            這個函式做合併的動作。
      }
      void mergeSort(int *data, int start, int end)
      {
            如果start == end，就return;
            //這個函式做切割的動作。
            (i)   先切成：mid = (start+end)/2，這代表一個陣列切成start到mid跟mid到end。
            (ii)  把start到mid的部分遞迴給自己切。mid+1到end遞迴給自己切。
            (iii) 把start到end部分陣列送給merge合併。
       }
2.   Quick Sort：
     
把以上這個圖所做的動作寫在一個函式裡(假設此函式叫做A)，在這個函式的最後回傳個索引值：i+1。
這樣就可以在QuickSort函式內利用遞迴，以下是QuickSort函式類內容架構：
   Quick Sort終止條件：if( indexLeft >= indexRight) return;
   int cut = A(data, indexLeft, indexRight);
   QuickSort(data, indexLeft, cut-1);
   QuickSort(data, cut+1, indexRight);

[C++] 讀取文字檔

不同文字檔案格式有不同的讀檔寫法。在此我整理我常用的讀檔方式，遇到不同的文字檔案格式，可以快速地使用以下不同的方法取得文字檔內的資料。
    (1) include<fstream>
         include<sstream>
         以上這兩個標頭檔先include起來。
    (2) 以下是我常用的標準讀取文字檔案的寫法：
          readData()
          {
               ifstream inputFile;
               inputFile.open(“input.txt”,ifstream::in);  //允許input operation。
               string line;
               int lineNumber = 0;
                                                            // 從inputFile，get一段文字到line。
                                                            // 將string命名為line有好處，讓使用
                                                            // getline時不會用錯。
               while(getline(inputFile,line)
               {
                     lineNumber++;
                     cout << lineNumber << “ “;
                     istringstream token(line);
                     string word;
                     while(token >> word)
                     {
                           cout << word << " ";
                     }
                     cout << endl;
               }
          }
         
          這個函式可以切token，並在每一行之前加上行號。
    (3)  getline(cin,line); //會讀入一整行，包括空白，遇到 '\n' 停止讀取。
           cin >> line;        //停止讀取於空白鍵。
           getline(cin,line,’?');   //代表讀到 '?' 就停止讀取。
           getline不會讀到 '\n'。
    (4)   string str = “12345”;
           int len = str.length();     //回傳幾個字。len = 5;
           string tmp = str.substr(0,2);  //從第0個位置取兩個字符。即 "12"。
    (5)  檔案開啟：
           ifstream inputFile;
           inputFile.open(“input.txt”);   //如此檔案內容不會被洗掉
           int oneNumber,anotherNumber;
           inputFile >> oneNumber >> anotherNumber;
           //從檔案讀兩個數設給oneNumber跟anotherNumber。
    (6)  ofstream開檔，如果沒有設ios::app，則檔案內容會被洗掉。

[Matlab] 匿名函數筆記

1.   匿名函數最簡單的使用方法，就是像數學表示函數一樣，將函數的因變數跟自變數表示出來：
   f = @(x,y) 2*x+6*y ;
   f([2 4], [3 6])
   執行結果：
   ans =
          22     44
2.   f = {@(x) x+3, @(y) y+1}
      %如此可以將f視為一個函數陣列。
      f{1}(2)   %第一個column的x代2，所以ans為5。
      f{2}(10) %第二個column的y代10，得到ans為11。
3.  以下是我寫的一個算函數下方面積的例子：
     clc,clear all
     f = @(x) 2*x;
    x = [0:0.01:2];
    fplot(f,[0 2]);

    ts = (2/(length(x)-1));
    tmp = 0;
    for i=1:length(x)-1,
           tmp = tmp + (f(x(i)))*ts;
    end;
    tmp

    執行結果>>tmp = 3.9800
    (執行環境：Octave)

[通訊] BPSK錯誤率筆記

---

BPSK通訊系統的錯誤率分析：

根據下圖：

現在若我們要計算錯誤率，那麼，很簡單，只要計算：傳送端送訊號為0結果接收端收成1。

因為這個錯誤率跟傳送端送1而接收端收成0的機率一樣。

所以根據上圖，可以看出，要計算傳送端送0然後收錯收成1的機率，勢必要先積分一個pdf。這個pdf就是高斯雜訊，將高斯雜訊從0往+1的方向一直積到無限大：(往 ”傳送訊號理當落在的位置”的反方向積分過去)

在這裡要注意，所謂傳送0在BPSK是指送，送1是指送。所以，如果要用coherent receiver來接收，其整個接收端架構的意義為先對基底向量做內積，求得基底方向的分量，再用一個判斷正負的設備來判斷此分量是大於0還是小於0。

[通訊] M-ary QAM

每個點的基底向量分量為sqrt(E0)的整數倍，因此可看出基底向量被離散的振幅所調變，因此為quadrature amplitude modulation。

我們可以從圖發覺，這些點有分成振幅比較大的，跟振福比較小的。

像中間紅色的部分，對Gaussian的pdf取積分，可以得到這部分的正確率是：

而信號落在橘色的邊緣，正確率在積分的時候就必須一個高斯從-sqrt(E0)積到sqrt(E0)，另一個從-sqrt(E0)積到無限大。這樣造成正確率為：

同理也可以積分算出藍色區域的正確率：

另外，我常常忘記一個很簡單的公式，在此記錄一下：

[Java] I/O：FileReader簡單用法

使用Java的IO都要import java.io.*;
FileReader可以包成BufferedReader，方便readLine()函式讀入一行。
例如：

   String fileName = “in.txt”;   //要被讀取的檔名。
   BufferedReader input = new BufferedReader(new FileReader(fileName));
   String tmp;
   while((tmp = input.readLine()) != null)
        System.out.println(tmp);
   //…
   input.close();