广工算法实验报告(共10篇).docVIP

广工算法实验报告(共10篇) 广东工业大学算法分析与设计实验 算法设计与分析实验报告 学 院专 业班 级 计算机软件1班 学 号 姓 名 周帅 指导教师 2014年06月03日 计算机 学院软件工程 专业 班 学号： 姓名： 协作者：________教师评定： 实验题目一、 实验目的与要求 ? 理解分治法的效率 ? 用分治法完成快包算法，并给出一个运行实例 二、 算法的运行环境： 在windows7系统中，用eclipse进行编译。 算法实现代码： import java.awt.Point; import java.util.Arrays; import java.util.Iterator; import java.util.LinkedList; public class 实验1 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Point[] Points = new Point[15]; Points[0] = new Point(-5, 7); Points[1] = new Point(3,-6); Points[2] = new Point(5, 4); Points[3] = new Point(-5, -5); Points[4] = new Point(1, 7); Points[5] = new Point(6, 0); Points[6] = new Point(0, 0); Points[7] = new Point(-5, 0); Points[8] = new Point(3, -2); Points[9] = new Point(3, 4); Points[10] = new Point(1, 6); Points[11] = new Point(5, 3); Points[12] = new Point(-4, -5); Points[13] = new Point(-3, 6); Points[14] = new Point(2, 5); Arrays.sort(Points); //预排序处理 LinkedListPoint list = new LinkedListPoint (); for(int i = 0;i Points.length;i++) list.add(Points[i]); //list存放全部的顶点 LinkedListPoint result = getConvexHulls(list); //result用来存放最终的结果顶点 System.out.println(一共有 + result.size() + 个顶点, + 凸包的顶点是： ); IteratorPoint it = result.iterator(); while(it.hasNext()) { Point next = (Point) it.next(); System.out.print(( + next.x + , + next.y + ) + );} } public static LinkedListPoint getConvexHulls(LinkedListPoint list){//将凸包顶点以result链表返回 LinkedListPoint result = new LinkedListPoint(); Point temp1 = list.removeFirst(); Point temp2 = list.removeLast(); result.add(temp1); result.add(temp2); //递归的处理temp1 --- temp2左右两侧的点 dealWithLeft(temp1,temp2,result,list); dealWithLeft(temp2,temp1,result,list);//注意每次要将result带着，存放结果集 return result; } private static void dealWithLeft(Point p1,Point p2,LinkedListPoint result,LinkedListPoint list){ //递归的处理p1，p2构成的射线左边的点 IteratorPoint it = list.iterator(); //找出左边最高的点Pmax P