第三周的作業是将二維平面所有的4個或4個以上的共線的點找出來！讓學生深刻了解排序算法和對比器的使用！
第一次送出95分，等有時間改改吧
1.作業中點代碼和分割代碼大部分已經提供，自己隻需要将其補全即可，隻是在對比斜率的時候，隻需注意處理号Double資料類型。
2.暴力算法也比較容易解決,隻需将所有4的不同點的組合進行一便即可，不過暴力算法的時間複雜太高了是O（N4），是無法接受的。
3.是以有了基于排序的快速算法，排序的算法複雜度 O(N* logN)，尋找多餘或等于4個點在一條線上的時間複雜度是O(N),總共是O(N2logN)這樣的結果是可以接受的。
Fast排序的唯一難點是如何找避免找到重複的組合，即找到P->Q->R->S->T,便不需要Q->P->R->S->T的組合,具體的做法是
I：首先對所有的點進行排序,記作Points[ ]。
II：将所有的點copy一份，記作Aux[ ],計算Points[ ] 中的第一個點與所有點的斜率，然後對所有點進行排序，使用MergeSort,
自己與自己對比是Negetive.Infinity,是最小的一個點，排好序後就去找在在一條線上4個或4個以上點的集合,将所有在一條線上點的最小的點和最大的點加入到LineSegment中。
III：計算第二個點與所有的點的斜率，找到的所有滿足條件點的集合，這個集合中最小的點必須為第二個點，如何最小的不是第二點的組合，說明該組合已經包含在第一個點的組合内了，這樣就避免了找到重複的組合。
IV：依此計算剩下的點，每一個組合組合最小的點必須是目前參與對比的點（對比器中放的點），因為所有的比目前點小的點的組合已經被找到了，到倒數第4個點就完成了所有的查找工作。高效且不會重複。
首先是暴力查找代碼：
//Libraries
//Libraries
//...Standard Libraries
import java.util.ArrayList;
//...Third-party packages
import edu.princeton.cs.algs4.Merge;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
public class BruteCollinearPoints {
private Point[] pts;
private ArrayList<LineSegment> lines;
//find all line segments containing 4 points
public BruteCollinearPoints(Point[] points) {
//check input points that if they contain NUll or Repeated item.
checkNullArgument(points);
checkDuplicatedElemen(points);
lines = new ArrayList<LineSegment>();
//copy the points avoid to change points's order;
this.pts = new Point[points.length];
for (int i = 0; i < points.length; i++) {
pts[i] = points[i];
}
Merge.sort(pts);
int N = points.length;
for (int i = 0; i < N-3; i++)
for (int j = i+1; j < N-2; j++)
for (int k = j+1; k < N-1; k++) {
if(pts[i].slopeTo(pts[j]) != pts[i].slopeTo(pts[k])) continue;
for (int l = k+1; l < N; l++) {
if (pts[i].slopeTo(pts[j]) == pts[i].slopeTo(pts[l]))
lines.add(new LineSegment(pts[i], pts[l]));
}
}
}
//the number of segments
public int numberOfSegments() {
return lines.size();
}
//the line segments
public LineSegment[] segments() {
return lines.toArray(new LineSegment[numberOfSegments()]);
}
//check input array whether contains a null pointer
private void checkNullArgument(Point[] points) {
// null array
if (null == points) {
throw new IllegalArgumentException("Input a null array\n");
}
// null elements
for (int i = 0 ; i < points.length; i++) {
if(null == points[i]) throw new IllegalArgumentException("Input array contains null\n");
}
}
//is two point are same in array
private void checkDuplicatedElemen(Point[] points) {
Merge.sort(points);
for (int i = 1; i < points.length; i++) {
if(points[i].slopeTo(points[i-1]) == Double.NEGATIVE_INFINITY)
throw new IllegalArgumentException("input contains repeated elements\n");
}
}
public static void main(String[] args) {
In in = new In(args[0]);
int n = in.readInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
}
// draw points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
for (Point p : points) {
p.draw();
}
StdDraw.show();
// print and draw the line segments using BruteCollinearPonints
BruteCollinearPoints brc = new BruteCollinearPoints(points);
for (LineSegment segment : brc.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
System.out.println("Done");
}
}
快速查找的代碼
Libraries
//Standard Libraries
import java.util.ArrayList;
import java.util.Arrays;
//Third-party package
import edu.princeton.cs.algs4.Merge;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.In;
public class FastCollinearPoints { private ArrayList<LineSegment> lines;
// find all line segments containing 4 or more points;
public FastCollinearPoints(Point[] points) {
int N = points.length; lines = new ArrayList<LineSegment>();
checkNullArgument(points);
checkDuplicatedElemen(points);
//copying a new array avoid to change origin array;
Point[] clone = new Point[N];
for (int i = 0; i < N; i++) {
clone[i] = points[i];
}
for (int i = 0; i < N-3; i++) {
Arrays.sort(clone, points[i].slopeOrder());
//log sum of slopes that have same tangent line;
//initialize num is 1;
int num = 1;
int min = 0;
double tempSlope = Double.NEGATIVE_INFINITY;
for (int j = 1; j < N; j++) {
if (tempSlope != clone[0].slopeTo(clone[j])) {
if (num >= 3) addPointsToLineSegment(clone, min, j-1);
tempSlope = clone[0].slopeTo(clone[j]);
min = j;
num = 1;
}
else num++;
//up boundary of list;
if (j == N-1 && num >=3) addPointsToLineSegment(clone, min, j);
}
}
}
// number of segments;
public int numberOfSegments() {
return lines.size();
}
//the line segments;
public LineSegment[] segments() {
return lines.toArray(new LineSegment[numberOfSegments()]);
}
//add Segment to Array;
private void addPointsToLineSegment(Point[] clone, int lo, int hi) {
int N = hi - lo + 2;
Point[] auxArray = new Point[N];
auxArray[N-1] = clone[0];
for (int i = 0; i < N-1; i++) {
auxArray[i] = clone[lo++];
}
Merge.sort(auxArray);
if(0 == clone[0].compareTo(auxArray[0]))
lines.add(new LineSegment(auxArray[0], auxArray[N-1]));
}
private void checkNullArgument(Point[] points) {
// null array
if (null == points) {
throw new IllegalArgumentException("Input a null array\n");
}
// null elements
for (int i = 0 ; i < points.length-1; i++) {
if(null == points[i]) throw new IllegalArgumentException("Input array contains null\n");
}
}
//is two point are same in array
private void checkDuplicatedElemen(Point[] points) {
Merge.sort(points);
for (int i = 1; i < points.length; i++) {
if(0 == points[i].compareTo(points[i-1]))
throw new IllegalArgumentException("input contains repeated elements\n");
}
}
//test unit
public static void main(String[] args) {
In in = new In(args[0]);
int n = in.readInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
}
//draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
for (Point p : points) {
p.draw();
}
StdDraw.show();
//print and draw the line segments
FastCollinearPoints collinear = new FastCollinearPoints(points);
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
System.out.println("Done");
}
}
測試結果：
java FastCollinearPoints grid6x6.txt
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)