算法概论实验三

算法概论实验

实验三
实验目的与要求：理解分治法的基本思想和设计方法。
实验题目：
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];
}