《高中數(shù)學(xué) 排序問題與算法的多樣性課件 北師大必修3》由會員分享，可在線閱讀，更多相關(guān)《高中數(shù)學(xué) 排序問題與算法的多樣性課件 北師大必修3（25頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、排序問題與算法多樣性排序問題與算法多樣性1.1.知識結(jié)構(gòu)知識結(jié)構(gòu)算法的概念算法的概念算法的步驟算法的步驟 算法的特點算法的特點算法算法小復(fù)習(xí)2.2.算法的特點算法的特點: :思路簡單清晰思路簡單清晰, ,敘述復(fù)雜敘述復(fù)雜, ,步驟步驟繁瑣繁瑣, ,計算量大計算量大, ,完全依靠人力難以完成完全依靠人力難以完成. .而這些而這些恰恰就是計算機的特長恰恰就是計算機的特長, ,它能不厭其煩地完成枯它能不厭其煩地完成枯燥的、重復(fù)的繁瑣的工作燥的、重復(fù)的繁瑣的工作. . 正因為這些正因為這些, ,現(xiàn)代算現(xiàn)代算法的作用之一就是使計算機代替人完成某些工法的作用之一就是使計算機代替人完成某些工作作, ,這也是

2、我們學(xué)習(xí)算法的重要原因之一這也是我們學(xué)習(xí)算法的重要原因之一. .明確性明確性: :算法對每一個步驟都有確切的算法對每一個步驟都有確切的, ,能有能有效執(zhí)行且得到確定結(jié)果的效執(zhí)行且得到確定結(jié)果的, ,不能模棱兩可。不能模棱兩可。有效性有效性: :算法從初始步驟開始算法從初始步驟開始, ,分為若干明確的分為若干明確的步驟步驟, ,每一步都只能有一個確定的繼任者每一步都只能有一個確定的繼任者, ,只有執(zhí)只有執(zhí)行完前一步才能進(jìn)入到后一步行完前一步才能進(jìn)入到后一步, ,并且每一步都確定并且每一步都確定無誤后無誤后, ,才能解決問題。才能解決問題。有限性有限性: :算法應(yīng)由有限步組成算法應(yīng)由有限步組成,

3、,至少對某些輸入至少對某些輸入, ,算法應(yīng)在有限多步內(nèi)結(jié)束算法應(yīng)在有限多步內(nèi)結(jié)束, ,并給出計算結(jié)果并給出計算結(jié)果不唯一性不唯一性: :求解某一個問題的解法不一定是唯一求解某一個問題的解法不一定是唯一的的, ,對于同一個問題可以有不同的解法對于同一個問題可以有不同的解法在函數(shù)的應(yīng)用部分在函數(shù)的應(yīng)用部分,我們學(xué)習(xí)了用二分法求方程我們學(xué)習(xí)了用二分法求方程f(x)=0的近似解的近似解.如圖所示如圖所示yxOabx*二分法的基本思想是二分法的基本思想是:將方程的將方程的有解區(qū)間分為兩個小區(qū)間有解區(qū)間分為兩個小區(qū)間,然后然后判斷解在哪個小區(qū)間判斷解在哪個小區(qū)間;繼續(xù)把有繼續(xù)把有解的區(qū)間一分為二進(jìn)行判斷解

4、的區(qū)間一分為二進(jìn)行判斷,如如此周而復(fù)始此周而復(fù)始,直到求出滿足精度直到求出滿足精度要求的近似解要求的近似解.1.確定有解區(qū)間確定有解區(qū)間 (f(a)f(b)0).ba,2.取取 的中點的中點ba,2bax3.計算函數(shù)計算函數(shù)f(x)在中點處的函數(shù)值在中點處的函數(shù)值)2(baf4.判斷函數(shù)值判斷函數(shù)值 是否為零是否為零)2(bafa)如果為零如果為零, 就是方程的解就是方程的解,問題就得到解決問題就得到解決.2bax)2(baff(a)1)若若 0,則得新有解區(qū)間為則得新有解區(qū)間為），（2baab) 如果函數(shù)值如果函數(shù)值 不為零不為零, 則分下則分下列兩種情形列兩種情形: )2(baf2)若若

5、則確定新的有解則確定新的有解區(qū)間為區(qū)間為, 02）（）（bafaf）（bba,25.判斷新的有解區(qū)間長度是否小于精判斷新的有解區(qū)間長度是否小于精確度確度:(1)如果新的有解區(qū)間長度大于精確如果新的有解區(qū)間長度大于精確度度,則在新的有解區(qū)間的基礎(chǔ)上重復(fù)則在新的有解區(qū)間的基礎(chǔ)上重復(fù)上述步驟上述步驟;(2)如果新的有解區(qū)間長度小于或等如果新的有解區(qū)間長度小于或等于精確度于精確度,則取新的有解區(qū)間的中點則取新的有解區(qū)間的中點為方程的近似解為方程的近似解.1.求方程求方程f(x)=x3+x2-1=0在區(qū)間在區(qū)間 上的實數(shù)解上的實數(shù)解,精確度為精確度為0.1.10，解解:1.因為因為f(0)=-1,f(1

6、)=1,f(0)f(1)0.110，2.取取 的區(qū)間中點的區(qū)間中點0.5;10，3.計算計算f(0.5)= -0.125;4.由于由于f(0.5)f(1)0.115.0，6.計算計算f(0.75)= - 0.1563;7.由于由于f(0.75)f(1)0.1175.0，8.取區(qū)間取區(qū)間 的中點的中點0.875;175.0，9.計算計算f(0.875)=0.4355510.由于由于f(0.75)f(0.875)0.1;875. 075. 0，11.取區(qū)間取區(qū)間 的中點的中點0.8125875. 075. 0，5.取取 的區(qū)間中點的區(qū)間中點0.75;15.0，11.計算計算f(0.8125)=0.

7、1965312.因因f(0.75)f(0.8125)0, 得區(qū)間得區(qū)間 精度精度0.8125-0.75=0.06250.18125. 075. 0，13.該區(qū)間一滿足精確度的要求該區(qū)間一滿足精確度的要求,所以取該所以取該區(qū)間的中點區(qū)間的中點0.78125,它是方程的一個近似它是方程的一個近似解解.排序問題與算法多樣性排序問題與算法多樣性 作者：tornado_lwp你會使用這些字典嗎？你會使用這些字典嗎？為了便于查詢和檢索，我們常常根據(jù)需要將被查尋的為了便于查詢和檢索，我們常常根據(jù)需要將被查尋的對象按照一定的順序排列，通常稱為對象按照一定的順序排列，通常稱為排序排序按照某種順序排列的數(shù)據(jù)列為按

8、照某種順序排列的數(shù)據(jù)列為有序列有序列你會從這些書籍中查你會從這些書籍中查閱你想要的東西嗎？閱你想要的東西嗎？新來的同學(xué)小黃身高新來的同學(xué)小黃身高1.75m，在班上是中等升高，在班上是中等升高，因為做操的需要，體育老師要將他插到隊中，你因為做操的需要，體育老師要將他插到隊中，你認(rèn)為老師應(yīng)該怎樣做？認(rèn)為老師應(yīng)該怎樣做？象這樣一種在象這樣一種在已經(jīng)按一定順序排好的序列已經(jīng)按一定順序排好的序列（有序列有序列）中插入，我們就叫它中插入，我們就叫它有序列直接插入排序有序列直接插入排序teacher小黃小黃？我們在一個已經(jīng)排好順序的一系列數(shù)中插入一個數(shù)據(jù)，成我們在一個已經(jīng)排好順序的一系列數(shù)中插入一個數(shù)據(jù)，成

9、為一個新的有序列，且仍按原來的規(guī)則排序。為一個新的有序列，且仍按原來的規(guī)則排序。要將要將8插入到插入到1,3,5,7,9,11,13中，中，我們怎樣考慮？我們怎樣考慮？確定確定8在原系列中的位置，使在原系列中的位置，使8小于或等于原系小于或等于原系列中右邊的數(shù)據(jù)，大于或等于左邊的數(shù)據(jù)列中右邊的數(shù)據(jù)，大于或等于左邊的數(shù)據(jù)將這個位置空出來，將數(shù)將這個位置空出來，將數(shù)據(jù)據(jù)8插進(jìn)去插進(jìn)去1357911138u對于一個有序列： - .欲將新數(shù)據(jù)欲將新數(shù)據(jù)A插入到有序列中，形成新的有序列，其做法插入到有序列中，形成新的有序列，其做法是：將數(shù)據(jù)是：將數(shù)據(jù)A與原有序列中的數(shù)據(jù)從右到左與原有序列中的數(shù)據(jù)從右到左

10、（也可以從左到右）進(jìn)行比較，直到發(fā)現(xiàn)某一（也可以從左到右）進(jìn)行比較，直到發(fā)現(xiàn)某一數(shù)據(jù)數(shù)據(jù) 使得使得 A， 把把A插入到插入到 的右邊；的右邊；如果數(shù)據(jù)如果數(shù)據(jù)A小于原有序列中的所有數(shù)據(jù)，則將小于原有序列中的所有數(shù)據(jù)，則將A插入到原序列的最左邊插入到原序列的最左邊na2a1aiaiaia例例1已知有一組系列已知有一組系列13,27,38,39,43,47,48,51,57,66,74,82，現(xiàn)要將數(shù)據(jù)現(xiàn)要將數(shù)據(jù)52插入到數(shù)據(jù)中。插入到數(shù)據(jù)中。數(shù)據(jù)系列12345678910 11 12原系列號13 27 38 39 43 47 48 51 57 66 74 82(1)請設(shè)計算法，確定請設(shè)計算法，確

11、定52在新數(shù)據(jù)中的位置，并畫出算法示意圖在新數(shù)據(jù)中的位置，并畫出算法示意圖(2)在確定在確定52的序列號后，請將的序列號后，請將52插入系列中插入系列中1.手工插入：手工插入： 把原序列中把原序列中912號的數(shù)據(jù)依次向右挪一位，號的數(shù)據(jù)依次向右挪一位，空出空出9號位置來，并插入號位置來，并插入52，得到一個新序列。，得到一個新序列?；蛘撸簝刹酵瑫r進(jìn)行，即從右邊最后一位開始，或者：兩步同時進(jìn)行，即從右邊最后一位開始，與與52比較，若比比較，若比52大就右挪，否則插入大就右挪，否則插入52. 確定確定52的序號：的序號：9;2.流程圖：流程圖：確定確定52的位置：從右到左比較系列數(shù)與的位置：從右到

12、左比較系列數(shù)與52的大小，使的大小，使52在兩個數(shù)之間，位置為在兩個數(shù)之間，位置為9數(shù)據(jù)數(shù)據(jù)號號12345678910111213原系原系列列1327 38394347485157667482排后排后系列系列1327 3839434748515257667482插入數(shù)據(jù)，位置插入數(shù)據(jù)，位置9以后的數(shù)據(jù)后移一位，在以后的數(shù)據(jù)后移一位，在9位置插入位置插入52 把數(shù)據(jù)52插入到有序列13,27,51,57,82中構(gòu)成一個新的有序列1.比較比較52與與82, 52 8252放放82 左邊左邊2.比較比較52與與57, 52 5152放放51與與57中間中間.得到新有序列得到新有序列13,27,51,

13、52,57,82分析：分析：1327515782首先選擇有序列的首先選擇有序列的“中間位置中間位置”數(shù)據(jù)數(shù)據(jù) =51,將將52與與 進(jìn)行比較，顯然進(jìn)行比較，顯然52 ,所以所以52應(yīng)排在應(yīng)排在 的的右邊右邊:132751525782然后取余下數(shù)據(jù)列然后取余下數(shù)據(jù)列 , 的的“中間位置中間位置”的數(shù)的數(shù)據(jù)據(jù) =57與與52比較，顯然比較，顯然52 ,因此因此52應(yīng)插到應(yīng)插到 的左邊：的左邊：小結(jié)：此排序方法稱為有序列的小結(jié)：此排序方法稱為有序列的折半插入排序折半插入排序1a2a3a4a5a5a4a3a2a1a3a3a3a4a5a4a4a4a3a有序列的折半插入排序的思想：有序列的折半插入排序的思

14、想：先將數(shù)據(jù)與先將數(shù)據(jù)與有序列中有序列中“中間位置中間位置”的數(shù)據(jù)進(jìn)行比較，若有序列的數(shù)據(jù)進(jìn)行比較，若有序列有有2n+1個數(shù)據(jù)則個數(shù)據(jù)則“中間位置中間位置”的數(shù)據(jù)指的是第個的數(shù)據(jù)指的是第個n+1數(shù)；若有序列有數(shù)；若有序列有2n個數(shù)據(jù)則個數(shù)據(jù)則“中間位置中間位置”的數(shù)的數(shù)據(jù)指的是第據(jù)指的是第n個數(shù)個數(shù); 如果新數(shù)據(jù)如果新數(shù)據(jù)小于小于“中間位置中間位置”的數(shù)據(jù)，則新數(shù)據(jù)的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)該在靠插入的位置應(yīng)該在靠左邊左邊的一半；如果新數(shù)據(jù)的一半；如果新數(shù)據(jù)等于等于“中間位置中間位置”的數(shù)據(jù)，則新數(shù)據(jù)應(yīng)插入到的數(shù)據(jù)，則新數(shù)據(jù)應(yīng)插入到“中間位中間位置置”的數(shù)據(jù)的的數(shù)據(jù)的右邊右邊；如果新數(shù)據(jù)大于

15、；如果新數(shù)據(jù)大于“中間位置中間位置”的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)靠的數(shù)據(jù)，則新數(shù)據(jù)插入的位置應(yīng)靠右邊右邊一半一半1)分別用兩種方法將數(shù)據(jù)分別用兩種方法將數(shù)據(jù)210插入到有序列插入到有序列6,56,98,114,156,320,421中，用自然語言中，用自然語言寫出排序算法的步驟寫出排序算法的步驟解：解：方法直接插入法：方法直接插入法：比較比較210與與421,210421210放放421左邊左邊比較比較210與與320,210156210放放156和和320之間之間得到新的有序列得到新的有序列6,56,98,114,156,210,320,421方法方法2折半插入法：折半插入法：取有序列中間數(shù)

16、取有序列中間數(shù)114210取取320左邊有序左邊有序列中間數(shù)列中間數(shù)156210將將210插入到插入到156和和320之間得出之間得出新的有序列新的有序列2)用直接插入排序法將用直接插入排序法將61插入插入13,37,40,55,65,76,97中，共比較了（）中，共比較了（）A,3次次 B,4次次 C,5次次 D,6次次思考題：思考題：如何將無序列如何將無序列15,3,10,12,8從小到大排從小到大排列，用自然語言寫出算法列，用自然語言寫出算法AB3)用折半插入排序法將用折半插入排序法將10插入有序列插入有序列7,9,11,12,15中中第第2次是次是10與（）的比較與（）的比較A,10與與7 B,10與與9 C,10與與12 D,10與與15有序列折半插入排序的思想和算法有序列折半插入排序的思想和算法有序列直接插入排序的思想和算法有序列直接插入排序的思想和算法注意理解同一個問題算法的多樣性注意理解同一個問題算法的多樣性及各自的優(yōu)缺點及各自的優(yōu)缺點