Array Indexing

「索引」是電腦的絕技！一個元素存放到陣列之後，不論是在陣列的哪個地方，只要利用索引值（index），就能一瞬間找到元素。大多數的演算法都運用了「索引」的技巧，讓程式執行時間更短。

以下介紹索引的常見運用方式。

一、定位

將物件放入陣列中，array[位置] = 物件。

當元素很多時，我們可以放到陣列裡。我們只要記錄索引值，依舊可以常數時間得到元素。

範例：求最大值

將元素連續地放入陣列，若想記錄一元素，僅需一索引值。

void find_maximum() // 用變數直接記最大值 { int array[5] = {3, 6, 9, 8, 1}; int max = -10000; for (int i=0; i<5; i++) if (array[i] > max) max = array[i]; cout << "最大值為" << max; } void find_maximum() // 用索引值記錄最大值位置 { int array[5] = {3, 6, 9, 8, 1}; int p = 0; // 最大值的索引值 for (int i=1; i<5; i++) if (array[i] > array[p]) p = i; cout << "最大值為" << array[p]; }

範例：求子字串

將元素連續地放入陣列，若想記錄一區間，僅需頭尾的索引值。

void substring() { char s[14] = "Hello, world!"; char t[14]; int i, j; for (i=2, j=0; i<6; i++, j++) t[j] = s[i]; t[j] = '\0'; cout << "s的子字串[2,6)是" << t; }

範例：連續數字和

將元素連續地放入陣列，利用問題本身的數學性質以及索引值，快速得到答案。

void consecutive_sum() { int array[5] = {3, 6, 9, 8, 1}; int sum[5] = {0}; sum[0] = array[0]; for (int i=1; i<5; i++) sum[i] = sum[i-1] + array[i]; cout << "區間[2,4]的連續數字和是" << sum[4] - sum[2-1]; }

範例：求中位數

將元素依照大小順序並連續地放入陣列，利用索引值得到位於中間的元素。

void median() { int array[5] = {1, 3, 6, 8, 9}; // 由小到大排序 cout << "中位數是" << array[5/2]; }

範例：二元搜尋法（Binary Search）

將元素依照大小順序並連續地放入陣列，然後夾擠索引值。

如果元素放入串列，則沒有索引值，無法使用二元搜尋法。

int binary_search() { int array[5] = {1, 3, 6, 8, 9}; // 由小到大排序 int key = 3; // 搜尋陣列裡有沒有3 int left = 0, right = 4; // 索引值範圍 while (left <= right) { int mid = (left + right) / 2; if (array[mid] < key) left = mid + 1; else if (array[mid] > key) right = mid - 1; else if (array[mid] == key) return mid; } return -1; // 找不到 }

範例：二元樹（Binary Tree）

元素的索引值對應到樹的結構，是一種特殊的定位。

// 得到array[index]的左邊小孩的索引值 int left_child_index(int index) {return index * 2;} // 得到array[index]的右邊小孩的索引值 int right_child_index(int index) {return index * 2 + 1;} void binary_tree() { int array[5 + 1] = {0, 3, 6, 9, 8, 1}; // array[0]不使用 cout << "根為" << array[1]; cout << "根的左邊小孩是" << array[ left_child_index(1) ]; cout << "根的右邊小孩是" << array[ right_child_index(1) ]; }

範例：堆疊（stack）、佇列（queue）

元素連續地放入陣列，然後以改變索引值的方式，來動態增減堆疊及佇列的元素。

void stack() { int stack[10]; // 一個堆疊 int top = 0; // 索引值 stack[top++] = 3; // push stack[top++] = 6; // push if (top > 0) // is empty? int n = stack[--top]; // pop } void queue() { int stack[10]; // 一個佇列 int front = 0, rear = 0; // 索引值 queue[rear++] = 3; // push queue[rear++] = 6; // push if (front < rear) // is empty? int n = queue[front++]; // pop }

二、歸類並標記

物件直接作為陣列的索引值，array[物件] = 物件的屬性。

範例：正整數集合

物件：正整數。物件的屬性：是否在集合裡頭出現。

void add_element() { // 一個有限集合 bool set[100]; // 初始化為空集合 for (int i=0; i<100; i++) set[i] = false; // 設定集合元素 set[5] = true; // 集合裡有5 set[3] = true; // 集合裡有3 set[3] = false; // 集合裡沒有3 }

範例：統計英文字母出現次數

物件：英文字母。物件的屬性：英文字母的出現次數。

void count_letter() { char s[20] = "hi, I am a boy"; // 歸類並標記 // 26個字母，字母的ASCII值剛好連續。 int count[26 + 26] = {0}; for (int i=0; s[i] != '\0'; i++) if (s[i] >= 'a' && s[i] <= 'z') count[ s[i] - 'a' ]++; else if (s[i] >= 'A' && s[i] <= 'Z') count[ s[i] - 'A' ]++; // 印出英文字母的出現次數，不分大小寫。 for (int i=0; i<26; i++) if (count[i] > 0) cout << char('A' + i) << "的個數為" << count[i]; }

範例：計數排序法（Counting Sort）

索引值的大小順序，恰是元素的大小順序，亦可用於排序。

void counting_sort() { // 假設陣列裡數值不重複 int array[5] = {3, 6, 9, 8, 1}; // 歸類並標記 bool count[100] = {false}; for (int i=0; i<5; i++) count[ array[i] ] = true; // 索引值的大小順序，恰是元素的大小順序。 for (int i=0, j=0; i<100 && j<5; i++) if (count[i]) // 數值不重複 array[j++] = i; }

範例：雜湊表（Hash Table）

元素的索引值由特殊方法決定，是一種特殊的歸類。

int hash(int n, int range) // 根據元素的數值來製造一個index { return n * 97 % range; } void hash_table() { int array[5] = {3, 6, 9, 8, 1}; int table[100]; for (int i=0; i<5; i++) { // 替array[i]製造一個index int index = hash(array[i], 100); // 將array[i]放入hash table table[index] = array[i]; } }

三、轉換

array[物件] = 另一個物件。概念等同數學術語「函數」。

範例：取代（substitution）、移位（transposition）

密碼學的基礎概念。取代是文字的轉換，移位是位置的轉換。

void substitution() { char s[10] = "Hello!", t[10] = ""; // 建立轉換表格 char crypt[128]; for (int i=0; i<128; i++) crypt[i] = i; crypt['!'] = 'w'; crypt['H'] = 'Y'; // 開始轉換 int n; for (n=0; s[n] != '\0'; n++) t[n] = crypt[ s[n] ]; t[n] = '\0'; } void transposition() { char s[10] = "Hello!", t[10] = ""; // 建立轉換表格 int crypt[50]; for (int i=0; i<50; ++i) crypt[i] = i; crypt[2] = 3; crypt[3] = 5; crypt[5] = 2; // 開始轉換 int n; for (n=0; s[n] != '\0'; n++) t[n] = crypt[ s[n] ]; t[n] = '\0'; }

定址的時間複雜度

當索引值大小為N，有人認為定址的時間複雜度是O(log₂N)，也有人認為是O(1)。兩種說法都有依據。

數學的觀點：N總共有log₂N個位元，運用二元樹的觀念，依照各個位元的數值是0或是1進行分枝，分枝到底後就完成定址了。所以定址的時間複雜度是O(log₂N)。

電路的觀點：一顆中央處理器可以平行處理32位元（現在已有64位元），只要是介於0到2³²-1的索引值，都可以在1單位時間完成定址，而不必用32單位時間來完成定址。所以定址的時間複雜度是O(1)。

大家傾向假設定址的時間複雜度是O(1)。

定址的範圍

方才提到一顆中央處理器可以平行處理32位元，理論上可以定址到2³²以內的位址。一個位址一般擁有1byte的記憶體大小，所以可以運用的記憶體就有2³²byte = 4GB 這麼多。

但是作業系統會保留一些位址、預留一些記憶體空間以維持系統運作，所以使用者實際可以運用的記憶體其實不到4GB。

當記憶體沒有插到4GB的時候，作業系統利用一種叫做virtual memory的技術，以硬碟空間補足記憶體不足4GB的部份。

位址是連續不斷的，我們寫程式也都直接假設位址對應到的記憶體空間是連續不斷的，然而實際上並不是連續的。作業系統運用一種叫做paging的技術，藉由page table，讓記憶體看起來是連續的。

Recursion

在函式內部呼叫原本的函式，叫做「遞迴」。

遞迴與迴圈一樣，將一件事情重複很多次，每次都改變一點點。遞迴與迴圈一樣，必須設定起始條件、結束條件、改變量，以避免無窮遞迴。

範例：階乘

1乘以2乘以3……乘以n。

int factorial(int n) { int value = 1; // 起始條件、結束條件、改變量 for (int i = n; i >= 1; i--) value *= i; return value; } int factorial(int n) // 起始條件 { if (n == 1) return 1; // 結束條件 return n * factorial(n - 1); // 改變量 } int factorial(int n) { return n == 0 ? 1 : n * factorial(n - 1); }

範例：兔子數列

0 1 1 2 3 5 8……，求第n項。公式f(n) = f(n-1) + f(n-2)。

迴圈輔以堆疊才能樹狀分枝。遞迴可以輕易地樹狀分枝。

int fibonacci(int n) { int value = 0; stack<int> s; s.push(n); while (!s.empty()) { int n = s.top(); s.pop(); if (n == 0) value += 0; else if (n == 1) value += 1; else { s.push(n); s.push(n-1); } } return value; } int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; // 輕鬆建立兩個分枝 return fibonacci(n - 1) + fibonacci(n - 2); }

UVa 110 177 183 839

Array Indexing

數10個數字，一般而言，從1開始，到10結束。

數10格陣列，有些不同，從0開始，到9結束。

陣列索引值，從0開始。原因可能是指標。存取陣列首格，不需要將記憶體位址+1。

// 1數到n。n個數字。 const int n = 10; for (int i=1; i<=n; i++) cout << i << '\n'; // 陣列則是0數到n-1。n個格子。 int array[n] = {0, 8, 0, 0, 0, 9, 2, 0, 0, 0}; for (int i=0; i<=n-1; i++) cout << array[i] << '\n';

Loop

迴圈索引值，從0開始，到n-1結束。原因是陣列。

小技巧：為了減少計算步驟-1，於是<= n-1改成< n。

結束條件是等於，明確合理，「這裡就是終點」。

結束條件是小於，不夠直覺，「似乎還沒到終點」。

為了減少計算步驟-1，只好採用不夠直覺的方式。

// 從0開始，到n-1結束。n個格子。 for (int i=0; i<=n-1; i++) cout << array[i] << '\n'; // 小技巧，減少計算步驟-1。 for (int i=0; i<n; i++) cout << array[i] << '\n';

Interval

數字0到9：左閉右閉區間[0,9]，左閉右開區間[0,10)。

正統的做法是左閉右閉[0,9]。

為了使用迴圈小技巧，大家習慣採用左閉右開[0,10)。

// [0,n-1] for (int i=0; i<=n-1; i++) cout << array[i] << '\n'; // [0,n) for (int i=0; i<n; i++) cout << array[i] << '\n';

左閉右開的優點：iterator

有些資料結構，例如串列list，只能單向移動，不能雙向移動。只能+1，不能-1。這種情況只能採用左閉右開，避免-1。

例如C++標準函式庫，循序存取資料結構的功能iterator。當遇到單向移動的資料結構，只能++，不能--。導致iterator的成員begin和end，採用左閉右開。導致內建函式的參數，採用左閉右開。

// [0,n)改成[begin,end) // <= end-1改成< end改成!= end list<int> l = {0, 8, 0, 0, 0, 9, 2, 0, 0, 0}; for (auto it = l.begin(); it != l.end(); it++) cout << *it << '\n'

左閉右開的優點：減少計算步驟-1

許多經典演算法，可以使用左閉右開，減少計算步驟-1。

// 左閉右閉 int binary_search(int array[], int n, int key) { int left = 0, right = n-1; while (left <= right) { // 若是偶數個數字，mid偏左。 int mid = left + (right - left) / 2; if (array[mid] < key) left = mid + 1; else if (array[mid] > key) right = mid - 1; else if (array[mid] == key) return mid; } return -1; // 找不到 } // 左閉右開 int binary_search(int array[], int n, int key) { int left = 0, right = n; // 不必-1 while (left < right) // 變成這樣 { // 若是偶數個數字，mid偏右。 int mid = left + (right - left) / 2; if (array[mid] < key) left = mid + 1; else if (array[mid] > key) right = mid; // 不必-1 else if (array[mid] == key) return mid; } return -1; // 找不到 }

左閉右開的優點：計算區間大小不必-1

計算區間的數字數量，可以使用左閉右開，減少計算步驟-1。

// 左閉右閉 int size = right - left + 1; // 減掉了頭，+1回來。 // 左閉右開 int size = right - left; // 不必-1

左閉右開的優點：空區間不會遭遇負數

[0,0]是一個數字0，[0,-1]是沒有數字。

[0,1)是一個數字0，[0,0)是沒有數字。

例如unsigned int，採用左閉右開可以避免向下溢位。

左閉右開的缺點：最大區間不會涵蓋整數最大值

左閉右開也有缺點。

例如涵蓋unsigned int最大值，區間右值會向上溢位。此時只能使用左閉右閉。

例如C++標準函式庫，隨機整數生成器uniform_int_distribution採用左閉右閉，隨機浮點數生成器uniform_real_distribution採用左閉右開，規則無法統一。

Metaprogramming

設計一支程式來製造程式碼，令該程式碼充分運用程式語言自身擁有的能力，輕鬆地、更有效率地完成更多事情。

範例：四則運算式

5 + 8 × (2 - 3) + 7 × -6 / (2 - 1) + 1

身經百戰的演算法設計高手，必然不假思索說出：stack，把所有符號依序放入stack，依照運算符號的優先次序push和pop。聽來簡單，實作起來還是頗麻煩。

這裡要介紹的是更輕鬆、更強悍的方法：寫程式製造一支會進行四則運算的程式。大家都知道C/C++的語法當中，就有四則運算的語法了。現在來設計一支程式，製作出四則運算的程式碼吧！

void arithmetic() { // 輸入四則運算式 string s; cin >> s; // 製作程式碼 ofstream fout("temp.cpp"); fout << "#include <iostream>\n"; fout << "int main()\n"; fout << "{\n"; fout << " std::cout << (" << s << ") << endl;\n"; fout << " return 0;\n"; fout << "}\n"; fout.close(); }

如果輸入方才的四則運算式，就會產生如下程式碼，檔名為temp.cpp。

#include <iostream> int main() { std::cout << (5 + 8 * (2 - 3) + 7 * -6 / (2 - 1) + 1) << endl; return 0; }

然後編譯temp.cpp、執行一下，就有答案了。甚至可以把編譯、執行的指令，統統寫進程式碼當中：

void arithmetic() { // 輸入四則運算式 ...... // 製作程式碼 ...... // 編譯和執行（在Linux底下） system("g++ temp.cpp -o temp.out"); system("./temp.out"); // 刪除暫存檔案 system("rm temp.out"); system("rm temp.cpp"); }

範例：quine

一支程式，其功能是輸出本身程式碼。純娛樂。

#include <cstdio> char s[]="#include <cstdio>%cchar s[]=%c%s%c;%cint main(){printf(s,10,34,s,34,10,10);retrun 0;}%c"; int main(){printf(s,10,34,s,34,10,10);return 0;}

Template Metaprogramming

C有個功能叫macro，可以代換程式碼。C++有個更厲害的功能叫template，可以代換並且遞迴展開程式碼。

運用template，編譯時期即可計算答案，令答案變成程式碼的一部分；執行時期不必花時間計算，直接印出答案！

不過這是個怪招，平常沒人這樣做，大家當作娛樂看看就好。儘管在C++裡面是怪招，但是在Haskell裡面卻是基本功。

範例：階乘

// 正常的寫法 // factorial(0) 得到 1 // factorial(4) 得到 24 unsigned int factorial(unsigned int n) { return n == 0 ? 1 : n * factorial(n - 1); } // 奇葩的寫法 // factorial<0>::value 得到 1 // factorial<4>::value 得到 24 template <unsigned int n> struct factorial { static const unsigned int value = n * factorial<n - 1>::value; }; template <> struct factorial<0> { static const unsigned int value = 1; };