開始用Word 2007發布日志
發現書上很多加了星號的題目我都得看Instructor's Manual才會做? =_=
Problem: Show how to solve the fractional knapsack problem in O(n) time. Assume that you have a solution to Problem 9-2.
Problem 9-2就是在最差情況下也能在O(n)時間內求出第k大元素的算法。
解答：
使用線性算法找出Vi / Wi的中位數
將物體分成三個集合，G = { i : Vi / Wi > m }??? E = { i : Vi / Wi = m}?? L : { i : Vi / Wi < m}，同樣能在線性時間內完成
計算WG = Sigma(Wi), i ∈ G; WE = Sigma(Wi), i ∈ E
-
如果WG > W，則不在G中取出任何物體，而是繼續遞歸分解G
-
如果WG <= W，取出G中所有物體，并盡可能多得取出E中物體
-
如果WG + WE >= W，也就是說步驟2以后背包已經放滿，則問題解決
-
否則如果尚未放滿，則繼續在L上遞歸調用查找W – WG - WE的方案
以上所有調用都在線性時間內完成，每次遞歸調用都能減少一半的數據規模
因此運行時間的遞歸式為
T(n) <= T(n/2) + Omega(n)
有Master Theorem可得
T(n) = O(n)
問題：
已知一些活動的起止時間{Si}, {Fi}，把它們安排在若干個大廳中進行，要求任一大廳任意時間段內不能有兩項活動同時進行，求出所需的最少的大廳數。
分析：(from CLRS Instructor's Manual)
這是一個區間圖的著色問題(Interval-graph Coloring Problem)，用點表示活動，把時間沖突的活動連起來，然后進行點的著色，要求同一線段的兩端不能有相同顏色的點。
首先最容易想到的就是用書上的Greedy-Activity-Selector找出可安排在大廳1的最長序列，然后刪去這些活動，再次調用該方法，找出安排在大廳2的活動，以此類推。
復雜度O(n*n)
還有一個O(n*logn)的算法，甚至在起止時間都是比較小的數字時復雜度只有O(n)。
主要思想是依次遍歷每個活動，把它們安排到不同的大廳中。
維護兩張表，一張記錄當前時間t已經安排了活動的大廳，另一張記錄當前時間空閑的大廳
然后從頭掃描排序后的時間點序列（如果事件a的結束時間等于時間b的開始時間，那么前者應該排在后者后面）
碰到開始時間t，把該活動放到空閑列表的第一個大廳中（如果空閑列表為空則新加一個大廳），然后把該大廳放入已安排的大廳列表中；
碰到結束時間t，從已安排的大廳列表中移出相應大廳到空閑列表。
復雜度分析：
排序：O(n logn)，如果時間范圍有限制還可以做到O(n)
處理：O(n)
發信人: CJC (藍色雪狐), 信區: 05SS
標 題: OS_Lab3 指南 List
發信站: 復旦燕曦BBS (2007年10月11日03:55:12 星期四), 轉信
先寫點List的東西吧，這個其實在以前并不作為重點講，不過好像大家對它還是有些偏
見，所以這次稍微講下吧。作用是為到時候建立進程關系列表做準備。
講的內容都在/usr/src/linux.../include/linux/list.h中，大家只要把一些不必要的
ifdef和一些prefetch的東西刪掉就好了。
首先講講歷史。在沒有范型的Java里面我們用的鏈表往往會這樣（如果轉成C的話）：
typedef struct list_head {
struct list_node *prev;
void *data;
struct list_node *next;
} list_t;
通過這個結構，我們就能完成鏈表的功能了。但是我覺得這個數據結構不好，原因有二
：
第一：這個結構比較容易引起內存碎片。
┌──┬─┬──┐
│prev│ │next│<----多余內存消耗
└──┴┼┴──┘
│ ┌───┐
└─>│ data │
└───┘
這種設計每一個節點都會引起一塊多余的內存消耗。
第二：類型不明確，因為現在沒辦法用范型。如果寫明了類型，那么還要為每種類型的
list自己再做一整套函數，得不償失。
當然，還會考慮類似于我們希望用別人寫得比較好的代碼之類的原因。
那讓我們來看看我們版本里的list_t是怎么定義的
typedef struct list_head {
struct list_head *next, *prev;
} list_t;
乍一看，這個list_head里面什么都沒包含，只有一對前后指針，沒有指向數據的指針
。那怎么用呢？這里的做法我叫做：反包含。我們來看一個具體的使用例子：
typedef struct test_struct {
int val1;
int val2;
char vals[4];
list_t all_tests; //千萬注意，這里是list_t，不是list_t *
} test_t;
那么我們聲明了這個數據結構在內存中是什么樣的呢？
(test_list) ┌─────┐┬ <--my_test_struct_p(test_t *)
┌──┬──┐ │ val1 ││
│prev│next├┐ ├─────┤│
└──┴──┘│ │ val2 ││h
│ ├─────┤│
│ │ vals ││
表示指向首地址└──>├──┬──┤┴ <--my_list_p(list_t *)
│prev│next│ //這里如果是list_t *就不是這樣畫了！
└──┴──┘
上圖就是一個test_t的結構圖。小地址在上，大地址在下，val1上面的那條分界線作為
val1的起始地址（請注意我my_test_struct_p及其它指針的畫法，是指向上面那根線，表示
為那個東西的起始地址，為清楚起見推薦大家以后這樣畫）
然后為了把所有的test_t數據結構串起來，我們需要一個全局變量：test_list，類行
為list_t（如果這里聲明list_t *的話一定要為它分配空間！如果是死的全局變量、全局數
組和一些臨時數組，推薦直接聲明成類型而不是指針，因為編譯器會放在dat/bss和stack段
里。但是如果這個數據結構是返回類型的分配空間，一定要malloc!否則回去就會錯。這里
也提醒一下）
我們可以看到test_list.next是指向my_test_struct_p->all_tests，而不是my_test_s
truct。但是對我有用的應該是my_test_struct。所以一般處理方法有二，
第一種比較死板，就是在數據結構的一開始就放一個list_t（命名為list），那么&lis
t=&stru，可以直接(xxx *)list_p。但是問題是如果一個數據結構可以同屬兩個鏈表，如pc
b，又要是run_list的成員，又要是all_tasks的成員，還要是父進程children的成員……這
種方法顯然是不夠的。
第二種方法就相對好些。大家可以看，
((unsigned int)my_list_p)-h=(unsigned int)my_test_struct_p
而怎么得到h呢？是不是需要每個數據結構都定義一個h呢？不需要，可以這樣看
h=(unsigned int)(&(((test_t *)0)->all_tests))
就是把0地址當作是test_t數據結構的開始地址，那么這個數據結構的all_tests所在的
地址就是h了。
通過把這兩個算式結合，我們可以得到一個宏：
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
在這里的用法就是：
my_test_struct_p = list_entry(test_list.next, test_t, all_tests);
（如果使用類似于Simics的編輯器的話，all_tests的顯示會是類似于沒有定義變量，
不用管它，的確是這樣的。最后編譯成功就對了）。
看過了最精妙的list_entry之后我們就可以來看一些簡單的操作了
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev = (ptr); \
} while (0)
為什么要加while(0)可以參見lab2指南里面的一些define幫助。其大致概念如下：
┌─────────┐
│ │
└->┌──┬──┐ │
┌─┤prev│next├─┘ //這里為了畫清邏輯，不把指針放在首地址
│ └──┴──┘<-┐
│ │
└─────────┘
這是一個環狀鏈表。一般這個作為頭指針，鏈表為空的判斷依據就是：
static inline int list_empty(struct list_head *head)
{
return head->next == head;
}
然后是添加，先有一個輔助函數：
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
next->prev = new;
new->next = next;
new->prev = prev;
prev->next = new;
}
這個是添加在第一個：
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
┌───────────────────┐
│ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├-─┘ //這里的數據結構就省略畫了
│ └──┴──┘<─┘├──┴──┤ <-┐
│ └─────┘ │
└───────────────────┘
ori_first
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
new ori_first
這個是添加在head->prev，由于是環狀的，那么就是添在了最后一個
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
┌────────────────────────────┐
│ ┌─────┐ ┌─────┐ │
└->┌──┬──┐┌─>├──┬──┤┌─>├──┬──┤ │
┌─┤prev│next├┘ ┌┤prev│next├┘ ┌┤prev│next├─┘
│ └──┴──┘<─┘├──┴──┤<─┘├──┴──┤<-┐
│ └─────┘ └─────┘ │
└────────────────────────────┘
ori_first new
接下來是刪除：
這是輔助方法
static inline void __list_del(struct list_head *prev, struct list_head *next)
{
next->prev = prev;
prev->next = next;
}
這個是用了輔助方法__list_del并且把entry的前后都設為NULL，是為了安全起見
static inline void list_del(struct list_head *entry)
{
__list_del(entry->prev, entry->next);
entry->next = (void *) 0;
entry->prev = (void *) 0;
}
個人覺得list_del_init, list_move, list_move_tail, list_splice沒啥太大作用…
…不過后面兩個非常重要：
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
#define list_for_each_prev(pos, head) \
for (pos = (head)->prev, prefetch(pos->prev); pos != (head); \
pos = pos->prev, prefetch(pos->prev))
使用方法：
list_t *pos;
list_for_each(pos, &test_list) {
test_t *tmp = list_entry(pos, test_t, all_tests);
//do something on tmp
}
=======================================================================
list_t *pos, *n;
list_for_each_safe(pos, n, &test_list) {
test_t *tmp = list_entry(pos, test_t, all_tests);
//do something on tmp
}
======================================================================
那么這兩個有什么差別呢？我們可以來看這個例子：
list_for_each(pos, &test_list) {
list_del(pos);
}
首先，我們得到pos=test_list.next，然后刪除，此時pos->next=0，如果按照list_fo
r_each的話下一個循環的pos就是NULL，再訪問下去就出錯了！同樣的，修改位置也是。所
以在需要修改隊列結構的時候，一定要使用list_for_each_safe。如果只修改對應的數據結
構其他字段，可以用list_for_each，因為這個效率比較高。
有了這些方法基本上就可以使用了。我們可以來看一個物理內存管理的例子：
#define USER_MEM_SIZE (256*1024*1024)
#define USER_MEM_START (16*1024*1024)
#define PAGE_SHIFT 12
#define PAGE_SIZE (1<<(PAGE_SHIFT))
#define PAGE_COUNT (((USER_MEM_SIZE)-(USER_MEM_START))>>(PAGE_SHIFT))
#define PAGE_START(ptr) (((ptr)-(all_pages))<<(PAGE_SHIFT)+(USER_MEM_START))
//獲取這個page數據結構對應的起始地址
#define PAGE_STRU(addr) (&all_pages[((addr)-(USER_MEM_START))<<(PAGE_SHIFT)])
typedef struct page_struct {
unsigned long use_count;
list_t mem_list;
} page_t;
list_t free_list, lru_list; //lru是用作換出的，最近使用在隊首，換出隊尾頁
//如果編譯器不肯讓我們這樣定義的話用lmm_alloc或者out_alloc也可以。
page_t all_pages[PAGE_COUNT];
void init()
{
int i;
INIT_LIST_HEAD(&free_list);
INIT_LIST_HEAD(&lru_list); //初始化兩個鏈表
for (i = 0; i < PAGE_COUNT; i++) {
all_pages[i] = 0;
list_add_tail(&all_pages[i].mem_list, &free_list); //加入free_list
}
}
//此處返回值作為錯誤信息，addr作為所需返回的物理內存起始地址
int get_page(unsigned int *addr)
{
if (list_empty(&free_list)) //沒有空頁
return -1;
list_t *lst = free_list.next;
list_del(lst);
list_add(lst, &lru_list); //最近使用，放到隊首
*addr = PAGE_START(list_entry(lst, page_t, mem_list);
return 0;
}
void use_page(unsigned int addr)
{
page_t *pg = PAGE_STRU(addr);
list_del(&pg->mem_list);
list_add(&pg->mem_list, &lru_list); //將頁面放到lru隊列首
}
void return_page(unsigned int addr)
{
page_t *pg = PAGE_STRU(addr);
list_del(&pg->mem_list);
list_add(&pg->mem_list, &free_list); //將頁面放到free隊列首，下次取時用
}
物理頁面管理基本上就類似于此。我們接下來來看一個稍微復雜些的例子，就是進程父
子關系的例子，去年又同學跟我反映這是一個交錯鏈接或者說是嵌套鏈接，其實不然。我們
拆分開來看：
┌─────────-┐
│┌-────────┼───┐
│ ↘ A->children │ │
┌───-┼─>┌──┬──┐ │ │
│ └-─┤prev│next├┐│ │
│ └──┴──┘││ │
│┌────────────┘│ │
││ ┌-───┘ │
││ ┌─────┐ ↘┌─────┐│
│└>├──┬──┤┌─>├──┬──┤│
└-─┤prev│next├┘ ┌┤prev│next├┘
├──┴──┤<─┘├──┴──┤
└─────┘ └─────┘
B C
由圖可知，A有BC兩個子進程，分別連接到A進程的children上。此時，處理A的childre
n又有兩種方法，第一種是增加指針，第二種是作為A進程的一部分。利用上面的思考方法，
我們可以知道，如果按照第一種做法，那么勢必會引起更多的內存碎片，不方便。于是我們
把children作為pcb的一個field。那么B和C里面的prev/next該叫什么呢？因為B和C也是pc
b的數據結構，已經不可能再叫children了（而且他們也應該有children節點，因為他們也
可能有子進程）。那么我們就叫它為sibling吧。因為在這個鏈表里，除了A是父進程，其余
的都是兄弟進程。
所以pcb的父子關系可以這樣寫：
#define TASK_STATE_RUNNING 0
#define TASK_STATE_ZOMBIE 1
//調用了wait指令，等待子進程結束
#define TASK_STATE_WAIT_CHILD 2
typedef struct pcb_struct{
struct pcb_struct *parent; 父進程
unsigned long state;
list_t children;
list_t sibling;
list_t all_tasks;
} pcb_t;
//init是一個非常特殊的進程，一般我們的kernel一起來，就只負責兩個進程：init和idle
//init的作用是先fork，子進程運行shell，它自身while(1) {wait(...);}就是負責回收
//孤兒進程。
//并且在此，我們可以把所有的進程都連接在init的all_tasks上面，這樣又可以節省一個
//相當于前例test_list的全局變量。找所有進程只須遍歷init->all_tasks即可。
//所以在生成init的時候應該是INIT_LIST_HEAD(&task->all_tasks)
void init_pcb(pcb_t *task, pcb_t *init)
{
INIT_LIST_HEAD(&task->children);
INIT_LIST_HEAD(&task->sibling);
task->parent = NULL;
task->state = TASK_STATE_RUNNING;
list_add_tail(&task->all_tasks, &init->all_tasks);
}
void add_child(pcb_t *parent, pcb_t *child)
{
child->parent = parent;
list_add_tail(&child->sibling, &parent->children); //想想為什么
}
void do_exit(pcb_t *task, pcb_t *init)
{
//exit_mem_first_part
list_t *pos, *n;
list_for_each_safe(pos, n, &task->children) //將所有子進程交給init
{ //~~~~
task_t *child = list_entry(pos, task_t, sibling); //這里是sibling
child->parent = init;
list_del(&child->sibling);
list_add_tail(&child->sibling, &init_children);
if (child->state == TASK_STATE_ZOMBIE && init->state != TASK_STATE_WAIT_
CHILD)
{
//這里激活init，并把init放到進程列表的尾端
}
}
//然后切換到父進程運行
}
如果看懂了以上的所有例子，那么鏈表結構應該就差不多了。由于篇幅關系，PCB的構
建就單列開來吧。這里專門講LIST好了。:)
如果有代碼覺得看的郁悶的，拿張紙畫畫對應的內存結構應該就會好些了
--
※ 修改:·CJC 于 Oct 11 03:57:46 修改本文·[FROM: 穿梭而來]
※ 來源:·復旦燕曦BBS yanxibbs.cn·[FROM: 穿梭而來]
http://10.132.140.73/lxr/http/blurb.html
在機房搭了一個，原本以為有筆記的功能，裝好以后才發現只能閱讀用，不過搜索功能還是很強大的。
轉載，部分修改（標為紅色）
我們在閱讀linux源代碼時都有這樣的體會:核心的組織相對松散，在看一個文件時往往要牽涉到其他的頭文件、源代碼文件。如此來回跳轉尋找變量、常量、函數的定義十分不方便，這樣折騰幾次，便使讀代碼的心情降到了低點。
lxr(linux cross reference)就是一個解決這個問題的工具：他對你指定的源代碼文件建立索引數據庫，利用perl腳本CGI動態生成包含源碼的web頁面，你可以用任何一種瀏覽器查閱。在此web頁中，所有的變量、常量、函數都以超連接的形式給出，十分方便查閱。比如你在閱讀/usr/src/linux/net/socket.c的源代碼，發現函數 get_empty_inode不知道是如何以及在哪里定義的，這時候你只要點擊get_empty_inode,lxr將返回此函數的定義、實現以及各次引用是在什么文件的哪一行，注意，這些信息也是超連接，點擊將直接跳轉到相應的文件相應的行。另外lxr還提供標識符搜索、文件搜索，結合程序 glimpse還可以提供對所有的源碼文件進行全文檢索，甚至包括注釋！
下面將結合實例介紹一下lxr和glimpse的基本安裝和使用，由于glimpse比較簡單，就從它開始：
首先訪問站點： http://glimpse.cs.arizona.edu/ 得到glimpse的源碼
,比如我得到的是glimpse-4.12.5.tar.gz . 用root登錄，在任一目錄下用tar zxvf glimpse-4.12.5.tar.gz解開壓縮包，在當前目錄下出現新目錄glimpse-4.12.5 .
進入該目錄，執行
./configure
make
make install
如果單獨使用glimpse，那么只要簡單的執行glimpseindex foo即可，其中foo是你想要索引的目錄，比如說是/usr/src/linux .glimpseindex的執行結果是在你的起始目錄下產生若干.glimpse*的索引文件。
然后你只要執行glimpse yourstring即可查找/usr/src/linux下所有包含字符串yourstring的文件。
對于lxr，你可以訪問lxr.linux.no得到它的源代碼解包后，遵循如下步驟：
/*下面的文字來源于lxr的幫助文檔以及本人的安裝體會*/
1)修改Makefile中的變量PERLBIN和INSTALLPREFIX,使它們分別為 perl程序的位置和你想lxr安裝的位置.在我的機器上，PERLBIN的值為/usr/bin/perl .至于INSTALLPREFIX，有如下原則，lxr的安裝路徑必須是web服務器能有權限訪問。因此它的值簡單一點可取 /home/httpd/html/lxr (對于Apache web server)。
2)執行 make install
3)修改$INSTALLPREFIX/http/lxr.conf :
baseurl : http://yourIP/lxr/http/
htmlhead: /home/httpd/html/lxr/http/template-head
htmltail: /home/httpd/html/lxr/http/template-tail
htmldir: /home/httpd/html/lxr/http/template-dir
sourceroot : /usr/src/linux # 假如對linux核心代碼索引
dbdir : /home/httpd/html/lxr/dbdir/ #dbdirk可任意起名，且位置任意 glimpsebin: /usr/bin/glimpse #可執行程序glimpse的位置
4)在$INSTALLPREFIX/http/下增加一個文件.htaccess內容：
<Files ~ (source|search|ident|diff|find)$> ***
SetHandler cgi-script
</Files>
上面這個文件保證Apache server將幾個perl文件作為cgi-script.
5)按照lxr.conf中的設置建立dbdir ,按照上例,建立目錄
/home/httpd/html/lxr/dbdir
進入這個目錄執行$INSTALLPREFIX/bin/genxref yourdir
其中yourdir是源碼目錄，比如/usr/src/linux
如果要結合glimpse，則執行glimpseindex -H . yourdir
6)修改 /etc/httpd/conf/
httpd.conf ,加入
<Directory /home/httpd/html/lxr/http>
Options All
AllowOverride All
order allow,deny
allow from all
</Directory>
7)進入/etc/rc.d/init.d/ 執行
killall httpd
./httpd start
進入X ，用瀏覽器
http://yourIP/lxr/http/blurb.html
大功告成 ，這下你可以舒心的讀源碼了。
Problem: You are given n real numbers - they are NOT sorted. Develop a linear time（O(n)）algorithm to find the largest gap between consecutive numbers when the n numbers are sorted. For example, given:
10 23 7 1 35 27 50 41
the algorithm should produce 13 as its result, since the sorted list is:
1 7 10 23 27 35 41 50
and the largest gap is 13 (between 10 and 23).
Please note that your algorithm cannot actually sort the n numbers.
Macsy (真心) 于 (Fri Oct 5 11:59:16 2007) 提到:
有一個方法需要額外的O(n)的空間。
首先找到最大最小數max,min
max gap 肯定不小于 (max-min)/n 。
然后以(max-min)/n為步長，建立n個桶
每個桶里面記錄落在這個桶中的最大最小值。
最后順序掃描這n個桶中的值就可以了。
大概代碼是
input: a[n];
min=min_of(a[1..n]);
max=max_of(a[1..n]);
step=(max-min)/n;
b[0..n].min=maxfloat; b[0..n].max=-maxfloat;
for i=1 to n
ind = (a[i]-min)/step;
b[ind].min=min(b[ind].min, a[i]);
b[ind].max=max(b[ind].max, a[i]);
maxgap=step;
last=b[0].max;
for i=1 to n
if (b[i].min != maxfloat)
maxgap=max(maxgap, b[i].min-last);
last=b[i].max;
output maxgap
proftpd.conf中增加兩行設置：
UseReverseDNS off
IdentLookups off
Come From Alacner Blog：http://blog.alacner.com/post/168.htm
同目錄下包含這三個文件即可
mingwm10.dll
QtCore4.dll
QtGui4.dll
以下轉載自《Linux kernel》
核心源碼的頂層是/usr/src/linux目錄，在此目錄下你可以看到大量子目錄：
arch
這個子目錄包含了所有體系結構相關的核心代碼。它還包含每種支持的體系結構的子目錄，如i386。
include
這個目錄包括了用來重構核心的大多數include文件。對于每種支持的體系結構分別有一個子目錄。 此目錄中的asm子目錄中是對應某種處理器的符號連接，如include/asm-i386。要修改處理器結構 則只需編輯核心的makefile并重新運行Linux核心配置程序。
init
此目錄包含核心啟動代碼。
mm
此目錄包含了所有的內存管理代碼。與具體體系結構相關的內存管理代碼位于arch/*/mm目錄下， 如arch/i386/mm/fault.c 。
drivers
系統中所有的設備驅動都位于此目錄中。它又進一步劃分成幾類設備驅動，如block。
ipc
此目錄包含了核心的進程間通訊代碼。
modules
此目錄僅僅包含已建好的模塊。
fs
所有的文件系統代碼。它也被劃分成對應不同文件系統的子目錄，如vfat和ext2。
kernel
主要核心代碼。同時與處理器結構相關代碼都放在arch/*/kernel目錄下。
net
核心的網絡部分代碼。
lib
此目錄包含了核心的庫代碼。與處理器結構相關庫代碼被放在arch/*/lib/目錄下。
scripts
此目錄包含用于配置核心的腳本文件（如awk和tk腳本）。
主要是做DS Project 1時碰到的問題
1. 泛型方法push(elemType &x)無法接受常數等const類型，必須將形參聲明為const elemType &x
2. 在給泛型類SimpleList增加operator<<方法時，把實現代碼放在類的聲明外部會報錯，直接放在里面就可以，不知道是不是必須是內聯inline的才可以。
水木問了下，答案是
除非在友元聲明中顯式指定了模板參數，否則與函數模板同名的友元函數的聲明不會引用該函數模板.如果未指定模板參數，則友元聲明將聲明一個非模板函數。
3. C++中可以throw很多東西，比如String, int等。catch (...)表示把所有的異常都捕捉到。
from 水木
1. 兩兩比較，找出最大的，n-1次
2. 從找最大的這條路線回溯，次大的必然在這條路線上，找到它需要logn - 1次（敗者樹的最大高度為logn）
其實就是一個錦標賽排序