算法設(shè)計(jì)與分析 王紅梅 第二版 第5章_ 減治法

1、教學(xué)重點(diǎn)教學(xué)重點(diǎn)減治法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的減治思想減治法的設(shè)計(jì)思想，各種經(jīng)典問(wèn)題的減治思想教學(xué)難點(diǎn)教學(xué)難點(diǎn)二叉查找樹(shù)，堆排序二叉查找樹(shù)，堆排序教學(xué)內(nèi)容教學(xué)內(nèi)容及目標(biāo)及目標(biāo)知識(shí)點(diǎn)知識(shí)點(diǎn)教學(xué)要求教學(xué)要求了解了解理解理解掌握掌握熟練掌握熟練掌握減治法的設(shè)計(jì)思想減治法的設(shè)計(jì)思想折半查找折半查找二叉查找樹(shù)二叉查找樹(shù)選擇問(wèn)題選擇問(wèn)題插入排序插入排序堆排序堆排序淘汰賽冠軍問(wèn)題淘汰賽冠軍問(wèn)題假幣問(wèn)題假幣問(wèn)題1122naanaannn111)2/(0)(nnnTnT對(duì)比分治法：對(duì)比分治法： 足夠小nnfnTngnT)()2/(2)()(步驟步驟操作說(shuō)明操作說(shuō)明序列序列A序列序列B1初始序列初始序列11,

2、13, 15, 17, 192, 4, 10, 15, 202分別求中位數(shù)分別求中位數(shù)11, 13, 15, 17, 192, 4, 10, 15, 2031510，結(jié)果在，結(jié)果在10, 15之間之間舍棄舍棄15之后元素，之后元素，11,13,15舍棄舍棄10之前元素，之前元素，10,15,204分別求中位數(shù)分別求中位數(shù)11,13,1510,15,2051315，結(jié)果在，結(jié)果在11, 15之間之間舍棄舍棄13之前元素，之前元素，13,15舍棄舍棄15之后元素，之后元素，10,156分別求中位數(shù)分別求中位數(shù)13,1510,1571013，結(jié)果在，結(jié)果在10, 13之間之間舍棄舍棄13之后元素，之

3、后元素，13舍棄舍棄10之前元素，之前元素，158長(zhǎng)度為長(zhǎng)度為1，較小者為所求，較小者為所求13151log2nC+描述按按63,90,55,58,70,42,10,45,83,67順序構(gòu)造的二叉排序樹(shù)順序構(gòu)造的二叉排序樹(shù)584270906345558367101log2n算法算法選擇問(wèn)題選擇問(wèn)題輸入：無(wú)序序列輸入：無(wú)序序列r ，位置，位置k輸出：返回第輸出：返回第k小的元素值小的元素值 1. i=1; j=n; /設(shè)置初始查找區(qū)間設(shè)置初始查找區(qū)間 2. 以以ri為軸值對(duì)序列為軸值對(duì)序列rirj進(jìn)行一次劃分，得到軸進(jìn)行一次劃分，得到軸值的位置值的位置s; 3. 將軸值位置將軸值位置s與與k比較

4、比較 3.1 如果如果k=s，則將，則將rs作為結(jié)果返回；作為結(jié)果返回； 3.2 否則，如果否則，如果ks，則，則j=s-1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2； 3.3 否則，否則，i=s+1，轉(zhuǎn)步驟，轉(zhuǎn)步驟2；( )(2)( )( )T nT nO nO nr1r2ri-1r1r2ri-1ri 初始：（初始：（49）38 13 76 27 49 （38 49）13 76 27 49 （13 38 49）76 27 49 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）212125插入排序插入排序2522222522211025211510

5、2525*2521151025*252118151018101825*25插入排序算法性能分析插入排序算法性能分析插入排序算法性能分析插入排序算法性能分析12121kknkkn221knk2log11log2nk1 19 98 810106 616162 211114 45 5n=10，故從第，故從第 10/2 5個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行調(diào)整個(gè)結(jié)點(diǎn)開(kāi)始進(jìn)行調(diào)整 1 19 98 810106 616162 211115 54 41 19 98 810106 611112 216165 54 41 19 98 810106 611112 216165 54 41 19 98 810106 611111616

6、2 25 54 41 19 98 810106 62 2161611115 54 416169 98 810106 62 21 111115 54 416169 98 810106 62 211111 15 54 416169 98 81 16 62 2111110105 54 4qRi左、右子樹(shù)是堆，子樹(shù)的根為各自子樹(shù)中關(guān)鍵字最大者，左、右子樹(shù)是堆，子樹(shù)的根為各自子樹(shù)中關(guān)鍵字最大者，q將將Ri和其左、右孩子中關(guān)鍵字最大者進(jìn)行比較。和其左、右孩子中關(guān)鍵字最大者進(jìn)行比較。若若Ri最大，則無(wú)需調(diào)整，以其為根的子樹(shù)已是堆；最大，則無(wú)需調(diào)整，以其為根的子樹(shù)已是堆；否則，將否則，將Ri和具有最大關(guān)鍵字的

7、左孩子和具有最大關(guān)鍵字的左孩子R2i或右孩子或右孩子R2i+1進(jìn)行交換。進(jìn)行交換。q交換后以交換后以R2i和和R2i+1為根的子樹(shù)可能不再是堆，但其左、為根的子樹(shù)可能不再是堆，但其左、右子樹(shù)仍然是堆，于是重復(fù)上述過(guò)程，右子樹(shù)仍然是堆，于是重復(fù)上述過(guò)程，將子樹(shù)調(diào)整為堆將子樹(shù)調(diào)整為堆，如此逐層遞推下去，最多可能一直調(diào)整到樹(shù)葉。如此逐層遞推下去，最多可能一直調(diào)整到樹(shù)葉。q這一過(guò)程就像過(guò)篩子一樣，把較小的關(guān)鍵字篩下去，而將最大這一過(guò)程就像過(guò)篩子一樣，把較小的關(guān)鍵字篩下去，而將最大關(guān)鍵字一層層地選擇上來(lái)。關(guān)鍵字一層層地選擇上來(lái)。 大根堆大根堆C+描述16169 98 81 16 62 2111110105 54 44 49 98 81 16 62 2111110105 511119 98 81 16 62 210104 45 52 29 98 81 16 610104 45 510109 98 81 16 65 54 42 21 19 98 86 65 54 42 29 98 81 16 65 54 42 21 18 86 65 54 42 28 86 61 15 54 42 21 16 65 54 42 26 61 15 54 42 22 21 15 54 45 51 14 42 22 21 14 44 41 12 21 12 22 21 11 112( )2 ( /