算法－第四版－练习1.2.3解答

一时失言乱红尘 2022-04-23 10:18 133阅读 0赞

# 解题思路 #

编写一个Interval2D的用例，从命令行接受参数N、min和max。生成N个随机的2D间隔，其宽度和高均匀地分布在单位正方形中的min和max之间。用StdDraw画出它们并打印出**相交的间隔对的数量**以及**有包含关系的间隔对数量**

# 代码 #

package homework1_2;
    
    import edu.princeton.cs.algs4.Interval1D;
    import edu.princeton.cs.algs4.Interval2D;
    import edu.princeton.cs.algs4.Point2D;
    import edu.princeton.cs.algs4.StdRandom;
    
    /**
     * @description: ${description}
     * @create: 2019-02-07
     **/
    public class E_1_2_3 {
        public static void main(String[] args) {
            int N = 20;//Integer.parseInt(args[0]);
            double min = 0.1;//Double.parseDouble(args[1]);
            double max = 0.9;//Double.parseDouble(args[2]);
            Interval2D[] dd = new Interval2D[N];
            Point2D[] p2d1 = new Point2D[N];
            Point2D[] p2d2 = new Point2D[N];
            for (int i = 0; i < N; i++) {
                double xlo = StdRandom.uniform(min, max);
                double xhi = StdRandom.uniform(min, max);
                if (xlo > xhi) {
                    double temp = xlo;
                    xlo = xhi;
                    xhi = temp;
                }
                double ylo = StdRandom.uniform(min, max);
                double yhi = StdRandom.uniform(min, max);
                if (ylo > yhi) {
                    double temp = ylo;
                    ylo = yhi;
                    yhi = temp;
                }
                p2d1[i] = new Point2D(xlo, ylo);
                p2d2[i] = new Point2D(xhi, yhi);
    
                Interval1D idx = new Interval1D(xlo, xhi);
                Interval1D idy = new Interval1D(ylo, yhi);
                dd[i] = new Interval2D(idx, idy);
            }
            for (int i = 0; i < N; i++) {
                dd[i].draw();
            }
            int count = 0;//相交
            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    boolean intersects = dd[i].intersects(dd[j]);
                    if (intersects) {
                        count++;
                    }
                }
            }
            System.out.println("相交的间隔对数量为: " + count);
            int count2 = 0;//包含
            for (int i = 0; i < N - 1; i++) {
                for (int j = i + 1; j < N; j++) {
                    // 第i个间隔对包含第j个间隔对
                    if (p2d1[i].x() < p2d1[j].x() && p2d1[i].y() < p2d1[j].y() && p2d2[i].x() > p2d2[j].x() && p2d2[i].y() > p2d2[j].y()) {
                        count2++;
    //                   System.out.println("--------------");
    //                   System.out.println(p2d1[i].x()+" "+p2d1[i].y()+" "+p2d2[i].x()+" "+p2d2[i].y());
    //                   System.out.println(p2d1[j].x()+" "+p2d1[j].y()+" "+p2d2[j].x()+" "+p2d2[j].y());
    //                   System.out.println("--------------");
                    }
                    // 第j个间隔对包含第i个间隔对
                    if (p2d1[i].x() > p2d1[j].x() && p2d1[i].y() > p2d1[j].y() && p2d2[i].x() < p2d2[j].x() && p2d2[i].y() < p2d2[j].y()) {
                        count2++;
    //                    System.out.println("--------------");
    //                    System.out.println(p2d1[i].x()+" "+p2d1[i].y()+" "+p2d2[i].x()+" "+p2d2[i].y());
    //                    System.out.println(p2d1[j].x()+" "+p2d1[j].y()+" "+p2d2[j].x()+" "+p2d2[j].y());
    //                    System.out.println("--------------");
                    }
                }
            }
            int count3 = 0;//包含
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (i != j && dd[i].contains(p2d1[j]) && dd[i].contains(p2d2[j])) {
                        count3++;
                    }
                }
            }
            System.out.println("包含2的间隔对数量为: " + count2);
            System.out.println("包含3的间隔对数量为: " + count3);
        }
    }

# 结果 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]

# 控制台 #

![在这里插入图片描述][2019020720483917.png]

# 解题思路 #

1 相交的间隔对:直接利用现成的api即可,1和2相交的话,那么2就不用和1对比了 所以j>i  
2 包含的间隔对:额外存储2个Point2D数组来记录每个Interval2D的坐标,可以利用间隔包含PointD来判断,也可以利用大小来判断,  
1不包含2的话,可能2包含1.所以i和j都是全部去遍历

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0NDUzMzAw_size_16_color_FFFFFF_t_70]: /images/20220321/8c036b5ad9a64d8f907a6a908127a028.png
[2019020720483917.png]: /images/20220321/5cea07cff57c45e1867eaf4221f020ad.png