HIT 软件构造Lab1 思考

Lab 1实验报告

3.1 Magic Squares
要求读取一些文件的输入，判断该文件内的数字组合是否为幻方。阶n的幻方是一个正方形中n×n个数字（通常是不同的整数）的排列，以便所有行，所有列和对角线中的n个数字求和为相同的常数。输出的结果是布尔值。注意还要针对一些特殊的不符合要求的输入进行异常处理，不能让他直接跳出错误。数字之间的间隔采用制表符\t。
主要操作就是读取矩阵，求行列对角线的和，比较是否相等进而判断是否为幻方。

3.1.1 isLegalMagicSquare()
定义一个二维数组，使用二维数组读取文本中的矩阵。因为要读取每行的数据，使用line.split()用\t分割，如果报错就是非法输入的格式，程序catch .split的错误信息，如果是非法输入就返回false并提示。

下面进行幻方的判断，判断之前要先把负数，小数的非法输入进行检测，还要判断是否有空缺，这些异常检测如果报错都返回false。
在这些异常检测结束之后，进行幻方的判断。把每行列和对角线加起来，比较是否全部相等，只有全部都相等才返回true，代表判断通过。结果如下：

3.1.2 generateMagicSquare()
赋值的核心思想就是每组的平均值都是中间的那个数字，假设在每组的每一位数字都有编号，我们的目的就是每个行和列和对角线内每个编号的数字各有一个，为了保证这样的规律就使用这种螺旋赋值的方法。

第一个错误原因: 数组下标越界。这样就不能确保对角线分到每组的每个下标编号的值，在(i % n == 0) row++;运行时会产生下标越界的情况，我们需要避免这种情况。
第二个错误是数组长度异常，如果应用程序试图创建大小为负的数组，则抛出该异常。不能赋值在-1的位置。
3.2 Turtle Graphics
获取turtle包，里面有一系列函数，其中我们需要完成TurtleSoup类的一系列方法。drawSquare方法需要我们使用海龟库内的绘图方法forward和turn实现画一个正方形。
calculateRegularPolygonAngle（），calculatePolygonSidesFromAngle（）这两个方法分别是根据边的输入输出对应正多边形的角度，以及反过来，根据正多边形角的输入判断这个多边形是几边形。
calculateBearingToPoint（）是给定一个现在点和现在点朝向的方向，根据给定的目标点判断需要转向的角度大小。因为在海龟绘图体体系中，默认的角都是顺时针方向的，所以角度大小在0到360之间。除此之外还有一些角度的特殊情况，比如二者已经在一个方向等情况，需要分情况讨论。calculateBearing就是对此的一个使用，需要读取输入的x和y的数组，根据对应的点调用上述函数，得到对应的角度值。
Covexhull就是求解点集的最小凸包，这是这个问题最为困难的部分，在下面详细解释。
个人艺术就是调用这些海龟库的函数绘制自己的图像。
3.2.1 Problem 1: Clone and import
从github的老师公布的库里获取代码，在P2中找到海龟库和rules，将其存储到本地的文件夹中。在Eclipse中，转到文件→导入…→常规→现有项目到Workspace。通过单击“浏览…”并导航到它，选择克隆的根目录。确保已选中项目，确保未选中“将项目复制到工作区” ，然后单击“完成”，这样就把实验需要的库导入了。
3.2.2 Problem 3: Turtle graphics and drawSquare
比较简单，只要用forward调整位置和turn调整角度在图中画出一个正方形即可。
3.2.3 Problem 5: Drawing polygons
calculateBearingToPoint和calculateBearing的实现也比较简单，使用正多边形内角和公式 angle=[180（n-2）]/n进行求解即可。当然注意输出的值的类型，我使用Math.rint(sides)进行转换。
在绘制多边形中调用calculateBearingToPoint进行判断输入的边对应的转角，然后调用forward和turn方法边数次绘制海龟库。但是海龟库默认是顺时针方向的，如果直接转会绘制出一个奇怪的图像，我选择把角加180，这样就可以正常的得到结果了。
3.2.4 Problem 6: Calculating Bearings
CalculatingBearingstopoint()：
首先分析这是角度问题而输入的是点，我们可以通过点的坐标求得方向角，求得的方法是math.atan()方法，但是这样是弧度值，使用angle=angle180/Math.PI这样可以方便的求得方向角的角度值大小。
之后就是清晰思路，以current为原点建立坐标系，针对target的相对位置可以分为以下几种情况：为了调整角度在0-360，如果角度小于0需要+360，在以下情况均加入这种判断，这也是后来测试发现的问题。
Ty>cy：
1： tx>cx angle=90-angle-currentBearing;
2： tx<cx angle=270+angle-2currentBearing;
3: tx=cx angle=(360-currentBearing)%360;

Ty=cy：
1： tx>cx angle=(630-currentBearing)%360;
2： tx<cx angle=(450-currentBearing)%360;
3: tx=cx angle=0

Ty<cy：
1： tx>cx angle=90+angle-currentBearing;
2： tx<cx angle=(double)270-angle-currentBearing;
3: tx=cx angle=(540-currentBearing)%360;

以上是数学规律，总结归纳得出。
CalculatingBearings（）使用刚才已经试验完成的方法，先读取其中第一第二对数字，以0为初始角度带入到刚才的方法里，存在数组中，然后再以数组的值为初始角度递归的求解，最后依次输出数组中的值。
3.2.5 Problem 7: Convex Hulls
算法的核心思路就是步进法，即先选定一个点，我寻找的是离原点最远的点，然后从这个点出发，按一定的方向我选取逆时针，寻找一个点，使得被选取点的和出发点以及出发点和出发点前一个点构成的边的夹角最小。
这个角度的求解方法就是使用刚才上一步的topoint方法。初始点的夹角是x轴正向和新点的夹角，然后对每个新选取点的进行这个过程，把所有选取的点加入我构建的用来存储凸包上面点的arraylist里面。跳出条件是在找到初始点时，即形成了一个闭环。这时就是跳出的好时机。

凸包算法

其实很简单，就是用一个的凸多边形围住所有的点。就好像桌面上有许多图钉，用一根紧绷的橡皮筋将它们全部围起来一样。算法详细步骤：

1. 找到所有点中纵坐标y最小的点，也就是这些点中最下面的点，记为p0。

2. 然后计算其余点与该点的连线与x轴之间夹角的余弦值，将这些点按其对于最低点的正弦值从大到小排序，排序好的点记为p1, p2, p3, …

3. 将最低点p0和排序好的点中的第一个点p1压入栈中，然后从p2开始计算，计算栈顶两个点与该点三点向量是否是逆时针转动，若是，则将该点压入栈中，否则将栈顶元素推出。（此处对栈的概念不清楚可自行搜索）

4. 最后栈里面元素就是所有的凸包外围的点
   Jarvis步进法

时间复杂度：O(nH)。（其中 n 是点的总个数，H 是凸包上的点的个数）
思路：

纵坐标最小的那个点一定是凸包上的点，例如图上的 P0。
从 P0 开始，按逆时针的方向，逐个找凸包上的点，每前进一步找到一个点，所以叫作步进法。
怎么找下一个点呢？利用夹角。假设现在已经找到 {P0，P1，P2} 了，要找下一个点：剩下的点分别和 P2 组成向量，设这个向量与向量P1P2的夹角为 β 。当 β 最小时就是所要求的下一个点了，此处为 P3 。

注意：

找第二个点 P1 时，因为已经找到的只有 P0 一个点，所以向量只能和水平线作夹角 α，当 α 最小时求得第二个点。
共线情况：如果直线 P2P3 上还有一个点 P4，即三个点共线，此时由向量P2P3 和向量P2P4 产生的两个 β 是相同的。我们应该把 P3、P4 都当做凸包上的点，并且把距离 P2 最远的那个点（即图中的P4）作为最后搜索到的点，继续找它的下一个连接点。

当然这里面有一个特殊的情况，即三点共线的情况，因为我们要求的是最小点集，所以我们并不需要把所有点加入，删除list顶部的点即上一个共线点，把下一个点加入其中。

3.3 Social Network
实现并测试一个FriendshipGraph类，该类表示社交网络中的友谊，并可以计算图中两个人之间的距离。还需要实现辅助类人员。您应该将社交网络建模为一个无向图，其中每个人都连接到零个或多个人，但是数据结构是有向图。
然后题目中给出了一个测试用例，应该构造运行这个测试，让程序可以跑起来。
3.3.1 设计/实现FriendshipGraph类
分析这个问题显然是图的问题，所以考虑使用图的数据结构存储，选择邻接矩阵代表图，可以清晰的表现出各个人即各个点之间的关系。
创建一个人就是在邻接矩阵中创建一个点，addvertex方法实现之，接受读入的人名，在矩阵中为他分配一个位置并且给他对应的num值，在存在异常输入时即重复人名时进行检测，我们是不允许这种输入的。

Addedge方法就是创建两个人之间的联系，每次调用都在邻接矩阵对应位置写上1。需要强调的是在我的定义中不允许自己存在边，所以自我重复仅仅会报错而不会产生效果。

之后就是求距离的getDistance方法，我的思想就是采取图的广度优先遍历的方法，定义一个队列，队列的定义和在数据结构课上的方法类似。求与开始的点相邻的点记为一层，由getvertex方法获取点，每一层中搜索，每层的点入队，同时标记位记为true，这一层找不到就到下一层，记录层数，直到找到跟目标的lab位相等的人，返回层数值。如果最终没有找到对应的人就返回-1。特殊情况是自身的距离，设定值为0.

核心内容：
3.3.2 设计/实现Person类
Num是这个人在邻接矩阵的编号，label储存这个人的名字，访问标志visited记录是否被访问过。Person是构造方法。

3.3.3 设计/实现客户端代码main()
Main里面实现的是实验报告内容的基本要求，创建了4个人，4个person，其中Rachel连rose连ben，kramer是一个孤立的点。要求输出Rachel和rose以及ben的距离。Rachel自身的特殊情况以及Rachel和孤立点的特殊情况。分别打印出来，期待的值是1,2,0,-1。结果符合预期。

3.3.4 设计/实现测试用例
测试用例加入几个新的点，
针对getdistance方法测试的内容包括，针对更大的数据量进行处理，正常的返回距离，返回自己到自己的距离，二者不可达的情况，单向图的情况。
针对addvertex的测试是正常的输入和重复输入。
针对addedge的测试是正常的输入和重复输入。