一、分治法求最近点对问题
1、数据结构：定义三个结构体：点坐标：typedef struct Node
点个数：typedef struct List
最近点：typedef struct CloseNode
2、六大类含实现：1、创建坐标：create(List &L) 2、最近点距离的平方：square(Node a,Node b)
3、冒泡排序：BubbleSort(Node r[],int length)
4、中线左右最近对（分三种情况）：middle(const List & L,CloseNode &cnode,int mid,double midX)
5、分治法：DivideConquer(const List &L,CloseNode &closenode,int begin,int end) 6、主函数
#include<iostream.h>
#include<cmath>
#define TRUE 1
#define FALSE 0
typedef struct Node
{
double x;
double y;
}Node; //坐标
typedef struct List
{
Node* data; //点
int count; //点的个数
}List;
typedef struct CloseNode
{
Node a;
Node b; //计算距离的两个点
double space; //距离平方
}CloseNode;
int n; //点的数目
//输入各点到List中
void create(List &L)
{
cout<<"请输入平面上点的数目:\n";
cin>>n;
L.count=n;
L.data = new Node[L.count]; //动态空间分配
cout<<"输入各点坐标 :x_y):"<<endl;
for(int i=0;i<L.count;++i)
cin>>L.data[i].x>>L.data[i].y;
}
//求距离的平方
double square(Node a,Node b)
{
return ((a.x-b.x)*(a.x-b.x))+((a.y-b.y)*(a.y-b.y));
}
//冒泡排序
void BubbleSort(Node r[],int length)
{
int change,n;
n=length;change=TRUE;
double b,c;
for(int i=0;i<n-1&&change;++i)
{
change=FALSE;
for(int j=0;j<n-i-1;++j)
{
if(r[j].x>r[j+1].x)
{
b=r[j].x;c=r[j].y;
r[j].x=r[j+1].x;r[j].y=r[j+1].y;
r[j+1].x=b;r[j+1].y=c;
change=TRUE;
}
}
}
}
//分治法中先将坐标按X轴从小到大的顺序排列
void paixu(List L)
{
BubbleSort(L.data,L.count); //调用冒泡排序
}
//左右各距中线d的区域的最近对算法
void middle(const List & L,CloseNode &cnode,int mid,double midX)
{
int i,j; //分别表示中线左边，右边的点
double d=sqrt(cnode.space);
i=mid;
while(i>=0&&L.data[i].x>=(midX-d)) //在左边的d区域内
{
j=mid;
while(L.data[++j].x<=(midX+d)&&j<=L.count) //在右边的d区域内
{
if(L.data[j].y<(L.data[i].y-d)||L.data[j].y>(L.data[i].y+d)) //判断纵坐标是否在左边某固定点的2d区域内
continue;
double space = square(L.data[i],L.data[j]);
if(cnode.space>space) //在满足条件的区域内依次判断
{
cnode.a=L.data[i];
cnode.b=L.data[j];
cnode.space=space;
}
}
--i;
}
}
//分治法求最近对
void DivideConquer(const List &L,CloseNode &closenode,int begin,int end)
{
if(begin!=end)
{
int mid = (begin+end)/2; //排列后的中间的那个点
double midX = L.data[mid].x;
DivideConquer(L,closenode,begin,mid); //继续在左半边用分治法求最近对
DivideConquer(L,closenode,mid+1,end); //继续在右半边用分治法求最近对
middle(L,closenode,mid,midX); //判断左右各距中线d的区域，是否有最近对
}
}
void main()
{
//初始化
List list;
CloseNode closenode;
closenode.space = 10000; //最近点的距离
create(list); //输入各点到NList中
cout<<"各点坐标为:"<<endl;
for(int i=0;i<list.count;++i)
cout<<"X="<<list.data[i].x<<" Y="<<list.data[i].y<<"\n";
cout<<"用分治法求最近对:"<<endl;
paixu(list);
cout<<"经过排序后的各点:"<<endl;
for(int j=0;j<list.count;++j)
cout<<"X="<<list.data[j].x<<" Y="<<list.data[j].y<<"\n";
DivideConquer(list,closenode,0,list.count-1);
cout<<"最近对为点 ("<<closenode.a.x<<","<<closenode.a.y<<")和点("<<closenode.b.x<<","<<closenode.b.y<<")\n"<<"最近距离为: "<<sqrt(closenode.space)<<endl;
}
二、采用贪心算法解决单会场安排问题
1、数据结构：
首先，定义两个数组s[N]、f[N]分别记录活动的开始时间和结束时间。对结束时间f[n]进行递增的排序并显示，N为活动总数。
在定义一数组A[N]存放选中的活动，其中s[i]: 第i个活动的开始时间、f[j]: 当前加入A集合中活动的最大结束时间。
当s[i]>f[j]时，把活动i加入到集合A[N]中，最后输出A[N]中的活动。
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#define N 50
#define TURE 1
#define FALSE 0
int s[N];/*开始时间*/
int f[N];/*结束时间*/
int A[N];/*用A存储所有的*/
int Partition(int *b,int *a,int p,int r);
void QuickSort(int *b,int *a,int p,int r);
void GreedySelector(int n,int *s,int *f,int *A);
int main()
{
int n=0,i;
while(n<=0||n>50)
{
printf("\n");
printf("请输入活动的个数,n=");
scanf("%d",&n);
if(n<=0) printf("请输入大于零的数!");
else if(n>50) printf("请输入小于50的数!");
}
printf("\n请分别输入开始时间s[i]和结束时间f[i]:\n\n");
for(i=1;i<=n;i++)
{
printf("s[%d]=",i,i);
scanf("%d",&s[i]);
printf("f[%d]=",i,i);
scanf("%d",&f[i]);
printf("\n");
}
QuickSort(s,f,1,n); //按结束时间非减序排列
printf("按结束时间非减序排列如下:\n"); /*输出排序结果*/
printf("\n 序号\t开始时间 结束时间\n");
printf("-------------------------\n");
for(i=1;i<=n;i++)
printf(" %d\t %d\t %d\n",i,s[i],f[i]);
printf("-------------------------\n");
GreedySelector(n,s,f,A);//贪心算法实现活动安排
printf("安排的活动序号依次为：");
for(i=1;i<=n;i++)
{
if(A[i])
printf("\n%d %d-->%d",i,s[i],f[i]);
}
printf("\n");
system("pause");
return 0;
}
//快速排序
void QuickSort(int *b,int *a,int p,int r)
{
int q;
if(p<r)
{
q=Partition(b,a,p,r);
QuickSort(b,a,p,q-1);/*对左半段排序*/
QuickSort(b,a,q+1,r);/*对右半段排序*/
}
}
//产生中间数
int Partition(int *b,int *a,int p,int r)
{
int k,m,y,i=p,j=r+1;
int x=a[p];y=b[p];
while(1)
{
while(a[++i]<x);
while(a[--j]>x);
if(i>=j)
break;
else
{
k=a[i];a[i]=a[j];a[j]=k;
m=b[i];b[i]=b[j];b[j]=m;
}
}
a[p]=a[j];
b[p]=b[j];
a[j]=x;
b[j]=y;
return j;
}
//贪心算法实现活动安排
void GreedySelector(int n,int *s,int *f,int *A)
{
//用集合A来存储所选择的活动
A[1]=TURE; //默认从第一次活动开始执行
int j=1; //j记录最近一次加入到A中的活动
for(int i=2;i<=n;i++)
{
//f[j]为当前集合A中所有活动的最大结束时间
//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]
if(s[i]>=f[j])
{
A[i]=TURE; //当A[i]=TURE时，活动i在集合A中
j=i;
}
else A[i]=FALSE;
}
}
三、基于动态规划的游艇租用问题
1、数据结构：
设游艇出租站有N个，且每两个出租站之间的出租价格均不同，用f[n][n]表示，要解决两个问题，租金的输入
——用类init（）解决； (i:出站台)和(j:入站台)之间的花费动态规划——用类dyna() 解决，难点在于dyna()
类的写法。
动态规划，举个例子：从第一个站到第三个站租金是15元但是我们看到第一个站到第二个站的租金只需5元
第二到第三个站的租金要7元因此我们可用采用先到第二个站把游艇归还然后再从第二个站租用游艇到
第三个站因此我们总共需要的费用就是5+7=12元比直接从第一个站到第三个站要花15元更经济也就是最少花费。
推广到1到N个站台的话是一个优化问题，从1到N个站台的最优解包含前N-1个站的最优解，具有重叠性，把前N-1
个站台看成一个整体，就如上例中的第1到第2站台；再把前N-1个站台做分解，依次类推。。。
#include<iostream>
using namespace std;
#define N 200
int f[N][N]; //任意两站台之间的租金
int n;
void init() //站与站之间的租金输入函数
{
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++) f[i][j]=0;
cout<<"请输入每两站之间的租金："<<endl;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{cout<<"输入"<<i+1<<"站到"<<j+1<<"站的租金："<<endl;
cin>>f[i][j];}
}
void dyna() //(i:出站台)和(j:入站台)之间的花费动态规划
{
for(int k=2;k<n;k++) //k:可停站台,从第二个站台开始
for(int i=0;i<n-k;i++)
{
int j=i+k;
for(int p=i+1;p<j;p++)
{
int temp=f[i][p]+f[p][j]; //temp表示从i到j点经过中间点p并在p点停的费用
