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

本文格式為Word版，下載可任意編輯——《算法設(shè)計與分析》課程上機(jī)指導(dǎo)《算法設(shè)計與分析》課程上機(jī)指導(dǎo)

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

實習(xí)內(nèi)容

習(xí)題一（工程名為101、源程序名為101）選擇排序法的偽代碼描述如下：算法1.4SelectionSort（參見Page8）輸入：數(shù)組A[1..n]

輸出：按升序排列的數(shù)組A[1..n]

1.fori←1ton-12.

Selection(i)

3.endfor過程Selection(i)

1.k←i

2.forj←i+1ton3.

ifA[j]4.endfor

5.ifk≠ithen交換A[i]和A[k]

用C語言實現(xiàn)上述算法并上機(jī)通過。

//*******************************************************//*工程名：101.dsp*//*程序名：101.cpp

*

//*主要功能：選擇排序法

*

//*學(xué)號姓名：20232633226張云龍*//*編制時間：2023年10月9日

//********************************************************#includevoidmain(){

*

intn=5,k,m;intA[6];

for(inti=1;i>A[i];}

for(i=1;i0)and(A[j]>x)4.A[j+1]←A[j]5.

j←j-1

6.endwhile7.A[j+1]←x

用C語言實現(xiàn)上述算法并上機(jī)通過。

//*******************************************************//*工程名：102.dsp*//*程序名：102.cpp

*

//*主要功能：插入排序法

*

//*學(xué)號姓名：20232633226張云龍//*編制時間：2023年10月9日

//********************************************************#includevoidmain()

**

2

{

inti,x,j,n=5,A[6];for(i=1;i>A[i];}

for(i=2;i0)j=j-1;}A[j+1]=x;}

couts表示剩余的元素個數(shù)大于被合并的子序列長度過程Merge(A[1..m],p,q,r)

1.comment:B[p..r]是個輔助數(shù)組//或B[1..m]2.s←p:t←q+1:k←p

//s和t分別指向數(shù)組A二個子數(shù)組元素//k指向數(shù)組B當(dāng)前空白元素位置

3.while(s≤q)and(t≤r).

ifA[s]≤A[t]thenB[k]←A[s]:s←s+1elseB[k]←A[t]:t←t+1endifk←k+1

//指向數(shù)組B下一個空白位置

8.endwhile

9.ifs=q+1thenB[k..r]←A[t..r]//說明子數(shù)組A[p..q]元素已處理完10.elseB[k..r]←A[s..q]11.endif

12.A[p..r]←B[p..r]

用C語言實現(xiàn)上述算法并上機(jī)通過。

//*******************************************************

4

//否則t=r+1，說明子數(shù)組A[q+1..r]已處理完。

//*工程名：103.dsp*//*程序名：103.cpp

*

//*主要功能：自底向上排序法

*

//*學(xué)號姓名：20232633226張云龍*//*編制時間：2023年10月9日

*

//********************************************************#include

voidme