《算法設(shè)計與分析》上機(jī)指導(dǎo)

1、算法設(shè)計與分析課程上機(jī)指導(dǎo)上機(jī)常見錯誤與對策1 2 5 PAGE PAGE 15上機(jī)常見錯誤與對策創(chuàng)建工程時，選錯工程類型（應(yīng)選擇倒數(shù)第三個“Win32Applicatio；創(chuàng)建源程序文件時，選錯文件類型。要修改程序，應(yīng)打開工作區(qū)（dsw）文件，而不是源程序（cpp）文件。VC+系統(tǒng)中，程序是用西文字符碼）字符串常數(shù)或注釋中。請注意漢字雙引號和西文雙引號的區(qū)別請注意漢字單引號和西文單引號的區(qū)別請注意漢字分號和西文分號的區(qū)別請注意漢字園括號和西文園括號的區(qū)別程序完成，編制下一個程序時，一定要新建工程（VC+VC+。當(dāng)系統(tǒng)出現(xiàn)不可解釋的現(xiàn)象時，此時應(yīng)選擇“編譯”“重建全部”若還不行，則重新啟動計算

2、機(jī)，利用硬盤保護(hù)卡功能恢復(fù)系統(tǒng)。操作步驟：重新啟動計算機(jī)后，出現(xiàn)菜單畫面。選中“Windows2000 Professional”。在按住“Ctrl”鍵的同時，按“R”健。對于系統(tǒng)提問，按“Y”鍵回答。條目，指針會自動指向出錯語句，編程者可逐字符查找錯誤。算法設(shè)計與分析上機(jī)指導(dǎo) 1（每個）程序書寫要求/ */*/*工程103.dsp103.cpp*/ *主要功能：自底向上合并排序法*/ *學(xué)號姓名：57053001 某某某*/ *編制時間：2011 7 13 日*/ * #include/#includevoidmain()/using namespacestd;/int main()/ret

3、urn 0;/實習(xí)內(nèi)容習(xí)題一（工程名為 101、源程序名為 101） 選擇排序法的偽代碼描述如下：1.4 SelectionSort（Page A1.n輸出：按升序排列的數(shù)組 A1.nfor i1 to n-1Selection(i)end for過程 Selection(i)kifor ji+1 to nif Aj0)and(Ajx) 4.Aj+1Aj5.jj-16.end while 7.C 語言實現(xiàn)上述算法并上機(jī)通過。選做題：用遞歸方法（歸納法）實現(xiàn)插入排序法。習(xí)題三（工程名為 103、源程序名為 103） 自底向上合并排序法的偽代碼描述如下： 算法 1.6 BottomUpSort（P

4、age 10）輸入：n 個元素的數(shù)組 A1.n輸出：按升序排列的數(shù)組1.t12.while tn3.st : t2s : i0while i+tnMerge(A,i+1,i+s,i+t)/Merge(A,p,q,r)ii+tend whileif i+ss Merge(A1.m,p,q,r)comment:Bp.r是個輔助數(shù)組 /B1.msp : tq+1kp/s和t分別指向數(shù)組A二個子數(shù)組元素while(sq)andtr)/k B當(dāng)前空白元素位置if AsAt then BkAs : ss+1else BkAt : tt+1end ifkk+1/B 下一個空白位置end whileif s=

5、q+1thenBk.rAt.r/Ap.q元素已處理完else Bk.rAs.qend if12. Ap.r Bp.r/t=r+1Aq+1.r已處理完。C 語言實現(xiàn)上述算法并上機(jī)通過。選做題：用遞歸方法（分治法）實現(xiàn)自底向上合并排序法。習(xí)題四（工程名為 104、源程序名為 104）評二種排序算法運(yùn)行效率，以期在理論和實踐上得出一致的結(jié)論。選擇排序算法修改#include #include #include #include #include #define N65536*2void Selection(short,int); void main()short AN+1; srand(time(N

6、ULL);for(int i=1;i=N;i+)Ai=rand()%10000; time_t t1,t2;struct tm *pt; time(&t1);pt=gmtime(&t1); coutsetfill(0);cout排序開始時間:;coutsetw(2)tm_hour+8)%24:setw(2)tm_min :setw(2)tm_secendl;coutSelectionSort 排序中flush;for(i=1;i=N-1;i+) if(i%2048=0)cout.flush; Selection(A,i);coutendl排序結(jié)束時間:; time(&t2);pt=gmtime

7、(&t2);coutsetw(2)tm_hour+8)%24:setw(2)tm_min:setw(2)tm_secendl;cout排序耗費(fèi)時間=t2-t1endl; getch();歸并排序法修改#include #include #include #include #include const int N=65536*2;void BottomUpSort(short,int); void Merg(short,int,int,int); void main()short AN+1; srand(time(NULL);for(int i=1;i=N;i+)Ai=rand()%1000;

8、time_t t1,t2;struct tm *pt; time(&t1);pt=gmtime(&t1); coutsetfill(0);cout排序開始時間:;coutsetw(2)tm_hour+8)%24:setw(2)tm_min :setw(2)tm_secendl;coutMergeSort 排序中flush;BottomUpSort(A,N); time(&t2);pt=gmtime(&t2); coutendl排序結(jié)束時間:;coutsetw(2)tm_hour+8)%24:setw(2)tm_min:setw(2)tm_secendl;cout排序耗費(fèi)時間=t2-t1endl

9、;/ getch();void BottomUpSort(short A,int n)int i,t=1,s; while(tn)cout.flush; s=t;t=2*s;i=0;程序運(yùn)行結(jié)果SelectionSortMergeSort提交方式學(xué)號姓名”“57053001某某某”“57053001某某某”本次實習(xí)“57053001某某某1” 中，應(yīng)具有如下文件：101.cpp、101.exe、102.cpp、102.exe 103.cpp、103.exe、104.cpp、104.exe算法設(shè)計與分析上機(jī)指導(dǎo) 2（每個）程序書寫要求/ */*/*工程103.dsp103.cpp*/ *主要功能

10、：自底向上合并排序法*/ *學(xué)號姓名：57053001 某某某*/ *編制時間：2011 7 13 日*/ * #include/#includevoidmain()/using namespacestd;/int main()/return 0;/實習(xí)內(nèi)容習(xí)題一（201快速排序法的偽代碼描述如下：6.6 QuickSort（Page n A1.nA1.n1.QuickSort(A,1,n)過程 QuickSort(A1.n,low,high)if lowx=Alowif ij then AiAjend ifend forif lowi then AlowAiwireturn wC 語言實現(xiàn)上

11、述算法并上機(jī)通過。習(xí)題二（工程名為 202、源程序名為 202） 運(yùn)動員比賽日程表n=2k n-1 個選手各賽一次每個選手一天只能賽一次循環(huán)賽一共進(jìn)行 n-1 天運(yùn)用分治策略，該問題的遞歸算法描述如下，根據(jù)算法編制程序并上機(jī)通過。n（n 2 i 次方A1.n,1.n1.for i1ton/設(shè)置運(yùn)動員編2.Ai,1iend forCalendar(0,n)/0。過程 Calendar(v, k)/v 表示位移（v起始行-，k 表示運(yùn)動員人數(shù)。1.ifk=2then/2 個2.Av+2,2Av+1,1/處理右下角3.Av+1,2Av+2,1/處理右上角elseCalendar(v,k/2)/假設(shè)已

12、制定了v+1至v+k/2運(yùn)動員循環(huán)賽日程表Calendar(v+k/2,k/2)/v+k/2+1 v+k 程表comment2k/21k 人組的解。for i1 tok/2for j1 tok/2Av+i+k/2,j+k/2Av+i,j/沿對角線處理右下角end forend forfor ik/2+1 tokfor j1 to k/2Av+i-k/2,j+k/2Av+i,j/沿對角線處理右上角end forend forend if選做題：編制該問題的非遞歸算法，上機(jī)通過。習(xí)題三（203203） 算法 LCSRec（遞歸算法）A BA B n 輸出：A B 的最長公共子序列的長度LCSRec

13、(n,m)過程 procedure LCSRec(i,j)if i=0 or j=0 then return 0elseif Ai=Bj thenreturn LCSRec(i-1,j-1)+1elsereturn max(LCSRec(i,j-1),LCSRec(i-1,j)end ifend ifC 語言實現(xiàn)上述算法并上機(jī)通過。選做題：給出最長公共子序列問題的非遞歸算法（動態(tài)規(guī)劃法習(xí)題四（工程名為 204、源程序名為 204） 解背包問題的偽代碼描述如下：算法 7.4 Knapsack（參見 Page 139）CS = s1,s2,.,snV = v1,v2,.,vn輸出：可裝入背包物品的

14、最大總價值for i0tonVi,00for j0 to Cfor i1 to n/背包容量為 0/背包未裝入任何物品for j1 to Cif si jthen/ui sij,不裝入。Vi,jVi-1,j/取上一次的計算結(jié)果else/物品ui的體積si不超過容量j,可裝入8.Vi,jmax(Vi-1,j,Vi-1,j-si+vi)end ifend forend forreturnVn,C/C語言實現(xiàn)上述算法并上機(jī)通過。選做題：如何修改算法Knapsac(C空間，其中C 量。選做題 2：給出背包問題的遞歸算法，并上機(jī)通過。提交方式學(xué)號姓名”“57053001某某某”“57053001某某某”

15、2（本次實習(xí)。在目錄“57053001某某某2” 中，應(yīng)具有如下文件：201.cpp201.exe202.cpp202.exe203.cpp203.exe204.cpp204.exe算法設(shè)計與分析上機(jī)指導(dǎo) 3（每個）程序書寫要求/ */*/*工程103.dsp103.cpp*/ *主要功能：自底向上合并排序法*/ *學(xué)號姓名：*/ *編制時間：2007 7 13 日*/ * #include/#includevoidmain()/using namespacestd;/int main()/return 0;/實習(xí)內(nèi)容習(xí)題一（工程名為 301、源程序名為 301） 解最短路徑問題的偽代碼描述如

16、下：算法 8.1（Page 147）1 輸出：G 1 到其它各結(jié)點的最短路徑長度1.X=1:Y=V-1: 1=0for y2 to nify 相鄰于頂點1then y=length1,yelse y=end ifend forfor j1ton-1/Y n-1 個頂點yY 且 y為最小XXy:YY-y/yXYfor 每條邊(y,w)if wYand y+lenghy,w w then w y+lenghy,wend ifend forend forC 語言實現(xiàn)上述算法并上機(jī)通過。習(xí)題二（工程名為 302、源程序名為 302） 解圖三著色問題的偽代碼描述如下：輸入：無向圖 G=(V,E)輸出：圖的結(jié)點3 著色