第一章 資料結構基礎
1-1 演算法
[演算法(algorithm)] 14 | 91,93,94(4),97,99(2),101,102,104,106
91關薦、93檢三、94公員晉高、94身三、94檢三(2)、97關三、99地三(2)、101地三、102地三、103高三、104地三、106關三
一、演算法特性：輸入+輸出+明確+有限+有效
(一)輸入(Input)：可以輸入或不輸入 (亂數產生)。
(二)輸出(Output)：需有結果產生。
(三)明確性(Definiteness)
每一行指令都必須明確，不可模稜兩可。例如成績優秀的學生才能領獎學金就不具有明確性，因為每個人對成績優秀的定義可能不相同，如果改為成績90分以上的學生才能領獎學金，則具有明確性，因為90分是比較客觀的定義。
註：y = x/0違反明確性。
參考資料：李春雄-計算機概論第六章演算法.ppt
(四)有限性(Finiteness)
不能有無窮迴路，必須能終止執行，就是必須在有限步驟內完成。
註：無窮迴圈 (infinite loop) 違反有限性。
(五)有效性(Effectiveness)或正確性(Correctness)：可以正確執行。
二、演算法工具
(一)工具：步驟條列、流程圖、虛擬碼 (pseudo code)、程式。
(二)舉例
以選擇排序法 (Selection Sort) 為例：
1.步驟條列：
step 1：輸入一組資料於輸入串列中，並設定輸出串列為空串列。
step 2：由輸入串列中選取出最小的一項資料，並將其自輸入串列中刪除。
step 3：將取得的加入輸出串列的尾端。
step 4：若輸入串列不是空的，則回到 step 2。
step 5：結束。
2.虛擬碼：
|
Function selectionSort(Type data[1..n]) Index i, j, max // 定義索引 For i←1 to n do min←i For j←i+1 to n do If data[j] < data[min] then min←j Exchange data[i] and data[min] End |
3.C語言的程式：
|
void Select_Sort(int data[ ], int n) { // data[ ] 是欲排序的資料，n 是陣列大小 int i, j, min, temp; for(i = 0; i < n-1; i++){ min = i; // 範圍內最左的鍵值索引 // 選擇出範圍內最小的鍵值，將它與範圍內最左的鍵值交換 for(j = i+1; j < n; j++) if(data[j] < data[min]) // 右鍵值小於左鍵值 min = j; // 最小鍵值索引為右鍵值索引 temp = data[min]; data[min] = data[i]; data[i] = temp; } } |
※參考資料：
1.http://program-lover.blogspot.tw/2008/08/selection-sort.html
2.http://freefeast.info/general-it-articles/selection-sort-pseudo-code-of-selection-sort-selection-sort-in-data-structure/
三、其他議題
(一)演算法與程式最大的不同
演算法具有「有限性」，程式不一定具有「有限性」。
(二)填魔術方陣的方法
以奇數最為簡單，第一個數字放在第一行第一列的正中央，然後向右 (左) 上填，如果右 (左) 上已有數字，則向下填，如下圖所示：
99年地特三等資料結構
|
五、考慮設計中式象棋 (如圖) 電腦程式系統：（每小題5分，共10分） (一)請設計一資料結構使能隨時表示出棋盤現狀 (current state)，包含所有棋子的位置、有那些棋子在棋盤上。 (二)寫出一演算法能產生「象」或「相」在任意位置之下一步可前往且合規則的所有位置 (next feasible positions)，注意，務必考慮其他棋子阻礙的因素。「象」或「相」的移動規則：(1)田字形的對角移動；(2)田字正中央有棋子時，不能移動前往。
|
答：
(一)
1.棋盤：
int board[10][9]; // 10*9 二維陣列棋盤，二維陣列的索引記錄目前棋盤上棋子的所在座標位置，二維陣列的值記錄目前棋盤是那顆棋子及是否沒棋子。
2.棋子代碼：
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|
將 |
士 |
士 |
象 |
象 |
車 |
車 |
馬 |
馬 |
包 |
包 |
卒 |
卒 |
卒 |
卒 |
卒 |
|
17 |
18 |
19 |
20 |
21 |
22 |
23 |
24 |
25 |
26 |
27 |
28 |
29 |
30 |
31 |
32 |
|
帥 |
仕 |
仕 |
相 |
相 |
俥 |
俥 |
傌 |
傌 |
炮 |
炮 |
兵 |
兵 |
兵 |
兵 |
兵 |
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
空 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
例如 board[0][0] = 6 (車)，座標位置 (0, 0)；board[0][1] = 8 (馬)，座標位置 (0, 1)；board[2][1] = 4 (砲)，座標位置 (2, 1)。
(二)
1.田字形的對角移動：
2.演算法：
|
void move(int i, int j, int direction) { // i, j 棋子座標，direction 移動方向 int temp = board[i][j]; // 舊棋子位置 if(board[i][j]==4 || board[i][j]==5 || board[i][j]==20 || board[i][j]==21) { // 如果是象或相 // 田字正中央有棋子時，不能移動前往 if(board[i-1][j+1] != NULL || board[i+1][j+1] != NULL || board[i+1][j+1] != NULL || board[i+1][j+1] != NULL) { exit(1); // 不能移動前往 } if(board[i-2][j-2] != NULL && direction = 0) { // 不是邊界，並且往左上角移動 board[ i-2][j-1] = temp; // 新棋子位置 board[i][j] = 0; // 舊棋子位置清空 } else if(board[i-2][j+2] != NULL && direction = 1) { // 不是邊界，並且往右上角移動 board[ i-2][j-1] = temp; board[i][j] = 0; } else if(board[i+2][j+2] != NULL && direction = 2) { // 不是邊界，並且往右下角移動 board[i+2][j+1] = temp; board[i][j] = 0; } else if(board[i+2][j-2] != NULL && direction = 3) { // 不是邊界，並且往左下角移動 board[ i+2][j-1] = temp; board[i][j] = 0; } } } |
101年地方特考三等資料結構
|
四、迴文 (palindrome) 乃是一個字串不論從左到右或從右到左看結果一模一樣，例如 “油麻地遍地麻油”、“人人為我、我為人人”、“Fall leaves as soon as leaves fall” 等。 (二)請寫出演算法以測試輸入的字串 (字串的長度不超過100個字) 是否為迴文。（10分） |
答：
(二)
|
CreateStack( ); while(input not end) { x←read next character; // 從左自右逐一讀取字元 push(x); } scan string again; while(input not end) { x←read next character; // 從左自右逐一讀取字元 y = pop( ); // 取出堆疊的字元 if(x≠y) { print “not palindrome”; exit; } } print “is palindrome”; |
102年地方特考三等資料結構
|
一、請參考圖1： (三)假設圖1代表 heap 上各個節點 (node) 及其相互指向的關係。p、q、r 三節點代表全域變數 (global variables)，其他的節點代表 heap 上的記憶體區塊。如果 p→a 的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾節點的方法及所需之資料結構。你的演算法只能從 a 節點出發，它必須指出所有的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演算法必須在每一個節點儲存那些資料？（15分）
|
答：
(三)
1.如果 p→a 的指標被消除，則 a, b, c, d, x 會變成圾垃節點，因為剩下2個全域變數指標 q→k 及 r→j 仍然可以拜訪其他節點。
2.尋找垃圾節點的演算法：
先將全部的節點都作記號;
For 每一個存在的節點 do 進行追蹤 // 從 q, r 二節點追蹤，p 無法追蹤
使用 DFS 或 BFS，將追蹤到的節點記號消除;
最後記號未消除的節點都是圾垃節點;
3.必須在每一個節點儲存布林值型態的旗標作記號，以便判斷是否為圾垃節點。
103年高考三級資料結構
|
五、若處理的資料，其數值均不同且已知均為1到100之間的整數或小數。若 K≦X＜K+1，集合 Lx 代表數值在 [K, K-1] 間全部資料，1≦K≦99, K 為整數，資料結構支援下列功能。 1.Insert(X)：增加 X，若 X 不存在 Lx 中。 2.Delete(X)：移除 X，若 X 存在 Lx 中。 3.List(X)：將 Lx 中的資料全部依序印出。 設計一資料結構滿足在最差情況的條件分析 (Worst Case Analysis)，每個功能的執行時間要求為：Insert(X) and Delete(X) 須在 O(log|Lx|) 時間內完成，List(X) 則須在 O(|Lx|) 時間內完成。請說明設計的資料結構為何？並解釋其執行時間為何滿足需求？（15分） |
答：
處理的資料為1到100之間的整數或小數。先判斷 K 位於那個範圍 (1≦K≦99)，然後建立99個首節點陣列存放 K 值，每個首節點陣列指向一個集合 Lx。此 Lx 為一棵 AVL-tree，存放帶有小數的正整數集合。
1.Insert(X)：
由首節點陣列找到 Lx 的 AVL-tree root，再將資料 X 插入樹中，時間複雜度為 O(log|Lx|)。
2.Detete(X)：
由首節點陣列找到 Lx 的 AVL-tree root，再將 X 由 AVL-tree 刪除，時間複雜度為 O(log|Lx|)。
3.List(X)：
由首節點陣列找到 Lx 的 AVL-tree root，再對 AVL-tree 進行中序走訪，時間複雜度為 O(|Lx|)。
104年地方特考三等資料結構
|
三、(一)請說明使用何種資料結構及其演算法，可有效判斷一運算式 (expression)中的巢狀 (nested) 括號是否正確配對 (matched)。（10分） (二)請以兩個運算式實例 {A*[B-(C+D)+8]-16} 及 {A+[B-(C+5])}，分別說明此演算法判斷的過程及結果。（10分） （注意：未說明判斷的過程，不予計分） |
答：
(一)
1.設計 A及 B 二個堆疊來存放運算子。左括號存放到堆疊 A，右括號存放到堆疊 B。
2.由左至右掃瞄運算式，遇到左括號放入堆疊 A。
3.由右至左掃瞄運算式，遇到右括號放入堆疊 B。
4.從堆疊 A 取出左括號，再從堆疊 B 取出右括號，如果括號能正確配對，則正確，反之錯誤。逐一配對直到堆疊 A、B 為空。
|
init. StackA, StackB is empty; while(scan expression left to right And not EOF) { x←read( ); if(x is 左括號) push StackA(x); } while(scan expression right to left And not EOF) { y←read( ); if(y is 右括號) push StackB(y); } } while(StackA And StackB not EOF) { x←pop(StackA); y←pop(StackB); if(x 與 y 是同一類型的左右括號) output “Match”; else { output “Not Match”; } } if(StackA and StackB empty) output “Match”; else output “Not Match”; |
(二)
1.{A*[B-(C+D)+8]-16}
把 {, [, ( 存放到堆疊 A。
|
( |
|
[ |
|
{ |
把 }, ], ) 存放到堆疊 B。
|
) |
|
] |
|
} |
取出堆疊 A 的左括號 (，與堆疊 B 的右括號 )，配對成功。
再取出堆疊 A 的左括號 [，與堆疊 B 的右括號 ]，配對成功。
再取出堆疊 A 的左括號 {，與堆疊 B 的右括號 }，配對成功。
堆疊 A、B 為空，配對成功。
2.{A+[B-(C+5])}
把 {, [, ( 存放到堆疊 A。
|
( |
|
[ |
|
{ |
把 }, ), ] 存放到堆疊 B。
|
] |
|
) |
|
} |
取出堆疊 A 的左括號 (，與堆疊 B 的右括號 )，配對失敗。不用繼續比對。
1-2 演算法的分類
一、貪婪法(Greedy Method)
[Greedy演算法] 2 | 102,106
102專三、106關三
(一)定義：貪錢
1.設定一個特定的選擇程序，稱為貪婪準則，以便在每一個步驟中做出目前最有利的選擇，即局部最佳解。
註：
每一步面臨選擇時，都做眼前最有利的選擇，不考慮對將來是否有不良的影響。
2.主要是採用按部就班地方式來產生最佳解。
3.在每個階段都產生一個看似最佳的選擇 (使用貪婪準則得到局部最佳解)。一旦做出選擇，就不可再更改，並希望這樣的選擇可以得到全域的最佳解。
4.在一般情況下，其結果大多是非常接近最佳解。
※參考資料：https://www.cyut.edu.tw/~ckhung/b/al/greedy.php
(二)步驟
從某一起點開始，不斷的改進該解答 (尋找周圍的更佳解，然後移到該更佳解上)，直到無法改進為止。
(三)特性
並不保證永遠可以得到最佳解，但是它仍是一個有效率的演算法，而且在很多時候也可以得到最佳解，或者得到跟最佳解相去不遠的解。
(四)實例
1.霍夫曼演算法：
(1)貪婪準則(Greedy Choice Property)：
確實存在「以最少見兩碼為兄弟」的最佳編碼。注意此處的邏輯，同一個問題可能可以有很多組不同的最佳編碼。只需要證明 Huffman Encoding 編出來的是其中之一即可。
(2)最佳化子結構(Optimal Substructure Property)：局部最佳解
從「小心挑選的小一號問題的最佳編碼」適當修改來的編碼，必為原問題的最佳編碼。
2.找零錢：
你去商店買東西，你掏出了一張一百元，買了一包 23 元的零食。售貨員須找零錢給你，但是你希望售貨員找給你的硬幣數目越少越好，如此口袋會輕一點。那麼售貨員會給你幾個硬幣呢？
(1)選擇程序(selection procedure)：
售貨員開始找尋收銀機中最大幣值的硬幣，且此時在他腦中用來選擇的準則是究竟哪一枚硬幣的幣值是目前最佳的選擇 (局部最佳解)。
(2)可行性檢查(feasibility check)：
售貨員必須判斷他剛剛選擇的那一枚硬幣的幣值加上「目前顧客方已經收到的幣值總數」是否超過「應找給顧客的最後總數」。
(3)解答檢查(solution check)：
售貨員必須檢查目前「已找給顧客方的零錢總數」是否等於「應找給顧客的最後總數」。如果兩者不相等，則售貨員必須繼續利用他的選擇硬幣機制拿出硬幣，並重複上述的過程直到「已找給顧客方的零錢總數」等於「應找給顧客的最後總數」或是收銀機裡的硬幣全部用盡為止。
註：答案的原則是先給你面額較高的硬幣。
※參考資料：
1.https://www.cyut.edu.tw/~ckhung/b/al/greedy.php
2.http://acm.nudt.edu.cn/~twcourse/Greedy.html
(五)適用時機
1.若遇最佳化問題，先思考可否用 Greedy Approach 解，若不行再考慮用 Dynamic Programming。
2.如果所要處理的最佳化問題無法找到一個選擇程序，則需要考慮所有的可能情況，就是屬於 Dynamic Programming。
※參考資料：
1.Sartaj Sahni-資料結構、演算法與應用使用C++ p.618~p.619
2.郭育倫-演算法導論-第12章貪婪演算法.ppt
3.(PTT)陳士杰-Course07_1 貪婪法則.ppt
4.http://ccckmit.wikidot.com/so:greedyalgorithm
106年關務三等資料結構
|
三、一個工廠有 n 台機器 M1, M2, …, Mn 及 k 份工作 J1, J2, …, Jk，每份工作都有其所需的執行時間 T(J1), T(J2), …,T(Jk)。每一台機器一次只能執行一份工作，每份工作只能交給一台機器執行，n 台機器可同時執行n 份不同的工作。 (一)請設計一個 Greedy (貪婪) 的演算法，來解決工作排程的問題，使得完成 k 份工作的時間最短。（15分） (二)此 Greedy 演算法適合使用何種資料結構來完成？（5分） (三)此 Greedy 演算法的解法是否能保證為最佳解？請舉例說明。（5分） |
答：
略
二、各個擊破法(Divide-and-Conquer)：切割征服
[切割征服(Divide and conquer)] 2 | 82,90
82地三、90地三
(一)定義
1.可以將大問題切割成較小的問題 (切割)，然後使用相同的解決程序加以處理 (征服)。
2.所有小問題的解可以成為大問題的最後解 (如階乘問題、費氏數)；若有必要，再將每個小問題的處理結果加以合併，就可以得到最後的答案 (如合併排序)。
3.由於使用相同的解決程序處理每個小問題，這一個程序就會被遞迴呼叫，因此一個遞迴演算法通常以一個副程式的型式出現，內部包含一個解決程序與遞迴呼叫。
(二)演算法
1.把大問題切割成兩個或多個更小的問題。
2.分別解決每個小問題。
3.把各小問題的解答組合起來，即可得到原問題的解答。
小問題通常與原問題相似，可以遞迴地使用分而治之策略來解決。
(三)特性：解決程序使用遞迴呼叫。
(四)優點：簡潔易懂。
(五)缺點：因為採用遞迴，效率較差。
(六)適用時機
1.問題本身具有遞迴關係：
大問題可被切割成較小的相同問題。例如階乘、費氏數、河內塔等問題。
2.資料結構屬於遞迴定義：
資料結構切割後仍然具相同性質。例如二元樹、鏈結串列等。
※參考資料：
1.(PTT)陳士杰-演算法課程-Course05 切割與征服.ppt
2.Sartaj Sahni-資料結構、演算法與應用使用C++ p.662
三、動態規劃(Dynamic Programming)
(一)定義
1.是一種表格式的演算法設計原則。若要解一個問題，需要解其子問題，再合併子問題的解以得出原問題的解。
2.一旦某個給定子問題的解已經算出，則將其記憶儲存，以便下次需要同一個子問題解時直接查表。
3.通常許多子問題非常相似，因此只需要解決每個子問題一次，從而減少計算量，
(二)實例
1.斐波那契數列(Fibonacci polynomial)：費氏數(Fibonacci Number)
|
n |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Fn |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
21 |
F8 = F(7)+F(6) = 13+8 = 21，F(7) = F(6)+F(5) = 8+5 = 13，計算 F8 和 F7 時，F(6) 會被用到2次，使用表格記錄已算過的部份，可以減少計算量。
2.最短路徑：
假設要尋找一條從來源節點 s 到目的節點 d 的最短路徑，如果在第一次決策時到達了某個節點 v，那麼不管 v 是如何決定的，之後選擇從 v 到 d 的最短路徑時，都必須採用最佳策略。
※參考資料：
1.http://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
2.(PTT)陳士杰-演算法課程-Course06 動態規劃.ppt
3.Sartaj Sahni-資料結構、演算法與應用使用C++ p.712
※Greedy Approach與Dynamic Programming的比較：
1.相同處：
對於具有限制的最佳化問題，可以採用貪婪法則或動態規劃來設計演算法則。
2.相異處：
|
Greedy Approach |
Dynamic Programming |
|
1.是一種階段性 (Stage) 的方法 2.具有一選擇程序 (Selection Procedure)，自某起始點 (值) 開始，在每一個階段逐一檢查每一個輸入是否適合加入答案中，重複經過多個階段後，即可順利獲得最佳解 3.較為簡單 (若遇最佳化問題，先思考可否用Greedy Approach 解，若不行再考慮用Dynamic Programming) 4.如果所要處理的最佳化問題無法找到一個選擇程序，則需要考慮所有的可能情況，就是屬於 Dynamic Programming |
1.先把所有的情況都看過一遍，才去挑出最佳的結果 2.考慮問題所有可能的情況，將最佳化問題的目標函數表示成一個遞迴關係式，結合 Table 的使用以找出最佳解 3.每採用一次貪婪準則便做出一個不可撤回的決策；而在動態程式規劃中，還要檢視每個最佳決策序列中是否包含一個最佳的子序列 |
※參考資料：
1.(PTT)陳士杰-演算法課程Course06 動態規劃.ppt
2.Sartaj Sahni-資料結構、演算法與應用使用C++ p.712
※子問題重覆(Overlapping Subproblem)：
可能會對相同子問題進行重覆計算，是 Divided-and-Conquer 主要的問題所在。
<圖10>pic10
※參考資料：
(PTT)陳士杰-演算法課程-Course06 動態規劃.ppt
※各個擊破法與動態規劃的比較：
1.相同處：都是將問題切割再採用遞迴方式處理子問題。
2.不同處：
|
|
各個擊破法 |
動態規劃 |
|
計算方式 |
可能會對相同子問題進行重覆計算 |
1.使用表格將子問題的計算結果加以儲存，在後面階段如果需要這個計算結果，再直接由表格中取出使用 2.可以避免許多重覆的計算，以提高效率 |
|
記憶體空間 |
不需要額外記憶體空間來儲存計算結果 |
需要額外記憶體空間來儲存計算結果 |
|
解題方式 |
Top-Down↓ |
Bottom-Up↑ |
|
適用 |
非重疊(non-overlap)子問題 |
重疊(overlap)子問題 |
※參考資料：(PTT)陳士杰-演算法課程Course06 動態規劃.ppt
四、回溯法(Backtracking)
(一)定義
1.是暴力搜尋法中的一種。採用嘗試錯誤的方式，嘗試逐步的去解決一個問題。
2.在逐步解決問題的過程中，通過嘗試發現現有的逐步答案不能得到有效的正確解答時，將取消上一步甚至是上幾步的計算，再通過其它的可能的逐步解答再次嘗試尋找問題的答案。
3.通常採用最簡單的遞迴方法來實現：
在反覆重複上述的步驟後可能出現兩種情況：
(1)找到一個可能存在的正確答案。
(2)在嘗試了所有可能的分步方法後宣告該問題沒有答案。
4.在最壞的情況下，會導致時間複雜度為指數時間。
(二)實例：八皇后問題、迷宮。
※參考資料：
http://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
五、分支設限(Branch and Bound)
(一)定義：把問題的可行解展開如樹的分枝，再經由各個分枝中尋找最佳解。
(二)實例：修剪過的狀態空間樹 (Pruned State Space Tree)。
※參考資料：
1.http://wiki.mbalib.com/zh-tw/%E5%88%86%E6%9E%9D%E7%95%8C%E9%99%90%E6%B3%95
2.http://episte.math.ntu.edu.tw/articles/mm/mm_11_3_02/page2.html
3.(PTT)陳士杰-演算法課程Course08 回溯、分枝與限制.ppt
※範例1：
|
如何由一陣列中找到最大與最小的值？ |
答：
[方法一]
[方法二]
1.每兩項資料為一組，每一組分別比較其大值與小值，然後大值分成一組，小值分成另一組 (分組需要 次)。
2.從大值的那一組資料找出最大值；從小值的那一組資料找出最小值。分別需要 次。
3.比較次數：。
※參考資料：98年王致強DVD-資料結構06.wmv
※範例：
103關三
|
寫一副程式對一個長度為10的整數陣列 A[0:9]，最多花費15次的數值比較運算，尋找陣列中的最小值及最大值。 |
答：
|
#include <iostream> using namespace std; #define INF 100; /* 測試用 */ void printData(int data[ ], int n) { for(int i = 0; i < n; i++) { cout << data[i] << ", "; } cout << endl; } void FindMinMax(int A[ ], int size, int &min, int &max) { int arr1[10] = {0}; int arr2[10] = {0}; int j = 0; int k = 0; /* 陣列相鄰值兩個為一組互相比較，分別找出最大值及最小值 */ for(int i = 0; i < size; i = i+2) { if(A[i] < A[i+1]) { min = A[i]; max = A[i+1]; } else { min = A[i+1]; max = A[i]; } arr1[j++] = min; arr2[k++] = max; } /* 上述陣列值大的分為一組，小的為另一組 */ min = arr1[0]; max = arr2[0]; /* 陣列值大的一組找出最大值，陣列值小的一組找出最小值 */ for(i = 1; i < size/2; i++) { if(arr1[i] < min) min = arr1[i]; if(arr2[i] > max) max = arr2[i]; } // printData(arr1, 10); // 測試用 // printData(arr2, 10); // 測試用 } int main(void) { int data[ ] = {5, 6, 12, -5, 7, 22, 4, 80, 3, 45}; int min; int max; printData(data, 10); FindMinMax(data, 10, min, max); cout << "min = " << min << ", max = " << max << endl; return 0; } |
執行結果：
5, 6, 12, -5, 7, 22, 4, 80, 3, 45,
min = -5, max = 80
※範例2：
|
將 n 個 boolean 所有可能的變數結果輸出。例如 n = 2，則有 true, false；false, true；true, true；false, false 四種可能。 |
答：
※範例3：
|
求出2到1000之間的所有質數。 |
答：
1.質數是一個數字，除了１和自己之外，沒有其他正因數。例如 2 (=1×2)、3、5、7、11 ...均為質數，而4、6、8不為質數 (因為有因數2)。
2.假設 i = 2~1000，a[i] = 1可能為質數；a[i] = 0為非質數。陣列初值設定 a[i] = 1。標示 2~i 的倍數 a[i] = 0。時間複雜度為 O(nlogn)。
|
for(i = 2; i <= 1000; i++) { // 陣列初值設定 a[i] = 1 a[i] = 1; } for(i = 2; i < = 1000; i++) { if(a[i] == 1) { printf(“%i”, a[i]); // 印出質數 for(k = i+i; k <= 1000; k += i) // 找出所有 i 的倍數，其倍數不是質數 a[k] = 0; // 當 i = 2 時，a[4] = 0, a[6] = 0, a[8] = 0, a[10] = 0, ... // 當 i = 3 時，a[6] = 0, a[9] = 0, a[12] = 0, a[15] = 0, ... // 當 i = 5 時，a[10] = 0, a[15] = 0, a[20] = 0, a[25] = 0, ... // ... } } |
※範例4：
|
計算 x 的 y 次方。 |
答：
[方法一]
|
int pow1(int x, int y) { int p = 1; for(int i = 1; i <= y; i++) { p = p*x; } return p; } |
[方法二]
p←1;
while y > 0 do begin
if y is odd then p = p*x; // y 是奇數 (odd)
x←x*x;
y←[y/2];
end;
|
int pow2(int x, int y) { int p = 1; while(y > 0) { if(y%2 == 1) { // y 是奇數 p = p*x; } x = x*x; y = y/2; } return p; } |
※參考資料：98王致強-資料結構06.wmv
留言列表
國考資訊處理解答 (7)
