《算法第四版》课后练习题1.2.1答案

习题1.2.1

编写一个Point2D的用例，从命令行接受一个整数 N 。在单位正方形内生成 N 个随机点，然后计算两点之间的最近距离。

要点分析

1.  Point2D

关于Point2D的相关介绍请看课本第46页

2.  计算距离

Point2D类为我们提供了用于计算欧几里得距离的方法：distanceTo(Point2D that) ，该方法用于计算该店到that的欧几里得距离

（注意：在课本上是disTo，应该是印刷错误，在查询了Point2D类中，并没有该方法）

关于欧几里得距离：欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。[1] 

另外此题计算两点之间的最近距离是指计算所有点中，最近的两个点的距离。

参考答案

import edu.princeton.cs.algs4.Point2D;

import java.util.Arrays;
import java.util.Random;

/**
 * @description: Point2D用例
 * @author: ZhangJia
 * @create: 2018-08-01 18:56
 **/
public class One {
    /**
    * @description: 在单位正方形内生成N个随机点
    * @param:  存储随机点的数组
    * @return:  Nothing
    */
    public static void Genetate_Point(Point2D[] a) {
        for (int i = 0; i < a.length; i++) {
            a[i] = new Point2D(Math.random(),Math.random());//在单位正方形内随机生成一个点
            a[i].draw();
        }
    }

    /**
    * @description: 计算最近的两个点的距离
    * @param:  存储随机点的数组
    * @return:  最近的距离
    */

    public static double distance(Point2D[] a) {
        double min = 200;
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = i + 1; j < a.length; j++) {
               double b =  a[i].distanceTo(a[j]);
                min = (min < b) ? min : b;
            }
        }
        return min;
    }
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        Point2D[] p = new Point2D[N];
        Genetate_Point(p);
        System.out.println(distance(p));;
    }

}

参考资料

[1] 百度百科：欧几里得度量