分治策略朱全民ppt課件(參考版)
2025-05-09 08:34本頁面
【正文】 。 check(p2,i+1,tail,state)。 i:=trunc((head+tail)/2)。 ? 設(shè)當前待接的開關(guān)為 head..tail,初始時為 1..m,則 左區(qū)間 head..[(head+tail1)/2], 開關(guān)集合為 p1={1..m} 右區(qū)間 [(head+tail1)/2]+1..tail, 開關(guān)集合為 p2={} ? 導線的連接狀態(tài) state=(0,1)，分別表示斷開和連接 ? 對區(qū)間進行檢測，對 p1中的每根導線發(fā)出 T命令，若開關(guān)狀態(tài)為閉合，且回答 N,或者開關(guān)狀態(tài)為斷開，且回答 Y,則移到 p2 2. 遞歸過程 ?check(p1,左區(qū)間 ,1state) ?check(p2,右區(qū)間 ,state) 3. 合并 當區(qū)間近近剩下一個開關(guān) (head=tail)且與之相連的導線集合 p1非空，則 p1中所有的導線與 head相連 ,并使得 ANS[i]=head,i屬于 p1 算法框架 Procedure check(p1,head,tail,state)。你的程序給出的命令總數(shù)應(yīng)不大于 900。 ? 你的程序可以給出一系列命令，將 T命令與 C命令以任意順序混合使用。若原來是斷開則變?yōu)榻油ǎ７粗?，回答?yīng)是 N。 ? 在命令 T和 C之后，你的程序應(yīng)從標準輸入（ standard input）讀入一行。 ? 改變開關(guān)狀態(tài)命令 C:C后面跟一個開關(guān)標號 。然后可以通過向標準輸出寫入一行以發(fā)出命令 (共 3種命令 )。我們可用一個探頭P在 A區(qū)進行測試 :如果探頭點到某根導線上，當且僅當該導線連到處接通狀態(tài)的開關(guān)時，燈 L才會點亮。 問題描述 測量 ? 你的程序應(yīng)作某些測量來確定，導線和開關(guān)怎樣連。每一根導線都被嚴格地連到這些開關(guān)中的某一個上 。 ? 一般說來，電纜含ｍ (1≤ｍ ≤90)根導線，在 A區(qū)標以1,2,…,m 。在 A區(qū) 3根導線標以 1， 2， 3。這個整理過程可以用一個遞歸過程來實現(xiàn)。 3. 左鄰括號的預(yù)算符為 “ *” 或 “ ”。 ? 樣例 : 輸入表達式 應(yīng)輸出表達式 a+b+(c) a+b+c (a*b)+c/(d*e) a*b+a/(d*e) a+b/(cd) a+b/(cd) 分析 對于四則運算表達式，我們分析一下哪些括號可以去掉。 ? 所有變量為單個小寫字母。 問題 7 ： 剔除多余括號 ? 輸入一個含有括號的四則運算表達式，可能含有多余的括號，編程整理該表達式，去掉所有多余的括號，原表達式中所有變量和運算符相對位置保持不變，并保持與原表達式等價。” ? 分治包含“分”和“治”兩層含義，如何分，分后如何“治”成為解決問題的關(guān)鍵所在 ? 不是所有的問題都可以采用分治，只有那些能將問題分成與原問題類似的子問題，并且歸并后符合原問題的性質(zhì)的問題，才能進行分治 ? 分治可進行二分，三分等等，具體怎么分，需看問題的性質(zhì)和分治后的效果。所以這個排序過程對整個問題的求解的正確性是沒有任何影響的。因為排序的過程是可以在遞歸求解子問題時就能夠完成的，算法的時間復(fù)雜度就降到了 O(nlogn)。而且這一統(tǒng)計步驟是能夠在線性時間內(nèi)完成的。 ?時間效率不盡如人意 ….. ?問題出現(xiàn)在哪里呢？？ 轉(zhuǎn)換思維 ? 用分治怎么樣 ? ? 首先將這一序列 A一分為二，分成兩個不同的序列 B、 C ? 如果求出了 B,C的逆序?qū)?,那么可由 B,C求出 A的逆序?qū)?. ? 如何來統(tǒng)計序列 B和序列 C之間的“逆序?qū)Α蹦兀? ? 如果還按照窮舉的思想來統(tǒng)計的話，那么我們采用分治法就沒有什么意義 !!! 提示 ? 在遞歸的求解 B、 C兩個序列中的逆序?qū)Φ膫€數(shù)以后，如果對 B、 C兩個序列當中的元素進行排序的話，要統(tǒng)計 B、C兩個序列之間的“逆序?qū)Α笔欠浅Ｈ菀椎?. ? 如圖 ? 排序前 ? 排序后 ? 在 B數(shù)組當中，首先， B中的 6， 5， 4都與 C數(shù)組當中的 3，2， 2都構(gòu)成了“逆序?qū)Α保?2不會構(gòu)成逆序?qū)?，因?B、C兩個數(shù)組之間構(gòu)成的逆序?qū)Φ膫€數(shù)為 3+3+3=9。 ? n≤10000。 end。 {繼續(xù)對左子序列遞歸排序 } Merge_Sort(A, Q + 1, R)。 begin if P R then begin {若子序列 A中不止一個元素 }
教學課件相關(guān)推薦
鄂ICP備17016276號-1