软件构造LAB1

1实验目标概述
本次实验通过求解三个问题，训练基本 Java 编程技能，能够利用 Java OO 开发基本的功能模块，能够阅读理解已有代码框架并根据功能需求补全代码，能够为所开发的代码编写基本的测试程序并完成测试，初步保证所开发代码的正确性。另一方面，利用 Git 作为代码配置管理的工具，学会 Git 的基本使用方法。
 基本的 Java OO 编程
 基于 Eclipse IDE 进行 Java 编程
 基于 JUnit 的测试
 基于 Git 的代码配置管理

2实验环境配置
在qq群下载了Eclipse和JDK并安装， 在GitHub网站下载安装了Gitbush，分为GUI（图形）和CMD（命令行）两种模式，并简单学习了两种模式的使用。
在配置环境变量的过程中，遇到了环境变量JAVA在电脑关机重启后就会失效的问题，在CSDN上找到了解决方案
在这里给出你的GitHub Lab1仓库的URL地址（Lab1-学号）。
https://github.com/ComputerScienceHIT/Lab1-1180300721
3实验过程
请仔细对照实验手册，针对四个问题中的每一项任务，在下面各节中记录你的实验过程、阐述你的设计思路和问题求解思路，可辅之以示意图或关键源代码加以说明（但无需把你的源代码全部粘贴过来！）。
为了条理清晰，可根据需要在各节增加三级标题。
3.1Magic Squares
首先要了解什么是Magic Squares，Magic Squares也就是幻方是一种将数字安排在正方形格子中，使每行、列和对角线上的数字和都相等的方法。
3.1.1isLegalMagicSquare()
该函数要实现判断一个矩阵是否为幻方。

1.读入文件
a) 创建FileReader、BufferReader、StringBuilder对象
b) 初始化line
2.逐行将字符串转换为整型矩阵存储
a) 将非空readline的字符串分割
b) 去除头尾空格后转换为数字存储到二维数组中
c) 存储时判断该数字是否出现过
i. 出现过则报错
ii. 否则用Boolean表标记
d) 判断行列长度是否相等
3.计算两条斜线的和并比较
a) 分别得出主对角线和次对角线的和
b) 比较
i. 若相等则记录，作为基准值
ii. 若不相等则报错
4.计算每条纵线和横线和和并比较
a) 分别计算第i条横线和纵线的和
b) 与基准值比较
i. 不相等则报错
5.确定是否为幻方
public static boolean isLegalMagicSquare(String fileName) throws IOException {
File file = new File(fileName);
FileReader reader = new FileReader(file);
BufferedReader bReader = new BufferedReader(reader);
StringBuilder sb = new StringBuilder();
String line = “”;

	int n = 0, m = 0;
	Arrays.fill(vis, false);
	while ((line = bReader.readLine()) != null) {
		String[] l = line.split("\t");
		m = l.length;
		for (int i = 0; i < m; i++) {
			square[n][i] = Integer.valueOf(l[i].trim());
			if (square[n][i] <= 0 || vis[square[n][i]])
				return false;
			else
				vis[square[n][i]] = true;
		}
		n++;
	}
	bReader.close();
	if (n != m)
		return false;
	int s1 = 0, s2 = 0, s = 0;
	for (int i = 0; i < n; i++) {
		s1 += square[i][i];
		s2 += square[n - i - 1][i];
	}
	if (s1 == s2)
		s = s1;
	else
		return false;
	for (int i = 0; i < n; i++) {
		s1 = s2 = 0;
		for (int j = 0; j < n; j++) {
			s1 += square[i][j];
			s2 += square[j][i];
		}
		if (s1 != s || s2 != s)
			return false;
	}
	return true;
}

3.12generateMagicSquare()
该函数要实现生成一个边长为奇数的幻方。

初始化
i. 生成空矩阵
ii. Row=0，Col=n/2
循环n*n次填充矩阵
i. 将矩阵的[row, col]位置填充为i
ii. 在保证坐标在矩阵范围内的情况下使Row–，Col++
打开文件，打印结果
public static boolean generateMagicSquare(int n) throws IOException {
int magic[][] = new int[n][n];
int row = 0, col = n / 2, i, j, square = n * n;
for (i = 1; i <= square; i++) {
magic[row][col] = i;
if (i % n == 0)
row++;
else {
if (row == 0)
row = n - 1;
else
row–;
if (col == (n - 1))
col = 0;
else
col++;
}
}
File file = new File(“src/P1/txt/6.txt”);
PrintWriter output = new PrintWriter(file);
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++)
output.print(magic[i][j] + “\t”);
output.println();
}
output.close();
return true;
}
3.2Turtle Graphics
该任务需要我们clone已有的程序后，利用turtle按照要求画图，其中需要利用几何知识设计一些函数简化编程，最后可以发挥想象力进行Personal Art。
3.2.1Problem 1: Clone and import
打开目标存储文件夹 右键点击Git Bash
输入git clone
3.2.1Problem 3: Turtle graphics and drawSquare
该函数需要实现：已知边长，画出边长为指定数值的正方形。参数是海龟对象turtle和编程sidelength。
首先将海龟画笔设置为黑色。然后执行4次的前进sidelength长度、转完90度，即可完成一个边长为sidelength的正方形。

3.2.2Problem 5: Drawing polygons
该问题首先希望已知正多边形边数的情况下计算正多边形的内角度。根据几何知识可以推导得公式：
(double)180.0−(double)360.0/sides(double) 180.0 - (double) 360.0 / sides(double)180.0−(double)360.0/sides使用该公式，实现calculateRegularPolygonAngle该问题还希望已知正多变型得边数和边长画出一个正多边形。参照画正方形的方法，可以先前进sidelength，再使海龟旋转一个角度，执行“边数”次。其中，这个角度是正多边形内角的补角，利用calculateRegularPolygonAngle的功能计算出多边形内角，再用180°减去这个值即可

3.2.3Problem 6: Calculating Bearings
该问题首先希望解决，已知起点和当前朝向角度，想知道到终点需要转动的角度。例如，如果海龟在（0，1）朝向 30 度，并且必须到达（0，0）它必须再转动 150 度。

首先使用Math.atan2函数计算两点之间的边在坐标系的角度，减去当前朝向的角度；
然后取相反数（海龟旋转的方向是顺时针，坐标轴角度的旋转角度的逆时针）；
再减去90°（海龟的0°线是向上，坐标轴的0°线是向右，向右到向上要逆时针旋转90°）；
最后调整为0-360°之间（可能大于360°或小于0°）
基于上一个问题，此时有若干个点，想知道从第一个点开始到第二个点，再从第二个点到第三个点……以此类推每次转向的角度。
将“起点”选为第一个点（坐标为(xCoords.get(0),yCoords.get(0))）；
循环n-1次（n为点的个数）
每次将第i+1号点设置为“终点”，通过上一个函数计算旋转角度并存储到List中；
将下一次的“起点”用当前“终点”更新，继续循环；
退出循环后返回List。
3.2.4Problem 7: Convex Hulls
算法描述：我们发现任意凸包上的点，你会发现以该点建立一个极角坐标系，该点连结其它所有点的极角中，该点逆时针方向的第一凸包点到该点极角最小，例如P0，到所有点的极角中P0P1极角最小。
算法中首先找到最左边的点，这个点必然在凸包上，然后计算该点连接点极角最小的，这里计算有技巧，算法中进行toright测试,直到找到到最右端的点，找到P1后，就可以从P1开始，接着顺次找到P2，又以P2为起点……
时间复杂度：因为每次的起点都是上次找到的凸包点，因此外层循环的复杂度为O(H)，H为凸包上的点，内层循环每次都会全部遍历点，因此时间复杂度为 O(n) ,因此总的是间复杂度为 O(nH) ,在一般情况下 凸包上的点的期望为logn ，算法复杂度为 O(nlogn) ,极端情况下，如下所示，所有点都在类似圆弧上的话，外层循环也是n，因此会达到O(n^2)。

3.2.5Problem 8: Personal art
思路：在画正多边形的基础上，步长不是一直相同，而是越来越长，并且角度比画正多边形需要的角度多一些，每次拐弯变换颜色。
3.2.6Submitting
安装git
注册github并新建仓库
初始化git
添加远程仓库URL
添加上传文件
添加修改日志
上传push
查看上传情况
下载/同步
3.3Social Network
该任务要求设计一张社交网络图，基于连接人与人，并且能计算任意两人之间的联系情况。网络图基于两个类，分别是FriendshipGraph类和Person类

3.3.1实现FriendshipGraph类
public class FriendshipGraph {
public Map<Person,ArrayList> map = new HashMap<Person, ArrayList>();

public void addVertex(Person p){
	if (this.map.containsKey(p)) {    
		System.out.println("This name is existed!");
	}
	else {
		ArrayList<Person> friends = new ArrayList<Person>();
		map.put(p, friends);
	}
}

public void addEdge(Person p1, Person p2) {
	int total = map.get(p1).size();
	boolean sign = true;   //设置标志
	for(int i = 0 ; i<total ;i++) {
		if(map.get(p1).get(i) == p2) {  
			sign = false;
			break;
		}
	}
	if(sign) {
		map.get(p1).add(p2);
	}
}

public int getDistance(Person p1, Person p2) {
	Person now = p1 , friend = p1;
	int i = 0 ,distance = 0;   
	Queue<Person> queue = new LinkedList<Person>();
	ArrayList<Person> visited = new ArrayList<Person>();
	if(p1 == p2) {
		return distance;
	}
	queue.add(now);
	visited.add(now);
	while (!queue.isEmpty()) {
		now = queue.poll();
		distance ++;
		while(i < map.get(now).size()) {
			friend = map.get(now).get(i);
			if( friend == p2) {    
				return distance;
			}
			if(!visited.contains(friend)) {
				queue.add(friend);
				visited.add(friend);
			}
			i++;
		}
		i = 0;
	}
	return -1;   
}


public static void main(String[] args) throws Exception {
	FriendshipGraph graph = new FriendshipGraph();
	Person rachel = new Person("Rachel");
	Person ross = new Person("Ross");
	Person ben = new Person("Ben");
	Person kramer = new Person("Kramer");
		
	ArrayList<Person> list = new ArrayList<Person>();
	list.add(rachel);
	list.add(ross);
	list.add(ben);		
	list.add(kramer);
	for(int i=0; i <list.size();i++) {
		for(int j=i+1 ; j < list.size();j++) {
			if(list.get(i).nameSameWith(list.get(j).getName())) {
				System.out.println("Wrong name:"+list.get(i).getName());
				throw new Exception("The name is repeated!");
			}
		}
	}
	
	graph.addVertex(rachel);
	graph.addVertex(ross);
	graph.addVertex(ben);
	graph.addVertex(kramer);
	graph.addEdge(rachel, ross);
	graph.addEdge(ross, rachel);
	graph.addEdge(ross, ben);
	graph.addEdge(ben, ross);
	System.out.println(graph.getDistance(rachel, ross));
	//should print 1
	System.out.println(graph.getDistance(rachel, ben));
	//should print 2
	System.out.println(graph.getDistance(rachel, rachel));
	//should print 0
	System.out.println(graph.getDistance(rachel, kramer));
	//should print -1
}

}

3.3.2设计实现Person类
public class Person {
private String name;
public Person (String name) {
this.name = name;
}
public String getName() {
return this.name;
}
public boolean nameSameWith(String name) {
if(this.name.equals(name)) {
return true;
}
else
return false;
}
}

3.3.3设计/实现客户端代码main()
Main函数只需要在点集、边集里加入人名和他们之间的关系即可。