算法设计与分析实验二

实验二：分治法实验

一、实验目的

（1）掌握设计有效算法的分治策略。

（2）通过快速排序学习分治策略设计技巧

二、实验要求

（1）熟练掌握分治法的基本思想及其应用实现。

（2）理解所给出的算法，并对其加以改进。

三、分治法的介绍

任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。而当n较大时，问题就不那么容易处理了。要想直接解决一个规模较大的问题，有时是相当困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题，1

分治法的适用条件：

（1）该问题的规模缩小到一定的程度就可以容易地解决；

（2）该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

（3）利用该问题分解出的子问题的解可以合并为该问题的解；

（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

上述的第一条特征是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。

分治法的基本步骤：

分治法在每一层递归上都有三个步骤：

分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题；

合并：将各个子问题的解合并为原问题的解。

它的一般的算法设计模式如下：Divide-and-Conquer(P)

1. if |P|≤n0

2. then return(ADHOC(P))

3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk

4. for i←1 to k

5. do yi ← Divide-and-Conquer(Pi) △递归解决Pi

6. T ← MERGE(y1,y2,...,yk) △合并子问题

7. return(T)

其中|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。ADHOC(P)是该分治法中的基本子算法，用于直接解小规模的问题P。因此，当P的规模不超过n0时，直接用算法ADHOC(P)求解。算法

MERGE(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。

根据分治法的分割原则，原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难予以肯定的回答。但人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。

四、实验内容

1、编程实现归并排序算法和快速排序算法，程序中加入比较次数的计数功能，输出排序结果和比较次数。输入10组相同的数据，验证排序结果和完成排序的比较次数。用表格列出比较结果。给出文字分析。

2、汉诺塔（hanoi）问题。

3、棋盘覆盖问题。

4、循环赛日程安排问题。

五、算法设计

1、归并排序算法

procedure MERGESORT(low，high)

//A(low；high)是一个全程数组，它含

有high-low+1≥0个待排序的元素//

integer low，high；

if low

then mid←， //求这个集合的分割点//

call MERGESORT(low，mid) //将一个子集合排序//

call MERGESORT(mid+1，high) //将另一个子集合排序

call MERGE(low，mid，high) //归并两个已排序的子集合//

endif

end MERGESORT

归并两个已排序的集合

procedure MERGE(low，mid，high)

//A(low：high)是一个全程数组//

//辅助数组B(low；high)//

integer h，i，j，k；

h←low；i←low；j←mid+1；

while h≤mid and j≤high do //当两个集合都没取尽时//

if A(h)≤A(j) then B(i) ←A(h)；h←h+1

else B(i) ←A(j)；j←j+1

endif

i←i+1

repeat

if h>mid then

for k←j to high do //处理剩余的元素//

B(i) ←A(k)；i←i+1

repeat

else for k←h to mid do

B(i) ←A(k)；i←i+1

repeat

endif

将已归并的集合复制到A

end MERGE

2、快速排序算法

我们已经知道，在决策树计算模型下，任何一个基于比较来确定两个元素相对位置的排序算法需要Ω(nlogn)计算时间。如果我们能设计一个需要O(n1ogn)时间的排序算法，则在渐近的意义上，这个排序算法就是最优的。许多排序算法都是追求这个目标。下面介绍快速排序算法，它在平均情况下需要O(nlogn)时间。这个算法是由C.A.R.Hoare发明的。

算法的基本思想：快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：

分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。

递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。

合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和

L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。

这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。

QuickSort(p,q)

//将数组A[1:n]中的元素

A[p], A[p+1], , A[q]按不降次序排列，

并假定A[n+1]是一个确定的、且大于

A[1:n]中所有的数。//

int p,q; global n, A[1:n];

if p

j=Partition(p, q+1); // 划分后j成为划分元素的位置

QuickSort(p,j-1);

QuickSort(j+1,q);

endif

end QuickSort

procedure PARTITION(m，p)

//退出过程时，p带着划分元素所在的下标位置。//

integer m，p，i；global A(m：p-1)

v←A(m)；i←m //A(m)是划分元素//

loop

loop i←i+1 until A(i)≥v repeat //i由左向右移//

loop p←p-1 until A(p)≤v repeat //p由右向左移//

if i

then call INTERCHANGE(A(i)，A(p)) //A(i)和A(p)换位//

else exit

endif

repeat

A(m) ←A(p)；A(p) ←v //划分元素在位置p//

End PARTITION

3、汉诺塔（hanoi）问题。设有 A、B、 C 共 3 根塔座，在塔座 A 上堆叠 n个金盘，每个盘大小不同，只允许小盘在大盘之上，最底层的盘最大，如下图所示。现在要求将 A 上的盘全都移到 C 上，在移的过程中要遵循以下原则：每次只能移动一个盘；圆盘可以插在 A、B 和 C 任一个塔座上；在任何时刻，大盘不能放在小盘的上面。

hanoi问题递归求解思想：

我们把一个规模为n的hanoi问题：1到n号盘按照移动规则从A上借助B移到C上表示为H(A,B,C,n)；原问题划分成如下三个子问题：

（1）将1到n-1号盘按照移动规则从A上借助C移到B上H(A,C,B,n-1);

（2）将n号盘从A上直接移到C上；

（3）将1到n-1号盘按照移动规则从B上借助A移到C上H(B,A,C,n-1);

经过三个子问题求解，原问题的也即求解完成。

4、盘覆盖问题。在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

六、参考程序代码

1、归并排序

#include

#include

#include

#include

#define M 11

typedef int KeyType;

typedef int ElemType;

struct rec{

KeyType key;

ElemType data;

};

typedef rec sqlist[M];

class guibing{

public:

guibing(sqlist b)

{

for(int i=0;i

r[i]=b[i];

}

void output(sqlist r,int n)

{

for(int i=0;i

cout<

cout<

}

void xuanze(sqlist b,int m,int n)

{

int i,j,k;

for(i=m;i

{

k=i;

for(j=i;j

if(b[k].key>b[j].key) k=j;

if(k!=i)

{

rec temp=b[k];

b[k]=b[i];

b[i]=temp;

}

}

}

void merge(int l,int m,int h,sqlist r2) {

xuanze(r,l,m);

xuanze(r,m,h);

output(r,M);

int i,j,k;

k=i=l;

for(j=m;i

{

if(r[i].key<=r[j].key)

{

r2[k]=r[i];

i++;

}

else

{

r2[k]=r[j];

j++;

}

output(r2,M);

}

while(j

{

r2[k]=r[j];

j++;

k++;

}

while(i<=m)

{

r2[k]=r[i];

i++;

k++;

}

output(r2,M);

}

private:

sqlist r;

};

void main()

{

cout<<"guibingfa1运行结果:\n";

sqlist a,b;

int i,j=0,k=M/2,n=M;

srand(time(0));

for(i=0;i

{

a[i].key=rand()%80;b[i].key=0;

}

guibing gx(a);

cout<<"排序前数组:\n";

gx.output(a,M);

cout<<"数组排序过程演示:\n";

gx.merge(j,k,n,b);

cout<<"排序后数组:\n";

gx.output(b,M);

cin.get();

}

2、快速排序

#include

#include

#include

#include

#define MAXI 10

typedef int KeyType;

typedef int ElemType;

struct rec{

KeyType key;

ElemType data;

};

typedef rec sqlist[MAXI];

class kuaisu

{

public:

kuaisu(sqlist a,int m):n(m)

{

for(int i=0;i

}

void quicksort(int s,int t)

{

int i;

if(s

i=part(s,t);

quicksort(s,i-1);

quicksort(i+1,t);

}

else return;

}

int part(int s,int t)

{

int i,j;

rec p;

i=s;j=t;p=b[s];

while(i

{

while(i=p.key)j--;

b[i]=b[j];

while(i

b[j]=b[i];

}

b[i]=p;

output();

return i;

}

void output()

{

for(int i=0;i

cout<

cout<

}

private:

sqlist b;

int n;

};

void main()

{

cout<<"kuaisu1.cpp运行结果:\n";

sqlist a1;

int i,n=MAXI,low=0,high=9;

srand(time(0));

for(i=0;i

a1[i].key=rand()%80;

kuaisu px(a1,n);

cout<<"数组排序过程演示:\n";

px.quicksort(low,high);

cout<<"排序后数组:\n";

px.output();

cin.get();

}

3、hanoi问题递归求解代码：

void H(char A,char B,char C,int n)

{

if(n>0)

{

H(A,C,B,n-1);

printf(“%d from %c to %c”,n,A,C);

H(B,A,C,n-1);

}

}

4、棋盘覆盖问题。

void chessBoard(int tr, int tc, int dr, int dc, int size) {

if (size == 1) return;

int t = tile++, // L型骨牌号

s = size/2; // 分割棋盘

// 覆盖左上角子棋盘

if (dr < tr + s && dc < tc + s)

// 特殊方格在此棋盘中

chessBoard(tr, tc, dr, dc, s);

else {// 此棋盘中无特殊方格

// 用 t 号L型骨牌覆盖右下角

board[tr + s - 1][tc + s - 1] = t;

// 覆盖其余方格

chessBoard(tr, tc, tr+s-1, tc+s-1, s);}

// 覆盖右上角子棋盘

if (dr < tr + s && dc >= tc + s)

// 特殊方格在此棋盘中

chessBoard(tr, tc+s, dr, dc, s);

else {// 此棋盘中无特殊方格

// 用 t 号L型骨牌覆盖左下角

board[tr + s - 1][tc + s] = t;

// 覆盖其余方格

chessBoard(tr, tc+s, tr+s-1, tc+s, s);}

// 覆盖左下角子棋盘

if (dr >= tr + s && dc < tc + s)

// 特殊方格在此棋盘中

chessBoard(tr+s, tc, dr, dc, s);

else {// 用 t 号L型骨牌覆盖右上角

board[tr + s][tc + s - 1] = t;

// 覆盖其余方格

chessBoard(tr+s, tc, tr+s, tc+s-1, s);}

// 覆盖右下角子棋盘

if (dr >= tr + s && dc >= tc + s)

// 特殊方格在此棋盘中

chessBoard(tr+s, tc+s, dr, dc, s);

else {// 用 t 号L型骨牌覆盖左上角

board[tr + s][tc + s] = t;

// 覆盖其余方格

chessBoard(tr+s, tc+s, tr+s, tc+s, s);}

}

5、循环赛日程安排问题

#include"stdio.h"

void Table(int k,int a[][9])

{

int n=1;

for(int i=1;i<=k;i++)n*=2;

for(i=1;i<=n;i++)a[1][i]=i;

int m=1;

for(int s=1;s<=k;s++)

{

n/=2;

for(int t=1;t<=n;t++)

for( i=m+1;i<=2*m;i++)

for(int j=m+1;j<=2*m;j++)

{

a[i][j+(t-1)*m*2]=a[i-m][j+(t-1)*m*2-m];

a[i][j+(t-1)*m*2-m]=a[i-m][j+(t-1)*m*2];}

m*=2;

}

}

main()

{

int k=3;

int a[9][9]={0};

Table(k,a);

for(int i=1;i<=8;i++)

{ for(int j=1;j<=8;j++)

printf("%3d",a[i][j]);

printf("\n");

}

}

思考问题：

1、递归的关键问题在哪里？

2、递归与非递归之间程序的转换？

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