2010 作戰流程圖上學期主線任務 ( 北市, 全國是去年日期地點 ) 時間比賽戰場說明 09/20 資訊科校內賽建中電教約選 20 名進入培訓 11/20 北市資訊能力競賽師大分部校內賽前 12 名參加 12/19 全國資訊能力競賽交通大學北市賽前 10 名參加, 全國賽前 10 名進入

Size: px

Start display at page:

Download "2010 作戰流程圖上學期主線任務 ( 北市, 全國是去年日期地點 ) 時間比賽戰場說明 09/20 資訊科校內賽建中電教約選 20 名進入培訓 11/20 北市資訊能力競賽師大分部校內賽前 12 名參加 12/19 全國資訊能力競賽交通大學北市賽前 10 名參加, 全國賽前 10 名進入"

铮镡森
5 years ago
Views:

1 2010 作戰流程圖上學期主線任務 ( 北市, 全國是去年日期地點 ) 時間比賽戰場說明 09/20 資訊科校內賽建中電教約選 20 名進入培訓 11/20 北市資訊能力競賽師大分部校內賽前 12 名參加 12/19 全國資訊能力競賽交通大學北市賽前 10 名參加, 全國賽前 10 名進入 TOI 第一階段上學期支線任務 ( 松山工農是去年日期 ) 時間比賽戰場說明 11/08 松山工農初賽 ( 筆試 ) 松山工農校內推薦 10 名參加, 分高中高職高商開放四組 11/13 松山工農決賽 ( 上機 ) 松山工農約取初賽前 25 名進入決賽 11/27 NPSC 初賽 ( 團體賽 ) 線上自由報名, 前 25 名進入決賽 ( 每校最多三隊晉級 ) 12/11 NPSC 決賽 ( 團體賽 ) 台灣大學有點心!! 下學期主線任務 (TOI APIO 為去年日期 ) 時間任務戰場說明 03/13 TOI 初選 ( 入營考 ) 師大分部依照北市賽成績推薦 ( 或遞補 ) 參加 04/01~04/11 TOI 第一階段師大分部初選前 20 名與全國賽前 10 名參加 04/19~05/02 TOI 第二階段師大分部兩次模擬考成績前 12 名 05/08 APIO 師大分部進入 TOI 第二階段者參加 07/22~07/29 IOI 2011 泰國四次模擬考成績前 4 名參加一常見 Online Judge.USACO Training: 競賽資源簡介.UVa Online Judge (ACM): INFOR Online Judge (TIOJ): Akademia Informatyczna (POI): Online Judge: 二常見線上賽三書籍.USACO Contest Gateway: Open Competition in Informatics: Coder: Code Jam: Introduction to Algorithms 3/e : Thomas H. C., Charles E. L., Ronald L. R., Clifford S.. Fundamentals of Data Structures in C(C++) 2/e : Horowitz, Sahni, Mehta. 算法藝術與信息學競賽 : 劉汝佳黃亮, 清華大學出版社 ( 超難 ) 四網路資源. 校內培訓網站 : 的網路日誌 : 補完計畫 : 上的 sa 板 :telnet://sony.twbbs.org 內的 sa 板 ( 以 ACM 解題文為大宗 ).Luckycat (godgunman s mirror):

時間複雜度 (Time Complexity) 本日演算法評估一個程式的效率最常見的是時空複雜度程式實際執行的速度受到許多因素影響, 很難有比較, 因此時間複雜度空間複雜度等所關心的是當輸入數據的規模擴大時, 一個演算法所需的時間空間的增長情形複雜度分析有三種常見符號 :( 備註 : = 符號其實是的意思) 一 O-notation: 上限漸近線定義 : 若 n 0, c R +,

2 時間複雜度 (Time Complexity) 本日演算法評估一個程式的效率最常見的是時空複雜度程式實際執行的速度受到許多因素影響, 很難有比較, 因此時間複雜度空間複雜度等所關心的是當輸入數據的規模擴大時, 一個演算法所需的時間空間的增長情形複雜度分析有三種常見符號 :( 備註 : = 符號其實是的意思) 一 O-notation: 上限漸近線定義 : 若 n 0, c R +, 使得 n n 0 皆有 f(n) c g(n), 則 f(n) = O( g(n) ) 直觀來說,c g(n) 可以視為 f(n) 的上限遞迴式通常畫遞迴樹分析, 而多項式函數通常可以直接忽略較低次項, 例如 7n 3 + 5n 2 + n + 1 = O( n 3 ) n n = O( n 2 ) 常見的時間複雜度 :O( 1 )<O( log n )<O( n )<O( n log n )<O( n k )<O( k n )<O( n! )<O( n n ) 二 Ω-notation: 下限漸近線定義 : 若 n 0, c R +, 使得 n n 0 皆有 f(n) c g(n), 則 f(n) = Ω( g(n) ) 最有名的就是基於比較的排序法的時間複雜度下限 : 以上是用 decision tree 來做比較排序法的圖考慮集合 S={a 1, a 2, a 3,..., a n }, 其中 a 1, a 2,, a n 兩兩相異, 則這 n 個元素總共可能形成的排列有 n! 種, 其中只有一種符合對於所有的 1 i<j n,a i <A j 假設比較排序法的 decision tree 的高度是 H, 有 L 個可到達的葉子, 因為所有 n! 個排列一定會是樹當中的某些葉子, 所以 n! L 又因為一棵高度為 H 的二元樹最多只會有 2 H 個葉子, 所以 n! L 2 H Ω

3 三 Θ-notation: 定義 : 若 n 0, c 1, c 2 R +, 使得 n n 0 皆有 c 1 g(n) f(n) c 2 g(n), 則 f(n) = Θ( g(n) ) 練習題 : 以下時間複雜度為? 1. T(n) = T(2n/3)+Θ(n) 2. T(n) = 2 T(n/2)+Θ(n) 3. T(n) = T( )+Θ(1) 4. T(n) = T(n/5)+T(7n/10)+Θ(n) 5. T(n) = T(n/4)+T(3n/4)+Θ(n) 6. 1 void XD(int n, int height[max], int ans[max]) { 2 int i, j; 3 static int jmp[max]; 4 for (i=n-1; i>=0; i--) { 5 for (j=i+1; j<n && height[i]>height[j]; j=jmp[j]); 6 jmp[i] = j; 7 ans[i] = (j==n? -1 : j); 8 } 9 } 常見排序法 (Sort) 一 Insertion Sort ( 插入排序 ) O( n 2 ) 1 For i 2 To n Do 2 k A[ i ] 3 For j i Down To 2 Do 4 If A[ j-1]>k Then Do A[ j ] A[ j-1] 5 Else Break 6 A[ j ] k 二 Bubble Sort ( 泡沫排序 ) O( n 2 ) 1 For i n Down To 2 Do 2 For j 2 To i Do 3 If A[ j-1]>a[ j ] Then Do 4 Exchange A[ j-1] A[ j ] 三 Selection Sort ( 選擇排序 ) O( n 2 ) 1 For i 1 To n-1 Do 2 k i 3 For j i+1 To n Do 4 If A[ j ]<A[ k ] Then Do k j 5 Do Exchange A[ i ] A[ k ] 雖然這些算法複雜度都是 O( n 2 ), 但常數較小, 在 n 很小時效率不錯底下是一些複雜度較好的 sort: 四 Merge Sort ( 合併排序 ) O(n log n) 對於兩個已排序長度各為 n, m 的序列, 如何在 Θ(n+m) 的時間將其合併成長度 n+m 的已排序序列? 若這一步能夠做到, 那我們每次把長度為 n 的陣列分成長度相等的兩段, 分別排好序後, 再合併即可將原序列排序, 且複雜度為 T(n)=2 T(n/2)+O(n), 如下 : MERGE-SORT (A, L, R) 1 If L<R Then Do 2 M [ (L+R)/2 ] 3 MERGE-SORT (A, L, M) 4 MERGE-SORT (A, M+1, R) 5 MERGE (A, L, M, M+1, R)

4 MERGE (A, L, M, R) 1 create array Out[ 1 R-L+1 ] 2 i L, j M+1, k 1 3 While i M And j R Do 4 If A[ i ] A[ j ] Do 5 Out[ k ] A[ i ] 6 i i+1 7 Else Do 8 Out[ k ] A[ j ] 9 j j+1 10 k k+1 11 While i M Do 12 Out[ k ] A[ i ] 13 i i+1, k k+1 14 While j M Do 15 Out[ k ] A[ j ] 16 j j+1, k k+1 17 A[ L R ] Out[ 1 k-1 ] 五 Quicksort ( 快速排序 ) Average case performance: O(n log n), Worst case performance: O( n 2 ) 考慮一種排序法 : 把現在的序列切成兩段, 並花 O(n) 的時間重排序列, 讓左邊那段的元素小於等於右邊那段的元素遞迴處理左右兩段, 切到每段的長度都是 1 時, 排序就完成了這就是 Quick Sort QUICKSORT (A, L, R) 1 If L<R Do 2 M PARTITION (A, L, R) 3 QUICKSORT (A, L, M-1) 4 QUICKSORT (A, M+1, R) PARTITION (A, L, R) 1 pivot A[ R ] 2 split L 3 For i L To R-1 Do 4 If A[ i ] pivot Do 5 Exchange A[ split ] A[ i ] 6 split split+1 7 Exchange A[ split ] A[ R ] 8 Return split 不過, 當 n 不大時,Quicksort 過度頻繁的切割序列遞迴反而會讓速度變慢而且當 n 不大時, Insertion Sort 等往往效率較高, 因此可以選一個值為分界點, 分界點以下使用 Insertion Sort, 以上則使用 Quicksort, 可以提高整體效率這種想法在撰寫 Strassen s algorithm 也可以使用要注意的是, 以上這段虛擬碼的 PARTITION 沒有特別處理相同數字的問題, 因此遇到相同數字時極可能掉入 O( n 2 ) 的情況.Stable sort: 若對於 A i =A j i<j, 排序後不改變 A i A j 的先後順序, 則稱為 stable sort.in-place sort: 若排序時所要耗用的額外空間為 O(1), 則稱為 in-place sort 以上哪些是 stable sort 呢? 哪一個不是 in-place sort? Quick Sort 又可以怎麼避免最差狀況的發生? 上面介紹的都是基於比較的排序法,O(n log n) 已經是下界底下還有一些線性的特殊排序法 : 六 Counting Sort ( 計數排序 ) O( n+c ),C 為輸入數值範圍 : 直接計算每個數字的出現次數 1 initialize cnt[ 0 C ] 0 2 For i 1 To n Do cnt[ A[ i ] ] cnt[ A[ i ] ]+1 3 k 1 4 For i 0 To C Do 5 For j 1 To cnt[ i ] Do 6 A[ k ] i 7 k k+1 七 Radix Sort ( 基數排序 ) O( (n+b) log B C ) 一開始先照最低的位數排序, 再照次高的位數排序,, 最後用最高的位數排序注意每次排序一位數的時候, 都必須是 stable sort, 否則會亂掉 Radix Sort 在 suffix array 的倍增算法中常用到

5 八一些內建的排序函數 #include <algorithm> // 這個函式在 std 命名空間下 void sort( random_iterator start, random_iterator end ); void sort( random_iterator start, random_iterator end, StrictWeakOrdering cmp ); 這是 STL 的內建排序函式, 為 introsort, 平均最佳時間複雜度都是 O(n log n) #include <cstdlib> void qsort( void *buf, size_t num, size_t size, int (*compare)(const void*, const void*) ); 這個則是 C 內建的快速排序函式注意 num 是要排序的元素個數,size 是每個元素的大小 (in bytes), 而比較函式要視大於等於小於的情況分別回傳九練習題逆序數對 TIOJ 1080 對一個序列 S 來說, 若 S 的第 i 項 s i 與第 j 項 s j 符合 s i >s j, 並且 i<j 的話, 那麼我們說 (i, j) 是一個逆序數對請問給定序列 S, 請問總共有多少個逆序數對呢? 請至少給出 O(n log n) 算法第 k 大的數 TIOJ 1364 給定序列 S, 請在期望 O(n) 的時間內求出此序列中第 k 大的數 TIOJ 1289 E. 畢氏煩惱給 n 條相異整數邊, 總共可以組合出幾種直角三角形 ( 只要任一邊長不同即視為相異 )? 相關題目 :TIOJ 1174, 1205, 1208, 1267, 1501, 1617 分而治之 (Divide and Conquer) 以此要領, 重複實施, 即得答案 -- pangfeng 分而治之就是把大問題切成許多相似的小問題, 然後各個擊破分治法通常可見以下的步驟 : 1. 把問題切成規模較小與原問題相似的子問題 2. 遞迴解決子問題 3. 合併子問題, 求得原問題的解答大家耳熟能詳的有 :. 階乘 :. 費氏數列 : 底下就來思考一些問題吧!.Merge Sort,Quicksort 等約瑟夫問題有 n 個人為成一圈, 且每數 k 個人就把第 k 個人殺掉, 並從下一個人繼續數最後活下來的是誰? 河內塔 TIOJ 1355 現在有三根柱子, 一開始在第一根柱子上有 n 個圓盤, 由大到小疊好, 請印出所有搬動圓盤步驟, 把所有圓盤從 1 號柱搬到 3 號柱子, 且移動過程中大圓盤不得疊在小圓盤上

6 快速冪運算 UVaOJ 374 給定 a, b, c, 請在 O(log b) 的時間內求出 a b Mod c 的值 UVaOJ Savage Garden 在一個 2 n 2 n 的棋盤中, 挖去了 1 1 的一塊請用形拼圖把棋盤填滿 TIOJ 1202 重疊的天際線地平線之上有 n 棟建築, 第 k 棟建築位在 [L k, R k ], 高度 H k 請描述出這些建築重疊後的天際線平面最近距點對 TIOJ 1500 給定平面上的 n 個點, 請問 ( 直線距離 ) 最近的兩個點距離為? 請給出 O(n log n) 算法相關題 :TIOJ 1154, 1199, 1203, 1360, 1455 超級挑戰題:TIOJ 1631 ( 期望複雜度 :O(n log n) ) 其他零零碎碎常見的東西一二分搜 (Binary Search) 請在一個已排序的序列 ( a 1 <a 2 < <a n ) 中, 找到給定的一個數 (x) 的位置觀察一下, 可以發現, 假設 a k =x, 那麼. 對於所有 1 a i <a k, 有 a i <x. 對於所有 a k <a j n, 有 x<a j 可以寫出如下的算法 : BINARY-SEARCH (A, L, R, x) 1 If L>R Then Return Not Found 2 M [ ( L+R ) / 2 ] 3 If x=a[ M ] Then Return x 4 Else If x<a[ M ] Then Return BINARY-SEARCH (A, L, M-1, x) 5 Else Return BINARY-SEARCH (A, M+1, R, x) 二分搜的應用範圍極廣除了找資料, 任何有單調性的東西, 二分搜都有機會派上用場其核心概念是每次丟掉一半不可能的解變化形則如三分搜 ( 搜凹或凸的圖形 ) 雙重二分搜等 UVaOJ Closest Sums 給定一個集合 S, 對於每個詢問給的數 k, 請找出集合中兩個數的和, 使其最接近 k UVaOJ Selfdescribing Sequence <f(1), f(2), > 是非遞減序列, 且 f(n)=k 代表值 n 會在序列中出現 k 次 f(1)=1, f(2)=2, 求 f(n) NTUJ 0062 Drying 你有 n 件衣服, 第 k 件衣服要花 A k 的時間才會乾在每一單位時間中, 你可以選擇任一件衣服, 讓它剩餘所需的乾衣時間減少 C 請問你最少要花多少時間, 才能讓所有衣服變乾? (A k 10 9 ) 鍊習題 :TIOJ 1044, 1406, 1525, 1614, UVaOJ 挑戰題 :TIOJ 1575, 1635

7 二輾轉相除法 (Euclidean Algorithm) 若 a=bq+r, 則 (a, b)=(b, r), 邊界條件為 (a, 0)=a 由此可以寫出 : GCD(a, b) 1 If b=0 Then Return a 2 Else Return GCD(b, a Mod b) 注意 GCD 的時間複雜度為 O(log b) 但我們更常用的是同時求出一組 (x, y) 使得 ax+by=gcd(a, b): EXTENDED-EUCLIDEAN-ALGORITHM(a, b) 1 A (1, 0), B (0, 1) 2 While b 0 Do 3 r a Mod b, R A-B [ a / b ] 4 a b, A B 5 b r, B R 6 Return (a, A). 若 (a, b)=1, 請求出 c 使得 a c 1 (Mod b) ( 註 :c 即為 a 在模 b 下的乘法逆元素 ) NPSC 2008 高中組決賽 pd. 輾轉難眠求 gcd(a m -b m, a n -b n ) Mod p 保證 (a, b)=1, 0<b<a<1000, 1<m<n 200 三質數篩法 (Prime Sieve) 判斷一個數 n 是不是質數, 直接做就是把以下的數全都試除過一遍不過當我們需要質數表時, 一個一個試除太慢好險兩千多年前, 古希臘數學家 Eratosthenes 發明了一個很好的演算法 : 把所有正整數排成一列, 每次找最小的還沒有被劃掉的數 p, 把 p 的倍數全部劃掉, 剩下的就是質數 ERATOSTHENES (n) 1 create array is_prime[ 2 n ] = true 2 For i 2 To Do 3 If is_prime[ i ]=true Then Do 4 For j To n Step i Do is_prime[ j ] false. 值得注意的是, 因為質數的倒數和為 O(ln ln n), 所以篩法的時間複雜度約為 O(n ln ln n). 把 n(n ) 質因數分解很容易, 那把 n! (n 10 6 ) 質因數分解呢? 如何快速的求 ( n! )Mod m? 練習題 :TIOJ 1036, 1193, 1350, UVaOJ 10140, 10311, 10699, 10892, USACO 1.5 Prime Palindromes 四離散化離散化是指把題目輸入數字的數值範圍縮小到比較好處理的範圍內, 通常是離線預處理 NPSC 2003 年決賽 pa. 細菌培養 TIOJ 1045 在的方格中, 每個方格一開始都有一隻細菌題目會做很多次操作, 每次操作會把一個矩形區域的細菌數倍增所有操作都結束後的總細菌數為? ( 操作數 200) 五大數運算電腦內建的型態有其範圍限制為了突破天際, 人類發明了大數運算 : 直式的加減乘除大數運算的想法是開個陣列存下每一位數, 然後手怎麼算, 程式就怎麼寫, 即使開平方根等等也一樣大數運算有兩個常見優化 :1. 記下大數的位數 2. 每一個 int 中存多位數 ( 純加減 9 位, 有乘除 4 位 )

8 本日資料結構資料結構可以視為處理資料的方法資料結構通常像一個集合, 並依照我們的需求維護這個集合的某種特性, 而這個集合可能支持新增刪除查找元素等操作常見的資料結構包含 Array Linked List Stack Queue Tree Graph Heap Hash Disjoint Sets 等等鍊結串列 (Linked List) 把資料用結構包成一個節點, 串起來, 就成了鍊結串列鍊結串列的節點通常會包含資料欄位以及指向下一個節點的指標串成一串後, 刪除新增只要常數時間刪除指定位置元素在指定位置新增元素這裡鍊結串列的指標都只有單向, 為 singlylinked list 也有雙向指標的鍊結串列, 稱為 doublylinked list 此外, 還有鍊結串列的尾端重新指向鍊結串列的開端, 形成一個環, 稱為 circular linked list 練習題 :TIOJ 1550 NTUJ 0952 Queue 一開始有 P (P 10 9 ) 個人依序排成一隊接著會有 N (N 50,000) 插隊事件發生, 每個插隊事件後, 編號 A 的人會插到編號 B 的人前面在所有插隊事件結束後有 Q (Q 50,000) 個詢問詢問有兩種 : 問編號 P 的人排在哪裡, 或是排在 L 的人編號為何請回答所有詢問堆疊 (Stack) 堆疊就像一疊盤子, 每次只能從頂端放上新盤子或把就盤子拿走堆疊只有一個資料的進出口 ( 堆疊頂, top), 並且滿足先進後出 (FILO, First-In Last-Out) 平常遞迴就是用堆疊來實做的 UVaOJ 514 Rails 假設現在有 n 輛列車依照 1, 2, 3,..., n 的順序要從 A 開到 B, 而他們都可以在 Station 任意停留任意時間, 請問他們能否以某特定的順序開到 B?

9 括弧匹配 S = ( +S+ ) [ +S+ ] { +S+ } 給定字串 s, 請問 s 是否符合 S 的定義? 中序轉後序 TIOJ 1378 請一四則運算的規則把一串含加減乘除括弧變數的式子轉成後序表示法 TIOJ 1176 Cows 給定 n 個數字的序列, 求出每個數在它之後第一個比它小的數距離它多遠請給出 O(n) 算法 NPSC 2009 初賽 pf. 檸檬汽水問題在序列 a 1, a 2,, a n 中, 共有多少個數對 (i, j) 滿足 1 i<j n, 且 i<k<j 有 a k min{a i, a j }? n 10 6 TIOJ 1370 超大鏡框設置許多緊貼地面的建築物排成如右的圖形 ( 沒有懸空或破洞的地方 ) 則其子矩形最大面積為? ( 子矩形的四邊也必須平行 x 軸或 y 軸 ) 笛卡爾樹(Cartesian Tree) TIOJ 1549 給定陣列 A[ 1 n ] 你希望建立一棵二元樹滿足: 1. 這棵樹的根是 A[ 1 n ] 中最小的元素 ( 假設是 A[ k ]) 2. A[ 1 k-1] A[ k+1 n ] 也都是笛卡爾樹請給出 O(n) 建立出這棵樹的算法 IOI 2004 Day II prob 1, Empodia NTUJ 0951 a 1, a 2,, a n 是 0, 1,, n-1 的重排列請找出所有的區段 a i, a i + 1, a i + 2,, a j 滿足.a i <a i + 1, a i + 2,, a j.a i + 1,, a j - 2, a j - 1<a j.a i, a i + 1, a i + 2,, a j 不包含任何更短的滿足上述條件的區段. 大家可以發現許多使用 stack 的算法通常都會維持 stack 中資料從頂到底的. 某些單調性練習題 :TIOJ 1063, 1320, 1204, 1225, 挑戰題 :TIOJ 1332, 1343, 1397 佇列 (Queue) 相對於堆疊, 佇列有一個資料入口 (front) 一個資料出口 (rear), 且有先進先出 (First-In First-Out, FIFO) 的特性除了長條形的佇列以外, 佇列也常實做成環形的, 減少空間的浪費 NPSC 2007 決賽 pf. 核心字串 TIOJ 1489 請找出字串 s ( s 10 6 ) 最短的子字串 s, 使得 s 中 a-z 都最少出現一次 NTUJ 0839 Finding Seats 在一個 R C(R, C 300) 的地圖中, 每個座標不是. 就是 x 請找出面積最小的一個區域, 使得這個區域中最少有 K 個. 輸出該區域的面積. 這些使用 queue 的算法則是維持 queue 中元素滿足某種特性, 且 queue 中的元素數量最多 / 少

二元樹 (Binary Tree) 在離散數學中, 圖是用來表現物體與物體之間關係的方法, 而圖論就是專門研究圖的理論在圖論當中, 我們把物件抽象成一個點與邊集合的模型, 以邊來表示點與點之間的關係一個圖是個二元組, 用 G=(V, E) 表示,V 表示頂點的集合,E 表示邊的集合其中若 u, v V 之間有邊連通, 則有 (u, v) E

v ]<depth[ u ], 則 u 是 v 的子節點兄弟節點 (sibling) 具有相同父節點的節點互為兄弟節點度數 (degree) 一個節點 v 的子節點個數葉子 (leaf) 沒有子節點的節點, 又稱外部節點高度 (height) 最深的節點的深度 m 元樹 (m-ary tree) 所有節點的度數皆不超過 m 的樹子樹

10 二元樹 (Binary Tree) 在離散數學中, 圖是用來表現物體與物體之間關係的方法, 而圖論就是專門研究圖的理論在圖論當中, 我們把物件抽象成一個點與邊集合的模型, 以邊來表示點與點之間的關係一個圖是個二元組, 用 G=(V, E) 表示,V 表示頂點的集合,E 表示邊的集合其中若 u, v V 之間有邊連通, 則有 (u, v) E 二元樹是樹的一種, 樹是圖的一種特例, 圖樹等到圖論再進一步介紹而關於有根樹的名詞 : 名詞定義深度 (depth) 該點與樹根的距離 ( 路徑中經過的邊數 ) 父節點 (parent) 若 (v, u) E 且 depth[ v ]<depth[ u ], 稱 v 是 u 的父節點子節點 (child) 若 (v, u) E 且 depth[ v ]<depth[ u ], 則 u 是 v 的子節點兄弟節點 (sibling) 具有相同父節點的節點互為兄弟節點度數 (degree) 一個節點 v 的子節點個數葉子 (leaf) 沒有子節點的節點, 又稱外部節點高度 (height) 最深的節點的深度 m 元樹 (m-ary tree) 所有節點的度數皆不超過 m 的樹子樹 (sub-tree) 取某一節點 v 為根, 所有 v( 含 ) 以下的節點邊形成的樹森林 (forest) 可能不連通但不含圈的圖, 即好幾棵樹形成的集合二元樹的儲存. 用相鄰串列 (adjacent list) 來存任意一棵樹 : 若總共有 V 個點, 則開 V 個鍊結串, 第 k 個鍊結串列儲存所有與節點 k 相鄰的點編號, 空間複雜度為 Θ( V )

11 . 二元樹中, 我們可以明確區分一個點的左子節點右子節點, 所以可以對每個點 v 直接儲存指向其左子右子節點的指標. 若一棵二元樹接近完整二元樹, 那我們可以直接開一個陣列 A[ 1 n ] 來代表這棵二元樹, 其中根為 A[ 1 ], 點 v 的左子節點為 A[ 2v ], 右子節點為 A[ 2v+1 ], 父節點為 A[ v/2 ]. 對任意一棵樹來說, 也可以用 left-child-right-sibling 的方式將其轉為二元樹儲存 : 對於每個點 v, 紀錄它最左邊的子節點, 以及它右邊的兄弟節點二元樹的走訪 (Traversal of Tree) 我們定義了二元樹的三種走訪方式 : PRE-ORDER ( v ) [ 前序走訪 ] If v Is Not Null Then Do 1 Print visit v 2 PRE-ORDER ( left[ v ] ) 3 PRE-ORDER ( right[ v ] ) IN-ORDER ( v ) [ 中序走訪 ] If v Is Not Null Then Do 1 IN -ORDER ( left[ v ] ) 2 Print visit v 3 IN -ORDER ( right[ v ] ) POST-ORDER ( v ) [ 後序走訪 ] If v Is Not Null Then Do 1 POST -ORDER ( left[ v ] ) 2 POST -ORDER ( right[ v ] ) 3 Print visit v. 完整二元樹 : 一棵二元樹的節點由上而下由左而又填滿排列. 滿枝二元樹 : 高度為 H 時, 具有 2 H+1-1 個節點的二元樹.n 個節點可以形成幾種不同的二元樹? ( 三元樹 m 元樹呢?). 給定一棵二元樹的中序走訪結果, 及前序或後序走訪結果, 怎麼重建出這棵樹? 練習題 :TIOJ 1106, 1107, 1108 二元搜尋樹 (Binary Search Tree) 二元搜尋樹是二元樹, 且對任意節點 v, 左子樹中節點的鍵值都比 v 的鍵值小, 右子樹中節點的鍵值都比 v 的鍵值大 ( 以下的虛擬碼當中,v 代表當前節點,data[v] 代表當前節點的資料,key[v] 代表當前節點的鍵值,left[v] 代表當前節點的左子節點,right[v] 代表當前節點的右子節點 ) 尋找節點依據二元搜尋樹的定義, 比較鍵值決定該往哪邊搜, 或是已經找到 FIND (v, key) 1 If v Is Null Then Return not found 2 If key<key[ v ] Then Return FIND (left[ v ], key) 3 Else If key>key[ v ] Then Return FIND (right[ v ], key) 4 Else Return v 插入節點插入的動作與刪除類似, 如果要插入的鍵值不在二元樹中, 那找到適當的位置之後把它插入 INSERT (v, key, data) 1 If key=key[ v ] Then Return v 2 If key<key[ v ] Then Do 3 If left[ v ] Is Null Then Do 4 left[ v ] NEW-NODE (key, data) 5 Return left[ v ] 6 Else Return INSERT (left[ v ], key, data)

12 7 Else Do 8 If right[ v ] Is Null Then Do 9 right [ v ] NEW-NODE (key, data) 10 Return right [ v ] 11 Else Return INSERT (right[ v ], key, data) 刪除節點考慮刪除節點 v 時的三種情況 :. 如果 v 是葉節點, 那直接刪除就好. 如果 v 只有一個子節點, 那把該子節點連到 v 的父親節點即可. 否則, 把 v 用左子節點中最右邊的一個節點 u 取代, 並將 u 刪除 REMOVE (v, key) 1 If v Is Null Then Return not found 2 If key<key[ v ] Then Do REMOVE (left[ v ], key) 3 Else If key>key[ v ] Then Do REMOVE (right[ v ], key) 4 If left[ v ] Is Null And right[ v ] Is Null Then Do 5 If v=left[ parent[ v ] ] Then Do left[ parent[ v ] ] Null 6 Else Do right[ parent[ v ] ] Null 7 DELETE-NODE (v) 8 Else If left[ v ] Is Null Then Do 9 If v=left[ parent[ v ] ] Then Do left[ parent[ v ] ] right[ v ] 10 Else Do right[ parent[ v ] ] right[ v ] 11 DELETE-NODE (v) 12 Else Do 13 p left[ v ] 14 While right[ p ] Is Not Null Do 15 p right[ p ] 16 key[ v ] key[ p ] 17 data[ v ] data[ p ] 18 REMOVE (p, key[ p ]) 若一棵二元搜尋樹的高度為 h, 則插入刪除查找操作的時間複雜度都是 O(h) 而元素插入二元搜尋樹的順序影響其高度很大, 最優是 log 2 (n+1), 最差是 n-1 在元素隨機插入二元搜尋樹的狀況下, 高度期望是 O(log h), 因此有種平衡的二元搜尋樹就是用此原理實現 ( 叫做 treap ) UVaOJ Lucky Number 首先先把所有的偶數刪去 :1, 3, 5, 7, 接著再每數 3 個數, 就把第 3 個數刪去 :1, 3, 7, 9, 13, 15, 然後每數 7 個數, 就把第 7 個數刪去依此類推, 最後剩下來的數字就稱為幸運數請問對任意 n (0<n 2,000,000),n 是不是兩個幸運數的和呢? TIOJ 1382 約瑟問題現在有 1, 2,, n 圍成一圈, 第 k 次數數數到第 a k 個數就要消失, 請問數消失的順序是?

演算法導入、ソート、データ構造、ハッシュ

演算法導入、ソート、データ構造、ハッシュ培訓 - 1 演算法導入ソートデータ構造ハッシュ演算法導入ソートデータ構造ハッシュ momohuang c2251393 chiangyo September 23, 2013 1 Schedule of the Year 1.1 Major Competition 9 12 11 10 12 10 TOI 的最 3 TOI 3 TOI 100 20 4 TOI 30 12 5 TOI