CH08

一、填充題

1. 從n個數中找出最大數，最少要用 次比較。

【解答】 n-1

2. 給定n個數，請將它們由小排到大，稱為 問題。

【解答】 排序

3. 排序法將數列切成兩部分：已排序數列及未排序數列，每次從未排序的數列中挑出最小的數，將它移到未排序數列的最前面。

【解答】 選擇

4. 排序法將數列切成兩部分：已排序數列及未排序數列，每次將未排序數列中的第一個數，插入到已排序數列中，使得插入後的已排序數列仍然維持由小排到大的性質。

【解答】 插入

5. 排序法將數列切成兩部分：已排序數列及未排序數列，每次從未排序數列中的最後一個數看起，如果它比前面的數小，則往前移，一直看到未排序數列的第一個數為止

【解答】 泡沫

二、問答題

1. 12個金幣，有一個假的，只知和其他標準金幣重量不同，請用天平秤三次，就把假的金幣找出來，並確認它比較重或比較輕。（每次稱有三種可能性：大於、等於及小於，可用一個樹狀圖來描繪各種可能性）

【詳解】

有兩種方式，第一種可先四個和四個秤；第二種可先三個和三個秤。兩種方式展開的樹狀圖都可在秤三次情況下，找出假金幣。

2. 給定數列23、12、58、85、72、98、13、37，請以課本介紹的兩個方法，找出其中的最大數及最小數，把你的做法記錄下來。

【詳解】

第一種方法逐一比較得最大數98；第二種方法兩兩比較，98會勝出。

3. 給定數列23、12、58、85、72、98、13、37，請以課本介紹的方法，找出其中的最大數及第二大數，把你的做法記錄下來。

【詳解】

第一種方法逐一比較得最大數98，再從剩下的23、12、58、85、72、13、37找出第二大數85；第二種方法兩兩比較得98最大，再從曾輸過98的85、72、37中找出第二大數85。

4. 給定一個數列，請設計一個可找出前三大數的演算法。

【詳解】

兩兩比較找出最大數，再從曾輸過最大數的那些數中找出第二大數，再從曾輸過最大數和第二大數的數中找出第三大數。

5. 給定數列23、12、58、85、72、98、13、37，請以「選擇排序法」將它由小排到大，記錄你的過程。

【詳解】

6. 給定數列23、12、58、85、72、98、13、37，請以「插入排序法」將它由小排到大，記錄你的過程。

【詳解】

7. 給定數列23、12、58、85、72、98、13、37，請以「泡沫排序法」將它由小排到大，記錄你的過程。

【詳解】

8. 給定數列23、12、58、85、72、98、13、37，請以「快速排序法」將它由小排到大，記錄你的過程。

【詳解】

9. 給定數列23、12、58、85、72、98、13、37，請以「合併排序法」(merge sort)將它由小排到大，記錄你的過程。（雖然本章沒介紹做法，但讀者可到圖書館找演算法相關書籍，以本章建立的基礎，應有辦法理解這個方法）

【詳解】

先以合併排序法排23、12、58、85，得12、23、58、85；再以合併排序法排72、98、13、37得13、37、72、98。再將12、23、58、85及13、37、72、98依序合併得12、13、23、37、58、72、85、98。

10. 給定數列12、13、23、37、58、72、85、98，請以「二元搜尋法」找看看85在不在這數列中，也找找看18在不在這數列中，記錄你的過程。

【詳解】

找看看85在不在這數列中？先比較85和37，因為85比較大，所以找後面部分；再比較85和72，85仍然比較大，再找後面部分；比較85和85時，回答85在這數列中。找找看18在不在這數列中？先比較18和37，因為18比較小，所以找前面部分；比較18和13，18比較大，所以比較後面的部分；此時只剩23和18比，並不相等，所以回答18不在這數列中。

11. 請解釋動態規劃技巧的解法三步驟。

【詳解】

動態規劃技巧有三個主要部份：遞迴關係（recurrence relation）用來定義最佳答案、列表式運算（tabular computation）用來找最佳答案的值及路徑迴溯（traceback）將最佳答案的組合列出。

12. 以LCS的方法，找PROFESSOR和CONFESSION這兩個序列的最長共同子序列。

【詳解】

OFESSO

13. 「旅行推銷員問題」和「小偷背包問題」這兩個問題，你有沒有想到好解法呢？

【詳解】

自由發揮。

14. 請計算1000n、100n log2n、10n2、n3及2n，在n = 1、100、10000及1000000時的值各為多少，把它們的大小關係列出來。

【詳解】

15. 已知128金幣中有一假金幣（假的較輕），請問用天平最少秤幾次可以得知那一個是假金幣？

【詳解】

如果每次都儘可能平分成三堆，一定至少有兩堆金幣個數相同，把那相同個數的兩堆拿來秤，如果有一堆比較輕，那一堆一定包含那個假金幣，否則金幣就在沒秤的那一堆，再把包含假金幣的那堆依同樣做法儘可能平分成三堆做下去，…。128金幣平均分成三堆，三堆個數分別為43、43、42，把那43個的兩堆拿來秤，如果一樣重，則假金幣在42個的那堆，否則比較輕的就包含假金幣，此時我們的問題大小已從128降到42或43，比剛剛分兩堆的策略只降到64有效多了，所以這樣總共要秤幾次呢？最糟情況是：128、43、15、5、2，共5次，也就是