算法設(shè)計(jì)與分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上計(jì)算機(jī)算法設(shè)計(jì)與分析1、 實(shí)驗(yàn)名稱：用貪心算法解決磁盤文件最優(yōu)存儲(chǔ)問(wèn)題。2、 實(shí)驗(yàn)?zāi)康模?）理解貪心算法的概念和掌握其基本要素； 2）針對(duì)具體問(wèn)題，能應(yīng)用貪心算法設(shè)計(jì)有效算法，提高對(duì)實(shí)際 問(wèn)題的分析、設(shè)計(jì)和實(shí)現(xiàn)能力； 3）為后續(xù)課程的學(xué)習(xí)及課程設(shè)計(jì)打下堅(jiān)實(shí)的實(shí)踐基礎(chǔ)。3、 實(shí)驗(yàn)內(nèi)容： 1）問(wèn)題描述： 設(shè)磁盤上有n個(gè)文件，f1,f2,fn，每個(gè)文件占磁盤上1個(gè)磁道。這n個(gè)文件的檢索概率分別是p1,p2,pn,且p1+p2+pn =1。磁頭從當(dāng)前磁道移到被檢信息磁道所需的時(shí)間可用這2 個(gè)磁道之間的徑向距離來(lái)度量。如果文件pi存放在第i道上, ，則檢索這n 個(gè)文件的期望時(shí)間

2、是 ,其中d(I,j) 是第i道與第j 道之間的徑向距離|i-j|。磁盤問(wèn)題就是要確定這n 個(gè)文件在磁盤上的存儲(chǔ)位置，使期望檢索時(shí)間達(dá)到最小。設(shè)計(jì)一個(gè)解此問(wèn)題的算法，并分析算法的正確性與計(jì)算復(fù)雜性。 2）問(wèn)題分析： a、通過(guò)對(duì)所給數(shù)據(jù)33 55 22 11 9的所有組合進(jìn)行窮舉計(jì)算可以發(fā)現(xiàn)規(guī)律所在。兩個(gè)最優(yōu)解是：9 22 55 33 11以及11 33 55 22 9 b、通過(guò)進(jìn)一步的研究分析可以證明這樣的規(guī)律是正確的。四、算法設(shè)計(jì)思路：如果對(duì)任何i，j，當(dāng)i<>j時(shí)，pi<>pj，則n個(gè)文件在磁盤上將有N!種不同的存儲(chǔ)方式。如果考慮到f1，f2fn，這種排列方式與fn

3、f1排列的期望檢索時(shí)間相等，則要計(jì)算n!/2種不同的盤列方式。對(duì)于指定的i和j，pi和pj是不變的，可變因子是d(i,j),如果將d(i,j)視為一個(gè)元素恒定的集合，則他們與排列順序無(wú)關(guān)。先將這n個(gè)文件按其概率進(jìn)行排序。設(shè)排序后有p1>=p2>=>=pn.則采用談心算法將文件f1放到中心磁道上，f2，f3分別靠著f1的左右磁道，f4在f2右邊得到最佳的方案。五、問(wèn)題的貪心選擇性質(zhì)及最優(yōu)子結(jié)構(gòu)性質(zhì)：磁盤文件最優(yōu)存儲(chǔ)問(wèn)題具有貪心選擇性質(zhì)：先將n個(gè)文件從大到小按概率進(jìn)行排序。假設(shè)排序后有p1>=p2>=>=pn。貪心選擇性質(zhì)表示每次所選擇加入的對(duì)象文件，都能得到當(dāng)

4、前的最優(yōu)值，即使得期望檢索時(shí)間達(dá)到最小。在磁盤最優(yōu)存儲(chǔ)問(wèn)題中，要想使期望檢索時(shí)間達(dá)到最小。那么就要使兩個(gè)概率較大者的徑向距離越小越好。因此第一次從p1>=p2>=>=pn中選取P1所對(duì)應(yīng)的文件f1置于中心磁道上。隨后從剩余概率隊(duì)列中選取概率最大和次最大者所對(duì)應(yīng)的文件放在靠著f1的左磁道，和f1的右磁道。這將得到初始的最優(yōu)值。同樣地，繼續(xù)選擇剩余概率隊(duì)列中概率最大和次最大者所對(duì)應(yīng)的文件分別置于靠著剛才所得最優(yōu)位置的左磁道和右磁道上，將得到新的最優(yōu)值。所以磁盤最優(yōu)存儲(chǔ)問(wèn)題具有貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：按照這n個(gè)文件的排序概率（p1>=p2>=>=pn），假設(shè)

5、排序后的理想最優(yōu)序列為：f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（n為奇數(shù)）。若n為偶數(shù)個(gè)，則補(bǔ)上一個(gè)數(shù)0。那么不管n為奇數(shù)或者是偶數(shù)，其理想最優(yōu)序列都可以表示為f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（因?yàn)榧由弦粋€(gè)0，對(duì)其達(dá)到最小期望檢索時(shí)間無(wú)影響，所以可以進(jìn)行此處理。）利用反證法思想假設(shè)存在一個(gè)f（n-1）,f(n-3),f(n-5),f(j)f4,f2,f1,f3,f5,f(i)f(n-2),fn。該序列是原序列對(duì)調(diào)f(i)與f(j)的位置所得。該序列所

6、得到的期望檢索時(shí)間小于上面的貪心策略時(shí)間。經(jīng)驗(yàn)證發(fā)現(xiàn)，該序列所獲得的期望檢索時(shí)間>原所獲得的期望檢索時(shí)間。與最優(yōu)值相矛盾。故貪心解為最優(yōu)解。六、實(shí)驗(yàn)代碼：#include"stdio.h"#define MAX 100void sort(float *a,int n) int i,j;float temp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(aj>aj+1)temp=aj;aj=aj+1;aj+1=temp;void main()int i,j,n,k;float aMAX,xMAX;float m=0,t=

7、0;printf("請(qǐng)輸入文件數(shù)：n");scanf("%d",&n);printf("請(qǐng)分別輸入這些文件的檢索概率：n");for(i=0;i<n;i+)scanf("%f",&ai);sort(a,n);k=(n-1)/2;xk=an-1;for(i=k+1;i<n;i+) xi=an-2*(i-k);for(i=k-1;i>=0;i-)xi=an-2*(k-i)-1;for(i=0;i<n;i+)m+=ai;for(j=i+1;j<n;j+)t+=xi*xj*(j-i);t=t/(m*m);printf("經(jīng)過(guò)合理的安排之后，最少期望檢索為:%f n&quo