算法练习(13):随机连接(1.1.31)

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 绘点
• 随机函数

题目

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

---

1.1.31 Random connections. Write a program that takes as command-line arguments an integer N and a double value p (between 0 and 1), plots N equally spaced dots of size .05 on the circumference of a circle, and then, with probability p for each pair of points, draws a gray line connecting them.

分析

这道题考察了Random库和StdDraw库的使用

Random的方法的使用
StdRandom.uniform()方法生成0到1之间的数；
StdDraw.point(0.5, 0.5)方法可以生成居中的点
举例，代码

//设置画笔颜色
StdDraw.setPenColor(StdDraw.RED);
//设置画笔的大小
StdDraw.setPenRadius(0.5);
//画个点
StdDraw.point(0.5, 0.5);

的效果如下

这也从侧面印证，不设置X轴和Y轴的话，默认的X轴Y轴大小是1个单位。

接着我们继续分析题目，首先我们要画个圆，画圆的方法是
public static void circle(double x, double y, double radius)
举例，我们通过如下代码一个半径为0.5的圆
StdDraw.circle(0.5, 0.5, 0.5);
如图:

解决了这个画圆，画点的问题后，我们开始着手找这道题的解题思路，首先，我们要在圆上画点，而且这些点需要满足距离相等，那假设要画N个点，点与点之间的角度为360/N。

Point[] points = new Point[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);
}

这样就画出了这N个点。

答案

public class RandomConnectSample {
    
    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 = 10;
        double p =  StdRandom.uniform();

        //算出角度
        double angle = 360.0 / N;
        StdDraw.circle(0.5, 0.5, 0.5);
        
        Point[] points = new Point[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);
        }
        
        StdDraw.setPenColor(StdDraw.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);
                }
            }
        }
        
    }

}

代码索引

RandomConnectSample.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。