算法設(shè)計(jì)與分析2011algoanswer可看性強(qiáng)點(diǎn)

1、一個(gè)正確的算法，對(duì)于每個(gè)合法輸入，都會(huì)在有限的時(shí)間內(nèi)輸出一個(gè)滿足要求的結(jié)果。NP 完全問題比其他所有NP 問題都要難?；厮莘ㄓ蒙疃葍?yōu)先法或廣度優(yōu)先法搜索狀態(tài)空間樹。在動(dòng)態(tài)規(guī)劃中，各個(gè)階段所確定的策略就構(gòu)成一個(gè)策略序列，通常稱為一個(gè)決策。類和類問題的關(guān)系用 來表示是錯(cuò)誤的。若近似算法A求解某極小化問題一實(shí)例的解為，且已知該問題的最優(yōu)解為/3，則該近似算法的性3。F通常來說，算法的最壞情況的時(shí)間復(fù)雜行比平均情況的時(shí)間復(fù)雜性容易計(jì)算。若P2多項(xiàng)式時(shí)間轉(zhuǎn)化為(polynomialtransformstoP1，則P2 P1 一樣難?；诒容^的尋找數(shù)組A1中最大元素的問題下屆是(/3)。O() + O()

2、 = O(min(),若() = ()，() = ()，則() = 若() = O()，則() = 貪婪技術(shù)所做的每一步選擇所產(chǎn)生的部分解，不一定是可行性的。LasVegas算法只要給出解就是正確的。判斷題1-5:TFFT 6-10: FTTFF 11-16: F TTTT何謂為多項(xiàng)式算法？如何將一MonteCarlo LasVegas 構(gòu)造AVL2-3 0/1背包問題的一個(gè)多項(xiàng)式等價(jià)(PolynomialEquivalent)下面問題是否屬于NP 問題表述：給定圖 = ()中的兩個(gè)點(diǎn)、，整數(shù)和，圖中每條邊的長度，問圖中是否存在一條由到的路徑，使得其長度大于，且遍歷時(shí)間小于問答題O(n)。（2

3、）Monte Carlo算法每次都能得到問題的解，但不保證所得解的準(zhǔn)確性；Las Vegas算法是每次不一定得到解，如果錯(cuò)誤就不能生成問題的解，這樣Monte Carlo Las Vegas 算法。構(gòu)建AVL2-3 0/1 屬于NP n 個(gè)數(shù)的一個(gè)序列12，若其中某兩個(gè)數(shù)和的關(guān)系為： 且 ，則A1為一個(gè)整數(shù)序列，A中的整數(shù)如果在A中出現(xiàn)次數(shù)多余/2，那么稱為多數(shù)元素。例如，在序列1,3,2,3,3,4,3中 3 是多數(shù)元素，因?yàn)槌霈F(xiàn)了 4 次，大于7/2。求 A 的多數(shù)元素問題的蠻力算法復(fù)時(shí)期（月需要量（產(chǎn)品單位12233244（千元（千元6 位。8 3 個(gè)過目，每個(gè)項(xiàng)目在不同筒子數(shù)額下（以萬

4、元為單位）投資01234567805050450個(gè)站點(diǎn)的有線通訊網(wǎng)絡(luò)，每兩個(gè)站點(diǎn)之間的線路敷設(shè)費(fèi)用由對(duì)成矩陣C U 給出。DMAX(D 給出)。（要求是二叉搜索樹（何時(shí)以及如何前進(jìn)、分支、回溯、剪枝等等 之間的貿(mào)易稅率由對(duì)稱矩陣R 給出，其中代表兩國不能直接通商。ABT給出。請(qǐng)安排一中轉(zhuǎn)貿(mào)易計(jì)劃，使得該交易所產(chǎn)生的向各中轉(zhuǎn)國繳納的稅費(fèi)最低，且整個(gè)交易能夠在時(shí)間t 內(nèi)完成。（要求是二叉搜索樹（何時(shí)以及如何前進(jìn)、分支、回溯、剪枝等等1.1.numnum- Merge(Typea,Typeleft,Typemid,Typei - left, j - right; while(imid&jnum+=m

5、id- MergeSort(Typea,Typeleft,Typeif(leftmid - (left + right) / 2; MergeSort(a, left, i); MergeSort(a,mid+1,right); Merge(a, left, i, right);num=num+mid-i。n時(shí)間復(fù)雜度的迭代公式為T(n)2T(n/2)nO(n2)，當(dāng)n 2.2. num-count-forfori -0 ton-1 if(num=if(count0)num-23456580123423456012345656789012345656789012345678901234789012345612345060 gk(xk)：把數(shù)目為xk 錢投資到項(xiàng)目k xk: 表示投資的數(shù)目；uk: 表示投給項(xiàng)目k ), fn(xn)=項(xiàng)目個(gè)數(shù)n=3，xk 80123456781040123456780041592345678012345678123456780551401 4 2 4 3