1.第一部分:准备工作
首先,一定要先阅读,并且理清楚整个实验的大体流程,实验需要做什么,需要什么工具,这些工具怎么下载、安装并且使用,然后把任务过程分析一下,把需要做的事情先后顺序分清楚才不会乱。我一开始因为有规划好,所以实验到后半部分也分不清自己做了什么,没做什么,因此,提前规划很重要。我的实验过程如下:
2. 第二部分:实验环境配置部分
2.1.下载和安装JDK:这次实验应老师要求,需要下载JDK11版本。下载过程中如果不知道怎么安装,就可以去CSDN搜索如何下载安装JDK以及环境变量的配置等,有很多前辈详细的解答和过程。
2.2.下载和安装Eclipse:过程与上一步相同。可以根据自己的需求,也可以去看看相关介绍该软件的教程,会更加清晰。
2.3.注册Github账号,并且根据老师发布的实验要求,把名称以及仓库等信息设置好。同时,需要用老师在实验要求里面发布的班级进入,并且创建自己的仓库,按实验要求设置好相关信息,最后提交到该仓库中。第一个仓库是个人仓库,是开放的,可以在实验完成之后把代码等放入里面,第二个仓库是学校为了查看实验而设置的,是私有的,除了老师和自己是看不到的。
2.4.Git的下载和使用:由于以前没有接触过Git,所以很陌生。我自己去网站上找了一些视频教程,学习了Git的使用方法以及其作用。
3.第三部分:Junit测试
Junit测试过程老师在课堂上也讲解过一些,如果还不知道怎么办,就需要自己去找相关资料了解并且学会使用,因为测试方法贯穿整个课程,非常重要,对于以后的工作以及其他方面都很有帮助。
4.第四部分:实验过程
4.1 由于这些题目来自于MIT的作业,因此,我们需要去阅读英文的题目要求,在这里不得不说,学好英语真的很重要,如果学不好,只靠机器翻译,将会非常的狼狈。
4.2 阅读好题目,了解相关要求之后,需要根据题目要求进行做题。在做题之前,需要从老师给的地址中下载相关代码到自己创建的Git仓库中,并且用该代码框架进行补充,从而完成实验。
4.3第一个实验:Magic Squares
A magic square of order n is an arrangement of n×n numbers, usually distinct integers, in a square, such that the n numbers in all rows, all columns, and both diagonals sum to the same constant .
根据题意,n阶幻方是n×n数在方格中的排列,通常是独立的,使得所有行中的n个数、所有列的n个数以及两者对角线都等于同一个常数。
根据题意,首先输入文件给出的n阶矩阵,判断该矩阵是否合法,若合法,判断是否是幻方。其次,输入一个正整数,如果是奇数,生成一个n阶矩阵,使其满足幻方性质,并保存到输出按文件中;如果是偶数,或者不是正整数,提示输入非法。然后判断生成的矩阵是否是幻方。
4.3.1 isLegalMagicSquare()
该函数要判断一个矩阵是否为幻方。
首先读入文件:创建FileReader、BufferReader、StringBuilder对象,初始化line。然后逐行将字符串转换为整型矩阵存储,将非空readline的字符串分割
并去除头尾空格后转换为数字存储到二维数组中,再存储时判断该数字是否出现过,如果出现过就报错,否则用Boolean表标记。再然后,判断行列长度是否相等,计算两条斜线的和并比较,分别得出主对角线和次对角线的和,比较后若相等则记录,作为基准值;若不相等则报错。再计算每条纵线和横线和和并比较。(分别计算第i条横线和纵线的和,与基准值比较,若不相等则报错)。最后,确定是否为幻方。
4.3.2 generateMagicSquare()
该函数要实现生成一个边长为奇数的幻方。
首先进行初始化,生成空矩阵。然后循环n*n次填充矩阵。最后打开文件,打印结果。
具体过程如下:把1放在第一行正中,按以下规律排列剩下的(n×n-1)个数:每一个数放在前一个数的右上一格,如果这个数所要放的格行数小于1,则放在底行,仍然要放在上一个放置的数的右一列;如果这个数所要放的格列数大于n,则放在第1列,仍然要放在上一个放置的数的上一行;如果这个数所要放的格行数小于1,且列数大于n,那么就把它放在第n行第1列;如果这个数所要放的格已经有数填入,那么就把它放在上一个放置的数的下一行同一列。
4.4第二个实验:Turtle Graphics
该任务需要我们clone已有的程序后,利用turtle按照要求画图,其中需要利用几何知识设计一些函数简化编程,最后可以发挥想象力进行Personal Art。首先分析turtle的package组成,了解类成员。
4.4.1 Problem1:Clone and import
(1)如何从GitHub获取该任务的代码:在进行第一项任务时利用Eclipse的import功能,把老师给的代码从Github中获取成功,在这次任务中继续使用即可。
(2)在本地创建git仓库:通过使用Git Bash命令窗口,根据视频教程在本地创建了git仓库,命名为xxx(自己的学号);
(3)使用git管理本地开发:根据教程,可以通过命令行来管理开发。
4.4.2 Problem 3: Turtle graphics and drawSquare
问题:给定爬行长度sideLength,使little turtle画一个边长为sideLength的正方形。
解决思路:画正方形,相当于先向前平移sideLength个单位,然后转90°,重复四遍即可。
代码如下:
public static void drawSquare(Turtle turtle, int sideLength) {
turtle.color(PenColor.BLACK);
for (int i = 0; i < 4; i++) {
turtle.forward(sideLength);
turtle.turn(90);
4.4.3 Problem 5: Drawing polygons
(1)
public static double calculateRegularPolygonAngle(int sides)
问题:给出正整数sides(>2),返回正sides边形的内角度数。
public static double calculateRegularPolygonAngle(int sides) {
return (double) 180.0 - (double) 360.0 / sides;
解决办法:用公式给出正整数sides(>2),返回正sides边形的内角度数。
(2)public static int calculatePolygonSidesFromAngle(double angle)
问题:给出浮点数angle(0<angel<180),返回以angle为内角度数的正n边形边数。
解决办法:多边形外角和=360°,所以正n边形边数公式为:sides=360/(180-angle)。
(3)public static void drawRegularPolygon(Turtle,int sides,int sideLength)
问题:给出边数、边长,画一个正多边形。
解决办法:调用3.2.3.(2)的函数,求出正多边形的内角度数,然后用画正方形的方法画正多边形,只不过循环的次数改为sides次,turn的角度改为算出的角度。
private JPanel contentPane;
public static void drawRegularPolygon(Turtle turtle, int sides, int sideLength) {
turtle.color(PenColor.BLACK);
for (int i = 0; i < sides; i++) {
turtle.forward(sideLength);
turtle.turn((double) 180.0 - calculateRegularPolygonAngle(sides));}
4.4.4 Problem6:Calculating Bearings
(1)Public static doublecalculateBearingToPoint(double currentBearing,int currentX,int currentY,int targetX,int targetY)
问题:计算当前向量与目标向量的夹角(当前向量转过多少度后达到目标向量)。其中当前向量由当前点、当前方向决定,目标方向由当前点、目标点决定,当前方向由当前方向与竖直向上方向(y轴正方向)的夹角表示,目标向量的方向由当前点与目标点的连线与竖直向上方向(y轴正方向)的夹角表示。
解决办法:目标向量的求法如下:先求当前点与目标点的连线与y轴夹角的正切值,tan=(targetX-currentX)/(targetY-currentY),然后调用Math库中的atan将其转化为弧度,再由公式——角度=弧度*180/PI——求得角度值,即为当前向量与y轴正方向的夹角,与currentBearing(当前方向)作差,得解。
(2)public static List<Double> calculateBearings(List<Integer> xCoords, List<Integer> yCoords)
问题:以列表形式给出一系列点的横纵坐标。假设海龟从给出的第一点开始,面朝上(即0度)。对于其后的每一点,假设海龟在移至前一点时仍朝其所面对的方向前进。
解决办法:对相邻两个点调用函数求夹角,保存在列表中,返回该列表。
4.4.5 Problem 7:Convex Hulls
问题:凸包问题,给出一组点的坐标,求最少的点的集合,使其他所有点都在这些点围成的闭合凸多边形内。
解决办法:使用gift-wrapping算法。
以任意凸包上的点建立一个极角坐标系,该点连结其它所有点的极角中,该点逆时针方向的第一凸包点到该点极角最小。首先找到最左边的点,这个点必然在凸包上,然后计算该点连接点极角最小的,这里计算有技巧,算法中进行toright测试,直到找到到最右端的点,找到P1后,就可以从P1开始,接着顺次找到P2,又以P2为起点一直进行到最后一个点为止。
4.4.6 Problem 8:Personal art
任务:自己画出一种图形。
思路:利用JAV画图turtle彩螺旋线。
4.4.7 :Submitting
在安装好Git,注册好Github账号并且创建仓库的基础上,利用Git bash来初始化Git,再添加远程仓库的URL,(命令行为:git remote add origin https://github.com/.../x...x.git)。然后再用命令行git pull添加上传文件,并且添加修改日志,用命令行:git commit -m "Initial commit"。最后用命令行git push -u origin master进行PUSH操作,然后刷新Github网页便能看见上传文件。其他具体操作可通过视频教程或者CSDN博客等方式进行自学。
4.5 Social Network
设计一张社交网络图,基于连接人与人,并且能计算任意两人之间的联系情况。网络图基于两个类,分别是FriendshipGraph类和Person类。
4.5.1 设计/实现FriendshipGraph类
存储结构:Set<Person> persons = new HashSet<Person>();
用HashSet存放Graph里的节点(人)。
4.5.1.1.public void addVertex(Person person);
作用:将person这个节点添加到HashSet中,相当于在图中插入一个独立的节点。
PS:如果有一个节点的name属性与待插入节点的name属性相同,就抛出重名提示,不插入这个节点。
4.5.1.2.public void addEdge(Person p1,Person p2);
作用:在p1到p2节点之间连一条单向边。用邻接表的方式存储边,
Person类的add_friend方法,在p1的friends集合里加入p2这个节点。
(为了避免重边,插入边之前先扫描p1的friends集合,判断是否有一个集合内的点,其name属性与p2相同,如果有,证明p1与p2之间已经存在这样的单向边,抛出重边提示,不插入这条边。)
4.5.1.3.public int getDistance(Person p1,Person p2);
作用:对给定的两个节点,求两点间的最短路。
实现过程:用BFS实现最短路。
(1)初始化图中的每个点的vis属性为false;
(2)新建一个队列,用来存放已搜索过的节点。
(3)p1作为根节点,p1.vis置为true,p1加入队列;
(4) 搜索p1的friends集合中未访问过的节点(vis属性为false),如果有一个满足要求的子节点等于p2,即找到一条最短路,结束搜索,返回当前路径长度distance;否则,将满足要求的子节点依次加入队列,修改其vis属性值为true;
(5)所有满足条件的子节点扫描完之后,当前路径++;
(6)取出队首节点,重复第3、4、5步操作,直到队列为空,或找到最短路径。
(7)值得注意的一点是存在p1和p2不相连的情况,这时BFS搜索到最后队列为空,扔找不到一条最短路径,因此需要在一开始设置一个标记变量flag,初始化为false,找到子节点为p2时修改flag的值为true,这样搜索结束时,如果flag的值没有发生变化,就说明两个节点不连通,返回值设为-1。
4.5.2 设计/实现Person类
(1)public String Name;存放当前节点的名字;
(2)HashSet<String> NameSet = new HashSet<>();:存放以当前节点为起点的所有边的终点;
(3)private boolean vis;在BFS中标记当前节点是否被访问过;
(4)public void addVertex(Person newPerson)向当前节点的friends集合中添加一个新节点,即在当前节点与目标节点之间添加一条单向边;
4.5.3 设计/实现客户端代码main()
调用FriendshipGraph类的正确方法:FriendshipGraph graph = new FriendshipGraph();
得到的graph相当于一张完整的有向图,可调用内部方法来实现节点的插入、边的插入和两点间最短路径的查询。
4.5.3 设计/实现测试用例
设计思路:
(1)测试新创建的图是否为空,初始化检测;
(2)插入新节点,测试addVertex方法是否能够实现功能;
(3)插入name属性相同的节点,测试addVertex方法是否按约定抛出提示;
(4)插入新的有效边,测试addEdge方法是否能够实现功能
(5)插入重复边,测试addEdge方法是否按约定抛出提示;
(6)选取两个连通点,测试getDistance方法是否返回正确结果;
(7)选取两个非连通点,测试getDistance方法是否返回-1;
总的来说,实验过程差不多就这样,其中有很多细节和问题还有待商榷。