欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HIT_SC:实验回顾 - Lab1

程序员文章站 2024-01-16 10:00:52
...

Magic Squares

不要被中英文结合的要求吓到,这个是四个部分中最简单的。主要涉及两个问题:

  • 判断一个矩阵是否是一个幻方
  • 理解一个针对n为奇数的幻方的生成算法
判断矩阵是否是一个幻方

1.首先使用java输入流按行读入文件。存在一个中间字符串string里,并按“\t”进行分割,分割后的结果放入字符数组中。并记录第一行元素个数及求和。
HIT_SC:实验回顾 - Lab1
这里可以用上面的语句对字符强制转换成整型数

2.接下来按行进行循环,首先记录各行的数字个数,若不等与第一行的即返回false;在对每行求和的同时,将数据存入一个动态二维数组。若求和不等,返回false。
HIT_SC:实验回顾 - Lab1
3.循环结束后比较记录的列数,若行列数不等,返回false;利用填充好数据的二维数组,求解每一列之和,并进行对主副对角线上的数据的求和及检验。

理解一个针对n为奇数的幻方的生成算法

1.思路
简单来说,就是把最小的数放在第一行正中,按规律进行拓展。每个数放在前一个数的右上一格。如果这个数所要放的格已经超出了行的边缘就放在另一个边缘,例如顶行→底行、右列→左列的同一位置的上一行;如果该数在右上角,那么将下一个数放在左下角。如果方格被占用,则使用方格下方的一个方格。
在传入偶数时,会发生数组越界。

2.流程图的绘制

授人以鱼不如授人以渔!
推荐给大家一个网站:

https://online.visual-paradigm.com/cn/

画出的流程图类似下图
HIT_SC:实验回顾 - Lab1

Turtle Graphics

这部分总体难度不大,有一个难点就是凸包问题。唯一涉及到的算法,这个算法应该在本学期的算法设计课程中业有讲到。

由于博主的算法学的很渣,所以查了很久才完成这个问题。在这里对凸包问题留下一个记录——

1.问题分析
凸包定义:一个点集合S的凸包是包含S的最小凸集合。可以假设有一块板子,板子上面有许多钉子,用一根橡皮筋将所有的钉子都围住,凸包就是以橡皮筋圈为边界的区域。
HIT_SC:实验回顾 - Lab1
2.求解思路
本次实验没有要求性能,所以就直接蛮力法来解了。

两点确定一条直线,如果剩余的其它点都在这条直线的同一侧,则这两个点是凸包上的点,否则就不是。
具体操作就是蛮力地直接进行遍历:
点集里面的所有点两两配对,对于每条直线,再检查剩余的 (n-2) 个点是否在直线的同一侧。这里可以利用一个线性代数的知识,结合行列式进行求解:HIT_SC:实验回顾 - Lab1
当上式结果为正,(x3,y3)在直线左侧;为负,在直线右侧。

3.代码示例

    /**
     * Given a set of points, compute the convex hull, the smallest convex set that contains all the points 
     * in a set of input points. The gift-wrapping algorithm is one simple approach to this problem, and 
     * there are other algorithms too.
     * 
     * @param points a set of points with xCoords and yCoords. It might be empty, contain only 1 point, two points or more.
     * @return minimal subset of the input points that form the vertices of the perimeter of the convex hull
     */
    public static Set<Point> convexHull(Set<Point> points) {
    	Set<Point> ans = new HashSet<>();
		int size = points.size();   //记录集合中元素个数
		Point[] pointsT = new Point[size]; 
		points.toArray(pointsT);    //由于set类不能直接访问下标所以进行强转
        //只有一个点
        if (size == 1){
            ans.add(pointsT[0]);
            return ans;
        }
        //对点i,j形成的直线两侧的点的个数进行判断
        for (int i = 0; i < size-1; i++){
            for (int j = i + 1; j < size; j++){
                int oneSide = 0, otherSide = 0;
                for (int k = 0; k < size; k++){
                    if (k == i || k == j) {
                        continue;
                    }
                    if (calcuTriangle(pointsT[i], pointsT[j], pointsT[k]) > 0){
                        oneSide++;
                    }
                    if (calcuTriangle(pointsT[i], pointsT[j], pointsT[k]) < 0){
                        otherSide++;
                    }
                    if (calcuTriangle(pointsT[i], pointsT[j], pointsT[k]) == 0){
                    	oneSide++;
                        otherSide++;
                    }
                }
                if (oneSide == 0 || otherSide == 0){  //如果任意一侧点的个数为0,则为凸包集合中的点
                    ans.add(pointsT[i]);
                    ans.add(pointsT[j]);
                }
            }
        }
        return ans;
    }
    //计算是否满足凸包集合的行列式
    private static double calcuTriangle(Point a1, Point a2, Point a3) {
        return a1.x() * a2.y() + a3.x() * a1.y() + a2.x() * a3.y() - a3.x() * a2.y() - a2.x() * a1.y() - a1.x() * a3.y();
    }  

利用turtle设计绘制自己的图案也相当有趣,大家可以拓展思维,往往非常简单的函数配合能画出很好看的图案。
这里抛砖引玉一下,仅供参考——
HIT_SC:实验回顾 - Lab1
代码非常简单:
内层循环用于绘制五角星,并更改颜色同时在每次循环结束后伸长,以造成螺旋效果。外层循环绕中心依次旋转6°。

public static void drawPersonalArt(Turtle turtle) {
    	int length = 30;
        for (int j = 0; j < 120; j++) {
        	for (int i = 0; i < 5; i++) {
        		if(i == 2)     		
        			turtle.color(PenColor.PINK);
        		else if(i == 3)     		
        			turtle.color(PenColor.YELLOW);
        		else 
        			turtle.color(PenColor.ORANGE);
                turtle.turn(144);
                turtle.forward(length+5*j);
            }
        	turtle.turn(6);
		}
    }

关于Junit测试

导入junit库文件是当时困扰我很久的一个问题,总结需要注意按一下步骤进行:
HIT_SC:实验回顾 - Lab1
英文不好的同学,也可以像我一样添加中文补丁
项目上右键,点击最下面的属性。如上图,找到构建路径,单击类路径,选择Add JAR…。然后把单击把lib文件夹下面的库文件一一添加进来即可。
HIT_SC:实验回顾 - Lab1
按照以上步骤操作后,你的项目目录中应出现以上内容。
junit相关的外部库,建议导入上面的1、2、4.

库文件可以在下面的网址进行下载:
https://search.maven.org/