实验1 递归与分治算法
实验目的和要求
（1）进一步掌握递归算法的设计思想以及递归程序的调试技术；
（2）理解这样一个观点：分治与递归经常同时应用在算法设计之中。
（3）分别用蛮力法和分治法求解最近对问题；
（4）分析算法的时间性能，设计实验程序验证分析结论。
实验内容
设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对。
实验环境
Turbo C 或VC++
实验结果：
1.随机生成：
2.手动输入：
源代码：
//二维最邻近点对问题
#include "stdafx.h"
#include
#include
#include
#include
using namespace std;
const int M=50;
//用类PointX和PointY表示依x坐标和y坐标排好序的点
class PointX {
public:
int operator<=(PointX a)const
{ return (x<=a.x); }
int ID; //点编号
float x,y; //点坐标
};
class PointY {
public:
int operator<=(PointY a)const
{ return(y<=a.y); }
int p; //同一点在数组x中的坐标
float x,y; //点坐标
};
float Random();
template
float dis(const Type&u,const Type&v);
bool Cpair2(PointX X[], int n,PointX& a,PointX& b, float& d);
void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX& a,PointX& b,float& d);
template
void Copy(Type a[],Type b[], int left,int right);
template
void Merge(Type c[],Type d[],int l,int m,int r);
template
void MergeSort(Type a[],Type b[],int left,int right);
int main()
{
srand((unsigned)time(NULL));
int length;
int chose;
cout<<"请选择随机生成(1)或手动输入(2)："< cin>>chose; cout<<"请输入点对数："; cin>>length; PointX X[M]; if (chose==2) { for(int i=0;i { cout< X[i].ID=i; cin>>X[i].x; cin>>X[i].y; cout<<"("< } } else if(chose==1) { cout<<"随机生成的二维点对为："< for(int i=0;i { X[i].ID=i; X[i].x=Random(); X[i].y=Random(); cout<<"("< } } PointX a; PointX b; float d; Cpair2(X,length,a,b,d); cout< cout<<"最邻近点对为：("< cout<<"最邻近距离为： "< system("pause"); return 0; } float Random() { float result=rand()%10000; return result*0.01; } //平面上任意两点u和v之间的距离可计算如下 template inline float dis(const Type& u,const Type& v) { float dx=u.x-v.x; float dy=u.y-v.y; return sqrt(dx*dx+dy*dy); } bool Cpair2(PointX X[], int n,PointX& a,PointX& b,float& d) { if(n<2) return false; PointX* tmpX = new PointX[n]; MergeSort(X,tmpX,0,n-1); PointY* Y=new PointY[n]; for(int i=0;i { Y[i].p=i; Y[i].x=X[i].x; Y[i].y=X[i].y; } PointY* tmpY = new PointY[n]; MergeSort(Y,tmpY,0,n-1); PointY* Z=new PointY[n]; closest(X,Y,Z,0,n-1,a,b,d); delete []Y; delete []Z; delete []tmpX; delete []tmpY; return true; } void closest(PointX X[],PointY Y[],PointY Z[], int l, int r,PointX& a,PointX& b,float& d) { if(r-l==1) //两点的情形 { a=X[l]; b=X[r]; d=dis(X[l],X[r]); return; } if(r-l==2) //3点的情形 { float d1=dis(X[l],X[l+1]); float d2=dis(X[l+1],X[r]); float d3=dis(X[l],X[r]); if(d1<=d2 && d1<=d3) { a=X[l]; b=X[l+1]; d=d1; return; } if(d2<=d3) { a=X[l+1]; b=X[r]; d=d2; } else { a=X[l]; b=X[r]; d=d3; } return; } //多于3点的情形，用分治法 int m=(l+r)/2; int f=l,g=m+1; //在算法预处理阶段，将数组X中的点依x坐标排序，将数组Y中的点依y坐标排序 //算法分割阶段，将子数组X[l:r]均匀划分成两个不想交的子集，取m=(l+r)/2 //X[l:m]和X[m+1:r]就是满足要求的分割。 for(int i=l;i<=r;i++) { if(Y[i].p>m) Z[g++]=Y[i]; else Z[f++]=Y[i]; } closest(X,Z,Y,l,m,a,b,d); float dr; PointX ar,br; closest(X,Z,Y,m+1,r,ar,br,dr); if(dr { a=ar; b=br; d=dr; } Merge(Z,Y,l,m,r);//重构数组Y //d矩形条内的点置于Z中 int k=l; for(int i=l;i<=r;i++) { if(fabs(X[m].x-Y[i].x) { Z[k++]=Y[i]; } } //搜索Z[l:k-1] for(int i=l;i { for(int j=i+1;j { float dp=dis(Z[i],Z[j]); if(dp { d=dp; a=X[Z[i].p]; b=X[Z[j].p]; } } } } template void Merge(Type c[],Type d[],int l,int m,int r) { int i = l,j = m + 1,k = l; while((i<=m)&&(j<=r)) { if(c[i]<=c[j]) { d[k++] = c[i++]; } else { d[k++] = c[j++]; } } if(i>m) { for(int q=j; q<=r; q++) { d[k++] = c[q]; } } else { for(int q=i; q<=m; q++) { d[k++] = c[q]; } } } template void MergeSort(Type a[],Type b[],int left,int right) { if(left { int i = (left + right)/2; MergeSort(a,b,left,i); MergeSort(a,b,i+1,right); Merge(a,b,left,i,right);//合并到数组b Copy(a,b,left,right);//复制回数组a } } template void Copy(Type a[],Type b[], int left,int right) { for(int i=left;i<=right;i++) a[i]=b[i]; } 问题场景：在应用中，常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中，常需要了解其邻域中其他几何对象的信息。例如，在空中交通控制问题中，若将飞机作为空间中移动的一个点来看待，则具有最大碰撞危险的2架飞机，就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。 问题描述：给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。严格地说，最接近点对可能多于1对。为了简单起见，这里只限于找其中的一对。 1、一维最接近点对问题 算法思路： 这个问题很容易理解，似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出，找出达到最小距离的两个点即可。然而，这样做效率太低，需要O(n^2)的计算时间。在问题的计算复杂性中我们可以看到，该问题的计算时间下界为Ω(nlogn)。这个下界引导我们去找问题的一个θ(nlogn)算法。采用分治法思想，考虑将所给的n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，然后在每个子集中递归地求其最接近的点对。在这里，一个关键的问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对，因为S1和S2的最接近点对未必就是S 的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n^2/4次计算和比较才能确定S的最接近点对。因此，依此思路，合并步骤耗时为O(n^2)。整个算法所需计算时间T(n)应满足:T(n)=2T(n/2)+O(n^2)。它的解为T(n)=O(n^2)，即与合并步骤的耗时同阶，这不比用穷举的方法好。从解递归方程的套用公式法，我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。 设S中的n个点为x轴上的n个实数x1,x2,..,xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1,x2,..,xn排好序，然后，用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上，在排序算法已经证明，时间复杂度为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此，对这种一维的简单情形，我们还是尝试用分治法来求解，并希望能推广到二维的情形。假设我们用x轴上某个点m将S划分为2个子集S1和S2，使得S1={x∈S|x≤m}；S2={x∈S|x>m}。这样一来，对于所有p∈S1和q∈S2有p 最接近点对问题 一．实验目的： 1.理解算法设计的基本步骤及各步的主要内容、基本要求； 2.加深对分治设计方法基本思想的理解，并利用其解决现实生活中的问题； 3.通过本次实验初步掌握将算法转化为计算机上机程序的方法。 二．实验内容： 1.编写实现算法：给定n对点，在这n对点中找到距离最短的点对。 2.将输出数据存放到另一个文本文件中，包括结果和具体的运行时间。 3.对实验结果进行分析。 三．实验操作： 1.最接近点对查找的思想： 首先，将所有的点对按照x坐标排序，找到x坐标的中位数，将所有的点对分成三部分，横坐标小于x（S1）、等于x（S2）和大于x（S3）的点对，在求取每部分中的最短距离，利用分治法，一步步地分解为子问题，找到最短距离d。由于距离最近的两个点可能在不同的区域中，需要进一步判断。 选择S1中的一个点，由于与它相比较的点的距离不可能超过d，故其配对范围为d*2d的矩形，将这个矩形划分为6份2/d*3/d的小矩形，其对角线的长度为5/6d，小于d,故S1中的任意一个点只需和S2中的6个点比较即可，最终确定最短的距离。 2.取中位数： 为了减少算法的时间开销，需要将所有的点对进行分组，以中位数为基准，考虑到快速排序的不稳定性，本次排序使用了合并排序。 代码实现： template 华南农业大学期末考试试卷（A卷）2008学年第一学期考试科目：算法分析与设计 考试类型：（闭卷）考试时间：120 分钟 学号姓名年级专业 一、选择题（20分，每题2分） 1.下述表达不正确的是。 A．n2/2 + 2n的渐进表达式上界函数是O(2n) B．n2/2 + 2n的渐进表达式下界函数是Ω(2n) C．logn3的渐进表达式上界函数是O(logn) D．logn3的渐进表达式下界函数是Ω(n3) 2.当输入规模为n时，算法增长率最大的是。 A．5n B．20log 2n C．2n2 D．3nlog 3 n 3.T（n）表示当输入规模为n时的算法效率，以下算法效率最优的是。A．T（n）= T（n – 1）+1，T（1）=1 B．T（n）= 2n2 C．T（n）= T（n/2）+1，T（1）=1 D．T（n）= 3nlog 2 n 4.在棋盘覆盖问题中，对于2k×2k的特殊棋盘（有一个特殊方块），所需的L型骨 牌的个数是。 A．（4k– 1）/3 B．2k /3 C．4k D．2k 5.在寻找n个元素中第k小元素问题中，若使用快速排序算法思想，运用分治算 法对n个元素进行划分，应如何选择划分基准？下面答案解释最合理。 A．随机选择一个元素作为划分基准 B．取子序列的第一个元素作为划分基准 C．用中位数的中位数方法寻找划分基准 D．以上皆可行。但不同方法，算法复杂度上界可能不同 6.有9个村庄，其坐标位置如下表所示： 现在要盖一所邮局为这9个村庄服务，请问邮局应该盖在才能使到邮局到这9个村庄的总距离和最短。 A．（4.5，0）B．（4.5，4.5）C．（5，5）D．（5，0） 7.n个人拎着水桶在一个水龙头前面排队打水，水桶有大有小，水桶必须打满水， 水流恒定。如下说法不正确？ A．让水桶大的人先打水，可以使得每个人排队时间之和最小 B．让水桶小的人先打水，可以使得每个人排队时间之和最小 C．让水桶小的人先打水，在某个确定的时间t内，可以让尽可能多的人打上水D．若要在尽可能短的时间内，n个人都打完水，按照什么顺序其实都一样 8.分治法的设计思想是将一个难以直接解决的大问题分割成规模较小的子问题， 分别解决子问题，最后将子问题的解组合起来形成原问题的解。这要求原问题和子问题。 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。这种最小距离问题实际上也就是距离最近的点对问题。 如果不用分治法，问题非常容易解决。也就是蛮力法。 代码如下： #include { int n, i; double d; printf("输入点的个数："); scanf("%d", &n); Point a[10000]; while (n) { for (i = 0; i < n; i++) scanf("%lf%lf", &(a[i].x), &(a[i].y)); d = nearest(a,n); printf("%.2lf\n", d); scanf("%d", &n); } return 0; } 但是本题是用分治法，我也参考了网上很多资料，他们要求对纵坐标进行排序，可能是为了对求右边的问题的点扫描用for 循环，但我发现那算法就不对，但愿是我的还没有完全明白按纵坐标排序的原因， 我参考的资料： https://www.doczj.com/doc/ba10306118.html,/p-198711591.html?qq-pf-to=pcqq.c2c 代码如下： #include 《算法设计与分析》实验报告 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 宁波工程学院电信学院计算机系 实验报告 课程名称：算法设计与分析实验项目：用分治法算法解 最接近点对问题 指导教师：崔迪 实验位置：软件工程实验室姓名： 班级： 学号： 日期： 2016/10/12 一、实验目的 通过上机实验，要求掌握分治法算法的问题描述、算法设计思想、程序设 计和算法复杂性分析等。 二、实验环境： Eclipse 三、实验内容：用分治法解最接近点对问题 （1）问题描述 给定平面S上n个点，找其中的一对点，使得在n(n-1)/2 个点对中，该 点对的距离最小。 （2）算法设计思想 1. n较小时直接求 (n=2). 2.将S上的n个点分成大致相等的2个子集S1和S2 3.分别求S1和S2中的最接近点对 4.求一点在S1、另一点在S2中的最近点对 5.从上述三对点中找距离最近的一对. （3）程序设计（程序清单及说明） package closestpair; import java.util.Arrays; import https://www.doczj.com/doc/ba10306118.html,parator; import java.util.Random; import java.util.Scanner; //定义坐标点 class Point { double x; double y; public Point(double x, double y) { this.x = x; this.y = y; } } // 根据x坐标排序 class MyComparatorX implements Comparator 算法分析与设计实验报告第四次附加实验 while (a[--j]>x); if (i>=j) { break; } Swap(a[i],a[j]); } a[p] = a[j]; //将基准元素放在合适的位置 a[j] = x; return j; } //通过RandomizedPartition函数来产生随机的划分 template vclass Type> int RandomizedPartition(Type a[], int p, int r) { int i = Random(p,r); Swap(a[i],a[p]); return Partition(a,p,r); } 较小个数排序序列的结果: 测试结果 较大个数排序序列的结果: 实验心得 快速排序在之前的数据结构中也是学过的，在几大排序算法中，快速排序和归并排序尤其是 重中之重，之前的快速排序都是给定确定的轴值，所以存在一些极端的情况使得时间复杂度 很高，排序的效果并不是很好，现在学习的一种利用随机化的快速排序算法，通过随机的确 定轴值，从而可以期望划分是较对称 的，减少了出现极端情况的次数，使得排序的效率挺高了很多， 化算法想呼应，而且关键的是对于随机生成函数，通过这一次的 学习终于弄明白是怎么回事了，不错。 与后面的随机实 验和自己的 实验得分助教签名 附录： 完整代码(分治法) //随机后标记元素后的快速排序 #i nclude 一、算法分析 该算法的问题描述为：给定二维平面上的点集，求解距离最近的两个点，并计算出两点间的距离。 解决问题最初的思路为穷举法。对所有两点间的组合计算其距离。然后对其进行比较，找出最小值即可。不过这样做的缺点是时间复杂度和空间复杂度十分庞大，消耗巨量资源。如有n个点的平面上，计算的复杂度能达到n*n。因此设计出一个高效的算法来代替穷举法是有现实意义的。 在思考问题的过程中，可以考虑使用分治法的思想，以x，y中x坐标作为划分区间的标准。将平面点集一分为二。求解其中的最小点对。由此产生的问题为划分点附近两个区间中两点的距离可能小于各自区间中的最小值，产生了纰漏。因此在在分治的过程中，加入分界线附近的点对最小值求解函数。分界线区域内区间的选取标准为d。其中d为左半区间和右半区间的最小值中的较小值。在具体实现中，首先建立一个空数组存放按y坐标排序的点集，判断两个相邻点之间的y坐标差值，若大于d，则两点间距离一定大于d，可以直接跳过，继续判断下一个点对。若小于d，则继续计算两点间的实际距离，若大于d，则跳过，小于d，将最小值更新为该点对距离。 二、算法实现 该算法的具体实现使用了两种求解方法，穷举法和分治法。其中，穷举法用于判断最近点对算法实现结果的正确性。 算法使用的数据结构为数组，其中为了简单起见，将x轴坐标与y轴坐标分别存入两个数组，并新建一个数组record[]，记录数组y的元素下标，用于绑定x坐标对应的y坐标。 在设计过程中使用到了比较排序算法，用于对x及y坐标排序，这并不增加其时间复杂度。因此是可行的。 在分治算法中，设置划分区间的下限为3，即当区间内元素个数小于等于3时，不再使用分治。在该设定下分为三种情况，元素数为1时，Min设为无穷。元素数为2时，计算两点间距离并返回。元素数为3时，一共计算三次距离，并取其最小值。 实验报告 （2015 / 2016 学年第二学期） 课程名称 实验名称分治法实现快速排序与两路合并排序 实验时间年月日指导单位计算机学院计算机科学与技术系 指导教师 学生姓名班级学号 学院(系) 专业 实验报告 三、实验原理及内容 实验原理： 分治法：即分而治之。将问题分解为规模较小，相互独立，类型相同的问题进行求解。对于无序数组的有序排序也就是按某种方式将序列分成两个或多个子序列，分别进行排序，再将已排序的子序列合并成一个有序序列。 实验内容： 两路合并排序算法的基本思想是：将待排序元素序列一分为二，得到两个长度基本相等的子序列，其过程类似于对半搜索；然后将子序列分别排序，如果子序列较长，还可以继续细分，知道子序列长度不超过1为止。 以上的实现由下列代码执行： void SortableList::MergeSort() { MergeSort(0,n-1); } void SortableList::MergeSort(int left,int right) { if (left 实验一 实验名称：利用分治法实现快速排序 实验时 2012 年12月成绩： 间： 一、实验目的 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 本实验的目的是利用分治策略实现快速排序算法。 二、实验内容 快速排序算法是基于分治策略的排序算法。其基本思想是，对于输入的子数组a[p:r],按以下三个步骤进行排序。 （1）分解:以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q] 和a[q+1:r]， 使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于 a[q]。下标q在划分过程中确定。 （2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。 （3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1] 和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。 基于这个思想，可实现的快速排序算法如下： void QuickSort(i nt a[],i nt p,i nt r) if(p int q=Partition(a,p,r); QuickSort(a,p,q-1); QuickSort(a,q+1,r); } } 对含有n 个元素的数组a[0;n-1] 进行快速排序只要调用QuickSort(a,0,n-1) 即可。 上述算法中的函数Partition ，以确定的一个基准元素a[p] 对子数组a[p:r] 进行划分，它是快速排序算法的关键。 int Partition(int a[],int p,int r) { int i=p,j=r+1; int x=a[p]; while(true) { while(a[++i] 最近点对问题 I.一维问题： 一、问题描述和分析 最近点对问题的提法是：给定平面上n个点，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。 严格的讲，最接近点对可能多于1对，为简单起见，只找其中的1对作为问题的解。简单的说，只要将每一点与其它n-1个点的距离算出，找出达到最小距离的2点即可。但这样效率太低，故想到分治法来解决这个问题。也就是说，将所给的平面上n个点的集合S 分成2个子集S1和S2，每个子集中约有n/2个点。然后在每个子集中递归的求其最接近的点对。这里，关键问题是如何实现分治法中的合并步骤，即由S1和S2的最接近点对，如何求得原集合S中的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决，但如果这2个点分别在S1和S2中，问题就不那么简单了。下面的基本算法中，将对其作具体分析。 二、基本算法 假设用x轴上某个点m将S划分为2个集合S1和S2，使得S1={x∈S|x<=m}；S2={x ∈S|x>m}。因此，对于所有p∈S1和q∈S2有p 一. 用分治算法解平面最接近点对问题 1.题目 关于最接近点对问题: 给定平面上n个点，找出其中一对点，使得在n个点所构成的所有点对中，该点对的距离最小。 2.程序详细介绍(各模块的功能等) 本程序主要包括两个类:类Point和类Ppoint.其中类Point为处理一些的基本数据传递等.类Ppoint为该程序的主要实现模块,该类中有输入点对的函数shuru,对所输入的点对按X轴排序的函数sort,求各点对的距离的函数xiao等. 假设S中的点为平面上的点，它们都有2个坐标值x和y。为了将平面上点集S线性分割为大小大致相等的2个子集S1和S2，我们选取一垂直线l（方程：x=m）来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1={p∈S|px≤m}和S2={p∈S|px>m}。从而使S1和S2分别位于直线l的左侧和右侧，且S=S1∪S2 。由于m是S中各点x坐标值的中位数，因此S1和S2中的点数大致相等。递归地在S1和S2上解最接近点对问题，我们分别得到S1和S2中的最小距离δ1和δ2.此即为该程序的大致算法. 3. 程序结构（流程图） 该程序的流程图如下所示 4. 调试与测试：调试方法，测试结果（包括输入数据和输出结果）的分析与讨论 运行该程序时,屏幕上会出现一个界面,首先该界面会提示输入要处理的点对个数,输入点对个数后从键盘输入数字0即可显示出处理后的各个结果,会出现如下结果: 5.程序代码(源程序) #include 分治策略 姓名：XXX 专业班级：XXX 学号：XXX 指导教师：XXX 完成日期：XXX 一、试验名称：分治策略 （1）写出源程序，并编译运行 （2）详细记录程序调试及运行结果 二、实验目的 (1)了解分治策略算法思想 (2)掌握快速排序、归并排序算法 (3)了解其他分治问题典型算法 三、实验内容 (1)编写一个简单的程序，实现归并排序。 (2)编写一段程序，实现快速排序。 (3)编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现 要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四、算法思想分析 (1)编写一个简单的程序，实现归并排序。 将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行 排序，最终将排好序的子集合合并成为所要求的排好序的集合。 (2)编写一段程序，实现快速排序。 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数 据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据 变成有序序列。 (3)编写程序实现循环日赛表。 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通 过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割， 直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让 这2个选手进行比赛就可以了。 五、算法源代码及用户程序 (1)编写一个简单的程序，实现归并排序。 #include 棋盘覆盖问题 问题描述： 在一个2k ×2k （k ≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中出现的位置有4k 中情形，因而有4k 中不同的棋盘，图（a ）所示是k=2时16种棋盘中的一个。棋盘覆盖问题要求用图（b ）所示的4中不同形状的L 型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且热河亮哥L 型骨牌不得重复覆盖。 问题分析： K>0时，可将2k ×2k 的棋盘划分为4个2k-1×2k-1的子棋盘。这样划分后，由于原棋盘只有一个特殊方格，所以，这4个子棋盘中只有1个子棋盘中有特殊方格，其余3个子棋盘中没有特殊方格。为了将这3个没有特殊方格的子棋盘转化成为特殊棋盘，以便采用递归方法求解，可以用一个L 型骨牌覆盖这3个较小的棋盘的会合处，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种划分策略，直至将棋盘分割为1×1的子棋盘。 问题求解： 下面介绍棋盘覆盖问题中数据结构的设计。 （1） 棋盘：可以用一个二维数组board[size][size]表示一个棋盘，其中size=2k 。为了 在递归处理的过程中使用同一个棋盘，将数组board 设为全局变量。 （2） 子棋盘：整个棋盘用二维数组board[size][size]表示，其中的子棋盘由棋盘左上 角的下标tr 、tc 和棋盘大小s 表示。 （3） 特殊方格：用board[dr][dc]表示特殊方格，dr 和dc 是该特殊方格在二维数组 board 中的下标。 （4） L 型骨牌：一个2k ×2k 的棋盘中有一个特殊方格，所以，用到L 型骨牌的个数 为（4k -1）/3，将所有L 型骨牌从1开始连续编号，用一个全局变量tile 表示。 图（b ） 图 （a ） 中南大学 《算法设计与分析》实验报告 姓名： 专业班级： 学号： 指导教师： 完成日期：2010.1 一．实验名称 分治算法实验 二．实验目的 1. 了解分治策略算法思想 2. 掌握快速排序、归并排序算法 3. 了解其他分治问题典型算法 三．实验内容 1. 编写一个简单的程序，实现归并排序。 2. 编写一段程序，实现快速排序。 3. 编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表：（1）每个选手必须与其它n-1个选手各赛一次（2）每个选手一天只能赛一场（3）循环赛进行n-1天 四．算法思想分析 1. 归并排序 归并排序算法思想: 分而治之(divide - conquer)，即每个递归过程涉及三个步骤：第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括n/2 个元素。第二, 治理: 对每个子序列分别调用归并排序MergeSort，进行递归操作。第三, 合并: 合并两个排好序的子序列,生成排序结果。 归并操作的工作原理如下： （1）申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 （2）设定两个指针，最初位置分别为两个已经排序序列的起始位置 （3）比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 （4）重复步骤3直到某一指针达到序列尾 （5）将另一序列剩下的所有元素直接复制到合并序列尾 比较操作的次数介于(nlogn) / 2和nlogn ? n + 1。赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：Θ (n) 2. 快速排序 快速排序法的基本精神是在数列中找出适当的轴心，然后将数列一分为二，分别对左边与右边数列进行排序，而影响快速排序法效率的正是轴心的选择。 （1）分解：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。 （2）递归求解：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。 （3）合并：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。 3. 循环赛日程表 按分治策略，将所有的选手分为两组，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就可以简单的处理了。 五．算法源代码及用户屏幕 1.归并排序 （备注：语言C++；编译器：MS VS2008；共2个文件） head.h文件 #include 一、最接近点对问题（一维） 1、最接近点对问题（一维） 最接近点对问题:给定平面上n个点，找其中的一对点，使得在n个点的所有点对中，该点对的距离最小。此时S中的n个点退化为x轴上的n个实数x1,x2,..,x n。最接近点对即为这n 个实数中相差最小的2个实数。 2、分析 将所给的平面上n个点的集合S分成2个子集S1和S2，每个子集中约有n/2个点，·然后在每个子集中递归地求其最接近的点对。S1和S2的最接近点对未必就是S的最接近点对，如果组成S的最接近点对的2个点都在S1中或都在S2中，则问题很容易解决。但是，如果这2个点分别在S1和S2中，则对于S1中任一点p，S2中最多只有n/2个点与它构成最接近点对的候选者，仍需做n2/4次计算和比较才能确定S的最接近点对。 因此，依此思路，合并步骤耗时为O(n2)。 整个算法所需计算时间T(n)应满足: T(n)=2T(n/2)+O(n2) 它的解为T (n)=O(n2) 3、伪代码 随机Random float Random() { float result=rand()%10000; return result*0.01; } 返回最大、最小 float Max OR Min(float s[],int p,int q)//返回s[]中的最大值 { float s_max（s_min）=s[p]; for(int i=p+1;i<=q;i++) if(s_max 实验一 实验名称：利用分治法实现快速排序实验时间: 2012年12月成绩：一、实验目的 分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。 本实验的目的是利用分治策略实现快速排序算法。 二、实验内容 快速排序算法是基于分治策略的排序算法。其基本思想是，对于输入的子数组a[p:r],按以下三个步骤进行排序。 （1）分解：以a[p]为基准元素将a[p:r]划分成3段a[p:q-1],a[q]和a[q+1:r]，使a[p:q-1]中任何一个元素小于等于a[q]，而a[q+1:r]中任何一个元素大于等于a[q]。下标q在划分过程中确定。 （2）递归求解：通过递归调用快速排序算法分别对a[p:q-1]和a[q+1:r]进行排序。 （3）合并：由于对a[p:q-1]和a[q+1:r]的排序是就地进行的，所以在a[p:q-1]和a[q+1:r]都已排好的序后，不需要执行任何计算，a[p:r]就已排好序。基于这个思想，可实现的快速排序算法如下：void QuickSort(int a[],int p,int r) { if(p 实验七最近点对问题的设计与实现 一、实验目的 1．掌握分治算法的基本原理 2．利用分治策略编程解决最近点对问题 二、实验要求 1．设计算法 2．写出相应程序 3．保存和打印出程序的运行结果，并结合程序进行分析。 三、实验内容 算法思想：用分治法解决最近对问题，很自然的想法就是将集合S分成两个子集S1和S2，每个子集中有n/2个点。然后在每个子集中递归地求其最接近的点对，在求出每个子集的最接近点对后，在合并步中，如果集合S 中最接近的两个点都在子集S1或S2中，则问题很容易解决，如果这两个点分别在S1和S2中，则根据具体情况具体分析。 1、考虑一维情形下的最近点对问题： 设x1, x2, …, xn是x轴上有n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。 算法思想：用x轴上的某个点m将S划分为两个集合S1和S2，并且S1和S2含有点的个数近似相同。递归地在S1和S2上求出最接近点对 (p1, p2) 和(q1, q2)，如果集合S 中的最接近点对都在子集S1或S2中，则d=min{(p1, p2), (q1, q2)}即为所求，如果集合S中的最接近点对分别在S1和S2中，则一定是(p3, q3)，其中，p3是子集S1中的最大值，q3是子集S2中的最小值。 例如：(1)输入 -8，-5，-4，1，3，7，输出为1. (2)输入 -8，-5，-2，1，3，7，输出为2. (3)输入 -8，-4，-1，1，4，7，输出为2. 附加题：（有时间可继续完成下面内容） 2、考虑一维情形下的最近点对问题： 设p1=(x1, y1), p2=(x2, y2), …, p n=(x n, y n)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。 算法： 算法实验报告一分治法实验 一、实验目的及要求 利用分治方法设计大整数乘法的递归算法，掌握分治法的基本思想和算法设计的基本步 骤。 要求：设计十进制的大整数乘法，必须利用分治的思想编写算法，利用c语言（或者c++ 语言）实现算法，给出程序的正确运行结果。（必须完成） 设计二进制的大整数乘法，要求利用分治的思想编写递归算法，并可以实现多位数的乘 法（利用数组实现），给出程序的正确运行结果。（任选） 二、算法描述 1、 输入两个相同位数的大整数u，v 输出uv的值 判断大整数的位数i； w=u/10^(i/2); y=v/10^(i/2); x=u-w*10^(i/2); z= v-y*10^(i/2); 然后将w,x,y,z代入公式求得最后结果 uv=wy10^i+((w+x)(y+z)-wy-xz)10^(i/2)+xz 三、调试过程及运行结果 在实验中我遇到的问题： 原来以为这两个大整数的位数不同，结果题目要求是相同位数的大整数在写10的多少 次方时，写的是10^(i/2),10^(i)，结果不对，我就将它改成了for循环语句 四、实验总结 在本次实验中，我知道了分治算法，以及分治算法的基本思想。我还掌握了编写大整数 乘法的算法与步骤，以及如何修改在编写程序时遇到的问题。 五、附录（源程序代码清单） 1、#include<iostream.h> int weishu(int x) { int i; while(x!=0) { x=x/10; i++; } return i; } void main() { int u,v; cout<<输入两个位数相同的大整数:<<endl; cin>>u; cin>>v;0007算法笔记——【分治法】最接近点对问题
最接近点对问题实验报告
2009.1算法设计与分析课程期末试卷-A卷(自测 )
最近点对分治法
算法分析实验报告--分治策略
分治法实验报告一
分治算法实验(用分治法实现快速排序算法)
算法实验四_空间最近点对算法
分治法实现快速排序与两路合并排序
分治法实现快速排序
最近点对问题
用分治算法解平面最接近点对问题
算法分析实验报告--分治策略
用分治法求解棋盘覆盖问题
分治算法实验
最接近点对问题
分治法实现快速排序
实验七 最近点对问题的设计与实现
分治法实验报告
相关主题
文本预览