《算法设计与分析》课程上机指导

《算法设计与分析》课程上机指导

《算法设计与分析》上机指导1

实习内容

习题一（工程名为101、源程序名为101） 选择排序法的伪代码描述如下： 算法1.4 SelectionSort（参见Page 8） 输入：数组A[1..n]

输出：按升序排列的数组A[1..n]

1. for i←1 to n-1 2.

Selection(i)

3. end for 过程Selection(i)

1. k←i

2. for j←i+1 to n 3.

if A[j]

4. end for

5. if k≠i then 交换A[i]和A[k]

用C语言实现上述算法并上机通过。

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

*

// * 主要功能：选择排序法

*

// * 学号姓名：20112633226 张云龙 * // * 编制时间：2013年10月9日

// ******************************************************** #include void main() {

*

int n=5,k,m; int A[6];

for(int i=1;i

cout<<\请输入第\个元素\ cin>>A[i]; }

for( i=1;i

for(int j=i+1;j

if(A[j]

} if(k!=i) { m=A[k]; A[k]=A[i]; A[i]=m; } }

cout<<\新的数组为：\ for( i=1;i

cout<

1

}

选做题：用递归方法（归纳法）实现选择排序法。

习题二（工程名为102、源程序名为102） 插入排序法的伪代码描述如下： 算法1.6 InsertionSort（参见Page 8-9） 输入：数组A[1..n]

输出：按升序排列的数组A[1..n]

1. for i←2 to n 2.

Insertion (i)

3. end for 过程Insertion(i)

1. x←A[i] 2. j←i-1

3. while (j>0) and (A[j]>x) 4. A[j+1]←A[j] 5.

j←j-1

6. end while 7. A[j+1]←x

用C语言实现上述算法并上机通过。

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

*

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

*

// * 学号姓名：20112633226张云龙 // * 编制时间：2013年10月9日

// ******************************************************** #include void main()

* *

2

{

int i,x,j,n=5,A[6]; for(i=1;i

cout<<\请输入数组的第\个元素\cin>>A[i]; }

for(i=2;i

while((j>0)&&(A[j]>x)) {

A[j+1]=A[j]; j=j-1; } A[j+1]=x; }

cout<<\新的数组为:\for(i=1;i

cout<

选做题：用递归方法（归纳法）实现插入排序法。

3

习题三（工程名为103、源程序名为103） 自底向上合并排序法的伪代码描述如下： 算法1.6 BottomUpSort（Page 10） 输入：n个元素的数组A[1..n] 输出：按升序排列的数组A[1..n]

1. t←1 2. while t

s←t : t←2s : i←0 while i+t≤n

Merge(A,i+1,i+s,i+t) //Merge(A,p,q,r) i←i+t

end while

if i+s

9. end while //n-i>s表示剩余的元素个数大于被合并的子序列长度 过程Merge(A[1..m],p,q,r)

1. comment:B[p..r]是个辅助数组 //或B[1..m] 2. s←p : t←q+1 : k←p

//s和t分别指向数组A二个子数组元素 //k指向数组B当前空白元素位置

3. while (s≤q) and (t≤r) 4. 5. 6. 7.

if A[s]≤A[t] then B[k]←A[s] : s←s+1 else B[k]←A[t] : t←t+1 end if k←k+1

//指向数组B下一个空白位置

8. end while

9. if s=q+1 then B[k..r]←A[t..r] //说明子数组A[p..q]元素已处理完 10. else B[k..r]←A[s..q] 11. end if

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

用C语言实现上述算法并上机通过。

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

4

//否则t=r+1，说明子数组A[q+1..r]已处理完。

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

*

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

*

// * 学号姓名：20112633226张云龙 * // * 编制时间：2013年10月9日

*

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

void merge(int *A,int p,int q,int r) {

int s,t,k;

int *B=new int[r]; s=p;t=q+1;k=p; while((s<=q)&&(t<=r)) {

if(A[s]<=A[t]) {

B[k]=A[s];

s=s+1;

}

else {

B[k]=A[t];

t=t+1;

} k=k+1; }

if(s=q+1)

{ for(int i=t;i<=r;i++)

{

5

B[k]=A[t];

t=t+1;

k=k+1; }

}

else {

for(int i=s;i<=q;i++) {

B[k]=A[s]; s=s+1;

k=k+1;

} }

for(int h=p;h<=r;h++) {

A[p]=B[p]; p=p+1;

} }

void main() { int n=5,i,t=1,s,m;

int *A=new int[6]; for(i=1;i<=n;i++)

{

6

cout<<\请输入数组的第\个元素:\ cin>>A[i]; }

while(t

s=t,t=2*s;i=0; while((i+t)<=n) {

merge(A,i+1,i+s,i+t);

i=i+t; }

if((i+s)

merge(A,i+1,i+s,n); }

}

cout<<\新数组为:\ for(m=1;m<=n ;m++) { cout<

}

}

选做题：用递归方法（分治法）实现自底向上合并排序法。 7

本文来源：https://www.bwwdw.com/article/2nga.html