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

习题1.1.31

随机连接。编写一段程序，从命令行接受一个整数 N 和 double 值 p(0 到 1 之间)作为参数，在一个圆上画出大小为 0.05 且间距相等的 N 个点，然后将每对点按照概率 p 用灰线连接。

要点分析

因为本题设计到很多图库的操作，所以我们可以先找出所有的操作可能用到的方法，再根据题意一步步的解题即可：

一.
因为本题设计到画圆操作，所以要用到本书为我们提供的标准绘图库StdDraw（详见课本P26），画圆需要用到的方法为：

public static void circle(double x, double y, double r) //x和y为圆心坐标，r为半径

二.
在圆上画出的大小0.05的点，设置点的大小为0.05需要的方法为（详见课本P26）：

static void setPenRadius(double r) //将画笔的粗细半径设为r

三.
在圆上画出的大小0.05的点，画点需要用到的方法为（详见课本P26）：

static void point(double x, double y) //将画笔的颜色设置为c

四.
每对点需要用灰色连接，点设置为灰色需要的方法为（详见课本P26）：

static void setPenColor(Color c) //根据参数坐标画出一个以(x,y)为中心的点

五.
获取概率p需要的方法为（详见课本18页）

static boolean bernoulli(double p)//返回真的概率为p

六.
每对点之间的连线，需要用到的方法为（详见课本P26）

static void line(double x0, double y0, double x1, double y1)
//根据参数的坐标画出一条连接点(x0,y0)和点(x1,y1)的线段

七.
通过第3步我们知道，所有点的操作都需要点的坐标，所以我们可以创建一个坐标类，用于存储坐标值，为了方便操作，我们可以使用匿名内部类的方式创建Point类（这一步也可以直接用一个二维数组代替）：

static class Point {
    double x;
    double y;

    public Point(double x, double y) {
        super();
        this.x = x;
        this.y = y;
    }
}

八.
知道需要使用的方法后，我们再来分析本题，本题的一大难点就是获取N个点的坐标，如果将圆的周长看成一个直线，将N个点，等举例的在这条线上画出来很简单，但是一旦变成圆，便没有了思路，在查询了kyson博客后，才知道可以使用角度的方法来解决这个问题，可以设N个点的点与点之间的角度为360/N：

for (int i = 0; i < N; i++) {
    points[i] = new Point(0.5 + 0.5 * Math.cos(angle * i * Math.PI / 180),
            0.5 + 0.5 * Math.sin(angle * i * Math.PI / 180));
    StdDraw.point(points[i].x, points[i].y);
}

九.
因为本文用到了静态类，这里补充一些静态类基础的知识点：

静态内部类特点

可以当做类的静态成员
使用static修饰的内部类叫做静态内部类
静态内部类可以当做和外部类平级的类
静态内部类的实例化
外部类名.内部类名实例名 =new 外部类名.内部类名(参数)

静态内部类的限制

内部类不能和外部类重名
静态内部类不能访问外部类的非静态属性和方法
外部类不能访问静态内部类的非静态属性和方法

参考答案

package tv.zhangjia.one.one;

import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdRandom;

import java.awt.*;


public class Test {
    static class Point {
        double x;
        double y;

        public Point(double x, double y) {
            super();
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        double p = Double.parseDouble(args[1]);
        Point[] points = new Point[N];
        double angle = 360.0 / N;
        StdDraw.circle(0.5, 0.5, 0.5);
        StdDraw.setPenRadius(0.05);
        for (int i = 0; i < N; i++) {
            points[i] = new Point(0.5 + 0.5 * Math.cos(angle * i * Math.PI / 180),
                    0.5 + 0.5 * Math.sin(angle * i * Math.PI / 180));
            StdDraw.point(points[i].x, points[i].y);
        }
        StdDraw.setPenColor(Color.GRAY);
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (StdRandom.bernoulli(p)) {
                    StdDraw.line(points[i].x, points[i].y, points[j].x, points[j].y);
                }
            }
        }
        //该for循环将每个点两两按照StdRandom.bernoulli(p)的结果选择是否连接
        //如果StdRandom.bernoulli(p)为true，则分别将这两个点的坐标作为StdDraw.line()的参数画出一条连接线段
    }
}