算法概论实验三

---

实验三

实验目的与要求：理解分治法的基本思想和设计方法。

实验题目：

1．寻找中项
【问题描述】
   对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中项。

2．寻找最邻近的点对
【问题描述】
设p1=(x1,y1), p2=(x2,y2), … , pn=(xn,yn) 是平面上n个点构成的集合S，设计和实现找出集合S中距离最近点对的算法。

#1.寻找中项

#include<iostream>
using namespace std;

struct partIndex
{
	int partIndex0;
	int partIndex1;
};


//将arrray分成三块，并返回各块的下标
partIndex partition(int *r, int low, int high) {
	// TODO 把数组段第一个数划分，并返回中间值的下标
	int pivot = r[low];// 记录pivot
	while (low < high)
	{
		while (low < high && r[high] > pivot)
			high--;
		if (low < high)
			r[low++] = r[high];
		while (low < high && r[low] < pivot)
			low++;
		if (low < high)
			r[high--] = r[low];
	}
	r[low] = pivot;

	partIndex pi; pi.partIndex0 = low; pi.partIndex1 = high;

	while (r[pi.partIndex0 - 1] == pivot)
	{
		pi.partIndex0--;
	}
	while (r[pi.partIndex1 + 1] == pivot)
	{
		pi.partIndex1++;
	}
	return pi;
}

/出 arrray中第k小的元素
int select(int *array, int startIndex, int endIndex, int k)
{
	int kItem;
	//只有2个元素的情况，返回相应值
	if (endIndex - startIndex < 2)
	{
		if (array[startIndex] < array[endIndex])
			kItem = k == 1 ? array[startIndex] : array[endIndex];
		else
			kItem = k == 1 ? array[endIndex] : array[startIndex];
		return kItem;
	}
	//小于段(0,partIndex0)  大于段（partIndex1,endIndex）
	partIndex pi = partition(array, startIndex, endIndex);
	if (k <= pi.partIndex0 - startIndex)
	{
		kItem = select(array, startIndex, pi.partIndex0, k);
	}
	else
	{
		if (k > pi.partIndex1 - startIndex + 1)
		{
			kItem = select(array, pi.partIndex1, endIndex, k - (pi.partIndex1 - startIndex) - 1);
		}
		else
		{
			kItem = array[pi.partIndex0];
		}
	}
	return kItem;
}





int main()
{
	int array[43] = { 76, 80, 82, 88 };
	int len = 4;
	cout << "分治算法求的的中位数为:" << select(array, 0, len - 1, len / 2);
	return 0;
}

#2．寻找最邻近的点对

import java.util.Random;
public class MinDistance {
	
	public static void main(String []agrs){
		Point[] points = getRandomPoints(1000, 1000);
		System.out.println("分治法求得:");
		Point[] minPair1 = getMinPair_DC(points, 0, points.length - 1);
		printMinPair(minPair1);
	}
	//compute the minimun distance by divide and conquer
	/**
	 * 
	 * @param points
	 * @return
	 */
	private static Point[] getMinPair_DC(Point[] points, int startIndex, int endIndex){
		int len = endIndex - startIndex + 1;
		double []arrayX = new double [len];
		for(int i = startIndex; i < len; i++){
			arrayX[i] = points[i].x;
		}
		quickSort(points, arrayX, startIndex, endIndex);
		return getMinPair(points, startIndex, endIndex);
	}
	
	/**
	 * 
	 * @param points
	 * @param startIndex
	 * @param endIndex
	 * @return
	 */
	private static Point[] getMinPair(Point[] points, int startIndex, int endIndex){
		Point[] minPair = new Point[2];
		if(endIndex <= startIndex){
			minPair[0] = points[startIndex];
			minPair[1] = null;
			return minPair;
		}
		if(endIndex - startIndex == 1){
			minPair[0] = points[startIndex];
			minPair[1] = points[endIndex];
			return minPair;
		}
		double minDis = Double.MAX_VALUE;
		int mid = (endIndex + startIndex) / 2;
		Point[] minPair0 = getMinPair(points, startIndex, mid);
		Point[] minPair1 = getMinPair(points, mid, endIndex);
		minPair = minPair0[0].getDistance(minPair0[1]) < minPair1[0].getDistance(minPair1[1]) ? minPair0 : minPair1;
		minDis = minPair[0].getDistance(minPair[1]);
		int midLeft, midRight;
		for(midLeft = mid; points[mid].x - points[midLeft].x < minDis && midLeft > startIndex; midLeft --){}
		for(midRight = mid; points[midRight].x - points[mid].x < minDis && midRight < endIndex; midRight ++){}
		int midNum = midRight - midLeft + 1;
		Point[] midAreaPoints = new Point[midNum];
		double [] arrayY = new double[midNum];
		System.arraycopy(points, midLeft, midAreaPoints, 0, midNum);
		for(int i = 0; i < midNum ; i ++){
			arrayY[i] = points[i].y;
		}
		quickSort(midAreaPoints, arrayY, 0, midNum - 1);
		for(int i = 0 ; i < midNum ;i ++){
			for(int j = i+1 ; j < midNum && j< i + 11; j ++){
				if(midAreaPoints[i].getDistance(midAreaPoints[j]) < minDis){
					minPair[0] = midAreaPoints[i];
					minPair[1] = midAreaPoints[j];
					minDis = midAreaPoints[i].getDistance(midAreaPoints[j]);
				}
			}
		}
		return minPair; 
	}
	
	

	/**
	 * 
	 * @param maxValue
	 * @param len
	 * @return
	 */
	private static Point[] getRandomPoints(int maxValue, int len){
		Point [] points = new Point[len];
		java.util.Random r = new Random();
		for(int i = 0; i < len; i++){
			points[i] = new Point();
			points[i].setx(r.nextDouble() * maxValue);
			points[i].sety(r.nextDouble() * maxValue);
		}
		return points;
	}
	
	/**
	 * 
	 * @param pointPair
	 */
	private static void printMinPair(Point[] minPair){
		if(minPair.length != 2){
			System.err.println("传入数据错误");
		}
		System.out.println("两点:" + minPair[0].toString() + "," + minPair[1].toString());
		System.out.println("距离:" + minPair[0].getDistance(minPair[1]));
	}

	/**
	 * 
	 * @param points
	 * @param array
	 * @param startIndex
	 * @param endIndex
	 */
	static void quickSort(Point[] points, double[]array, int startIndex, int endIndex){
		if(startIndex < endIndex)
		{
			int mid = partition(points, array, startIndex, endIndex);
			quickSort(points, array, startIndex, mid);
			quickSort(points, array, mid+1, endIndex);
		}
	}
	
	/**
	 * 
	 * @param points
	 * @param array
	 * @param startIndex
	 * @param endIndex
	 * @return
	 */
	static int partition(Point[] points, double []array, int startIndex, int endIndex){
		int i = startIndex;
		int j = endIndex;
		double pivot = array[startIndex];
		Point pivotP = points[startIndex];
		while(i < j){
			while(array[j] > pivot && i < j){
				j--;
			}
			if(i < j){
				points[i] = points[j];
				array[i++] = array[j];
			}
			while(array[i] < pivot && i < j){
				i++;
			}
			if(i < j){
				points[j] = points[i];
				array[j--] = array[i];
			}
		}
		array[i] = pivot;
		points[i] = pivotP;
		return j;
	}
}

class Point{
	double x;
	double y;
	Point(){
		this.x = 0;
		this.y = 0;
	}
	Point(double x, double y){
		this.x = x;
		this.y = y;
	}
	void setx(double x){
		this.x = x;
	}
	void sety(double y){
		this.y = y;
	}
	double getDistance(Point p){
		if(p == null){
			return Double.MAX_VALUE;
		}
		return Math.sqrt((p.x - this.x) * (p.x - this.x) + (p.y - this.y) * (p.y - this.y));
	}
	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "(" + this.x + "," +this.y + ")";
	}
}

#2．寻找最邻近的点对

//二维最邻近点对问题  
//#include "stdafx.h"  
#include<time.h>  
#include<iostream>   
#include<cmath>  

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 <class Type>
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 <typename Type>
void Copy(Type a[], Type b[], int left, int right);

template <class Type>
void Merge(Type c[], Type d[], int l, int m, int r);

template <class Type>
void MergeSort(Type a[], Type b[], int left, int right);

int main()
{
	srand((unsigned)time(NULL));
	int length;

	cout << "请输入点对数：";
	cin >> length;

	PointX X[M];
	cout << "随机生成的二维点对为：" << endl;

	for (int i = 0; i<length; i++)
	{
		X[i].ID = i;
		X[i].x = Random();
		X[i].y = Random();
		cout << "(" << X[i].x << "," << X[i].y << ") ";
	}

	PointX a;
	PointX b;
	float d;

	Cpair2(X, length, a, b, d);

	cout << endl;
	cout << "最邻近点对为：(" << a.x << "," << a.y << ")和(" << b.x << "," << b.y << ") " << endl;
	cout << "最邻近距离为： " << d << endl;

	return 0;
}

float Random()
{
	float result = rand() % 10000;
	return result*0.01;
}

//平面上任意两点u和v之间的距离可计算如下  
template <class Type>
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<n; i++) //将数组X中的点复制到数组Y中  
	{
		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<d)
	{
		a = ar;
		b = br;
		d = dr;
	}

	Merge(Z, Y, l, m, r);//重构数组Y  

	//d矩形条内的点置于Z中  
	int k = l;
	for ( i = l; i <= r; i++)
	{
		if (fabs(X[m].x - Y[i].x)<d)
		{
			Z[k++] = Y[i];
		}
	}

	//搜索Z[l:k-1]  
	for ( i = l; i<k; i++)
	{
		for (int j = i + 1; j<k && Z[j].y - Z[i].y<d; j++)
		{
			float dp = dis(Z[i], Z[j]);
			if (dp<d)
			{
				d = dp;
				a = X[Z[i].p];
				b = X[Z[j].p];
			}
		}
	}
}

template <class Type>
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 <class Type>
void MergeSort(Type a[], Type b[], int left, int right)
{
	if (left<right)
	{
		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 <typename Type>
void Copy(Type a[], Type b[], int left, int right)
{
	for (int i = left; i <= right; i++)
		a[i] = b[i];
}