久久久国产精品秘人口麻豆|永久免费AV无语国产|人成电影免费中文字幕|久久AV嫩草影院2

    1. <dfn id="yitbn"><samp id="yitbn"><progress id="yitbn"></progress></samp></dfn>

          <div id="yitbn"></div>

          1. 首頁 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實(shí)用文檔 求職招聘 論文下載
            2011中考 | 2011高考 | 2012考研 | 考研培訓(xùn) | 在職研 | 自學(xué)考試 | 成人高考 | 法律碩士 | MBA考試
            MPA考試 | 中科院
            四六級 | 職稱英語 | 商務(wù)英語 | 公共英語 | 托福 | 雅思 | 專四專八 | 口譯筆譯 | 博思 | GRE GMAT
            新概念英語 | 成人英語三級 | 申碩英語 | 攻碩英語 | 職稱日語 | 日語學(xué)習(xí) | 法語 | 德語 | 韓語
            計(jì)算機(jī)等級考試 | 軟件水平考試 | 職稱計(jì)算機(jī) | 微軟認(rèn)證 | 思科認(rèn)證 | Oracle認(rèn)證 | Linux認(rèn)證
            華為認(rèn)證 | Java認(rèn)證
            公務(wù)員 | 報(bào)關(guān)員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問 | 導(dǎo)游資格
            報(bào)檢員 | 教師資格 | 社會工作者 | 外銷員 | 國際商務(wù)師 | 跟單員 | 單證員 | 物流師 | 價(jià)格鑒證師
            人力資源 | 管理咨詢師考試 | 秘書資格 | 心理咨詢師考試 | 出版專業(yè)資格 | 廣告師職業(yè)水平
            駕駛員 | 網(wǎng)絡(luò)編輯
            衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護(hù)士
            會計(jì)從業(yè)資格考試會計(jì)證) | 經(jīng)濟(jì)師 | 會計(jì)職稱 | 注冊會計(jì)師 | 審計(jì)師 | 注冊稅務(wù)師
            注冊資產(chǎn)評估師 | 高級會計(jì)師 | ACCA | 統(tǒng)計(jì)師 | 精算師 | 理財(cái)規(guī)劃師 | 國際內(nèi)審師
            一級建造師 | 二級建造師 | 造價(jià)工程師 | 造價(jià)員 | 咨詢工程師 | 監(jiān)理工程師 | 安全工程師
            質(zhì)量工程師 | 物業(yè)管理師 | 招標(biāo)師 | 結(jié)構(gòu)工程師 | 建筑師 | 房地產(chǎn)估價(jià)師 | 土地估價(jià)師 | 巖土師
            設(shè)備監(jiān)理師 | 房地產(chǎn)經(jīng)紀(jì)人 | 投資項(xiàng)目管理師 | 土地登記代理人 | 環(huán)境影響評價(jià)師 | 環(huán)保工程師
            城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價(jià)師 | 安全評價(jià)師 | 電氣工程師 | 注冊測繪師 | 注冊計(jì)量師
            繽紛校園 | 實(shí)用文檔 | 英語學(xué)習(xí) | 作文大全 | 求職招聘 | 論文下載 | 訪談 | 游戲
            您現(xiàn)在的位置: 考試吧(eeeigo.com) > 軟件水平考試 > 復(fù)習(xí)資料 > 其它資料 > 正文

            軟件水平考試常用算法設(shè)計(jì)方法

             

              分治法的合并步驟是算法的關(guān)鍵所在。有些問題的合并方法比較明顯,有些問題合并方法比較復(fù)雜,或者是有多種合并方案;或者是合并方案不明顯。究竟應(yīng)該怎樣合并,沒有統(tǒng)一的模式,需要具體問題具體分析。
              【問題】 大整數(shù)乘法
              問題描述:
              通常,在分析一個算法的計(jì)算復(fù)雜性時(shí),都將加法和乘法運(yùn)算當(dāng)作是基本運(yùn)算來處理,即將執(zhí)行一次加法或乘法運(yùn)算所需的計(jì)算時(shí)間當(dāng)作一個僅取決于計(jì)算機(jī)硬件處理速度的常數(shù)。

              這個假定僅在計(jì)算機(jī)硬件能對參加運(yùn)算的整數(shù)直接表示和處理時(shí)才是合理的。然而,在某些情況下,我們要處理很大的整數(shù),它無法在計(jì)算機(jī)硬件能直接表示的范圍內(nèi)進(jìn)行處理。若用浮點(diǎn)數(shù)來表示它,則只能近似地表示它的大小,計(jì)算結(jié)果中的有效數(shù)字也受到限制。若要精確地表示大整數(shù)并在計(jì)算結(jié)果中要求精確地得到所有位數(shù)上的數(shù)字,就必須用軟件的方法來實(shí)現(xiàn)大整數(shù)的算術(shù)運(yùn)算。

              請?jiān)O(shè)計(jì)一個有效的算法,可以進(jìn)行兩個n位大整數(shù)的乘法運(yùn)算。

              設(shè)X和Y都是n位的二進(jìn)制整數(shù),現(xiàn)在要計(jì)算它們的乘積XY。我們可以用小學(xué)所學(xué)的方法來設(shè)計(jì)一個計(jì)算乘積XY的算法,但是這樣做計(jì)算步驟太多,顯得效率較低。如果將每2個1位數(shù)的乘法或加法看作一步運(yùn)算,那么這種方法要作O(n2)步運(yùn)算才能求出乘積XY。下面我們用分治法來設(shè)計(jì)一個更有效的大整數(shù)乘積算法。
              
              圖6-3 大整數(shù)X和Y的分段
              我們將n位的二進(jìn)制整數(shù)X和Y各分為2段,每段的長為n/2位(為簡單起見,假設(shè)n是2的冪),如圖6-3所示。
              由此,X=A2n/2+B,Y=C2n/2+D。這樣,X和Y的乘積為:
              XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)
              如果按式(1)計(jì)算XY,則我們必須進(jìn)行4次n/2位整數(shù)的乘法(AC,AD,BC和BD),以及3次不超過n位的整數(shù)加法(分別對應(yīng)于式(1)中的加號),此外還要做2次移位(分別對應(yīng)于式(1)中乘2n和乘2n/2)。所有這些加法和移位共用O(n)步運(yùn)算。設(shè)T(n)是2個n位整數(shù)相乘所需的運(yùn)算總數(shù),則由式(1),我們有:
               (2)由此可得T(n)=O(n2)。因此,用(1)式來計(jì)算X和Y的乘積并不比小學(xué)生的方法更有效。要想改進(jìn)算法的計(jì)算復(fù)雜性,必須減少乘法次數(shù)。為此我們把XY寫成另一種形式:
              XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
              雖然,式(3)看起來比式(1)復(fù)雜些,但它僅需做3次n/2位整數(shù)的乘法(AC,BD和(A-B)(D-C)),6次加、減法和2次移位。由此可得:
               (4)
              用解遞歸方程的套用公式法馬上可得其解為T(n)=O(nlog3)=O(n1.59)。利用式(3),并考慮到X和Y的符號對結(jié)果的影響,我們給出大整數(shù)相乘的完整算法MULT如下:
              function MULT(X,Y,n); {X和Y為2個小于2n的整數(shù),返回結(jié)果為X和Y的乘積XY}
              begin
              S=SIGN(X)*SIGN(Y); {S為X和Y的符號乘積}
              X=ABS(X);
              Y=ABS(Y); {X和Y分別取絕對值}
              if n=1 then
              if (X=1)and(Y=1) then return(S)
              else return(0)
              else begin
              A=X的左邊n/2位;
              B=X的右邊n/2位;
              C=Y的左邊n/2位;
              D=Y的右邊n/2位;
              ml=MULT(A,C,n/2);
              m2=MULT(A-B,D-C,n/2);
              m3=MULT(B,D,n/2);
              S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
              return(S);
              end;
              end;
              上述二進(jìn)制大整數(shù)乘法同樣可應(yīng)用于十進(jìn)制大整數(shù)的乘法以提高乘法的效率減少乘法次數(shù)。
              【問題】 最接近點(diǎn)對問題
              問題描述:
              在應(yīng)用中,常用諸如點(diǎn)、圓等簡單的幾何對象代表現(xiàn)實(shí)世界中的實(shí)體。在涉及這些幾何對象的問題中,常需要了解其鄰域中其他幾何對象的信息。例如,在空中交通控制問題中,若將飛機(jī)作為空間中移動的一個點(diǎn)來看待,則具有最大碰撞危險(xiǎn)的2架飛機(jī),就是這個空間中最接近的一對點(diǎn)。這類問題是計(jì)算幾何學(xué)中研究的基本問題之一。下面我們著重考慮平面上的最接近點(diǎn)對問題。

              最接近點(diǎn)對問題的提法是:給定平面上n個點(diǎn),找其中的一對點(diǎn),使得在n個點(diǎn)的所有點(diǎn)對中,該點(diǎn)對的距離最小。

              嚴(yán)格地說,最接近點(diǎn)對可能多于1對。為了簡單起見,這里只限于找其中的一對。

              這個問題很容易理解,似乎也不難解決。我們只要將每一點(diǎn)與其他n-1個點(diǎn)的距離算出,找出達(dá)到最小距離的兩個點(diǎn)即可。然而,這樣做效率太低,需要O(n2)的計(jì)算時(shí)間。我們能否找到問題的一個O (nlogn)算法。

              這個問題顯然滿足分治法的第一個和第二個適用條件,我們考慮將所給的平面上n個點(diǎn)的集合S分成2個子集S1和S2,每個子集中約有n/2個點(diǎn),然后在每個子集中遞歸地求其最接近的點(diǎn)對。在這里,一個關(guān)鍵的問題是如何實(shí)現(xiàn)分治法中的合并步驟,即由S1和S2的最接近點(diǎn)對,如何求得原集合S中的最接近點(diǎn)對,因?yàn)镾1和S2的最接近點(diǎn)對未必就是S的最接近點(diǎn)對。如果組成S的最接近點(diǎn)對的2個點(diǎn)都在S1中或都在S2中,則問題很容易解決。但是,如果這2個點(diǎn)分別在S1和S2中,則對于S1中任一點(diǎn)p,S2中最多只有n/2個點(diǎn)與它構(gòu)成最接近點(diǎn)對的候選者,仍需做n2/4次計(jì)算和比較才能確定S的最接近點(diǎn)對。因此,依此思路,合并步驟耗時(shí)為O(n2)。整個算法所需計(jì)算時(shí)間T(n)應(yīng)滿足:

              T(n)=2T(n/2)+O(n2)

              它的解為T(n)=O(n2),即與合并步驟的耗時(shí)同階,顯示不出比用窮舉的方法好。從解遞歸方程的套用公式法,我們看到問題出在合并步驟耗時(shí)太多。這啟發(fā)我們把注意力放在合并步驟上。

              為了使問題易于理解和分析,我們先來考慮一維的情形。此時(shí)S中的n個點(diǎn)退化為x軸上的n個實(shí)數(shù)x1、x2、…、xn。最接近點(diǎn)對即為這n個實(shí)數(shù)中相差最小的2個實(shí)數(shù)。我們顯然可以先將x1、x2、…、xn排好序,然后,用一次線性掃描就可以找出最接近點(diǎn)對。這種方法主要計(jì)算時(shí)間花在排序上,因此如在排序算法中所證明的,耗時(shí)為O(nlogn)。然而這種方法無法直接推廣到二維的情形。因此,對這種一維的簡單情形,我們還是嘗試用分治法來求解,并希望能推廣到二維的情形。

              假設(shè)我們用x軸上某個點(diǎn)m將S劃分為2個子集S1和S2,使得S1={x∈S | x≤m};S2={x∈S | x>m}。這樣一來,對于所有p∈S1和q∈S2有p  遞歸地在S1和S2上找出其最接近點(diǎn)對{p1,p2}和{q1,q2},并設(shè)δ=min{|p1-p2|,|q1-q2|},S中的最接近點(diǎn)對或者是{p1,p2},或者是{q1,q2},或者是某個{p3,q3},其中p3∈S1且q3∈S2。如圖1所示。
              
              圖1 一維情形的分治法
              我們注意到,如果S的最接近點(diǎn)對是{p3,q3},即 | p3-q3 | < δ,則p3和q3兩者與m的距離不超過δ,即 | p3-m | < δ,| q3-m | < δ,也就是說,p3∈(m-δ,m),q3∈(m,m+δ)。由于在S1中,每個長度為δ的半閉區(qū)間至多包含一個點(diǎn)(否則必有兩點(diǎn)距離小于δ),并且m是S1和S2的分割點(diǎn),因此(m-δ,m)中至多包含S中的一個點(diǎn)。同理,(m,m+δ)中也至多包含S中的一個點(diǎn)。由圖1可以看出,如果(m-δ,m)中有S中的點(diǎn),則此點(diǎn)就是S1中最大點(diǎn)。同理,如果(m,m+δ)中有S中的點(diǎn),則此點(diǎn)就是S2中最小點(diǎn)。因此,我們用線性時(shí)間就能找到區(qū)間(m-δ,m)和(m,m+δ)中所有點(diǎn),即p3和q3。從而我們用線性時(shí)間就可以將S1的解和S2的解合并成為S的解。也就是說,按這種分治策略,合并步可在O(n)時(shí)間內(nèi)完成。這樣是否就可以得到一個有效的算法了呢?

              還有一個問題需要認(rèn)真考慮,即分割點(diǎn)m的選取,及S1和S2的劃分。選取分割點(diǎn)m的一個基本要求是由此導(dǎo)出集合S的一個線性分割,即S=S1∪S2 ,S1∩S2=Φ,且S1 {x | x≤m};S2 {x | x>m}。容易看出,如果選取m=[max(S)+min(S)]/2,可以滿足線性分割的要求。選取分割點(diǎn)后,再用O(n)時(shí)間即可將S劃分成S1={x∈S | x≤m}和S2={x∈S | x>m}。然而,這樣選取分割點(diǎn)m,有可能造成劃分出的子集S1和S2的不平衡。例如在最壞情況下,|S1|=1,|S2|=n-1,由此產(chǎn)生的分治法在最壞情況下所需的計(jì)算時(shí)間T(n)應(yīng)滿足遞歸方程:
              T(n)=T(n-1)+O(n)

              它的解是T(n)=O(n2)。這種效率降低的現(xiàn)象可以通過分治法中“平衡子問題”的方法加以解決。也就是說,我們可以通過適當(dāng)選擇分割點(diǎn)m,使S1和S2中有大致相等個數(shù)的點(diǎn)。自然地,我們會想到用S的n個點(diǎn)的坐標(biāo)的中位數(shù)來作分割點(diǎn)。在選擇算法中介紹的選取中位數(shù)的線性時(shí)間算法使我們可以在O(n)時(shí)間內(nèi)確定一個平衡的分割點(diǎn)m。

              至此,我們可以設(shè)計(jì)出一個求一維點(diǎn)集S中最接近點(diǎn)對的距離的算法pair如下。
              Float pair(S);
              { if | S | =2 δ= | x[2]-x[1] | /*x[1..n]存放的是S中n個點(diǎn)的坐標(biāo)*/
              else
              { if ( | S | =1) δ=∞
               else
              { m=S中各點(diǎn)的坐標(biāo)值的中位數(shù);
               構(gòu)造S1和S2,使S1={x∈S | x≤m},S2={x∈S | x>m};
              δ1=pair(S1);
               δ2=pair(S2);
               p=max(S1);
               q=min(S2);
               δ=min(δ1,δ2,q-p);
              }
              return(δ);
              }
              由以上的分析可知,該算法的分割步驟和合并步驟總共耗時(shí)O(n)。因此,算法耗費(fèi)的計(jì)算時(shí)間T(n)滿足遞歸方程:
              
              解此遞歸方程可得T(n)=O(nlogn)。
              
              【問題】循環(huán)賽日程表
              問題描述:設(shè)有n=2k個運(yùn)動員要進(jìn)行網(wǎng)球循環(huán)賽,F(xiàn)要設(shè)計(jì)一個滿足以下要求的比賽日程表:
             。1)每個選手必須與其他n-1個選手各賽一次;
              (2)每個選手一天只能參賽一次;
              (3)循環(huán)賽在n-1天內(nèi)結(jié)束。
              請按此要求將比賽日程表設(shè)計(jì)成有n行和n-1列的一個表。在表中的第i行,第j列處填入第i個選手在第j天所遇到的選手。其中1≤i≤n,1≤j≤n-1。

              按分治策略,我們可以將所有的選手分為兩半,則n個選手的比賽日程表可以通過n/2個選手的比賽日程表來決定。遞歸地用這種一分為二的策略對選手進(jìn)行劃分,直到只剩下兩個選手時(shí),比賽日程表的制定就變得很簡單。這時(shí)只要讓這兩個選手進(jìn)行比賽就可以了。
              
               1 2 3 4 5 6 7
               1 2 3 4 5 6 7 8
               2 1 4 3 6 7 8 5
               3 4 1 2 7 8 5 6
               1 2 3 4 3 2 1 8 5 6 7
               1 2 3 4 5 6 7 8 1 4 3 2
               1 2 1 4 3 6 5 8 7 2 1 4 3
              1 2 3 4 1 2 7 8 5 6 3 2 1 4
              2 1 4 3 2 1 8 7 6 5 4 3 2 1
             。1) (2) (3)
              圖1 2個、4個和8個選手的比賽日程表
              圖1所列出的正方形表(3)是8個選手的比賽日程表。其中左上角與左下角的兩小塊分別為選手1至選手4和選手5至選手8前3天的比賽日程。據(jù)此,將左上角小塊中的所有數(shù)字按其相對位置抄到右下角,又將左下角小塊中的所有數(shù)字按其相對位置抄到右上角,這樣我們就分別安排好了選手1至選手4和選手5至選手8在后4天的比賽日程。依此思想容易將這個比賽日程表推廣到具有任意多個選手的情形。

              八、動態(tài)規(guī)劃法

               經(jīng)常會遇到復(fù)雜問題不能簡單地分解成幾個子問題,而會分解出一系列的子問題。簡單地采用把大問題分解成子問題,并綜合子問題的解導(dǎo)出大問題的解的方法,問題求解耗時(shí)會按問題規(guī)模呈冪級數(shù)增加。

               為了節(jié)約重復(fù)求相同子問題的時(shí)間,引入一個數(shù)組,不管它們是否對最終解有用,把所有子問題的解存于該數(shù)組中,這就是動態(tài)規(guī)劃法所采用的基本方法。以下先用實(shí)例說明動態(tài)規(guī)劃方法的使用。

              【問題】 求兩字符序列的最長公共字符子序列
              問題描述:字符序列的子序列是指從給定字符序列中隨意地(不一定連續(xù))去掉若干個字符(可能一個也不去掉)后所形成的字符序列。令給定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一個嚴(yán)格遞增下標(biāo)序列,使得對所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一個子序列。

              給定兩個序列A和B,稱序列Z是A和B的公共子序列,是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。

              如采用列舉A的所有子序列,并一一檢查其是否又是B的子序列,并隨時(shí)記錄所發(fā)現(xiàn)的子序列,最終求出最長公共子序列。這種方法因耗時(shí)太多而不可取。

              考慮最長公共子序列問題如何分解成子問題,設(shè)A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”為它們的最長公共子序列。不難證明有以下性質(zhì):
             。1) 如果am-1=bn-1,則zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一個最長公共子序列;
              (2) 如果am-1!=bn-1,則若zk-1!=am-1,蘊(yùn)涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一個最長公共子序列;
             。3) 如果am-1!=bn-1,則若zk-1!=bn-1,蘊(yùn)涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一個最長公共子序列。
              這樣,在找A和B的公共子序列時(shí),如有am-1=bn-1,則進(jìn)一步解決一個子問題,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一個最長公共子序列;如果am-1!=bn-1,則要解決兩個子問題,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一個最長公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一個最長公共子序列,再取兩者中較長者作為A和B的最長公共子序列。
              定義c[i][j]為序列“a0,a1,…,ai-2”和“b0,b1,…,bj-1”的最長公共子序列的長度,計(jì)算c[i][j]可遞歸地表述如下:
             。1)c[i][j]=0 如果i=0或j=0;
             。2)c[i][j]= c[i-1][j-1]+1 如果I,j>0,且a[i-1]=b[j-1];
             。3)c[i][j]=max(c[i][j-1],c[i-1][j]) 如果I,j>0,且a[i-1]!=b[j-1]。
              按此算式可寫出計(jì)算兩個序列的最長公共子序列的長度函數(shù)。由于c[i][j]的產(chǎn)生僅依賴于c[i-1][j-1]、c[i-1][j]和c[i][j-1],故可以從c[m][n]開始,跟蹤c[i][j]的產(chǎn)生過程,逆向構(gòu)造出最長公共子序列。細(xì)節(jié)見程序。
              # include
              # include
              # define N 100
              char a[N],b[N],str[N];
              
              int lcs_len(char *a, char *b, int c[ ][ N])
              { int m=strlen(a), n=strlen(b), i,j;
               for (i=0;i<=m;i++) c[i][0]=0;
               for (i=0;i<=n;i++) c[0][i]=0;
               for (i=1;i<=m;i++)
               for (j=1;j<=m;j++)
               if (a[i-1]==b[j-1])
               c[i][j]=c[i-1][j-1]+1;
               else if (c[i-1][j]>=c[i][j-1])
               c[i][j]=c[i-1][j];
               else
               c[i][j]=c[i][j-1];
               return c[m][n];
              }
              
              char *buile_lcs(char s[ ],char *a, char *b)
              { int k, i=strlen(a), j=strlen(b);
               k=lcs_len(a,b,c);
               s[k]=’\0’;
               while (k>0)
               if (c[i][j]==c[i-1][j]) i--;
               else if (c[i][j]==c[i][j-1]) j--;
               else { s[--k]=a[i-1];
               i--; j--;
               }
               return s;
              }
              
              void main()
              { printf (“Enter two string

            文章搜索
            軟件水平考試欄目導(dǎo)航
            版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請與我們聯(lián)系800@eeeigo.com,我們將會及時(shí)處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請注明出處。