分治策略朱全民ppt課件-資料下載頁
2025-05-06 08:34本頁面
【正文】 鄰括號的預(yù)算符為 “ *” 或 “ ”。而 op為 “ +”或 “ ”，則保留括號，即 … *（ s1+s2） … 或 … （ s1+s2） … 或 … *（ s1s2） … 或 … （ s1s2） … 4. 右鄰括號的運(yùn)算符為 “ *” 或 “ /”，而 op為 “ +”或 “ ”，原式中的 op運(yùn)算必須優(yōu)先進(jìn)行，因此括號不去除，即（ s1+s2）* … 5. 除上述情況外，可以括號去除，即 … s1 op s2… 等價(jià)于 … （ s1 op s2） … ? 我們從最里層嵌套的括號開始，依據(jù)上述規(guī)律逐步向外進(jìn)行括號整理，直至最外層的括號保留或去除為止。這個(gè)整理過程可以用一個(gè)遞歸過程來實(shí)現(xiàn)。 剔除“ ((a+b)*f)(i/j)”中多余的括號 問題 8： 導(dǎo)線和開關(guān) ? 如上圖是一個(gè)具有 3根導(dǎo)線的電纜把 A區(qū)和 B區(qū)連接起來。在 A區(qū) 3根導(dǎo)線標(biāo)以 1， 2， 3。在 B區(qū)導(dǎo)線 1和３被連到開關(guān) 3，導(dǎo)線 2連到開關(guān) 1。 ? 一般說來，電纜含ｍ (1≤ｍ ≤90)根導(dǎo)線，在 A區(qū)標(biāo)以1,2,…,m 。在 B 區(qū)有ｍ個(gè)開關(guān)，標(biāo)為 1， 2， … ，ｍ。每一根導(dǎo)線都被嚴(yán)格地連到這些開關(guān)中的某一個(gè)上 。 每一個(gè)開關(guān)上可以連有 0根或多根導(dǎo)線。 問題描述 測量 ? 你的程序應(yīng)作某些測量來確定，導(dǎo)線和開關(guān)怎樣連。 每個(gè)開關(guān)或處于接通或處于斷開狀態(tài)，開關(guān)的初始狀態(tài)為斷開。我們可用一個(gè)探頭P在 A區(qū)進(jìn)行測試 :如果探頭點(diǎn)到某根導(dǎo)線上，當(dāng)且僅當(dāng)該導(dǎo)線連到處接通狀態(tài)的開關(guān)時(shí)，燈 L才會點(diǎn)亮。 ? 你的程序從標(biāo)準(zhǔn)輸入讀入一行以得到數(shù)字ｍ 。然后可以通過向標(biāo)準(zhǔn)輸出寫入一行以發(fā)出命令 (共 3種命令 )。每種命令的開頭是一個(gè)大寫字母 : ? 測試導(dǎo)線命令 T:T后面跟一個(gè)導(dǎo)線標(biāo)號 。 ? 改變開關(guān)狀態(tài)命令 C:C后面跟一個(gè)開關(guān)標(biāo)號 。 ? 完成命令 D:D后面跟的是一個(gè)表列（ LIST），該表列中的第ｉ個(gè)元素代表與導(dǎo)線ｉ相連的開關(guān)號。 ? 在命令 T和 C之后，你的程序應(yīng)從標(biāo)準(zhǔn)輸入（ standard input）讀入一行。 若開關(guān)狀態(tài)能使燈亮，則命令 T的回答應(yīng)是 Y。反之，回答應(yīng)是 N。命令 C的作用是改變開關(guān)的狀態(tài)（若原來是接通則變?yōu)閿嚅_ 。若原來是斷開則變?yōu)榻油ǎ?。?C命令的回答是作為一種反饋信號。 ? 你的程序可以給出一系列命令，將 T命令與 C命令以任意順序混合使用。最后給出命令 D，并結(jié)束。你的程序給出的命令總數(shù)應(yīng)不大于 900。 樣例 Standard Output Standard Input C 3 T 1 T 2 T 3 C 3 C 2 T 2 D 3 1 3 3 Y Y N Y N Y N 分析 ? 為了使導(dǎo)線和開關(guān)的連接工作有規(guī)律地進(jìn)行，我們不妨采用二分法。 ? 設(shè)當(dāng)前待接的開關(guān)為 head..tail,初始時(shí)為 1..m,則 左區(qū)間 head..[(head+tail1)/2], 開關(guān)集合為 p1={1..m} 右區(qū)間 [(head+tail1)/2]+1..tail, 開關(guān)集合為 p2={} ? 導(dǎo)線的連接狀態(tài) state=(0,1)，分別表示斷開和連接 ? 對區(qū)間進(jìn)行檢測，對 p1中的每根導(dǎo)線發(fā)出 T命令，若開關(guān)狀態(tài)為閉合，且回答 N,或者開關(guān)狀態(tài)為斷開，且回答 Y,則移到 p2 2. 遞歸過程 ?check(p1,左區(qū)間 ,1state) ?check(p2,右區(qū)間 ,state) 3. 合并 當(dāng)區(qū)間近近剩下一個(gè)開關(guān) (head=tail)且與之相連的導(dǎo)線集合 p1非空，則 p1中所有的導(dǎo)線與 head相連 ,并使得 ANS[i]=head,i屬于 p1 算法框架 Procedure check(p1,head,tail,state)。 Begin if p1[] then if head =tail then begin 計(jì)算左區(qū)間 p1； 通過 c命令和用戶應(yīng)答，將左區(qū)間開關(guān)狀態(tài)取反； 右區(qū)間 p2=[]； 對 p1中的每根導(dǎo)線發(fā)出 T命令，若開關(guān)狀態(tài)為閉合，且回答 N,或者開關(guān)狀態(tài)為斷開，且回答 Y,則移到 p2； end。 i:=trunc((head+tail)/2)。 check(p1,head,i,state)。 check(p2,i+1,tail,state)。 End。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1